Grind ECDSA signatures for low-R (RFC6979)

[msgilligan]

We need to implement "grinding" for low-R ECDSA signatures to create shorter and deterministic signatures. This should be implemented both in the libsecp256k1/FFM implementation and the Bouncy Castle implementation.

This was first mentioned by @craigraw in Issue #79 (Feedback on 0.0.1) along with a list of other suggestions/requirements.

@schildbach has been working on a PR to add this capability to bitcoinj: bitcoinj/bitcoinj#2302

[msgilligan]

I can take a look at updating the FFM implementation to make use of the libsecp256k1 C API that @craigraw pointed out.

I think @schildbach will continue work on his PR for "legacy" bitcoinj ECDSA crypto, but mid-term we should create the Bouncy Castle implementation of the secp-jdk API and create unit tests and test vectors that test both implementations.

[schildbach]

If we want strictly deterministic signatures between wallets, I think the Bitcoin wallet dev community needs to come up with a BIP that describes what Bitcoin Core is doing, maybe amend it with some of the improvements that have been implemented by some wallets, and supplement the BIP with test vectors. Currently, everyone is figuring out what everyone else has been doing, and I found maybe 1½ unofficial test vectors that I could use for our own unit tests.

RFC6979 is part of the picture, but does not nearly describe everything that's needed.

Currently, my main driver for this effort is simplifying the fee logic. Craig has brought up the issue of key exfiltration.

[craigraw]

Fwiw, the Keepkey is the only signer on the market I'm aware of that does not grind for low R. Everyone else has already implemented it.

[msgilligan]

@craigraw said:

secp256k1-jdk currently has no ability to specify the RFC6979 extra ndata in secp.ecdsaSign. Currently, it's set to nullPointer.

Can I just add the ndata parameter, while leaving the default noncefp function (secp256k1_nonce_function_default)? Will that work for Sparrow?

[craigraw]

Yes, I can't imagine there will ever be any need to change the nonce function from RFC6979.