Does Bitcoin Core Validate ECDSA Signature Component r Using Mod N?

Question

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 = |<G>| = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, field order p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, and ephemeral private key k is defined by :

1. 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])
   

2. 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 :

1. r is taken to be mod N (so r is in the range [0, N - 1]),

2. (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 ?

Answer 1

The ECDSA verification algorithm (in general, and as implemented in Bitcoin) unambiguously requires both r and s to be less than the group order, so descriptions of signature generation algorithms usually include taking r to be the X coordinate of R modulo the curve order. In the extraordinaly unlikely case that r falls between n and p - 1, omitting the modulo step would just result in an invalid signature (which all Bitcoin nodes would recognize as invalid).

Note that in the Schnorr signature algorithm as described in BIP340, r is not required to be less than the curve order (meaning it can go up to p - 1).