Avoid field inverse for r == x comparison #123

pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:fastcheck changing 3 files +46 −21

sipa commented at 11:15 PM on November 28, 2014: contributor

As suggested by @gmaxwell. This seems to give a 3% speedup for verification.

Builds on top of #119.
sipa force-pushed on Nov 29, 2014
sipa force-pushed on Nov 29, 2014
sipa force-pushed on Nov 30, 2014
sipa force-pushed on Nov 30, 2014
sipa force-pushed on Nov 30, 2014
gmaxwell commented at 10:17 AM on December 1, 2014: contributor

Ah this needs a comment to explain what we're doing, something like:

/_To finish the verification we must check that the r provided matches the X from our multi-exponentation. To do this the obvious way requires converting the point in jacobian coordinate back to affine, or at least it's X value, which requires a slow modular inverse. To avoid the inverse instead of computing r == (Fp(x)/Fp(z)^2) % n, we test (r_z^2 == x) || ((r < p-n) && ((r+n)*z^2 == x)). */
gmaxwell commented at 10:17 AM on December 1, 2014: contributor

ACK. Tested and reviewed the implementation. Perhaps since this is my hairbrained scheme, someone additional should review the idea too.
sipa force-pushed on Dec 1, 2014
sipa commented at 12:30 PM on December 1, 2014: contributor

@gmaxwell Added a bit more elaborate explanation.
gmaxwell commented at 12:33 PM on December 1, 2014: contributor

@sipa Good. I like that.
sipa force-pushed on Dec 2, 2014
sipa commented at 3:46 PM on December 2, 2014: contributor

Rebased.
sipa force-pushed on Dec 7, 2014
sipa commented at 1:41 PM on December 7, 2014: contributor

Rebased.
sipa cross-referenced this on Dec 10, 2014 from issue Weak normalization by sipa
sipa commented at 1:28 PM on December 16, 2014: contributor

@apoelstra Care to review?
apoelstra commented at 2:55 PM on December 16, 2014: contributor

@sipa yes, gimme 48 hours.
Optimize verification: avoid field inverse
Suggested by Greg Maxwell.
ce7eb6fb3d
Add explanation about how inversion can be avoided 13278f642c

in src/ecdsa_impl.h:None in 8430e02665 outdated

 133 | +    unsigned char c[32];
 134 | +    secp256k1_scalar_get_b32(c, &sig->r);
 135 | +    secp256k1_fe_t xr;
 136 | +    secp256k1_fe_set_b32(&xr, c);
 137 | +
 138 | +    // We now have the recomputed R point in pr, and its claimed x coordinate (modulo the order)

apoelstra commented at 8:18 PM on December 16, 2014:

Can you change order to group order (n)? Intuitively x should be mod the field order, but ofc ECDSA uses it as an exponent, so it's better to be explicit.

in src/ecdsa_impl.h:None in 8430e02665 outdated

 137 | +
 138 | +    // We now have the recomputed R point in pr, and its claimed x coordinate (modulo the order)
 139 | +    // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
 140 | +    // compute the remainder modulo the order, and compare it to xr. However:
 141 | +    //
 142 | +    //   x(R) mod n == xr

apoelstra commented at 8:26 PM on December 16, 2014:

Here you say n but every time afterward you say order. IMHO they should all be n.

in src/ecdsa_impl.h:None in 8430e02665 outdated

 138 | +    // We now have the recomputed R point in pr, and its claimed x coordinate (modulo the order)
 139 | +    // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
 140 | +    // compute the remainder modulo the order, and compare it to xr. However:
 141 | +    //
 142 | +    //   x(R) mod n == xr
 143 | +    //   <=> exists h. (x(R) + h * order < p && x(R) == xr + h * order)

apoelstra commented at 9:17 PM on December 16, 2014:

Do you mean && xr == x(R) + h * order) (and then to change the rest of the lines)? Otherwise I don't see this -- it seems like you're checking that x(R) won't overflow but then adding to xr rather than x(R).

sipa commented at 10:19 PM on December 16, 2014:

Rewrote the comments a bit; indeed, the bounds checks were wrong.

sipa force-pushed on Dec 16, 2014
apoelstra commented at 10:12 PM on December 16, 2014: contributor

utACK. Thanks for waiting on me.
sipa merged this on Dec 16, 2014
sipa closed this on Dec 16, 2014
sipa referenced this in commit e99c4c461c on Dec 16, 2014

Contributors

sipa

gmaxwell

apoelstra

Linked (view graph)

#119 Make the num module optional #120 Optimize doubling: secp256k1 has no y=0 point #122 Do signature recovery/verification with 4 possible recid case #154 Weak normalization #1762 Update README.md