Informational BIP describing low-R grinding: re-deriving the ECDSA nonce under a counter until r has its high bit unset, so the DER encoding needs no leading null byte.
This was discussed on the mailing list: https://groups.google.com/g/bitcoindev/c/boEZRlqczvw
Reference implementation and test vectors are TODO.
Feedback is very welcome.
For reviewers, see also discussion in https://github.com/bitcoinj/secp256k1-jdk/issues/419 and the following posts by @Sjors (ordered by date inc) in the relevant Bitcoin Core PR:
Thanks, adding this to my to-read list.
Another important motivation is that signatures produced according to a standardised approach will be byte-identical. This means signers can be compared to ensure they are not leaking secrets by embedding them in signatures (e.g. Dark Skippy).
18 | +DER treats *r* and *s* as big-endian *signed* integers, so an integer whose most significant bit is set must be preceded by a null byte to keep it positive. 19 | + 20 | +The *s* value of a signature can be normalized through simple negation, resulting in an equally valid signature whose *s* value has its most significant bit unset. A signature's *r* value cannot be modified in a similar way: it is the x-coordinate of the nonce point, and is fixed once the nonce is chosen. Its most significant bit is set about half the time. 21 | +Thus, about half of ECDSA signatures carry an extra padding byte when DER encoded. 22 | + 23 | +The only way to obtain a different *r* is to re-sign with a different nonce. Low-R Grinding takes two signing operations on average[^geometric] and saves roughly 0.5 vbytes per signature in legacy inputs and 0.125 vbytes in v0 segwit inputs.[^optech]
When it is needed it saves a whole byte, so maybe add “in average”:
The only way to obtain a different *r* is to re-sign with a different nonce. Low-R Grinding takes two signing operations on average[^geometric] and saves in average roughly 0.5 vbytes per signature in legacy inputs and 0.125 vbytes in v0 segwit inputs.[^optech]
It says "on average" before, but perhaps it isn't clear that all the figures given in this sentence are on average.
20 | +The *s* value of a signature can be normalized through simple negation, resulting in an equally valid signature whose *s* value has its most significant bit unset. A signature's *r* value cannot be modified in a similar way: it is the x-coordinate of the nonce point, and is fixed once the nonce is chosen. Its most significant bit is set about half the time. 21 | +Thus, about half of ECDSA signatures carry an extra padding byte when DER encoded. 22 | + 23 | +The only way to obtain a different *r* is to re-sign with a different nonce. Low-R Grinding takes two signing operations on average[^geometric] and saves roughly 0.5 vbytes per signature in legacy inputs and 0.125 vbytes in v0 segwit inputs.[^optech] 24 | + 25 | +Combined with normalizing *s*, Low-R Grinding lets a signer produce ECDSA signatures for arbitrary messages with a fixed *maximum* size: 70 bytes of DER, 71 with the sighash flag. This allows for lower fees and more accurate transaction size predictions. Smaller *r* values could be ground for in theory, but are not in Low-R Grinding.[^pr13666]
You could also mention that for 2-of-3 P2SH inputs, having at least one high-r signature increases the input by an additional 2 bytes because the input script’s length indicator then requires three bytes. For 2-of-3 P2SH inputs, roughly 25% of inputs have two low-r signatures and take 293 bytes, about 50% have one high-r signature and take 296 bytes, and 25% of inputs have two high-r signatures that take 297 bytes. So for 2-of-3 P2SH inputs, the expected savings of low-r grinding is 2.5 vB.
Looks very good. I just have a couple nits for you.
The document should have a Rationale section. The Rationale should describe design decisions, compare to potential alternate designs and related work. You could mention the suggestion that Craig gave there. The explanation why incrementing a counter on top of RFC6979 is safe and recommend could also be located in that section. Some of the Footnotes would fit there as well, in fact, many BIPs use the Footnotes section as the Rationale.
Since the reference implementation and test vectors are still marked TODO, I'd like to offer help there, if you aren't already deep into them.
What I have in mind is an independent Python implementation of the recommended instantiation: pure Python secp256k1, RFC 6979 with the grind counter in the additional data, the grinding loop, and DER encoding, plus a script that generates the vectors and a separate one that verifies them, everything checked byte for byte against Bitcoin Core's signer. I built the spend-path vectors for the BIP 360 draft recently (#2232), so this is familiar ground.
The reason I think an implementation that shares no code with libsecp is worth having: if it agrees with Core on the vectors, that's good evidence the text is unambiguous, and if it doesn't, the first diverging intermediate value shows exactly which part needs tightening.
If that sounds useful, two things worth deciding up front:
Happy to open the result as a PR against your branch, or just post it here, whichever works better for you.
@jeanpablojp I appreciate the offer, but I've already written a test implementation, and waiting to push it until I resolve everything in the text. Once it is pushed, I would really appreciate a review of the code, if you have time.
Will do, happy to review it when it's up.
@murchandamus made the changes you recommended. However, I'm wondering whether or not this BIP should be classified as "Informational". With the addition of the Rationale section, the BIP seems split across how Low-R Grinding can be done and how it should be done. Of course, a signer need not follow Core's implementation in order to produce low-r signatures, but BIP-3 does say the "distinguishing characteristic of a Specification BIP is that it can be implemented, and implementations can be compliant with it". What do you think?
56 | + 57 | +The predicate *r* < 2<sup>255</sup> is equivalent to testing that the most significant byte of *bytes(32, r)* is below *0x80*, which is how Bitcoin Core expresses it.[^core] 58 | + 59 | +### Recommendations for Exact Implementation 60 | + 61 | +This document does not fix an exact nonce function.[^noncereq] Matching the implementation below is nonetheless strongly recommended: it is what Bitcoin Core's wallet has used since v0.17.0,[^pr13666] and the reference implementation and test vectors accompanying this document will follow it, so a conforming implementation can be checked against them byte for byte.
Your idea to go for a Specification BIP makes sense to me. However, if that’s your goal, I would recommend that you commit to a specific nonce derivation strategy, i.e., to require use of RFC6979 here, otherwise implementers would optionally be unable to use the test vectors. You could still mention that people can make use of other nonce derivation strategies, and they could implement the idea described here, but they would not be in compliance with the BIP, strictly speaking.
83 | + 84 | +The grind counter is exactly such a value, and can be used as the additional data directly. 85 | + 86 | +### Potential Alternate Designs 87 | + 88 | +**A fresh random nonce on each attempt.** Drawing each candidate nonce from a cryptographically secure random source also yields unrelated nonces, and is a valid means of producing low-*r* signatures. It is not recommended because the signatures are not reproducible, which reopens the exfiltration problem described above.
In technical writing, it is generally preferred to repeat the same concrete term for the same concept or to use explicit references rather than falling back to pronouns to remove ambiguity.
**A fresh random nonce on each attempt.** Drawing each candidate nonce from a cryptographically secure random source also yields unrelated nonces, and is a valid means of producing low-*r* signatures. Random nonces are not recommended because the signatures are not reproducible, which reopens the exfiltration problem described above.
87 | + 88 | +**A fresh random nonce on each attempt.** Drawing each candidate nonce from a cryptographically secure random source also yields unrelated nonces, and is a valid means of producing low-*r* signatures. It is not recommended because the signatures are not reproducible, which reopens the exfiltration problem described above. 89 | + 90 | +**Grinding for smaller *r*.** In order for a lower *r* value to save any space, it must be an entire byte smaller, and thus must have the leading 9 bits unset rather than just the leading bit. Computing such an *r* value would take 512 signing operations on average, as opposed to the two of regular Low-R Grinding.[^geometric2] This was deemed too expensive to be adopted widely, which would leave those who did grind for such an *r* fingerprinted.[^pr13666] 91 | + 92 | +**Speeding up grinding with the *λ* endomorphism.** It was suggested to use secp256k1's *λ* endomorphism to quickly compute alternative nonces.[^endomorphism] This was not chosen because Low-R Grinding as specified takes only two point multiplications on average, and the added complexity of making use of it cannot meaningfully improve on that.[^endospeedup]
Could be simplified, and “use of it” should be more specific:
**Speeding up grinding with the *λ* endomorphism.** It was suggested to use secp256k1's *λ* endomorphism to quickly compute alternative nonces.[^endomorphism] Low-R Grinding as specified takes only two point multiplications on average. The added complexity of using the *λ* endomorphism cannot meaningfully improve on that.[^endospeedup]
I’m open to the idea to make it a Specification BIP, but in that case, you should specify one concrete approach. :)
@murchandamus made the changes you requested and turned it into a specification BIP, and included the pseudocode.
cc: @achow101 as the original proposer of low-r grinding.
I think this should really be titled "Deterministic ECDSA Signatures" since it describes the entire ECDSA algorithm, not just how to do low R grinding. That low R grinding is here is interesting and should be mentioned somewhere, but it really is a spec for how to sign something.
Sounds good, I'll go ahead and change the title+text to reflect that.
Yeah, that’s a good point, @achow101. Let’s call this BIP461. When you’re updating the document, please also add an entry to the README table for your BIP, add the number to the preamble and update the Assigned header to today’s date.
81 | +- Fail if *k = 0* or *k >= n* 82 | +- Let *R = k⋅G* 83 | +- Let *r = x(R) mod n* 84 | +- Fail if *r = 0* 85 | +- Let *s' = k<sup>-1</sup> * (d * r + int(msghash)) mod n* 86 | +- If *s' > (n - 1) / 2*:[^lows]
I think it would help to write out what this value is, since it is a constant. See also https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#low-s-values-in-signatures
34 | + 35 | +### Notation 36 | + 37 | +Lowercase variables represent integers, byte arrays, or signatures: 38 | + 39 | +- The constant *p* refers to the field size, *0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F*.
For completeness, the name of the curve being used and it's definition document (https://www.secg.org/sec2-v2.pdf) should be referenced somewhere in these constants definitions.
All above changes should now be implemented.
BIP specifying how to deterministically produce
valid ECDSA signatures using low-r grinding and
low-s normalization with RFC 6979.
132 | +- If *is_infinite(P)*: 133 | + - Return *false* 134 | +- If *y(P)<sup>2</sup> ≠ x(P)<sup>3</sup> + 7 mod p*: 135 | + - Return *false* 136 | +- Let *(r, s) = sig* 137 | +- If *r = 0* or *r >= n*:
Bitcoin Core rejects negative r and s in transaction signatures during DER validation in IsValidSignatureEncoding():
if (sig[4] & 0x80) return false;
if (sig[lenR + 6] & 0x80) return false;
Suggestion:
diff --git a/bip-0461.md b/bip-0461.md
index 444db94..608e093 100644
--- a/bip-0461.md
+++ b/bip-0461.md
@@ -134,9 +134,9 @@ The algorithm *verify(sig, P, msghash)* is defined as:
- If *y(P)<sup>2</sup> ≠ x(P)<sup>3</sup> + 7 mod p*:
- Return *false*
- Let *(r, s) = sig*
-- If *r = 0* or *r >= n*:
+- If *r <= 0* or *r >= n*:
- Return *false*
-- If *s = 0* or *s >= n*:
+- If *s <= 0* or *s >= n*:
- Return *false*
- Let *w = s<sup>-1</sup>*
- Let *u<sub>1</sub> = w * int(msghash) mod n*
Good catch.
ACK b24f038c78f07eea2f3b7fdf792eb6eaec900672
LGTM. Will need test vectors and reference implementation to advance to Complete, but I think it’s ready to be published as Draft.