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?

$\endgroup$
9
$\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.)

$\endgroup$
3
  • $\begingroup$ Thanks -- I totally misunderstood the context. I think I'll prefix a Resulting to the sentence in the wiki. $\endgroup$
    – jhfrontz
    Nov 25 '19 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
    Sep 10 '20 at 8:03
  • 1
    $\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$ Sep 11 '20 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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