Test all ecmult functions with many j*2^i combinations #920

pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:202104_ecmult_bitcomb changing 2 files +78 −26
  1. sipa commented at 8:46 pm on April 13, 2021: contributor

    Instead of just testing properties of the points xG for x=-36..36:

    • also compute all xG where x=j*2^i for i=0..255 and odd j=1..255.
    • test them against known exact results (SHA256 all of them, and compared against an independently created result)
    • test all 4 ecmult functions (and for secp256k1_ecmult and secp256k1_ecmult_multi_var, both as G, and through the generic point input)
  2. sipa cross-referenced this on Apr 13, 2021 from issue Replace gen_context.c with a Python implementation by sipa
  3. real-or-random approved
  4. real-or-random commented at 2:01 pm on April 15, 2021: contributor
    ACK ec6dff0f532b9f029de6c64af1cd0480651f51f2 diff looks good
  5. in src/tests.c:3726 in ec6dff0f53 outdated
    3722 void test_ecmult_constants(void) {
    3723-    /* Test ecmult_gen() for [0..36) and [order-36..0). */
    3724+    /* Test ecmult_gen for:
    3725+     * - Numbers 0..36 and their negations
    3726+     * - Numbers 2^i (with i=0..255)
    3727+     * - Numbers 2^i + 2^j (with i=0..255, j=i+1..255)
    


    jonasnick commented at 9:09 pm on April 15, 2021:
    i only goes up to 254.

    real-or-random commented at 11:36 am on April 18, 2021:
    Well yeah it’s equivalent in the end.

    jonasnick commented at 8:18 pm on May 13, 2021:
    If it’s equivalent I’d prefer i=0..42069. Fwiw I’m only mentioning this because I added some printfs to this code and was confused for a moment why there was no i=255. @sipa care to fix the micronit? Fine for me either way.

    sipa commented at 8:36 pm on May 13, 2021:
    Oh, I was considering an alternative approach to instead test all numbers of the form a*(2^N)^b a=1..M b=0..256/M, for some M and N, as that’d give better coverage of the actual tables involved.

    sipa commented at 11:17 pm on November 22, 2021:
    I’ve rewritten it to use (j*2^i) for i=0..255 and odd j=1..255.
  6. jonasnick commented at 9:13 pm on April 15, 2021: contributor
    ACK mod nit
  7. real-or-random commented at 1:36 pm on November 19, 2021: contributor
    @sipa Can you fix this? This will be helpful for testing #988 .
  8. in src/tests.c:3694 in ec6dff0f53 outdated
    3689@@ -3690,37 +3690,77 @@ void run_wnaf(void) {
    3690     CHECK(secp256k1_scalar_is_zero(&n));
    3691 }
    3692 
    3693+void test_ecmult_accumulate(secp256k1_sha256* acc, const secp256k1_scalar* x) {
    3694+    /* Compute x*G in 4 different ways, serialize it uncompressed, and feed it into acc. */
    


    robot-dreams commented at 11:07 pm on November 19, 2021:
    Just confirming, secp256k1_ecmult_multi_var is out of scope as a 5th way for this test?

    sipa commented at 11:17 pm on November 22, 2021:
    Nope, added!
  9. robot-dreams commented at 11:26 pm on November 19, 2021: contributor

    ACK ec6dff0f532b9f029de6c64af1cd0480651f51f2

    I don’t have enough context to comment on the choice of test cases (e.g. whether there are other precomputed values that would be good to test), but the test itself looks good and passes locally.

    I also checked against an independent Python implementation and got the exact same SHA256 output.

  10. sipa force-pushed on Nov 22, 2021
  11. sipa commented at 11:18 pm on November 22, 2021: contributor
    Rebased, addressed some comments, and made some more changes.
  12. sipa renamed this:
    Test ecmult functions with all 2^i+2^j combinations
    Test all ecmult functions with many j*2^i combinations
    on Nov 22, 2021
  13. sipa commented at 11:23 pm on November 22, 2021: contributor

    FWIW, the Python code to recreate the hash (in the https://github.com/bitcoin/bitcoin/tree/22.0/test/function directory):

     0from test_framework import key
     1import hashlib
     2
     3s = hashlib.sha256()
     4
     5def add(s, v):
     6    v = v % key.SECP256K1_ORDER
     7    if v == 0:
     8        s.update(b"\x00")
     9    else:
    10        keyb = v.to_bytes(32, 'big')
    11        ec = key.ECKey()
    12        ec.set(keyb, False)
    13        s.update(ec.get_pubkey().get_bytes())
    14
    15for i in range(0, 37):
    16    add(s, i)
    17    add(s, -i)
    18
    19for b in range(256):
    20  for v in range(1, 256, 2):
    21    add(s, v << b)
    22
    23print(s.hexdigest())
    
  14. sipa force-pushed on Nov 22, 2021
  15. robot-dreams commented at 5:33 pm on November 23, 2021: contributor

    ACK 8ed167b4949898a531a57296b15f749037cc73d0

    • Verified again with independent implementation, hash still matches
    • Build timeout doesn’t seem related to this change; ./configure --with-valgrind=yes; make; make check passed locally

    Edit: My mistake, running make check locally isn’t the way to reproduce what happened in CI

  16. real-or-random commented at 9:41 am on November 24, 2021: contributor
    Hm, the re-run didn’t work. @sipa Can you increase the timeout or decrease TEST_ITERS for the valgrind build?
  17. real-or-random commented at 11:22 am on December 5, 2021: contributor
    @sipa needs trivial rebase :/
  18. sipa force-pushed on Dec 5, 2021
  19. sipa commented at 4:03 pm on December 5, 2021: contributor
    Rebased, but I don’t think the CI failures are related to any change in this PR?
  20. real-or-random commented at 4:48 pm on December 5, 2021: contributor

    @sipa You rebased on the wrong branch.

    https://github.com/sipa/secp256k1/tree/202104_ecmult_bitcomb says “This branch is 1 commit ahead, 158 commits behind bitcoin-core:master.”

  21. Test ecmult functions for all i*2^j for j=0..255 and odd i=1..255. e2cf77328a
  22. ci: reduce TEST_ITERS in memcheck run 5eb519e1f6
  23. sipa force-pushed on Dec 5, 2021
  24. real-or-random approved
  25. real-or-random commented at 8:29 am on December 6, 2021: contributor
    ACK 5eb519e1f60c305e9240946d5773a635192d2a1a
  26. in src/tests.c:4546 in 5eb519e1f6
    4559-    }
    4560-    for (i = 1; i <= 36; i++ ) {
    4561+    secp256k1_sha256 acc;
    4562+    unsigned char b32[32];
    4563+    int i, j;
    4564+    secp256k1_scratch_space *scratch = secp256k1_scratch_space_create(ctx, 65536);
    


    jonasnick commented at 2:18 pm on December 6, 2021:
    nit: thats more than 10 times what’s required for a single point to go into the strauss batch codepath.

    sipa commented at 4:24 pm on December 6, 2021:
    Fair, but I think it’s small enough not to matter.
  27. jonasnick commented at 2:18 pm on December 6, 2021: contributor
    ACK 5eb519e1f60c305e9240946d5773a635192d2a1a
  28. real-or-random merged this on Dec 6, 2021
  29. real-or-random closed this on Dec 6, 2021

  30. sipa referenced this in commit 86dbc4d075 on Dec 15, 2021
  31. sipa cross-referenced this on Dec 15, 2021 from issue Update libsecp256k1 subtree to current master by sipa
  32. sipa cross-referenced this on Dec 23, 2021 from issue Faster fixed-input ecmult tests by sipa
  33. jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick
  34. real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022
  35. real-or-random referenced this in commit 0a40a4861a on Jan 24, 2022
  36. gwillen referenced this in commit 35d6112a72 on May 25, 2022
  37. janus referenced this in commit 879a9a27b9 on Jul 10, 2022
  38. patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022
  39. patricklodder referenced this in commit 03002a9013 on Jul 28, 2022
  40. backpacker69 referenced this in commit 77186f4a04 on Jan 18, 2023
  41. str4d referenced this in commit 6de4698bf9 on Apr 21, 2023
  42. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
  43. vmta referenced this in commit 8f03457eed on Jul 1, 2023

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: 2024-12-22 21:15 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me