Replace ed25519-dalek with ed25519-zebra or ed25519-compact

[koushiro]

Description

Replace the ed25519-dalek with ed25519-zebra or ed25519-compact.

Motivation

I noticed that substrate has replaced the ed25519 implementation with ed25519-zebra, and I'm not sure if libp2p needs to be replaced as well.

Current Implementation

Are you planning to do it yourself in a pull request?

Yes

[mxinden]

Substrate changing its ed25519 implementation does not require libp2p to change its implementation as well. The two projects can still be compatible.

Do you know why they changed? Can you expand on why libp2p should change?

[thomaseizinger]

If anything, I'd be in favor of changing it to https://crates.io/crates/ed25519-compact.

• No dependencies
• More actively maintained

The downside is that ed25519-dalek is - to my knowledge - the only ed25519 implementation that has been officially audited. Plus, we recently introduced a cross-crate testing approach where we use ed25519_compact for the tests so that would need to be addressed as well.
Perhaps we can flip that though and only depend on ed25519_dalek in the tests and use ed25519-compact for our production code?

[umgefahren]

There are other reasons to change to ed25519-compact too. I.e. most of our duplicate dependencies originate in ed25519-dalek. So changing to ed25519-compact might have a measurable impact on our compile times.

[thomaseizinger]

There are other reasons to change to ed25519-compact too. I.e. most of our duplicate dependencies originate in ed25519-dalek. So changing to ed25519-compact might have a measurable impact on our compile times.

The only downside is that it is not audited. How much do we care about that @mxinden? Could PL perhaps sponsor an audit?

Getting rid of the duplicate dependencies would be fantastic.

[dignifiedquire]

Unclear how important an audit is, given the field arithmetic is generated code: jedisct1/rust-ed25519-compact#13 (comment)

[dignifiedquire]

Though it is a little unfortunate that it brings its own sha512 implementation, and not reuse the audited existing one.

[umgefahren]

But that is something that could be changed. I.e. one could develop a PR that adds the ability to use sha512 from a crate instead of the internal implementation.

[thomaseizinger]

But that is something that could be changed. I.e. one could develop a PR that adds the ability to use sha512 from a crate instead of the internal implementation.

I doubt that will be accepted given that "no dependencies" is an advertised feature.

[mxinden]

How much do we care about that @mxinden?

I don't have enough experience here. I would trust on your and @dignifiedquire expertise.

Could PL perhaps sponsor an audit?

Yes, I think that is an option. That said I can not drive this right now, though I could connect someone with the right folks.

[umgefahren]

I doubt that will be accepted given that "no dependencies" is an advertised feature.

Just to clarify here: I would suggest keeping the zero dependency policy, however it would be possible to introduce some sort of ext-sha which would outsource sha to a dependency. But it could be disabled by default and it wouldn't increase our compile time, since we already have sha somewhere in our dependency tree. On the other hand it would increase performance, since sha2 uses hardware extension, ed25519-compact uses only software to perform the hashing which is significantly slower.

[thomaseizinger]

I doubt that will be accepted given that "no dependencies" is an advertised feature.

Just to clarify here: I would suggest keeping the zero dependency policy, however it would be possible to introduce some sort of ext-sha which would outsource sha to a dependency. But it could be disabled by default and it wouldn't increase our compile time, since we already have sha somewhere in our dependency tree. On the other hand it would increase performance, since sha2 uses hardware extension, ed25519-compact uses only software to perform the hashing which is significantly slower.

That is still difficult to design because features should be additive and not change functionality. If one of our users depends on the crate too and would like to use it without an external hash impl, then they can't do that if we activate the ext-sha feature.

The crate would have to expose an entirely different interface or some kind of plugging mechanism which I am unsure will be accepted.

[thomaseizinger]

That is already happening though: jedisct1/rust-ed25519-compact#9

[thomaseizinger]

Another data point, compiling libsodium is a PITA. For some reason, the build cache for that one constantly gets invalidated and I routinely find myself waiting for that build-script to finish when I test changes locally.

[umgefahren]

Another data point, compiling libsodium is a PITA. For some reason, the build cache for that one constantly gets invalidated and I routinely find myself waiting for that build-script to finish when I test changes locally.

You are so right. We should tackle this, please. Especially because it's no longer maintained.

[dignifiedquire]

I have been talking with folks from the rustcrypto land and it looks like the dalek crates are being worked on again and updated (by new folks). So my recommendation would be to stick with them for now.

[umgefahren]

I see, actually, I just wanted to advocate for getting rid of libsodium. It increases build time on dev builds by a lot.

[thomaseizinger]

I see, actually, I just wanted to advocate for getting rid of libsodium. It increases build time on dev builds by a lot.

On that matter, see #3212 (comment).

[thomaseizinger]

I think we can close this. The dalek crates are now maintained again and not far off a release.

[pinkforest]

I'll send a PR that ref's the current release branches that then gets replaced with release-crates - I could use your CI :)

There crates pre-release is imminent as well - want to see how it works from CI here.

Also re: libsodium - I'm rustifying a minified crate for those fn's that can be used for testing that avoids pulling it externally

[kayabaNerve]

Necrobump, yet Ed25519 Zebra has a standardized set of consensus rules whereas most Ed25519 libraries don't, enabling netsplits by publishing signatures some clients reject and others don't.

Nobody should be using Ed25519 in a P2P environment, especially a multi-impl environment, without said rules as if so, they're implementing different protocols.

Worth a new issue, @thomaseizinger?

And cc @pinkforest for discussing adding a version of ZIP-215 to ed25519-dalek. verify_strict claims to be the same in practice (ban non-reduced scalars, ignore torsion) yet adds its own additional rules (undocumented) banning small order keys making it non-compliant.

Also, can I take a moment to ask what paperwork I have to fill out to request Ristretto be added to rust-libp2p? I assume some libp2p RFC would need to occur?

[thomaseizinger]

Worth a new issue, @thomaseizinger?

Yeah I'd say so. Might be worth discussing over at https://github.com/libp2p/specs.

Also, can I take a moment to ask what paperwork I have to fill out to request Ristretto be added to rust-libp2p? I assume some libp2p RFC would need to occur?

If you want it to be interoperable with other implementations, it should be discussed at https://github.com/libp2p/specs. I am not sure if I want to support a keypair in here that is not part of the spec.

[kayabaNerve]

Completely agreed on the latter point, even if I'd wish I could make a PR to rust-libp2p and have it merged in just a month or two...

[thomaseizinger]

Happy to first have a discussion in this repo and exchange some ideas. Posting in specs often has quite the blast radius so it might be better to hash out a few details within a smaller group first.

[kayabaNerve]

I opened the issue on where the spec is incomplete, yet then commented on the sr25519 issue my thoughts on why Ristretto should be added. I'm happy to sketch things out there until I actually have a spec to propose. The discussion around custom peer IDs may be enough for my use case... Unsure how that left off though.