Bitcoin Forum
August 19, 2019, 05:58:53 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: BIP proposal: Canonical Deterministic Signatures  (Read 2454 times)
oleganza
Full Member
***
Offline Offline

Activity: 200
Merit: 100


Software design and user experience.


View Profile WWW
August 07, 2014, 09:31:12 AM
 #1

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


Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo
1566237533
Hero Member
*
Offline Offline

Posts: 1566237533

View Profile Personal Message (Offline)

Ignore
1566237533
Reply with quote  #2

1566237533
Report to moderator
1566237533
Hero Member
*
Offline Offline

Posts: 1566237533

View Profile Personal Message (Offline)

Ignore
1566237533
Reply with quote  #2

1566237533
Report to moderator
1566237533
Hero Member
*
Offline Offline

Posts: 1566237533

View Profile Personal Message (Offline)

Ignore
1566237533
Reply with quote  #2

1566237533
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
August 07, 2014, 12:28:28 PM
 #2

Quote
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
Legendary
*
qt
Offline Offline

Activity: 1064
Merit: 1036


View Profile WWW
August 07, 2014, 01:45:58 PM
 #3

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".

I do Bitcoin stuff.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2772
Merit: 2374



View Profile
August 07, 2014, 02:05:04 PM
 #4

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
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1005


Gerald Davis


View Profile
August 07, 2014, 11:29:27 PM
 #5

Quote
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.

Quote
// 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
Full Member
***
Offline Offline

Activity: 200
Merit: 100


Software design and user experience.


View Profile WWW
August 11, 2014, 07:57:19 AM
 #6

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?

Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!