Rip out non-endomorphism code + dependencies

sipa commented at 6:08 pm on October 11, 2020: contributor

This is a rebased/combined version of the following pull requests/commits with minor changes:

#825 Switch to our own memcmp function
- Modification: secp256k1_memcmp_var is marked static inline
- Modification: also replace memcmp with secp256k1_memcmp_var in exhaustive tests
- Modification: add reference to GCC bug 95189
#822 Increase precision of g1 and g2
- Modification: use the new secp256k1_memcmp_var function instead of memcmp (see #822 (comment))
- Modification: drop the " Allow secp256k1_split_lambda_verify to pass even in the presence of GCC bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189." commit, as it’s dealt with using secp256k1_memcmp_var.
- Modification: rename secp256k1_gej_mul_lambda -> secp256k1_ge_mul_lambda
A new commit that moves the lambda constant out of secp256k1_scalar_split_lambda and (_verify).
The test commit suggested here: #822 (comment)
- Modification: use the new accessible secp256k1_const_lambda instead of duplicating it.
#826 Rip out non-endomorphism code
A new commit that reduces the size of the WNAF output to 129, as we now have proof that the split output is always 128 bits or less.
A new commit to more consistently use input:k, integer outputs:k1,k2, modulo n outputs:r1,r2

Switch to our own memcmp function

Fixes #823.

6173839c90

Increase precision of g1 and g2

This allows us to shift by 256+128 = 384 bits, which is a multiple of the limb size of
the scalar representation. This also happens to be the most precision possible for g2
that still fits into a 256-bit value.

76ed922a5f

sipa cross-referenced this on Oct 11, 2020 from issue Increase precision of g1 and g2. by roconnor-blockstream

sipa cross-referenced this on Oct 11, 2020 from issue Switch to our own memcmp function by real-or-random

sipa cross-referenced this on Oct 11, 2020 from issue Rip out non-endomorphism code by sipa

gmaxwell commented at 4:55 am on October 12, 2020: contributor

ACK

sipa commented at 7:57 pm on October 12, 2020: contributor

Comment by @real-or-random, putting it here so I don’t forget:

here’s a nit: the comment for split_lambda is now confusingly far from the actual function. this bit me when looking at it today. the current order is:

huge comment

lambda constant

split_lambda_verify

split_lambda

we could make it

lambda constant

huge comment

split_lambda

split_lambda_verify

feel free to either fix or ignore

gmaxwell commented at 8:04 pm on October 12, 2020: contributor

putting verify last puts things out of calling order (split_lambda calls _verify). maybe instead just split up the comment and put the range validation proof stuff on the verify part.

in src/scalar.h:108 in 959ccaa374 outdated

109-static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a);
110-#endif
111+/** Find r1 and r2 such that r1+r2*2^128 = k. */
112+static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k);
113+/** Find r1 and r2 such that r1+r2*lambda = k,
114+ * where r1 and r2 or their negations are maximum 128 bits long (see secp256k1_gej_mul_lambda). */

jonasnick commented at 2:14 pm on October 13, 2020:

Perhaps a good time to remove the reference to secp256k1_gej_mul_lambda which doesn’t seem to exist.

sipa commented at 7:25 pm on October 13, 2020:

Good idea, done.

in src/scalar_impl.h:308 in 959ccaa374 outdated

309+ * and k2 have a small size.
310+ *
311+ * The algorithm computes c1 = round(b2 * k / n) and c2 = round((-b1) * k / n), and gives
312  * k1 = k - (c1*a1 + c2*a2) and k2 = -(c1*b1 + c2*b2). Instead, we use modular arithmetic, and
313- * compute k1 as k - k2 * lambda, avoiding the need for constants a1 and a2.
314+ * compute k - k2 * lambda (mod n) which is equivalent to k1 (mod n), avoiding the need for

jonasnick commented at 2:31 pm on October 13, 2020:

“we […] compute” only with r1, r2 not k1, k2. Maybe introduce what exactly r1, r2 are or s/we/one can/.

sipa commented at 7:25 pm on October 13, 2020:

I’ve changed this line a bit.

jonasnick commented at 9:39 pm on October 13, 2020:

Looks better now.

in src/scalar_impl.h:419 in 959ccaa374 outdated

369+ *
370+ * Let
371+ *  - k1 = k - c1*a1 - c2*a2
372+ *  - k2 = - c1*b1 - c2*b2
373+ *
374+ * Lemma 3: |k1| < (a1 + a2 + 1)/2 < 2^128

jonasnick commented at 2:32 pm on October 13, 2020:

Above we say that k1 has a small size and this lemma only shows that |k1| has a small size. Does k1 refer to different quantities in this text?

sipa commented at 7:25 pm on October 13, 2020:

I checked the book (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.3037&rep=rep1&type=pdf), and it says “are small in absolute value”. I’ve updated the comment.

Detailed comments for secp256k1_scalar_split_lambda acab934d24

Add secp256k1_split_lambda_verify 9aca2f7f07

Add tests to exercise lambda split near bounds 9d2f2b44d8

Make lambda constant accessible fe7fc1fda8

Check correctness of lambda split without -DVERIFY

The VERIFY macro turns on various paranoid consistency checks, but
 the complete functionality should still be tested without it.

This also adds a couple of static test points for extremely small
 split inputs/outputs.  The existing bounds vectors already check
 extremely large outputs.

ebad8414b0

Rip out non-endomorphism code 4232e5b7da

WNAF of lambda_split output has max size 129 2edc514c90

sipa force-pushed on Oct 13, 2020

sipa commented at 7:26 pm on October 13, 2020: contributor

I reordered the comments and functions bit, and addressed @jonasnick’ nits.

luke-jr commented at 8:01 pm on October 13, 2020: member

IMO if GCC bug 95189 is the only problem with normal memcmp, I don’t think implementing a new one here is the right solution. At most, check for it in configure and add –no-builtin-memcmp ?

sipa commented at 8:04 pm on October 13, 2020: contributor

@luke-jr I tried writing a test for the bug in autoconfese, but it was more effort than it’s worth I think, especially since none of the uses of memcmp in libsecp256k1 are performance critical. This approach also protects non-autoconf builds.

Reorder comments/function around scalar_split_lambda 63c6b71616

Consistency improvements to the comments c582abade1

sipa force-pushed on Oct 13, 2020

luke-jr commented at 8:32 pm on October 13, 2020: member

Moving memcmp discussion to #832

real-or-random commented at 8:34 pm on October 13, 2020: contributor

@luke-jr I tried writing a test for the bug in autoconfese, but it was more effort than it’s worth I think, especially since none of the uses of memcmp in libsecp256k1 are performance critical. This approach also protects non-autoconf builds.

Agreed, just adding our memcmp is simpler. @luke-jr Also see more discussion in #823 .

real-or-random commented at 9:22 pm on October 13, 2020: contributor

ACK c582abade1c50ef50dc7ee9f7b7af8e06e22065d code inspection, some tests, verified the new g1/g2 constants

(mod the decision how we want to solve #823 )

jonasnick commented at 9:40 pm on October 13, 2020: contributor

ACK c582abade1c50ef50dc7ee9f7b7af8e06e22065d didn’t verify the proof

sipa merged this on Oct 14, 2020

sipa closed this on Oct 14, 2020

jasonbcox referenced this in commit 8510c863c0 on Oct 22, 2020

jasonbcox referenced this in commit bf580dc212 on Oct 22, 2020

jasonbcox referenced this in commit 51e4185983 on Oct 22, 2020

jasonbcox referenced this in commit e2d35a90e5 on Oct 22, 2020

jasonbcox referenced this in commit 6a7c8cf132 on Oct 22, 2020

jasonbcox referenced this in commit 9fcb376c78 on Oct 22, 2020

jasonbcox referenced this in commit a4e1c1dc5e on Oct 22, 2020

jasonbcox referenced this in commit 49833872c3 on Oct 22, 2020

jasonbcox referenced this in commit eeb6583ff9 on Oct 22, 2020

deadalnix referenced this in commit e49accc636 on Oct 22, 2020

deadalnix referenced this in commit 809d688d5d on Oct 23, 2020

deadalnix referenced this in commit 8d2fa2846c on Oct 23, 2020

deadalnix referenced this in commit 59a40bbcf6 on Oct 23, 2020

deadalnix referenced this in commit 0d18e0e751 on Oct 23, 2020

deadalnix referenced this in commit 9a85e64c28 on Oct 23, 2020

deadalnix referenced this in commit 5a44e23d0e on Oct 23, 2020

deadalnix referenced this in commit 88e25117fd on Oct 23, 2020

deadalnix referenced this in commit 701d49b4ef on Oct 23, 2020

deadalnix referenced this in commit cf0238e77e on Oct 23, 2020

deadalnix referenced this in commit 9f1506b533 on Oct 23, 2020

ofek cross-referenced this on Jan 19, 2021 from issue upgrade libsecp256k1 by ofek

Rip out non-endomorphism code + dependencies #830