3

So i was reading the BIP for Schnorr signatures and I couldn't find any explanation on why the simple RFC6979 Variant wasn't chosen for their nonce generation. Instead, they decided to go with their own implementation. Why is this?

EDIT: to clarify I'm not refering to normal RFC6979.

10

I'm not sure what simplified variant you're referring to, but this is a great question.

There are a number of reasons.

First, RFC6979 is not cheap and fairly complex. Computing a single candidate nonce costs 22 invocations of the SHA256 compression function. Hashes are fast, but this actually corresponds to hashing 1400 bytes which isn't trivial anymore compared to the time of signing. It serves a purpose - it's instantiating a well-knowing PRNG to generate the candidate nonces - but this is overkill for us. secp256k1 has the interesting property that its group order is negligibly close to 2256. So instead no PRNG is needed at all - a single hash suffices, which is lower complexity, and obviously constant time as well.

A simpler alternative is the one used by Ed25519, where a single SHA512 invocation generates a 512-bit number that is reduced modulo the curve order. Our construction is different, but is inspired by this. There are some changes though:

  • We don't need a 512-bit hash and a modulo reduction, again because the curve order is close to 2256, so we can use a 256-bit hash directly without reduction instead.

  • We're concerned about implementations where the public key of the signer is taken from untrusted input (something most signing APIs don't seem to protect against, as it's a performance penalty to recreate the public key from the private key instead). Greg Maxwell started a discussion on this cryptography mailing list about this problem: https://moderncrypto.org/mail-archive/curves/2020/001012.html, which received comments from DJB and others. We address this issue by including the public key into the nonce generation.

  • We're trying to protect against fault attacks and differential power analysis attacks by encouraging synthetic nonces (which incorporate actual randomness when it is available). RFC6979 also has a variant that supports this, but it appears that due to our use of linearly derived private keys (through BIP32, and through Taproot), DPA attacks are much harder to protect against, and standard solutions may not apply. See the bitcoin-dev mailinglist discussion here: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-March/017711.html (where I agreed with OP that some of our design choices are not well explained in the BIP yet)

| improve this answer | |
  • Thanks for the reply. I was refering to this one K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k') its explained on the link above. BCH uses this for their implementation just that k' is always known and its a UTF-8 string of certain size (dont remember from the top of my head) – sken May 7 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.