Add exhaustive tests for ellswift (with create+decode roundtrip)

theStack commented at 3:14 pm on July 4, 2023: contributor

This PR adds the basic structure for ellswift exhaustive tests. Right now only a secp256k1_ellswift_create + secp256k1_ellswift_decode indirect roundtrip (exhaustive loop scalar -> ellswift pubkey -> decoded pubkey -> decoded group element, compared with exhaustive precomputed group element) is included.

The exhaustive tests passes locally with all currently supported orders (n=13 [default] and n=199). Note that for n=7, the test is skipped, as the used curve in this case is even-ordered and ellswift only supports odd-ordered curves.

sipa commented at 3:57 pm on July 4, 2023: contributor

It certainly doesn’t hurt to add this as a test, but it has significant limitations too which are perhaps worth pointing out in comments.

SwiftEC/ElligatorSwift are inherently curve operations, and not group operations. For secp256k1, the group and the curve are the same thing (ignoring the point at infinity), but for the exhaustive test curves that’s not the case. The test as included here only tests the curve point which are in a tiny subgroup, and in that sense can’t really be seen as exhaustive as it doesn’t (and for computational reasons obviously cannot) test the entire domain ellswift operates under.
The ellswift algorithm does have additional edge cases when operating on curves of even order, which are not included in the code as secp256k1 is of odd order. The n=7 exhaustive group is on an even-ordered curve, which in theory could mean there are some missing cases; these probably just don’t occur because the tested subset of points just doesn’t include any such points.

alokeutpal approved

real-or-random commented at 9:13 pm on July 4, 2023: contributor

I think it’s worth including these restrictions as a comment (now that @sipa spelled them out explicitly).

Concept ACK.

As @sipa says, in terms of code complexity, etc. it probably won’t hurt to add tests. Also, those here should be quick to run.

It’s reasonable to ask if it’s worth our time working on this, but now that the code is already there, why not? :) But not sure either if it makes sense to spend addtional time on secp256k1_ellswift_xdh.

theStack force-pushed on Jul 5, 2023

theStack commented at 0:40 am on July 5, 2023: contributor

@sipa @real-or-random Thanks for the valuable feedback!

Added both (shortened) comments about the limitations. As for the second one, IIUC for the n=7 exhaustive group we are currently just lucky that this passes and it would be cleaner to not run the test for even-order curves at all, as they are not supported. I’ve included skipping to run the test in this case with an additional pre-processor condition. (This is obviously a bit ugly. I though rather than checking for a concrete value, it would be nice if gen_exhaustive_groups.sage could emit another #define that tells whether the a curve is even- or odd-ordered and we could then check on that instead. But that seems to be overkill?)

in src/tests_exhaustive.c:502 in 38a3c5dda8 outdated

493@@ -490,6 +494,15 @@ int main(int argc, char** argv) {
494 #ifdef ENABLE_MODULE_SCHNORRSIG
495         test_exhaustive_schnorrsig(ctx);
496 #endif
497+#ifdef ENABLE_MODULE_ELLSWIFT
498+    /* The ellswift algorithm does have additional edge cases when operating on
499+     * curves of even order, which are not included in the code as secp256k1 is
500+     * of odd order. The n=7 exhaustive group is on an even-ordered curve, so
501+     * skip the tests for it. */
502+    #if EXHAUSTIVE_TEST_ORDER != 7

sipa commented at 1:55 pm on July 5, 2023:

Another test is looking at SECP256K1_B; if it’s 1, 6, or 8, the order is even (for B values <= 8, which we require in some places).

real-or-random commented at 2:47 pm on July 5, 2023:

Indeed, that test is a bit more direct because the curve size depends only on B.

But I’d also be fine with not excluding the n=7 group at all, and just adding a warning in a comment there. (I mean, the passes… ^^)

theStack commented at 4:07 pm on July 5, 2023:

Thanks! Introduced a EXHAUSTIVE_TEST_CURVE_IS_EVEN_ORDERED define (maybe it will be useful for other tests in the future) which is used instead.

theStack force-pushed on Jul 5, 2023

sipa commented at 4:06 pm on July 5, 2023: contributor

ACK f4527f443685730a919d9125c4590b21d4f400f0

real-or-random approved

real-or-random commented at 4:08 pm on July 5, 2023: contributor

ACK f4527f443685730a919d9125c4590b21d4f400f0

in src/tests_exhaustive.c:17 in f4527f4436 outdated

12@@ -13,6 +13,8 @@
13 #define EXHAUSTIVE_TEST_ORDER 13
14 #endif
15 
16+#define EXHAUSTIVE_TEST_CURVE_IS_EVEN_ORDERED (SECP256K1_B == 1 || SECP256K1_B == 6 || SECP256K1_B == 8)

real-or-random commented at 4:12 pm on July 5, 2023:

0/* These values of B are all values in [1, 8] that result in a curve with even order. */ 
1#define EXHAUSTIVE_TEST_CURVE_HAS_EVEN_ORDER (SECP256K1_B == 1 || SECP256K1_B == 6 || SECP256K1_B == 8)

nits: I think adding the [1,8] helps here, and I think _HAS_EVEN_ORDER is more natural language

theStack commented at 4:18 pm on July 5, 2023:

👍 Done.

theStack commented at 4:25 pm on July 5, 2023:

Oops, missed the second part of your recommendation. Agree that _HAS_EVEN_ORDER sounds better than _IS_EVEN_ORDERED. Force-pushed once again.

theStack force-pushed on Jul 5, 2023

real-or-random approved

real-or-random commented at 4:18 pm on July 5, 2023: contributor

utACK 883d64a492d4aec7e2dd0987e0d8300495267e8a

Add exhaustive test for ellswift (create+decode roundtrip)

Co-authored-by: Pieter Wuille <pieter@wuille.net>
Co-authored-by: Tim Ruffing <crypto@timruffing.de>

2792119278

theStack force-pushed on Jul 5, 2023

real-or-random approved

real-or-random commented at 7:25 pm on July 5, 2023: contributor

utACK 2792119278bcb2a0befce3fbc64c83578df54953

real-or-random added the label assurance on Jul 5, 2023

sipa commented at 7:36 pm on July 5, 2023: contributor

utACK 2792119278bcb2a0befce3fbc64c83578df54953

real-or-random merged this on Jul 5, 2023

real-or-random closed this on Jul 5, 2023

theStack deleted the branch on Jul 5, 2023

fanquake referenced this in commit 56c05c5ec4 on Jul 17, 2023

fanquake referenced this in commit ff061fde18 on Jul 18, 2023

hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023

jonasnick cross-referenced this on Jul 27, 2023 from issue Upstream PRs 1357, 1345, 1358, 1368, 1369, 1323, 1364, 1370, 1367, 1344, 1371, 1363, 1340, 1366, 1313, 1378, 1298, 1382, 1383, 1384, 1386 by jonasnick

Add exhaustive tests for ellswift (with create+decode roundtrip) #1371