Avoid field inverse for r == x comparison

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

Avoid field inverse for r == x comparison #123