In the book Programming Bitcoin (2019) by Jimmy Song (pg’s 61-72) the ECDSA signing/verification procedure for message hash z, private/public key pair (e, P), generator point G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8), elliptic curve cyclic group order
N = |
-
Signature (r, s) created as follows :
r = x coordinate of the point R = kG (so r is in the range [0, p – 1]),
s = (z + re) / k mod N (so s is in range [0, N – 1]) -
Signature (r, s) is validated as follows :
Calculate the point Q = (z/s)G + (r/s)P.
(r, s) is valid if x coordinate of Q equals r
This is implemented in the book code at :
https://github.com/jimmysong/programmingbitcoin/blob/master/code-ch13/ecc.py
in the methods PrivateKey.sign and S256Point.verify.
However in other sources, eg :
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/
https://www.secg.org/sec1-v2.pdf
the algorithm is slightly different :
-
r is taken to be mod N (so r is in the range [0, N – 1]),
-
(r, s) is considered valid if (x coordinate of Q mod N) equals r
My question is which approach does Bitcoin itself adopt ?
If Bitcoin adopts the latter approach then if we sign as in Jimmy’s book, and if the x coordinate of R is in the range [N, p – 1], which is possible as N < p, then our r value is in the range [N, p – 1]. However then, on validation using the second approach we compute (x coordinate of Q mod N), which must lie in the range [0, N – 1] and thus it can never equal r, and the validation fails.
The probability of obtaining the x coord of R in the range [N, p – 1] is very small as N is proportionately very close to p, however is it good practice in Bitcoin programming to assume this can never happen ?
