Consider `ed25519-zebra` crate?

[tarcieri]

Presently the tendermint crate uses the ed25519-dalek vicariously through the signatory-dalek crate.

There's an alternative I think that's worth considering: ed25519-zebra. Both ed25519-dalek and ed25519-zebra are based on the underlying curve25519-dalek library. However, ed25519-zebra focuses on Ed25519 usage in consensus-critical (i.e. blockchain) contexts, where discrepancies in Ed25519 validation have been problematic in the past. Also, ed25519-zebra is written by curve25519-dalek author @hdevalence.

There are a few issues at play here: existing Ed25519 libraries don't properly implement RFC 8032, and RFC 8032 doesn't go far enough to remove edge cases in verification. Per @hdevalence, he aims for ed25519-zebra to be the first Ed25519 library to actually implement RFC 8032 verification logic correctly.

If you do decide to adopt ed25519-zebra it seems like you'd want to ensure the Go side has a matching solution, either by implementing the same verification checks that ed25519-zebra uses, or by using ed25519-zebra directly. I'm guessing the latter might be problematic as it seems unlikely Tendermint would adopt a Rust-based dependency.

More generally, even if you don't wind up adopting ed25519-zebra, I think it would make sense to more precisely specify the Ed25519 verification logic Tendermint uses as part of an overall Tendermint specification, as I assume it's presently "whatever Go does".

This seems like the sort of change it might be good to introduce in a chain upgrade (e.g. Stargate). Namely Tendermint only uses Ed25519 signatures for consensus, so previous chains' Ed25519 signatures are irrelevant (only the ECDSA/secp256k1 signed transactions are persisted across chain upgrades). This means introducing stricter Ed25519 verification logic during a chain upgrade carries no risk (to my knowledge) of existing signatures which previously verified but wouldn't verify under the stricter logic, since it's a brand new chain and therefore has no existing Ed25519 signatures to worry about.

/cc @zmanian

[hdevalence]

Just to update/clarify this: ed25519-zebra is aiming to implement ZIP 215 in its 2.x series and legacy Zcash-flavored validation in its 1.x series.

ZIP 215 defines precise validation criteria for Ed25519 signatures and verification keys to ensure that there are no edge cases in verification and that individual and batch verification produce identical results. However, while these criteria are internally consistent (and thus suitable for consensus-critical applications), they aren't exactly the same as RFC8032 (which doesn't require conformant implementations to agree on whether signatures are valid) or the Go standard library (which does not conform to RFC8032 because it allows non-canonical point encodings).

However, it would not be difficult to implement ZIP 215 rules in Go and use that instead of the standard library implementation, and it might be preferable for a consensus-critical system like Tendermint to do so. I'm not sure it's safe for tendermint-rs to use any Ed25519 implementation other than the existing Go one without carefully replicating its exact behavior (i.e., creating an ed25519-tendermint for the same reason that ed25519-zebra exists). I am also not sure what the policy of the Go standard library is around changes to Ed25519 validation criteria. I assume that Go has a strong focus on maintaining compatibility, but if consensus-critical applications are not be top-of-mind, it's possible for breaking changes to be introduced under the guise of "stronger validation" as happened in libsodium.

The tracking issue for ZIP 215 support in ed25519-zebra is here: https://github.com/ZcashFoundation/ed25519-zebra/issues/16

[ebuchman]

Wow thanks for raising this and working on it.

Is it correct that neither ed25519-dalek nor ed25519-zebra are expected to be compatible with Go's x/crypto/ed25519 ?

And does the ambiguity in RFC 8032 apply even if not doing batch verification?

And what does ed25519-zebra 1.X target? Is it compatibility with some C++ implementation?

Presumably this is something other blockchain systems are going to be grappling with as well as ed25519 adoption picks up and we'd presumably want to see something like ZIP 215 established as a common standard for libraries to target.

We should probably open a corresponding issue in the Tendermint Go repo and target the next block protocol breaking release which will also include other changes to prepare Tendermint to support signature aggregation (eg. https://github.com/tendermint/tendermint/issues/2840)

[hdevalence]

Wow thanks for raising this and working on it.

Thanks, I'm glad it's useful work! I've been working on a cross-ecosystem survey of how different implementations behave on these edge cases using a list of test vectors I created for ZIP 215 and a blog post writeup explaining more of the context and motivation, but I haven't finished it yet. I'd be happy to share a draft with you if you'd like.

Is it correct that neither ed25519-dalek nor ed25519-zebra are expected to be compatible with Go's x/crypto/ed25519 ?

And what does ed25519-zebra 1.X target? Is it compatibility with some C++ implementation?

Yes, ed25519-zebra 1.x is expected to be compatible with the specific point release of libsodium originally used in Zcash, and ed25519-zebra 2.x targets the ZIP 215 rules. In general I think it's not safe to assume that any Ed25519 implementations are compatible unless they specifically advertise compatibility with each other. Even if they are coincidentally compatible at one point, if that compatibility isn't an explicit goal, a future release might be incompatible. (This is what happened with libsodium, which changed validation criteria in point releases).

And does the ambiguity in RFC 8032 apply even if not doing batch verification?

Presumably this is something other blockchain systems are going to be grappling with as well as ed25519 adoption picks up and we'd presumably want to see something like ZIP 215 established as a common standard for libraries to target.

The ambiguity is in the spec, in the sense that conformant implementations are not required to agree on which signatures are valid. It's possible to select a precise set of rules, but then it's not that an implementation is conformant with RFC 8032 or not, but with some specific choices.

Basically there are two choices to make:

• Compatibility with batch verification -- do the validation rules allow implementations to perform batch verification, or not? In order to allow this, batch and individual verification must always agree, which means that individual verification MUST use the "cofactored" verification equation rather than the cofactorless one.

• Compatibility with existing signatures accepted by other implementations (like Go's crypto/ed25519) that don't require canonically encoded points. This is asking whether every signature that was considered valid by an existing implementation is considered valid under the new rules. This allows using a new implementation in place of an existing one and "retconning" the new validation criteria onto the old signatures. On the other hand, if the new rules are more strict than the previous ones, it might be possible for someone to insert a signature valid under the old rules and not the new ones, which could cause unexpected breakage. Note that there's no security impact to choosing the less strict validation criteria here, because they only affect signatures created with specially crafted low-order public keys -- the goal is just to have consistent criteria to prevent someone from injecting a signature into the chain that could later cause consensus divergence.

Each pair of choices on these decision points gives a different set of validation criteria. The ZIP 215 rules are obtained by choosing yes to both, in order to allow batch verification and to ease the upgrade process.

Presumably this is something other blockchain systems are going to be grappling with as well as ed25519 adoption picks up and we'd presumably want to see something like ZIP 215 established as a common standard for libraries to target.

We should probably open a corresponding issue in the Tendermint Go repo and target the next block protocol breaking release which will also include other changes to prepare Tendermint to support signature aggregation (eg. tendermint/tendermint#2840)

Yes, I'd like it if other projects adopted these rules. To this end I've started work on a Go implementation of these rules here: https://github.com/hdevalence/ed25519consensus

So far this just has vendored crypto/ed25519 source, but I should have the ZIP 215 rules (& tests) done soon. I'm less familiar with the practical mechanics of "doing Go" (from the software engineering point of view, releases, publishing, modules, api design, etc), so if you know anyone who'd like to help I'd appreciate a second set of eyes on it.

[hdevalence]

Update: I've added a VerifyConsensus function to that repo with an implementation of the ZIP215 rules.

[hdevalence]

cf https://github.com/golang/go/issues/40478#issuecomment-666043072 with description of the current consensus rules inherited by tendermint from crypto/ed25519

[hdevalence]

Update to this -- since this issue was filed, Tendermint now uses the ZIP215 rules. I've created https://github.com/penumbra-zone/ed25519-consensus for use in Penumbra.

[thanethomson]

Closed by #1046 / #1067