In the code libraries in Programming Bitcoin by Jimmy Song in the method PrivateKey.sign, and in the Python package ecdsa.util.sigencode_der_canonize, which both support Python 3, the checks for high “s” value in a signature (r, s) use floating point arithmetic :
if s > N / 2:
s = N - s
if s > order / 2:
s = order - s
respectively, where N and “order” are the order of the elliptic curve secp256k1, and “/” is the Python 3 “true division” operator producing a floating point type irrespective of the type of the operands (eg. as described in [1] p146). The Python ecdsa package is not specific to Bitcoin but in its documentation (eg. here) it does mention this canonicalization is “most commonly used in bitcoin”.
This causes some high “s” values to not be detected by these libraries and thus the canonicalization is not performed and the signature they produce is then considered invalid by Bitcoin nodes. Specifically using N // 2 as the exact value of one less than the “mid point” of odd prime N (where “//” is the Python 3 “floor division” operator which discards the remainder and performs exact integer arithmetic for integer operands of arbitrary size (eg. [1] p135)) we have (using Python interpreter v3.8.10) :
N = order of secp256k1 generator point G =
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
N // 2 =
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0 (exact)
>>> N / 2
5.78960446186581e+76 (approximate)
>>> s = (N // 2) + 2**127
>>> s > N / 2
False
>>> s = (N // 2) + 2**128
>>> s > N / 2
True
so all the high “s” values in at least the range [N // 2 + 1, N // 2 + 2**127] are not correctly detected.
The exact value of N / 2 should be N // 2 + 0.5, but we see it is considerably larger than that due to the floating point error:
>>> N/2 > N//2 + 2**127
True
>>> N/2 > N//2 + 2**128
False
Does Bitcoin work this way also and that is the reason for floating point usage in these libraries, to be compatible with Bitcoin? It would seem to me better to use exact integer arithmetic, even if there is not much probability that “s” could land in the range [N // 2 + 1, N // 2 + 2**127], it would seem to be better form.
[1] Mark Lutz (2013), Learning Python 5th Edition, O’Reilly
