search

tradecraftio / tradecraft

Tradecraft integration/staging tree https://tradecraft.io/download
Other
13 stars 9 forks source link

Change deterministic nonces to a simpler hash for smaller zk-proofs #13

Open maaku opened 5 years ago

maaku commented 5 years ago

The deterministic signing code for Bitcoin Core uses RFC 6979, which is an internet standard for deterministic nonce selection. It is however an excessively conservative algorithm with an unnecessary number of hashing steps, due to the author's decision to rely on existing approved primitives rather than optimize for speed:

Deterministic signatures are safe in the random oracle model. Using HMAC_DRBG allowed me to rely on existing research on the safety of that construction and how close it comes to a "true" random oracle. If I had used any other "handmade" construction, then I would have had to provide extensive analysis on why it is secure. Being naturally lazy, I chose HMAC_DRBG.

Moreover, this use of HMAC_DRBG makes the end result more "convincing" -- and a large part of specifying a cryptographic algorithm as a RFC is to get other people to use it. (https://crypto.stackexchange.com/a/24326)

However in our use case where it would be useful to report a zero-knowledge proof that the algorithm was followed in the construction of a signature, e.g. to prove a hardware signer is not compromised, we want this algorithm to be as simple as possible to express in an arithmetic circuit. A straight hash should work, as is done by Ed25519.

maaku commented 5 years ago

Renamed issue as it has become apparent this is something we should do.

maaku commented 5 years ago

The Ed25519 scheme is described on page 8 of this document:

https://ed25519.cr.yp.to/ed25519-20110926.pdf

maaku commented 5 years ago

Upon reflection, this really shouldn’t be a release blocker for 0.10. It doesn’t matter too much if older clients use the inefficient scheme. It is rather unlikely that anyone would need to go back and make proofs for signatures produced by older clients. We should put a note in the code that the scheme deployed now is depreciated, however, then we can remove the project tag for rebasing to 0.10. (While we’re at it, make the same note for BIP32 key derivation.)

maaku commented 5 years ago

Notes made. Removing project tag.

maaku commented 5 years ago

v11 released without this; bumping to v13 which is the first release that uses BIP32 keys in any visible way.

maaku commented 4 years ago

Oops. v13 was released already. Bumping to v14.