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$
4
$\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 required 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$
  • $\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

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.