Decide what to do with ed25519 in SDK

[robert-zaremba]

Context

SDK has it's own implementation of ed25519 which is compatible with Tendermint one and extends it for proto.Message. We need it to serialize keys (mainly the public keys) in many SDK structures.

ed25519 however is not supported in SDK user land - antehandlers don't validate ed25519 keys. One of the reason is the security concern discussed in ADR-28.

In ADR-28 we designed an address scheme for all addressable accounts. In #8415 we wanted to update the SDK's ed25519.PubKey.Address method according to ADR-28. However this causes problems:

• in SDK we convert all tendermint ed25519 keys to SDK ed25519
• Tendermint is using the legacy address, which is different thant ADR-28 address.
• so the DB has a broken state.

Current state (0.42)

We decided to not support ed25519 in the app user land and updated the package docs.

Followups

Inspect Tendermint ed25519 updates

• check if breaking ed25519.PubKey.Address is an option (probably not)
• export tendermint keys to a separate package and make them proto.Message compatible - with this we won't need to keep the ed25519 wrapper in SDK. Also other applications, which will need to import crypto/keys packages will have a better choice - they will not need to import whole Tendermint or SDK if they just need to do signatures.

Future of ed25519 without updating Tendermint

If we want to have ed25519 in SDK user land without modifying Tendermint, then we have to provide it with a new type, not via ed25519.PubKey / ed25519.PrivKey (unless we decide to update Tendermint). So one would need to create a new type (or a new package) implementing ed25519 and proto.Message and make the Address method compatible with ADR-28.

Other idea is to discourage ed25519 in SDK user land and use something else.

ed25519 Private Keys

Today, the ed25519 private keys are not used at all: keyring doesn't support them, and they have no use in SDK. However they are defined, and, based on the above description, can only be used for tendermint ed25519. Hence, the current ed25519 private key is totally deprecated and shouldn't be used. However there is a problem with removing it - because it would break proto 1.0 versioning promise.

[robert-zaremba]

For the record: I already expressed in other places.
My personal preference is to not allow ed25519 in SDK because it's malleable and could lead to problems if an app developer is assuming uniqueness of (message, signature).

Instead it's more interesting to use sr25519 which is already in the Tendermint codebase. Not sure if it's use in Tendermint though. We could extract it to a separate package and make it proto.Message and ADR-28 compatible (for the reasons discussed in OP).

[robert-zaremba]

The main problem here with ed25519 is that curve25519 field is not of a prime order, so even with the same random parameter there are multiple (max 8) valid signature for the same message.

[webmaster128]

I see, thank you. What consequences does this have? Can someone else that is not having the private key change the signature to a different valid one?

[robert-zaremba]

yes, https://www.getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html

[webmaster128]

Thank you for the pointer.

The potential signature maleability is described in more detail on https://slowli.github.io/ed25519-quirks/malleability/ and in https://datatracker.ietf.org/doc/html/rfc8032#section-8.4, which also says that

Ed25519 and Ed448 signatures are not malleable due to the verification check that decoded S is smaller than l. Without this check, one can add a multiple of l into a scalar part and still pass signature verification, resulting in malleable signatures.

This is also explicitly enforced when using ZIP-215 validation rules for Ed25519.

[webmaster128]

I did not read the full paper, but this seems to cover the concerns raised here: https://eprint.iacr.org/2020/823.pdf

[robert-zaremba]

cc: @marbar3778 , @aaronc , @ethanfrey ,

[tac0turtle]

How hard is it to add both ed and sr? It doesn't seem like a heavy lift. Ideally it should be a minor change.

[robert-zaremba]

We can add both. By adding any key scheme, we are signalling some preference. So the question here is:

• do we want to signal preference for both?

[ethanfrey]

I would signal preference for both, as they have different use cases (ed25519 for best ecosystem compatibility, sr25519 for polkadot-style forward looking crypto). You also support both secp256k1 and secp256r1 for different use cases (not because you were unsure which curve you preferred)

[ethanfrey]

And while you're at it, how about BIP-340 compatible Schnorr sigs for the secp256k1 curve? 😉

I don't actually propose you add this now, but this would be a good thing for a mid-term roadmap and at least take into account with the proto naming

[robert-zaremba]

This is on my list! -> #7315
PS: We can do it with ed25519 and sr25519, but I don't think we can do it with secp256k1.

[aaronc]

I had proposed what I thought was a simple solution which is basically:

1. if nobody wants to use ed25519 we do nothing, or
2. if people want ed25519 we create another ed25519 proto type definition different from the tendermint one with 32-byte addresses to use for signatures

Is that not acceptable?

[robert-zaremba]

The discussion is to check on what SDK will promote. For the moment we made ed25519 deprecated and guided app developers for 2. (but in custom chain). Alternative is to create something useful for them in SDK (so 2. or sr25519 for example).

[robert-zaremba]

People here, what do you think - how important it is to adding ed25519 in next release? It's rather an easy task.

[ethanfrey]

If you mean 0.43, I would add secp256k1 (ecdsa and schnorr) and ed25519 (ecdsa and schnorr).

I have a feeling 0.43 will be a baseline many chains will stabilize on post-stargate (if out soon enough and they don't stabilize on 0.42) and it is good to get basic infrastructure in there to see how chains experiment with crypto and especially off-chain multi-sig (this will take several months of client side tooling to make it easy to use)

If schnorr is a lot more work, at least adding the basic algorithms would be a nice start

[robert-zaremba]

I guess you mean secp256r1? We merged it :)

[zmanian]

I also think ed25519 is a bad choice for user signatures.

[zmanian]

Basically in the cryptocurrency user context, more cofactor fun seems to arise than in the Tendermint consensus use case.

[aaronc]

Cofactor fun? Sorry you lost me there...

[ebuchman]

The ed25519 curve has a "co-factor", meaning the group is not prime order (unlike secp256k1). This can make it dangerous to compose the signature scheme into larger protocols - even HD key derivation protocols have serious issues. The Why Ristretto doc gives a good short overview.

[robert-zaremba]

Well, there is no standard HD key derivation for ed25519. W3F developed one and it seams to be OK.

ed25519 signatures are secured with a proof and they are widely used. The problem is only if one expects not malleable signatures. More specifically, if one we see a signature S for message M verifiable by key P, we can construct another signature S' for same message and same key (without knowing the private key). This was a big issue in zk protocols, which constructed a nullifiers from a signature. So, they are OK with "normal" operations.

Also, see my comment above.

[robert-zaremba]

Here is one of the most recent analysis proving security of ed25519 signatures.

Remarkably, no detailed proofs have ever been given for these security properties for EdDSA,and in particular its Ed25519 instantiations. Ed25519 is one of the most efficient and widely used signature schemes, and different instantiations of Ed25519 are used in protocols such as TLS 1.3, SSH,Tor, ZCash, and WhatsApp/Signal. The differences between these instantiations are subtle, and only supported by informal arguments, with many works assuming results can be directly transferred from Schnorr signatures. Similarly, several proofs of protocol security simply assume that Ed25519 satisfies properties such as EUF-CMA or SUF-CMA.In this work we provide the first detailed analysis and security proofs of Ed25519 signature schemes.

[robert-zaremba]

To resolve this discussion, I propose:

Let's implement an ed25519 version which is compatible with ADR-28. This will make it easier for users willing to use that keys and won't conflict with the rest of the SDK. It's an easy task - we have almost everything already.

[robert-zaremba]

@aaronc , @alexanderbez , @zmanian - does anyone have objections?

[zmanian]

I don't object to ed25519 as an option for signatures. I don't recommend it but zones can pick their poison.

[aaronc]

@robert-zaremba have we identified which users want this and how important this is to them? I'm not seeing anything in this thread that indicates this is something we need to prioritize.

[alessio]

I agre with Aaron. I would not oppose introducing ed25519. I just think that if there is no demand, there might be no point in doing the work (however little it might be). Every single line unused adds up to maintenance cost IMHO.

(Just my 2c)

[robert-zaremba]

@aaronc , IXO is using it. The task is simple - it's just copy-pasting the existing package + proto, and changing the Address function.

See more comments #8543 (comment):

[webmaster128]

I think before promoting Ed25519, there needs to be an officially supported HD derivation strategy. There are multiple options out there but none seems to be fully convincing. SLIP-0010 seems to be a safe bet, but only supports hardened derivation. Cardano developed their own algorithm, a few other have been proven to be insecure. But I think a user should know that when exporting their secret recovery phrase from one client and importing it to another one, funds are accessible.

[kayabaNerve]

This seems to be a dead topic, yet I wanted to ask what'd it take to revive it/get it eligible for review.

The benefit of Ed25519, beyond the raw performance, is sane multisig. This enables everything from custody solutions to atomic swaps with no additional code or trust assumptions (assuming the chain being swapped with has the necessary primitives, as Bitcoin/Ethereum do).

It seems the discussion may have stalled on HDKD discussions? I'm not entirely sure why that's needed. Personally, I see the benefit of EdDSA, beyond the raw performance, being in higher level protocols, not user-land (though sure, performance is always nice).

It also sounds like there's legacy code which is annoying. I ask the fault of legacy not prevent the progress here.

The other possible discussion would be to skip Ed25519 for Ristretto via schnorrkel (which has an audited Go implementation).

[robert-zaremba]

I think the main reason was that nobody really needed it, so priority is low. But feel free to contribute.

[tac0turtle]

Sorry for the delay in responding. It is a low priority like robert mentioned. But there has been thought around different curves for accounts. We are starting a auth working group to surface a new account model in the sdk in order to both allow the current and other schemes to be used freely by application developers or users. This would be a good place to discuss different curves as a use case.

[kopeboy]

User pespective after reading the whole discussion: I didn't get if I could/should use ed25519 keys, given that they are supported by the latest gaia CLI (and also used on Solana?) and even provide lower gas consumption. Also, do they work with Ledger devices (HD derivation?)

[danwt]

To date, I guess there is no support of signing and verifying TX using ed25519? Thanks

[tac0turtle]

adding ed25519 to a chain is quite simple, you only need to add the key type and it will be handled

[Alperen-Dere]

Can you elaborate more, can we use Ed25519 keys for signing without extensive custom development?

[kayabaNerve]

I'd point out how even if it's simple to add, it's clear most people don't bother despite the clear cryptographic benefits. Default support for Ed25519 would be a major QoL improvement.

(I also understand this hasn't had a champion, and I'm not asking one be assigned. I just want to say the fact chains can add it themselves don't mean the topic of including it out the gate should be dropped)

[raynaudoe]

Hey, we're working on a library that will allow to add new curves without much overhead in the sdk, still in POC phase though. Just created an issue to track support for ed25519 cosmos/crypto#8