ecdsa: Clarify derivation of the r check in `_sig_verify` #1949

pull real-or-random wants to merge 1 commits into bitcoin-core:master from real-or-random:202609-ecdsa-comments changing 1 files +21 −15

real-or-random commented at 7:25 AM on September 29, 2026: contributor

Introduce the xr + n < p condition in the step where it is needed, namely right before switching from integer equality to equality modulo p, and explain why it is required there. Write congruences as a == b (mod m), because a mod p == b reads as if mod p were an operator applied to the left-hand side only.

Also reword the comment at the p - n check: the check is needed for correctness, not merely an optimization.

Made these improvements when trying to understand the background of #1948.
real-or-random added the label tweak/refactor on Sep 29, 2026
real-or-random added the label meta/development on Sep 29, 2026

in src/ecdsa_impl.h:254 in af52718c1d

 255 | -     *    [Multiplying both sides of the equations by pr.z^2 mod p]
 256 | -     *    <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
 257 | +     *    [Now both sides of each equality are in [0, p), so we can compare them modulo p
 258 | +     *     instead. In Jacobian coordinates, X(pr) is pr.x / pr.z^2]
 259 | +     *    <=> (xr == pr.x / pr.z^2 (mod p)) || (xr + n < p && xr + n == pr.x / pr.z^2 (mod p))
 260 | +     *    [Multiplying both sides of the equalities by pr.z^2]

ViniciusCestarii commented at 2:25 PM on September 29, 2026:

nit: since the previous step introduced (mod p), these are congruences now

     *    [Multiplying both sides of the congruences by pr.z^2]

real-or-random commented at 6:59 AM on September 30, 2026:

done

ViniciusCestarii commented at 2:55 PM on September 29, 2026: contributor

As someone not so familiar with this code, I found this clearer. It's nice that it state the check xr + n >= p is required for correctness and not just an optimization.
theStack commented at 12:16 AM on September 30, 2026: contributor

ACK af52718c1d871b5e2448d50863beae940c92d0aa (modulo #1949 (review) if it's taken)

As someone not so familiar with this code, I found this clearer. It's nice that it state the check xr + n >= p is required for correctness and not just an optimization.

+1, agree that this is clearer, and made reviewing #1948 much easier for me. I vaguely remember that I looked at this code a while ago and also had the impression the second return condition is an optimization.

nit: if we want to be fancy, we could use directly the tribar (≡) character in the file for the modular congruences (maybe a bit too fancy though :p)

ecdsa: Clarify derivation of the r check in `_sig_verify`

Introduce the `xr + n < p` condition in the step where it is needed,
namely right before switching from integer equality to congruence
modulo p, and explain why it is required there. Write congruences as
`a === b (mod m)`, because `a mod p == b` reads as if `mod p` were an
operator applied to the left-hand side only.

Also reword the comment at the `p - n` check: the check is needed for
correctness, not merely an optimization.

93987567a1

real-or-random force-pushed on Sep 30, 2026
real-or-random commented at 7:06 AM on September 30, 2026: contributor

Updated. I made a few more small improvements.

nit: if we want to be fancy, we could use directly the tribar (≡) character in the file for the modular congruences (maybe a bit too fancy though :p)

I've settled on === now to avoid the non-ASCII char. I think writing the relations as congruences is a bit uncommon – it feels more like high school than real algebra – but it makes sense here. Usually we write just = (or == in code) because the two sides are literally equal if we consider them elements of the corresponding finite field $\mathbb{Z}_n$ or $\mathbb{Z}_p$. But here we deal with different fields/moduli (damn ECDSA!), and then working with ordinary integers in $\mathbb{Z}$ and writing congreunces explicitly seems clearer.

I vaguely remember that I looked at this code a while ago and also had the impression the second return condition is an optimization.

Indeed, this confused me to (though then it would be a misoptimization because it optimizes for the rare case of a wrong signature).
theStack approved
theStack commented at 12:43 PM on September 30, 2026: contributor

re-ACK 93987567a1bf2bb5d3ea1492c286cd2b5a76f544
theStack merged this on Sep 30, 2026
theStack closed this on Sep 30, 2026

Contributors

real-or-random

ViniciusCestarii

theStack

Labels

tweak/refactor meta/development

Linked (view graph)

#1948 tests: add ECDSA verify case where r + n overflows p