0
$\begingroup$

The article Elliptic Curve Digital Signature Algorithm in Bitcoin's wiki talks about signatures having probabilities (as in Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50%, and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.).

What does “probability” mean in this context?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

It's the probability that an ECDSA signature (over the Bitcoin curve, secp256k1) will have the corresponding size. In other words, 25% of the secp256k1 ECDSA signatures have 73 bytes, 50% of them have 72 bytes and 25% of them have 71 bytes. Of course, after the signature is generated its size is settled and the probability does not apply anymore.

(The reason is that an ECDSA signature is the ASN.1 encoding of a structure with two integers. Each encoded integer requires a bit to indicate the sign, even though in ECDSA they are always positive. Therefore, if the upper bit of the integer is set, then the encoded integer will require a whole byte to store the sign bit since the integers have 256 bits, a multiple of 8. There is a chance of roughly 50% of an integer in the secp256k1 ECDSA signature having the upper bit set, requiring a whole byte for the sign bit, which creates the 25%/50%/25% split over two integers.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks -- I totally misunderstood the context. I think I'll prefix a Resulting to the sentence in the wiki. $\endgroup$
    – jhfrontz
    Commented Nov 25, 2019 at 19:11
  • 1
    $\begingroup$ Note: the probabilities in the question and answer are approximate, and >0.19% of signatures are less than 71-byte $\endgroup$
    – fgrieu ♦
    Commented Sep 10, 2020 at 8:03
  • 2
    $\begingroup$ Actually the bitcoin format (for transactions) is the ASN.1 encoding of SEQUENCE{INTEGER,INTEGER} plus one added octet for sighash. And the wiki is out of date: since 2014 bitcoin has required so-called 'low-S' signatures (S < n/2, by using -S mod n if needed, which verifies the same because the final check is only on the x-coordinate) to block certain transaction malleability attacks, thus the ASN.1 portion is now ~50% 71, ~50% 70, tiny <70. $\endgroup$
    – dave_thompson_085
    Commented Sep 11, 2020 at 0:28
  • $\begingroup$ my2cents to just share that someone has thought to use it as a PoW over PoW: github.com/VzxPLnHqr/sig-pow $\endgroup$
    – baro77
    Commented Jul 30, 2022 at 12:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.