What is signature grinding and why does the answer to What is the size and weight of a wrapped segwit single-sig input? "highly recommend it"?
Add a comment
|
1 Answer
The serialization format used for ECDSA signatures requires 33 bytes to encode an r-value that falls into the higher half of the range, but only 32 bytes to encode one falling into the lower half of the range. This means that by repeating the signing until you get an r-value in the lower range ("grinding the signature"), you can decrease the size of your signature by 1 byte. This takes an expected two attempts per signature and makes it easier to estimate the necessary fees for transactions before signing and reduces the blockspace footprint and fees for transactions.
Is this a real technique used in practice? Only 1 byte in reduction seems impractical. Still very interesting. – m1xolyd1an
Yes, and it's not just 1 B, it's 1 B per signature.
On P2PKH, when you build a transaction, you have to conservatively estimate inputs as 148 B, lest you perhaps undershoot a target feerate, although about half of the inputs will be 147 B and the other half will be 148 B. Using signature grinding, you can always estimate with 147 B.
For 2-of-3 P2SH, you always have to estimate with 297 B, because both signatures could be high-r. However, only about 1/4 of the inputs ends up being 297 B, 1/2 will be 296 B, and 1/4 will be 293 B. Why 293? Well, if both signatures are low-r, you slide into the smaller varInt range to specify the length of the scriptSig which saves another two bytes. You can therefore estimate with 4 B less using signature grinding, and save an average 2.5 B on each input from hitting the blockchain.
So for P2PKH, it reduces the overall cost (input+output size) you need to conservatively estimate for by about 0.5% (181 B vs 182 B) and produces an about 0.25% reduction of actual blockspace used (181 B vs 181.5 B). For 2-of-3 P2SH, it's about a 1.2% reduction of the fees (325 B vs 329 B), and a 0.75% reduction of blockspace used (325 B vs 327.5 B). Implementation is easy, and the only on-going cost is approximately doubling the signing effort. See e.g. Bitcoin Core's implementation here: Always create signatures with Low R values #13666