Implement signature grinding

[evanlinjin]

Describe the bug
BDK does not do signature grinding for ecdsa signatures.

Expected behavior
BDK should have signature grinding.

Additional context

This is what BDK currently does.

https://github.com/bitcoindevkit/bdk/blob/a1477405d1adebd9a95689af17d3912edf1e57ef/src/wallet/signer.rs#L460-L463

But we have this to use.

https://github.com/rust-bitcoin/rust-secp256k1/blob/7fde3325075f16ec4b8c2c624fee523cc5225047/src/ecdsa/mod.rs#L341-L344

    /// Constructs a signature for `msg` using the secret key `sk`, RFC6979 nonce
    /// and "grinds" the nonce by passing extra entropy if necessary to produce
    /// a signature that is less than 71 - `bytes_to_grind` bytes. The number
    /// of signing operation performed by this function is exponential in the
    /// number of bytes grinded.
    /// Requires a signing capable context.
    pub fn sign_ecdsa_grind_r(&self, msg: &Message, sk: &SecretKey, bytes_to_grind: usize) -> Signature {
        let len_check = |s : &ffi::Signature| der_length_check(s, 71 - bytes_to_grind);
        self.sign_grind_with_check(msg, sk, len_check)
    }

More context

After we are certain that the BDK ECDSA signer(s) implementation uses signature grinding, we should optimize fee-rate calculation to take into consideration of grinding.

Do we need another signer method to inform whether the signer does ecdsa signature grinding?

[LLFourn]

eak concept NACK.

If my understanding is up to date we currently use max_satisfaction_weight() to figure out weight for coin selection which will not use the grinded value. So fixing this won't improve much other than increase the feerate.

It is also not possible to control this on most hardware wallets. If people want less weight I think they should just use taproot addresses rather than demand libraries to have this wacky parameter to save a few bytes.

[evanlinjin]

eak concept NACK.

If my understanding is up to date we currently use max_satisfaction_weight() to figure out weight for coin selection which will not use the grinded value. So fixing this won't improve much other than increase the feerate.

It is also not possible to control this on most hardware wallets. If people want less weight I think they should just use taproot addresses rather than demand libraries to have this wacky parameter to save a few bytes.

In all else being said, increasing the fee rate slightly is a side-effect most people will be happy with imo.

[RCasatta]

IIRC bitcoin core is grinding for low R, thus always obtaining len(signature) < 71 bytes, thus BDK should do the same for privacy reasons ? (without optimizing fee calculation)

[danielabrozzoni]

If my understanding is up to date we currently use max_satisfaction_weight() to figure out weight for coin selection which will not use the grinded value.

From the max_satisfaction_weight docs:

All signatures are assumed to be 73 bytes in size, including the length prefix (segwit) or push opcode (pre-segwit) and sighash postfix.

The lenght prefix or push opcode is 1 byte, the sighash postfix is 1 byte, which means that rust-miniscript considers one signature to be 71 bytes in size (i.e., considers them to be grinded).

If we don't want to grind signatures, we should take this into account in the coin selection. This means adding 1 WU per input per signature in segwit inputs, 4WU per input per signature in non-segwit inputs.

If we don't do so we risk returning a transaction with a feerate lower than what the user requested.

[afilini]

I don't think it's easy to account for the extra weight ourselves, we basically have to do minisiscript's job of counting how many signatures can end up in a script in the worst case (for example, if we have 10 keys overall in our descriptor, it's not guaranteed that there's a path that actually contains 10 signatures in the scriptsig/witness).

So here's my proposal, which is a bit of a compromise I think:

• we should fix the issue first in miniscript. I don't think they'll be against the change, since we are talking about a "max satisfaction wieght" (so it should take into account the worst case scenario (which means high-r and high-s sigs in legacy contexts, because while it's non-standard I think it's still allowed by consensus. Segwit should have low-s by consensus, I think)).
• we should add an option to our SignOptions to enable/disable signature grinding. By default I would keep it enabled, for the reason @RCasatta described and also because it increases the feerate slightly essentially for free. But being an option, it can still be disabled by the user if they don't want it for whatever reason

[apoelstra]

For my part, I have no problem fixing rust-miniscript to add 1 to the signature size estimate.

I would also be open to having a more flexible API that could specify this .. but I've explored this is the past and I'm skeptical that we'd be able to make a good complexity/functionality tradeoff here.

[danielabrozzoni]

Wait, I might have gotten my math wrong...

The lenght prefix or push opcode is 1 byte, the sighash postfix is 1 byte, which means that rust-miniscript considers one signature to be 71 bytes in size (i.e., considers them to be grinded).

After a bit more research, it seems to me that low-R signatures are 70 bytes long, and high-R signatures are 71 bytes long. Which would mean that rust-miniscript already considers high-R (not grinded) signatures. Does that check out?

[vladimirfomene]

@danielabrozzoni and @evanlinjin let me take this up.

[evanlinjin]

@vladimirfomene I personally don't think it will hurt if you get started with changing how our Software "signers" are implemented first.

However, since this is still tagged as discussion, I would first see the opinions of everyone else.

It will be fine to slightly overshoot feerate.

[danielabrozzoni]

I think this is ready to be worked on. It's a small change on the signer side which gives some pros (Bitcoin Core txs indistinguishable from the bdk ones, and you get some extra priority for your tx without paying additional fees).

I feel like we should have some method in the tx_builder (allow_grinding or something) so that the user can customize this. @evanlinjin what do you think?

[evanlinjin]

@danielabrozzoni I also think this is ready to be worked on. I think the changes on the signer-side is a "no-brainer" (for the reasons that you have mentioned).

In terms of changing up the TxBuilder, I think this should be done in a separate PR, and would need more discussion.

[danielabrozzoni]

In terms of changing up the TxBuilder, I think this should be done in a separate PR, and would need more discussion.

Ok, then I guess we'll just grind by default for now :)

[notmandatory]

Closing this now that #779 is merged.