Add another ecmult

sipa commented at 4:44 pm on December 18, 2021: contributor

Add a large randomized test for ecmult_multi_* functions, which aims to test:

Small and large numbers of (scalar,point) input pairs (from 0 to 128, vaguely exponentially distributed).
Small and large numbers of (scalar,point) input pairs that individually multiply to zero (so scalar=0 or point=infinity), as those are handled specially in wnaf loops.
With final output equal to infinity or not (roughly 50% chance).
With the factor for G equal to 0 or not (roughly 50% chance).
All single-batch algorithms (ecmult_multi_var, as well as ecmult_strauss_single_batch and ecmult_pippenger_single_batch).

I wrote this mostly to gain confidence in the handling of (0,p) or (s,infinity) inputs being changed by #899.

in src/tests.c:4124 in a00ff07f9c outdated

4119+        /* Compute the expected result. */
4120+        CHECK(filled <= 1);
4121+        secp256k1_ecmult(&result, &gejs[0], &scalars[0], &g_scalar);
4122+        mults += filled + g_nonzero;
4123+    }
4124+    /* At this point we have (filled <= 2) and result equals the sum of all (scalars,gejs) pairs. */

jonasnick commented at 9:43 pm on December 19, 2021:

Is (g_scalar, g) part of “all pairs”? If no, it should be mentioned here because it’s included in the result. If yes, then the comment above filled = 0 should mention “excluding g”.

sipa commented at 10:24 pm on December 20, 2021:

Yes, it is. I’ve improved the comments.

in src/tests.c:4102 in a00ff07f9c outdated

4080+                    (int)secp256k1_testrand_bits(1);
4081+    /* Which g_scalar pointer to pass into ecmult_multi(). */
4082+    const secp256k1_scalar* g_scalar_ptr = (g_nonzero || secp256k1_testrand_bits(1)) ? &g_scalar : NULL;
4083+    /* How many scalars/gej pairs have been filled. */
4084+    int filled = 0;
4085+    /* How many EC multiplications were performed in this function. */

jonasnick commented at 9:49 pm on December 19, 2021:

“excluding ecmult_multi” if this is intentional. But it seems like it would be preferable to include ecmult_multi (the nonzero pairs) because multi appears to be a proxy for time and most of the multiplications will happen inside ecmult_multi. Probably worth to add a note on what mults is for exactly.

sipa commented at 10:25 pm on December 20, 2021:

Nice catch. That wasn’t intentional (and also the reason why this test added so much runtime). I’ve fixed it.

jonasnick commented at 9:53 pm on December 19, 2021: contributor

I can’t judge if this helps with coverage of corner cases in #899. But I’ll take a look at that PR.

This new test adds about 16% (7.5 seconds) to my ./tests.

sipa force-pushed on Dec 20, 2021

sipa commented at 10:27 pm on December 20, 2021: contributor

I’ve improved comments, fixed the ecmult count, and now benchmark the added cost of this test at 2% of the total runtime (at iters=64; at iters=1 it should be much lower), running ~1400 instances of it.

sipa commented at 10:46 pm on December 20, 2021: contributor

@jonasnick My goal isn’t increasing test coverage as such, but just having something that tests many scenarios that involve 0*P or a*INF terms in the beginning/end/middle of the list of terms. Just because all lines are hit doesn’t mean those line are correct.

sipa force-pushed on Dec 21, 2021

real-or-random commented at 4:59 pm on December 21, 2021: contributor

This valgrind failure on CI is not a timeout:

0==2989== Conditional jump or move depends on uninitialised value(s)
1==2989==    at 0x468DCD: secp256k1_ecmult_strauss_wnaf (ecmult_impl.h:235)
2==2989==    by 0x43C309: secp256k1_ecmult (ecmult_impl.h:348)
3==2989==    by 0x43C309: test_ecmult_multi_random (tests.c:4137)
4==2989==    by 0x43E7F7: run_ecmult_multi_tests (tests.c:4424)
5==2989==    by 0x465503: main (tests.c:6818)

sipa force-pushed on Dec 21, 2021

sipa commented at 8:45 pm on December 21, 2021: contributor

@real-or-random Fixed.

in src/tests.c:4147 in ba61b18308 outdated

4142+
4143+    /* At this point we have expected = scalar_g*G + sum(scalars[i]*gejs[i] for i=0..filled-1). */
4144+    CHECK(filled <= 1 + !nonzero_result);
4145+    CHECK(filled <= num_nonzero);
4146+
4147+    /* Add entries to sclalars,gejs so that there are num of them. All the added entries

jonasnick commented at 9:29 pm on December 21, 2021:

0    /* Add entries to scalars,gejs so that there are num of them. All the added entries

sipa commented at 9:42 pm on December 21, 2021:

Done.

in src/tests.c:4116 in ba61b18308 outdated

4111+
4112+    if (g_nonzero) {
4113+        /* If g_nonzero, set g_scalar to nonzero value r. */
4114+        random_scalar_order_test(&g_scalar);
4115+        if (!nonzero_result) {
4116+            /* And if 0 expected is desired, add a (a*r, -(1/a)*g) term to compensate. */

jonasnick commented at 9:30 pm on December 21, 2021:

0            /* And if expected=0 is desired, add a (a*r, -(1/a)*g) term to compensate. */

sipa commented at 9:42 pm on December 21, 2021:

Done.

in src/tests.c:4187 in ba61b18308 outdated

4182+            secp256k1_scalar_add(&scalars[j], &scalars[j], &scalars[j+1]);
4183+            secp256k1_gej_neg(&gej, &gejs[j]);
4184+            secp256k1_gej_add_var(&gejs[j+1], &gejs[j+1], &gej, NULL);
4185+        }
4186+        /* Transform the last input: a*P -> (v*a) * ((1/v)*P). */
4187+        if (num_nonzero >= 1) {

jonasnick commented at 9:30 pm on December 21, 2021:

That condition seems to be true always.

sipa commented at 9:42 pm on December 21, 2021:

Changed to an assertion.

jonasnick commented at 9:33 pm on December 21, 2021: contributor

@sipa Sure, I didn’t mean to refer to metrics like line or branch coverage. I have looked at PR #899 enough now to see why this added test is useful. It exercises conditions that can uncover potential bugs in the rewritten loop of commit “Eliminate input_pos state field from ecmult_strauss_wnaf.”. I think both the commit and this PR are worth having.

Can confirm the 2% test time increase. 7% with 256 iters.

ACK mod nits

Add another ecmult_multi test 22d25c8e0a

sipa force-pushed on Dec 21, 2021

sipa commented at 9:44 pm on December 21, 2021: contributor

Idea for a follow-up: when testing ecmult_mult_var, also randomly choose the amount of scratch space, so it’ll exercise splitting into batches.

jonasnick commented at 9:47 pm on December 21, 2021: contributor

ACK 22d25c8e0ab1d24f0f4a80fe016cbd71cd889866

jonasnick merged this on Dec 22, 2021

jonasnick closed this on Dec 22, 2021

jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick

real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022

dhruv referenced this in commit 6f7e395acc on Jan 26, 2022

hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022

dhruv referenced this in commit 139d4b881e on Feb 1, 2022

fanquake referenced this in commit 8f8631d826 on Mar 17, 2022

fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022

fanquake referenced this in commit 465d05253a on Mar 30, 2022

stratospher referenced this in commit 4d5afc9767 on Apr 3, 2022

stratospher referenced this in commit 5b18493cfa on Apr 3, 2022

fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022

gwillen referenced this in commit 35d6112a72 on May 25, 2022

patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022

patricklodder referenced this in commit 03002a9013 on Jul 28, 2022

janus referenced this in commit 3a0652a777 on Aug 4, 2022

str4d referenced this in commit 522190d5c3 on Apr 21, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

Add another ecmult_multi test #1044