Exhaustive test improvements + exhaustive schnorrsig tests

sipa commented at 3:58 am on September 6, 2020: contributor

A few miscellaneous improvements:

Just use EXHAUSTIVE_TEST_ORDER as order everywhere, rather than a variable
Move exhaustive tests for recovery module to the recovery module directory
Make secp256k1_scalar_set_b32 detect overflow correctly for scalar_low (a comment in the recovery exhaustive test indicated why this was the case, but this looks incorrect).
Change the small test groups so that they include a point with X coordinate 1.
Initialize the RNG seed, allowing configurating from the cmdline, and report it.
Permit changing the number of iterations (re-randomizing for each).
Support splitting the work across cores from the cmdline.

And a big one:

Add exhaustive tests for schnorrsig module (and limited ones for extrakeys).

sipa cross-referenced this on Sep 6, 2020 from issue Make group order purely compile-time in exhaustive tests by sipa

jonasnick approved

jonasnick commented at 3:37 pm on September 6, 2020: contributor

ACK 634b3e9024340797b09105533ca63cf35cce427d

I don’t really see the point of removing the order variable - was less strenous to read.

Did you notice the low order scalar_set_b32 issue in the exhaustive schnorrsig tests? I couldn’t find a historic reason for the old comment about the infinite loop but the test clearly show that it’s wrong.

sipa commented at 8:06 pm on September 6, 2020: contributor

I don’t really see the point of removing the order variable - was less strenous to read.

I’m also ok with replacing it with order everywhere, but in the current code it’s a mix, which makes no sense IMO. In theory using a compile-time constant should be faster (modulus operations are very slow for the CPU, but modulus with a known constant can be rewritten using multiply/shift/subtract by the compiler), so I chose that side. I can’t measure a difference in performance though, so it probably doesn’t matter much.

Did you notice the low order scalar_set_b32 issue in the exhaustive schnorrsig tests?

Sort of, I wanted to add a test that uses an out-of-range s value, but expected it would break things with the low-order scalar implementation that ignored overflows. In trying to fix that, I noticed it wasn’t actually necessary in the first place.

sipa commented at 11:52 pm on September 6, 2020: contributor

Added a commit that changes the exhaustive test groups so they include a point with X coordinate 1 (suggested by @gmaxwell).

sipa force-pushed on Sep 7, 2020

gmaxwell commented at 0:49 am on September 7, 2020: contributor

nice, utack

in src/group_impl.h:21 in 27dd2f14f3 outdated

21  *
22- * 0. Setup a worksheet with the following parameters.
23- *   b = 4  # whatever CURVE_B will be set to
24- *   F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
25- *   C = EllipticCurve ([F (0), F (b)])
26+ * They can generated with the following Sage code:

jonasnick commented at 5:12 pm on September 7, 2020:

We have a sage directory, perhaps best to move this over? My first attempt at copy & pasting this messed up indentation.

sipa commented at 9:47 pm on September 7, 2020:

Yeah, done.

in src/group_impl.h:19 in 27dd2f14f3 outdated

15+/* These exhaustive group test orders and generators are chosen such that:
16+ * - The field size is equal to that of secp256k1, so field code is the same.
17+ * - The curve equation is of the form y^2=x^3+B for some constant B.
18+ * - The order is less than 1000 to permit exhaustive testing.
19+ * - The order is a multiple of 3 plus 1, enabling the endomorphism optimization.
20+ * - The generator is 2*P, where P has X coefficient equal to 1.

jonasnick commented at 5:12 pm on September 7, 2020:

coefficient -> coordinate?

sipa commented at 9:47 pm on September 7, 2020:

Done.

jonasnick commented at 5:13 pm on September 7, 2020: contributor

Nice idea to create groups with an X=1 point!

sipa force-pushed on Sep 7, 2020

sipa commented at 1:43 am on September 8, 2020: contributor

I’ve updated https://github.com/sipa/secp256k1/commits/202009_schnorrsig_exhaustive to build on this, including tests with signatures that have R.x=(fieldsize+1). It now catches removing the check on the return value of secp256k1_fe_set_b32(&rx, &sig64[0]).

in src/group_impl.h:24 in aa48ca9c5b outdated

43- *   print "%x %x" % P.xy()
44+ * They can generated using the Sage code in sage/gen_exhaustive_groups.sage.
45  */
46 #if defined(EXHAUSTIVE_TEST_ORDER)
47-#  if EXHAUSTIVE_TEST_ORDER == 199
48+#  if EXHAUSTIVE_TEST_ORDER == 13

real-or-random commented at 11:16 am on September 8, 2020:

Shouldn’t EXHAUSTIVE_TEST_LAMBDA chosen by these #ifs too?

sipa commented at 7:49 pm on September 8, 2020:

They’re needed in scalar, which is independent from the group “module”. Otherwise, done: I’ve added ifdefs there to pick the correct one automatically.

in src/group_impl.h:35 in aa48ca9c5b outdated

61-#  elif EXHAUSTIVE_TEST_ORDER == 13
62+static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(
63+    0x3d3486b2, 0x159a9ca5, 0xc75638be, 0xb23a69bc,
64+    0x946a45ab, 0x24801247, 0xb4ed2b8e, 0x26b6a417
65+);
66+#  elif EXHAUSTIVE_TEST_ORDER == 199

real-or-random commented at 11:16 am on September 8, 2020:

And have you tried running this with 199? Seems to take forever.

jonasnick commented at 3:56 pm on September 8, 2020:

I tried it on my laptop over night but terminated it the next morning.

sipa commented at 4:08 pm on September 8, 2020:

I tested an earlier version of the extrakeys/schnorr exhaustive tests. The generic group and ECDSA ones are too slow with 199 (they include quintuple nested loops; the schnorr tests are only quartic).

real-or-random approved

real-or-random commented at 11:18 am on September 8, 2020: contributor

ACK aa48ca9c5b91f570eb2cb52636cd590eccea5de4 careful code inspection

My two comments are strictly speaking not this PR. If these are real issues, I guess you could address them here or in another PR, either is fine.

in sage/gen_exhaustive_groups.sage:59 in aa48ca9c5b outdated

54+                continue
55+            rb = b*m^3
56+            RE = EllipticCurve(F, [0, rb])
57+
58+            # Use as generator twice the point with this low X coordinate (like secp256k1!)
59+            RG = RE.lift_x(1) * 2

jonasnick commented at 5:15 pm on September 8, 2020:

Why does RG have the same order as G?

sipa commented at 5:19 pm on September 8, 2020:

It’s the image of G under the isomorphism described in the comments. I can make it more explicit by computing it directly instead of re-lifting from 1.

sipa commented at 7:50 pm on September 8, 2020:

Done.

jonasnick commented at 3:27 pm on September 9, 2020:

Oh I see now. You’re specifically checking that m is square, i.e., that a exists.

jonasnick commented at 3:43 pm on September 12, 2020:

The new script output makes running this quite exciting!

jonasnick approved

jonasnick commented at 5:18 pm on September 8, 2020: contributor

ACK aa48ca9c5b91f570eb2cb52636cd590eccea5de4

sipa force-pushed on Sep 8, 2020

in src/scalar_impl.h:263 in c124528a43 outdated

258+#    define EXHAUSTIVE_TEST_LAMBDA 9
259+#  elif EXHAUSTIVE_TEST_ORDER == 199
260+#    define EXHAUSTIVE_TEST_LAMBDA 92
261+#  else
262+#    error No known lambda for the specified exhaustive test group order.
263+#endif

real-or-random commented at 11:35 pm on September 8, 2020:

nit: indentation.

No lambda for order 7?

sipa commented at 11:45 pm on September 8, 2020:

I just pushed another update.

The order 7 subgroup in fact does not have the endomorphism property (apparently all subgroups do, except the order 2, 3, and 7 ones).

real-or-random commented at 0:52 am on September 9, 2020:

Ok I see.

Can you fix the #endif indentation?

sipa commented at 1:13 am on September 9, 2020:

It’s already fixed, I think?

sipa commented at 1:38 am on September 9, 2020:

Oh, it was fixed in a later commit only. Really fixed now.

real-or-random commented at 8:35 am on September 9, 2020:

Oh sorry, I thought I looked in the later commits too. For some reason I missed it there.

sipa commented at 11:47 pm on September 8, 2020: contributor

I made another change, making the exhaustive tests correctly initialize the RNG, and adding a way to split the workload (invoke with ./exhaustive_tests 1 "" 8 0 on CPU 0, ./exhaustive_tests 1 "" 8 1 on CPU 1, etc).

I’m done expanding the scope of this PR now. If this is too much I’m happy to split stuff off.

sipa force-pushed on Sep 9, 2020

real-or-random commented at 8:53 am on September 9, 2020: contributor

Valgrind fails on Travis: https://travis-ci.org/github/bitcoin-core/secp256k1/jobs/725488761#L573

I made another change, making the exhaustive tests correctly initialize the RNG, and adding a way to split the workload (invoke with ./exhaustive_tests 1 "" 8 0 on CPU 0, ./exhaustive_tests 1 "" 8 1 on CPU 1, etc).

Really invoke the seed with "" ? Doesn’t every instance get a different random seed then?

I’m done expanding the scope of this PR now. If this is too much I’m happy to split stuff off.

I think that’s ok.

in src/tests_exhaustive.c:378 in 8c5dfdf576 outdated

468-                    secp256k1_pubkey_save(&pk, &nonconst_ge);
469-                    CHECK(should_verify ==
470-                          secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk));
471-                }
472-            }
473+    printf("test count = %i\n", count);

real-or-random commented at 9:03 am on September 9, 2020:

This is where valgrind on MacOS complains about uninit data.

This is spurious, see https://stackoverflow.com/questions/29312335/valgrind-on-os-x-yosemite-giving-bogus-errors … @elichai Do you think we can update to MacOS 10.13 ? According to homebrew, valgrind supports this now.

real-or-random commented at 9:16 am on September 9, 2020:

Ah no, we’re at 10.13 already… Upstream bug: https://bugs.kde.org/show_bug.cgi?id=399584 There they mention https://github.com/LouisBrunner/valgrind-macos as an alternative tap. Do you think it’s worth trying?

elichai commented at 11:26 am on September 9, 2020:

We can try, idk how much will we trust it though (if someone is bored enough, he can go over their patches hehe https://github.com/LouisBrunner/valgrind-macos/commits/patches)

sipa commented at 1:01 am on September 10, 2020:

Anyone have a clue why the tests binary doesn’t have the exact same problem?

real-or-random commented at 10:38 am on September 10, 2020:

I was wondering about this, too. The compile/link options seem to be the same. Now that I looked at the two files again, my best guess is https://github.com/bitcoin-core/secp256k1/blob/master/src/tests.c#L5529

sipa commented at 8:06 pm on September 10, 2020:

Seems that fixed it.

gmaxwell commented at 10:44 am on September 9, 2020: contributor

I don’t think exhaustive_tests should be actually random. There is a need for ‘random’ values, but I don’t see a lot of gain in having every run use different ones… and they make reproducing issues harder. Is there a reason to not just give it a constant seed?

sipa commented at 6:42 pm on September 9, 2020: contributor

Really invoke the seed with "" ? Doesn’t every instance get a different random seed then?

Yes, for the random part. You can also specify a fixed seed by passing a non-empty hex string.

I don’t think exhaustive_tests should be actually random. There is a need for ‘random’ values, but I don’t see a lot of gain in having every run use different ones… and they make reproducing issues harder. Is there a reason to not just give it a constant seed?

Unsure.

At least the gej tests are explicitly rescaled with a random z in every run, and unfortunately, those cannot be selected from an tractably-sized set for exhaustive tests.

The main thing these tests hope to reveal shouldn’t be dependent on the choice of the seed, though, so perhaps it’s ok to just pick a fixed seed. If so, we can probably also do without the iteration count.

real-or-random commented at 10:25 pm on September 9, 2020: contributor

Really invoke the seed with "" ? Doesn’t every instance get a different random seed then?

Yes, for the random part. You can also specify a fixed seed by passing a non-empty hex string.

Ok, yes. I somehow wrongly assumed that the randomness affects the mapping of work to CPUs, but it does not of course.

I don’t think exhaustive_tests should be actually random. There is a need for ‘random’ values, but I don’t see a lot of gain in having every run use different ones… and they make reproducing issues harder. Is there a reason to not just give it a constant seed?

Unsure.

At least the gej tests are explicitly rescaled with a random z in every run, and unfortunately, those cannot be selected from an tractably-sized set for exhaustive tests.

The main thing these tests hope to reveal shouldn’t be dependent on the choice of the seed, though, so perhaps it’s ok to just pick a fixed seed. If so, we can probably also do without the iteration count.

“Unsure” was my first thought, too. Yes, the main thing here does not depend of on the choice of the seed but I still believe that randomness helps more than it hurts here. For example, it could detect a bug that occurs as a combination of special coordinate value 1 and some z value that we hit with probability 1/10000. This could be missed by the normal tests, even though they’re randomized.

gmaxwell commented at 10:37 pm on September 9, 2020: contributor

I suppose it doesn’t hurt. If a user reports a bug that only happens with some particular seeds and they fail to provide their seed– well that’s a bug which wouldn’t have otherwise been detected at all.

Just please no “expected failures”, the situation in CI (common in bitcoin core but has happened here too) where people are responding to failures by retrying the CI rather than treating the failure as an emergency is a dangerous practice.

sipa force-pushed on Sep 9, 2020

sipa commented at 8:09 pm on September 10, 2020: contributor

Adding setbuf(stdout, NULL); seems to have fixed it…

sipa cross-referenced this on Sep 11, 2020 from issue Avoid overly-wide multiplications in 5x52 field mul/sqr by peterdettman

real-or-random approved

real-or-random commented at 11:39 am on September 11, 2020: contributor

ACK dd29d2ef298e92e9bae0bf35b269fb38dd79b23f code review and tests pass

sipa force-pushed on Sep 12, 2020

sipa renamed this:
~~Exhaustive test improvements~~
Exhaustive test improvements + exhaustive schnorrsig tests
on Sep 12, 2020

sipa commented at 2:59 am on September 12, 2020: contributor

Rebased on the now-merged #558, and added exhaustive tests for schnorrsig module too.

in src/modules/schnorrsig/tests_exhaustive_impl.h:92 in 9737f95773 outdated

87+        for (k = 1; k <= EXHAUSTIVE_TEST_ORDER / 2 + NUM_INVALID_KEYS; ++k) {
88+            unsigned char sig64[64];
89+            int actual_k = -1;
90+            int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
91+            int e_count_done = 0;
92+            if (skip_section(iter++)) continue;

jonasnick commented at 2:16 pm on September 12, 2020:

skip_section takes a pointer, same in schnorrsig_sign

sipa commented at 6:28 pm on September 12, 2020:

Fixed.

in src/modules/schnorrsig/tests_exhaustive_impl.h:205 in 9737f95773 outdated

200+        CHECK(secp256k1_xonly_pubkey_serialize(ctx, xonly_pubkey_bytes[i - 1], &xonly_pubkey[i - 1]));
201+    }
202+
203+    /* The keypairs/pubkey functions above have already been tested agains the group;
204+       see src/modules/extrakeys/tests_exhaustive_impl.h. */
205+    (void)group;

jonasnick commented at 3:42 pm on September 12, 2020:

why not just remove this argument?

sipa commented at 6:30 pm on September 12, 2020:

Yeah, done.

I wanted to keep the same “interface” for all exhaustive tests that are delegated to modules, but that’s easy to add if we’d a lot more modules too.

jonasnick commented at 3:44 pm on September 12, 2020: contributor

Nice! LGTM mod nits

sipa force-pushed on Sep 12, 2020

sipa force-pushed on Sep 13, 2020

in src/tests_exhaustive.c:386 in 4ecde861d4 outdated

501+    /* set up split processing */
502+    if (argc > 4) {
503+        num_cores = strtol(argv[3], NULL, 0);
504+        this_core = strtol(argv[4], NULL, 0);
505+        if (num_cores < 1 || this_core >= num_cores) {
506+            fprintf(stderr, "Usage: %s [count] [seed] [numcores] [thiscore]", argv[0]);

gmaxwell commented at 7:18 pm on September 13, 2020:

needs a \n at the end.

sipa commented at 7:22 pm on September 13, 2020:

Fixed.

sipa force-pushed on Sep 13, 2020

in src/tests_exhaustive.c:389 in b6f299ee1a outdated

504+        this_core = strtol(argv[4], NULL, 0);
505+        if (num_cores < 1 || this_core >= num_cores) {
506+            fprintf(stderr, "Usage: %s [count] [seed] [numcores] [thiscore]\n", argv[0]);
507+            return 1;
508+        }
509+        printf("running tests for core %lu out of %lu\n", (unsigned long)this_core, (unsigned long)num_cores);

gmaxwell commented at 7:30 pm on September 13, 2020:

running tests for core 255 out of 256 doesn’t sound quite right, makes it sound like you’re missing one when you’re not because its zero indexed. I’m not instantly seeing how to better rephrase that, however.

sipa commented at 9:16 pm on September 18, 2020:

I’ve changed it to core 255 (out of [0..255]). Does that seem better?

gmaxwell commented at 9:51 pm on September 18, 2020:

Seems fine to me!

in src/tests_exhaustive.c:378 in b6f299ee1a outdated

491+
492+    /* find iteration count */
493+    if (argc > 1) {
494+        count = strtol(argv[1], NULL, 0);
495+    }
496+    printf("test count = %i\n", count);

gmaxwell commented at 8:04 pm on September 13, 2020:

The output should print the order somewhere.

sipa commented at 9:16 pm on September 18, 2020:

Done.

in src/group.h:141 in 3acadb107a outdated

137@@ -138,4 +138,7 @@ static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_g
138 /** Rescale a jacobian point by b which must be non-zero. Constant-time. */
139 static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b);
140 
141+/** Determine if a point (which is assumed to be on the curve) is in the group. */

real-or-random commented at 9:21 pm on September 13, 2020:

I think “is in group” is somewhat imprecise (which group?), even for readers who know about exhaustive tests. And others may really wonder what the point of this function is.

The same is true for the name of the function. When I saw this, I first assumed it checks if the input is really on the point.

sipa commented at 9:46 pm on September 13, 2020:

Added some comments. WDYT?

real-or-random commented at 9:18 am on September 16, 2020:

Yes, looks good! Now that you got a few more comments, I still think the function name can be improved. I don’t have a great suggestion but something like ge_is_in_correct_subgroup, ge_is_in_subgroup would already make clear that this function is not about being on the curve or not. Note also the “is”, I think that’s more consistent with other names like is_infinity and makes clear that this is a getter.

sipa commented at 9:16 pm on September 18, 2020:

Done.

sipa force-pushed on Sep 13, 2020

jonasnick approved

jonasnick commented at 5:24 pm on September 15, 2020: contributor

ACK 76ac2bf214cd6a272176e90b98c84d34fe440f18

in src/testrand_impl.h:115 in 76ac2bf214 outdated

111@@ -111,4 +112,47 @@ static void secp256k1_rand_flip(unsigned char *b, size_t len) {
112     b[secp256k1_rand_int(len)] ^= (1 << secp256k1_rand_int(8));
113 }
114 
115+static void secp256k1_rand_init(const char* hexseed) {

gmaxwell commented at 6:19 pm on September 15, 2020:

Maybe the function name also should get a “test” or “insecure” in it, before someone sees this function and thinks that the software will use insecure randomness for private keys (or someone generating a private key thinks they can use this function).

sipa commented at 9:15 pm on September 18, 2020:

You’re right, but that’s not specific to that function. It’s in a file called testrand - should all functions in it be renamed to have test in the name?

gmaxwell commented at 9:53 pm on September 18, 2020:

That wouldn’t be bad. Mostly I raised this one becuase I thought it was likely to come to someone’s attention if they searched the codebase for ‘random’, and in isolation it looks kind of bad! :) (and was probably somewhat less of an issue previously when it was in tests.c’s main, so it was clear that it wasn’t being used anywhere else)

sipa commented at 3:51 am on September 26, 2020:

Done in a separate PR: https://github.com/bitcoin-core/secp256k1/pull/827

gmaxwell commented at 10:49 am on September 16, 2020: contributor

I ran this for 199 without and with endo across 256 cores. Each process completed within +/-0.3% of the others. Total CPU time was 292 CPU-days (for each configuration), as expected– it passed.

Make group order purely compile-time in exhaustive tests be31791543

Move exhaustive tests for recovery to module c498366e5b

Make secp256k1_scalar_b32 detect overflow in scalar_low 8bcd78cd79

Delete gej_is_valid_var: unused outside tests d7f39ae4b6

Make the curve B constant a secp256k1_fe 78f6cdfaae

Select exhaustive lambda in function of order cec7b18a34

Change exhaustive test groups so they have a point with X=1

This enables testing overflow is correctly encoded in the recid, and
likely triggers more edge cases.

Also introduce a Sage script to generate the parameters.

b110c106fa

refactor: move RNG seeding to testrand 49e6630bca

Give exhaustive_tests count and seed cmdline inputs e99b26fcd5

Support splitting exhaustive tests across cores 39f67dd072

Disable output buffering in tests_exhaustive.c 63e1b2aa7d

Abstract out challenge computation in schnorrsig 87af00b511

Make pubkey parsing test whether points are in the correct subgroup 08d7d89299

Add exhaustive test for extrakeys and schnorrsig 8b7dcdd955

sipa force-pushed on Sep 18, 2020

jonasnick approved

jonasnick commented at 7:41 am on September 24, 2020: contributor

ACK 8b7dcdd955a4f57174f478e36bdae5b84784fb9c

real-or-random commented at 8:26 am on September 24, 2020: contributor

ACK 8b7dcdd955a4f57174f478e36bdae5b84784fb9c

sipa merged this on Sep 26, 2020

sipa closed this on Sep 26, 2020

sipa cross-referenced this on Sep 26, 2020 from issue Rename testrand functions to have test in name by sipa

real-or-random referenced this in commit 63150ab4da on Sep 27, 2020

deadalnix referenced this in commit e01389c3ea on Sep 29, 2020

deadalnix referenced this in commit a7206a83a7 on Sep 29, 2020

deadalnix referenced this in commit ef5bb90888 on Sep 29, 2020

jasonbcox referenced this in commit af04b3dd3b on Sep 29, 2020

jasonbcox referenced this in commit 14b9df3262 on Sep 29, 2020

jasonbcox referenced this in commit 2657986ae0 on Sep 29, 2020

jasonbcox referenced this in commit 4d157a3251 on Sep 29, 2020

jasonbcox referenced this in commit b65e9ad734 on Sep 29, 2020

jasonbcox referenced this in commit 6a316e94bd on Sep 29, 2020

jasonbcox referenced this in commit 0029010ce8 on Sep 29, 2020

jasonbcox referenced this in commit 6ee6cc93fe on Sep 29, 2020

jasonbcox referenced this in commit 175e3ee20f on Sep 29, 2020

jasonbcox referenced this in commit c7ed0bca26 on Sep 29, 2020

jasonbcox referenced this in commit a9d47b1da0 on Sep 29, 2020

deadalnix referenced this in commit 7ccac17d2e on Sep 30, 2020

deadalnix referenced this in commit 4d46e3f558 on Sep 30, 2020

deadalnix referenced this in commit 4b98dde776 on Sep 30, 2020

deadalnix referenced this in commit 52b55a985c on Sep 30, 2020

deadalnix referenced this in commit c927b9b030 on Sep 30, 2020

deadalnix referenced this in commit bc83900e93 on Sep 30, 2020

deadalnix referenced this in commit b059413880 on Sep 30, 2020

deadalnix referenced this in commit 169b01ca41 on Sep 30, 2020

deadalnix referenced this in commit f9f6163d70 on Sep 30, 2020

deadalnix referenced this in commit b579ff6900 on Sep 30, 2020

deadalnix referenced this in commit 2a3941a509 on Sep 30, 2020

deadalnix referenced this in commit e803744500 on Sep 30, 2020

deadalnix referenced this in commit c1685a7a14 on Sep 30, 2020

deadalnix referenced this in commit 8e82a43f7e on Sep 30, 2020

Exhaustive test improvements + exhaustive schnorrsig tests #808