BIP proposal: Canonical Deterministic Signatures

[oleganza]

I want to start a discussion about deterministic signatures in the context of RNG failures, hardware wallets' auditability, malleability and CompactSignature. And wrap everything in a single canonical specification.

Here's the proposal. It specifies how to produce k deterministically from the message hash and a private key. Also specifies canonical format for the signature and CompactSignature algorithm. This is an opportunity to have a single BIP to cover everything regarding signatures that we need in Bitcoin, so it is easy for developers to understand signatures, learn about hazards and embrace best practice.
https://github.com/oleganza/bips/blob/master/bip-oleganza-detsig.mediawiki

Previous discussion on the topic: https://bitcointalk.org/index.php?topic=285142.0

[1715289009]

1715289009

[1715289009]

1715289009

[amaclin]

Make sure that S value is even (pseudo code):
  if s > (n >> 1)
    s = n - s
  end

Does this really gets even value? I see the lowest (and I vote for lowest from two possibilities), not even

[Pieter Wuille]

BIP 62 already contains a proposal to make S values deterministic (by making it eventually a consensus rule inside version=3 transactions).

Instead of forcing an even value, it forces the value to be in the lower half of the range. Reason: makes signatures on average half a byte smaller. This is also what Bitcoin Core does since 0.9 (and afaik BitcoinJ as well).

EDIT: seems your code already does this, but the text says "even".

[gmaxwell]

RFC 6979 is hash-function agile, though it suggests that you use the same hash for its hmac as you use for message hashing in your signature. I believe it's being used by some Bitcoin wallets already, and although the spec is wordy the implementation is pretty straight forward.

It's my general preference to stick with a construction that has has more review absent a good reason not to. E.g. Just do 6979 but with the HMAC-SHA512 used for derivation elsewhere. This way one of the answers to 'oh no I'm giving my private key to this!' is "It's a standard"... obviously this is no excuse for us to not review it too, but it will increase other people's confidence if the specific construction has been widely reviewed.

I also think it's a good idea to have a single spec which defines everything you need in signing, see my BIP 32.5 mailing list post.

It would be good to review what other things are doing. My strong preference would just be to give a simplified explanation of 6979 using HMAC-SHA512,  plus the low-S rule, plus canonical DER encoding. Sipa's canonical encoding BIP can just explain enforcing the canonical encoding rules.  Hopefully we can get everyone behaving consistently, particularly for hardware wallets its important that the _exact_ behavior be verifiable so that you can preclude the possibility of kleptographic backdoors.

[DeathAndTaxes]

Why not simply using RFC 6979?

RFC 6979 is not used by anyone and is unnecessary complex.
It's preferrable to reuse existing hash functions like double-SHA256 or HMAC-SHA512 since they are heavily used in Bitcoin infrastructure already.
This BIP also specifies canonical ECDSA signature and CompactSignature algorithm. Those are out of scope of RFC 6979.

I don't feel these are particularly good reasons to not use an existing standard.

RFC6979 is already incorporated into multiple libraries (bitcoinj, NBitcoin, bitcoinjs-lib, python-ecdsa, etc).  In the case of bitcoinjs-lib they claim it is used by blockchain.info so potentially the largest web wallet in the world has the ability to use deterministic signatures right now (if they aren't already).  I haven't verified this claim maybe someone from blockchain.info can verify if they are using bitcoinjs.

As gmaxwell pointed out RFC6979 can be used with HMAC-SHA512.  All existing implementations use HMAC-SHA256 but that isn't a requirement rather a choice. 

The "full" RFC6979 is rather complex as it is a universal solution which handles lots of edge cases which don't apply to Bitcoin signatures.  From bitcoinjs the "route" taken by Bitcoin signatures makes implementing a Bitcoin only subset pretty straight forward.

// https://tools.ietf.org/html/rfc6979#section-3.2
function deterministicGenerateK(curve, hash, d) {
  var x = d.toBuffer(32)
  var k = new Buffer(32)
  var v = new Buffer(32)

  v.fill(1)
  k.fill(0)
  k = crypto.HmacSHA256(Buffer.concat([v, new Buffer([0]), x, hash]), k)

  v = crypto.HmacSHA256(v, k)
  k = crypto.HmacSHA256(Buffer.concat([v, new Buffer([1]), x, hash]), k)

  v = crypto.HmacSHA256(v, k)
  v = crypto.HmacSHA256(v, k)

  var T = BigInteger.fromBuffer(v)

  //will only occur less than 1 in
  while ((T.signum() <= 0) || (T.compareTo(curve.n) >= 0)) {
    k = crypto.HmacSHA256(Buffer.concat([v, new Buffer([0])]), k)
    v = crypto.HmacSHA256(v, k)
    T = BigInteger.fromBuffer(v)
  }

  return T
}

https://github.com/bitcoinjs/bitcoinjs-lib/blob/master/src/ecdsa.js

[oleganza]

Thanks for feedback guys. Since people already implement RFC6979, lets use it.

Question: why HMAC-SHA512 is preferable to HMAC-SHA256? Only to be the same as in BIP32? But unlike BIP32, here we do not use extra 32 bytes output and would simply throw it away. Is it correct that SHA512 is faster than SHA256 on 64-bit systems, so using HMAC-SHA512 would allow better singing performance?