[Cryptography] Proof-of-Satoshi fails Proof-of-Proof.

[Ron Garret]

On May 7, 2016, at 4:06 AM, Allen <allenpmd at gmail.com> wrote:

> > Interesting sidebar: ECDSA nonces were one of the sources of Bitcoin's transaction malleability.
> > The (massive pile of hacks that is) segregated witness feature being added to Bitcoin has an added
> > side effect of removing signatures from the hash of a transaction, and with it the associated malleability.
> > All that said, if you're designing a new system today, pick Ed25519.
> 
> FYI, while Ed25519 specifies that the nonce should be set deterministically, a signer can set it randomly and the signature will still verify.  In fact, I don't see any way for a verifier to know if a signature was generated with a deterministic or a random nonce, so using Ed25519 might not solve malleability.

No, that’s not true either.  Ed25519 is not merely ECDSA with a specified nonce, it has structural changes from ECDSA specifically to prevent the kind of attack you are suggesting.  The message content is hashed twice, once to produce the nonce, and again with the secret key as a prefix to produce the signature.  Not only does this prevent malleability attacks, but it also protects against collisions in the underlying hash.  Two different messages can actually have hash collisions and still produce different signatures.  (The converse is also possible: two messages which do not collide in the underlying hash can collide in the signatures, but this is extremely unlikely because Ed25519 is, essentially, a keyed hash construction.)

(I hereby coin Ron's first law of cryptography: if you think you’ve found a flaw in a DJB design, you are almost certainly wrong.)

rg