Rip out non-endomorphism code + dependencies #830

pull sipa wants to merge 11 commits into bitcoin-core:master from sipa:202010_endo_omni changing 28 files +548 −469
  1. 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
  2. Switch to our own memcmp function
    Fixes #823.
    6173839c90
  3. 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
  4. gmaxwell commented at 4:55 AM on October 12, 2020: contributor

    ACK

  5. 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

  6. 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.

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

  8. 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.

  9. 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.

  10. Detailed comments for secp256k1_scalar_split_lambda acab934d24
  11. Add secp256k1_split_lambda_verify 9aca2f7f07
  12. Add tests to exercise lambda split near bounds 9d2f2b44d8
  13. Make lambda constant accessible fe7fc1fda8
  14. 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
  15. Rip out non-endomorphism code 4232e5b7da
  16. WNAF of lambda_split output has max size 129 2edc514c90
  17. sipa force-pushed on Oct 13, 2020
  18. sipa force-pushed on Oct 13, 2020
  19. sipa commented at 7:26 PM on October 13, 2020: contributor

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

  20. 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 ?

  21. 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.

  22. Reorder comments/function around scalar_split_lambda 63c6b71616
  23. Consistency improvements to the comments c582abade1
  24. sipa force-pushed on Oct 13, 2020
  25. luke-jr commented at 8:32 PM on October 13, 2020: member

    Moving memcmp discussion to #832

  26. 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 .

  27. 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 )

  28. jonasnick commented at 9:40 PM on October 13, 2020: contributor

    ACK c582abade1c50ef50dc7ee9f7b7af8e06e22065d didn't verify the proof

  29. sipa merged this on Oct 14, 2020
  30. sipa closed this on Oct 14, 2020
  31. jasonbcox referenced this in commit 8510c863c0 on Oct 22, 2020
  32. jasonbcox referenced this in commit bf580dc212 on Oct 22, 2020
  33. jasonbcox referenced this in commit 51e4185983 on Oct 22, 2020
  34. jasonbcox referenced this in commit e2d35a90e5 on Oct 22, 2020
  35. jasonbcox referenced this in commit 6a7c8cf132 on Oct 22, 2020
  36. jasonbcox referenced this in commit 9fcb376c78 on Oct 22, 2020
  37. jasonbcox referenced this in commit a4e1c1dc5e on Oct 22, 2020
  38. jasonbcox referenced this in commit 49833872c3 on Oct 22, 2020
  39. jasonbcox referenced this in commit eeb6583ff9 on Oct 22, 2020
  40. deadalnix referenced this in commit e49accc636 on Oct 22, 2020
  41. deadalnix referenced this in commit 809d688d5d on Oct 23, 2020
  42. deadalnix referenced this in commit 8d2fa2846c on Oct 23, 2020
  43. deadalnix referenced this in commit 59a40bbcf6 on Oct 23, 2020
  44. deadalnix referenced this in commit 0d18e0e751 on Oct 23, 2020
  45. deadalnix referenced this in commit 9a85e64c28 on Oct 23, 2020
  46. deadalnix referenced this in commit 5a44e23d0e on Oct 23, 2020
  47. deadalnix referenced this in commit 88e25117fd on Oct 23, 2020
  48. deadalnix referenced this in commit 701d49b4ef on Oct 23, 2020
  49. deadalnix referenced this in commit cf0238e77e on Oct 23, 2020
  50. deadalnix referenced this in commit 9f1506b533 on Oct 23, 2020
Contributors
sipagmaxwelljonasnickluke-jrreal-or-random
Linked (view graph)
#822 Increase precision of g1 and g2.#825 Switch to our own memcmp function#826 Rip out non-endomorphism code
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-05-19 06:52 UTC