EC signature generation grinding to achieve deterministic results

[dangershony]

It seems EC sig is not always deterministic but still valid.

When I try to sign one of the BOLT test vectors in a 2_of_2 P2WSH commitment transaction one of the signature payload does not match the test vector.

For reference the test vector can be found here https://github.com/lightningnetwork/lightning-rfc/blob/master/03-transactions.md#appendix-c-commitment-and-htlc-transaction-test-vectors name: simple commitment tx with no HTLCs

The excepted witness redeem script:

0 3044022051b75c73198c6deee1a875871c3961832909acd297c6b908d59e3319e5185a46022055c419379c5051a78d00dbbce11b5b664a0c22815fbcc6fcef6b1937c383693901 3045022100f51d2e566a70ba740fc5d8c0f07b9b93d2ed741c3c0860c613173de7d39e7968022041376d520e9c0e1ad52248ddf4b22e12be8763007df977253ef45a4ca3bdb7c001 5221023da092f6980e58d2c037173180e9a465476026ee50f96695963e8efe436f54eb21030e9f7b623d2ccc7c9bd44d66d5ce21ce504c0acf6385a132cec6d3c39fa711c152ae

The result using NBitcoin Secp256k1 signing code

0 3044022051b75c73198c6deee1a875871c3961832909acd297c6b908d59e3319e5185a46022055c419379c5051a78d00dbbce11b5b664a0c22815fbcc6fcef6b1937c383693901 304402207caaf1fc81064a8e2ac64ce5631e073e0c5b769efcc15bb08c22312367d9c2a50220524c8936c9120fc4f86aa954d00b1c53d818251915e59f216fb3ef5f5843e9e201 5221023da092f6980e58d2c037173180e9a465476026ee50f96695963e8efe436f54eb21030e9f7b623d2ccc7c9bd44d66d5ce21ce504c0acf6385a132cec6d3c39fa711c152ae

Notice the second signature in the redeem script is not the same

I narrowed it down to the grinding part of the signature (in the ECPrivKey extension method Sign:

        internal static Secp256k1.SecpECDSASignature Sign(this Secp256k1.ECPrivKey key, uint256 h, bool enforceLowR, out int recid)
        {
            ...
            bool ret = key.TrySignECDSA(hash, null, out recid, out sig);
            // Grind for low R
            while (ret && sig.r.IsHigh && enforceLowR)
            {
                         ...
                ret = key.TrySignECDSA(hash, nonceFunction, out recid, out sig);
            }
            return sig;
        }

When signing the first key that produces a similar sig as the test vector the while loop is not triggered

ret = true
sig.r.IsHigh = false
enforceLowR = true

When signing the second key with a different sig

ret = true
sig.r.IsHigh = true
enforceLowR = true

Then we go in the while loop for a second attempt at signing that the reason the sig is different. In a test I wrote if I ignore the sig.r.IsHigh = true condition and skip the loop then I get the expect sig

What is the purpose of sig.r.IsHigh ? Shall I try to change the code so we pass a flag that allow to ignore it? (what are the security implications?)

We need a cryptographer... 🤔 🆘 😱

[dangershony]

A quick solution is to add a flag to SigningOptions that will not grind (or will ignore the IsHigh condition)

[lontivero]

The problem seems to be that you are using enforceLowR = true when you really are okay with low and high Rs. Try passing enforceLowR = false.

[lontivero]

Btw, this is what the IsHigh and enforceLowR is abaout: https://github.com/bitcoin/bitcoin/pull/13666

[dangershony]

Try passing enforceLowR = false. Ah lol of course how did I not associate that flag 😜 I will try the flag.

Thanks for the link mate.

[dangershony]

That was my issue thanks @lontivero for the help 👍

[NicolasDorier]

We grind the signature to save 1 byte per sig.