ElligatorSwift + integrated x-only DH

sipa commented at 10:21 pm on July 21, 2022: contributor

Builds on top of #979, #1118. Replaces #982.

This implements encoding of curve points using the ElligatorSwift algorithm, using 4 new API calls:

secp256k1_ellswift_encode, which converts a public key to a 64-byte pseudorandom encoding.
secp256k1_ellswift_decode, the reverse operation to convert back to normal public keys.
secp256k1_ellswift_create, which can be seen as a combination of secp256k1_ec_pubkey_create + secp256k1_ellswift_encode, but is somewhat safer.
secp256k1_ellswift_xdh, which implements x-only Diffie-Hellman directly on top of 64-byte encoded public keys, and more efficiently than decoding + invoking normal ECDH.

The scheme matches that of the SwiftEC paper (https://eprint.iacr.org/2022/759), with two changes (remapping undefined inputs, and encoding the Y parity in the u/t values themselves rather than in a separate bit). To decode an ElligatorSwift 64-byte encoded public key:

Interpret the encoding as two field elements $(u, t)$ in big-endian 32-byte encoding each, reducing modulo $p$.
If $u=0$, let $u=1$ instead.
If $t=0$, let $t=1$ instead.
If $u^3 + 7 + t^2 = 0$, let $t = 2t$ instead.
Let $X = \dfrac{u^3 + 7 - t^2}{2t}$.
Let $Y = \dfrac{X + t}{\sqrt{-3}u}$.
Let $x$ be the first of $(u + 4Y^2, \dfrac{-X}{2Y} - \dfrac{u}{2}, \dfrac{X}{2Y} - \dfrac{u}{2})$ which is on the curve (at least one will be).
Let $y$ be the corresponding Y coordinate, with the same parity as (the original) $t$.
Return $(x,y)$.

This is significantly faster than the Elligator Squared code in #982.

Relevant benchmark (AMD Ryzen 5950X, GCC 12.2.0, default config options; frequency fixed at 2.80 GHz):

0Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)    
1
2ec_keygen                     ,    27.9       ,    28.0       ,    28.0    
3ecdh                          ,    53.9       ,    53.9       ,    54.0    
4ellswift_encode               ,    24.5       ,    24.5       ,    24.6    
5ellswift_decode               ,    11.1       ,    11.1       ,    11.1    
6ellswift_keygen               ,    52.5       ,    52.5       ,    52.6    
7ellswift_ecdh                 ,    57.9       ,    58.0       ,    58.0

in .cirrus.yml:255 in 34227ad260 outdated

275@@ -271,6 +276,8 @@ task:
276     RECOVERY: yes
277     EXPERIMENTAL: yes
278     SCHNORRSIG: yes
279+    ELLSWIFT: yes
280+    ELLSWIFT: yes

real-or-random commented at 8:12 am on July 22, 2022:

duplicate line

sipa commented at 9:08 pm on November 4, 2022:

Fixed.

in src/modinv64_impl.h:703 in 34227ad260 outdated

698+     * In VERIFY mode use a lower number of iterations (744, close to the median 756), so failure actually occurs. */
699+#ifdef VERIFY
700+    for (count = 0; count < 12; ++count) {
701+#else
702+    for (count = 0; count < 25; ++count) {
703+#endif

real-or-random commented at 8:18 am on July 22, 2022:

Maybe introduce a constant for the max count? having unmatched { or } in #ifdef is hard to read and confuses editors.

sipa commented at 9:44 pm on November 4, 2022:

Done in #979.

real-or-random commented at 8:28 am on July 22, 2022: contributor

(just skimming)

Do you think there’s a nice way to avoid code duplication between divsteps and posdivsteps?

sipa commented at 12:54 pm on July 22, 2022: contributor

@real-or-random Re posdivsteps see #979 which this PR is based on.

dhruv cross-referenced this on Jul 22, 2022 from issue BIP324: CKey encode/decode to elligator-swift by dhruv

dhruv cross-referenced this on Jul 22, 2022 from issue BIP324: Handshake prerequisites by dhruv

paulmillr commented at 7:32 pm on July 26, 2022: contributor

Looks awesome! Wanted to clarify this bit, for implementors of EllSwift in other languages / for standardization purpose.

Inputs (u,t) where u=0, t=0, or u^2+t^3+7=0, are remapped to other finite points, rather than outputting infinity.

To which points exactly? It’s not immediately obvious from the code.

sipa commented at 7:35 pm on July 26, 2022: contributor

@paulmillr They are remapped as follows:

If $t=0$, set $t=1$ instead
If $u=0$, set $u=1$ instead
If $u^2+t^3+B=0$, set $t=2t$ instead
Run the normal algorithm

(for applicable odd-ordered curves with A=0, this covers all otherwise unmapped points, but this remapping doesn’t work for every ellswift-compatible curve).

in include/secp256k1_ellswift.h:143 in 34227ad260 outdated

143+ *  Returns: 1: shared secret was succesfully computed
144+ *           0: secret was invalid or hashfp returned 0
145+ *  Args:    ctx:        pointer to a context object.
146+ *  Out:     output:     pointer to an array to be filled by hashfp.
147+ *  In:      theirs64:   a pointer to the 64-byte ElligatorSquare public key received from the other party.
148+ *           ours64:     a pointer to the 64-byte ElligatorSquare public key sent to the other party.

stratospher commented at 2:46 pm on July 28, 2022:

s/ElligatorSquare/ElligatorSwift in theirs64 and ours64?

sipa commented at 9:45 pm on November 4, 2022:

Done.

dhruv cross-referenced this on Sep 12, 2022 from issue #23432 bip324-ellsq by dhruv

dhruv cross-referenced this on Sep 12, 2022 from issue #23561 bip324-handshake by dhruv

sipa force-pushed on Sep 16, 2022

stratospher cross-referenced this on Oct 3, 2022 from issue test: add python implementation of Elligator swift by stratospher

sipa force-pushed on Oct 5, 2022

sipa commented at 6:49 pm on October 5, 2022: contributor

Added test vectors.

sipa force-pushed on Nov 1, 2022

sipa force-pushed on Nov 2, 2022

sipa force-pushed on Nov 3, 2022

sipa force-pushed on Nov 4, 2022

sipa commented at 1:06 am on November 5, 2022: contributor

I’ve made a number of improvements:

Addressed comments so far
Added test vectors that are verified against the paper author’s Sage code (https://github.com/Jchavezsaab/SwiftEC).
Documented the algorithms line-by-line
Renamed functions to better match the paper’s names.
Split up the commits
A few small performance optimizations
Factored out helper functions for checking if an X coordinate is on the curve (directly, and when given as a fraction).

I think it’s ready for more review.

sipa force-pushed on Nov 5, 2022

sipa force-pushed on Nov 12, 2022

sipa force-pushed on Nov 14, 2022

dhruv cross-referenced this on Nov 18, 2022 from issue BIP324: Enable v2 P2P encrypted transport by dhruv

sipa force-pushed on Dec 12, 2022

sipa commented at 6:09 pm on December 12, 2022: contributor

Rebased on updated #979.

sipa force-pushed on Dec 23, 2022

sipa commented at 7:55 pm on December 23, 2022: contributor

Added an explanation of the algorithm and its relation to the paper, in doc/ellswift.md. I’ve also changed some of the code to better match the algorithm as described in that document (I found some simplifications while writing it).

sipa force-pushed on Dec 23, 2022

sipa force-pushed on Dec 27, 2022

sipa force-pushed on Dec 28, 2022

sipa force-pushed on Jan 26, 2023

sipa force-pushed on Mar 1, 2023

sipa cross-referenced this on Mar 1, 2023 from issue Add secp256k1_fe_add_int function by sipa

sipa force-pushed on Mar 7, 2023

sipa commented at 2:41 pm on March 7, 2023: contributor

Rebased on #1217, making use of the new secp256k1_fe_add_int.

sipa force-pushed on Apr 10, 2023

sipa commented at 11:24 am on April 10, 2023: contributor

Rebased after merge of #1118, also consistently applying the convention from #1252.

real-or-random added this to the milestone 0.3.2 (or 0.4.0) on Apr 10, 2023

sipa force-pushed on Apr 17, 2023

sipa commented at 1:47 pm on April 17, 2023: contributor

Rebased, and added to CMakeLists.txt.

sipa cross-referenced this on Apr 17, 2023 from issue BIP324: ElligatorSwift integrations by sipa

in src/modules/ellswift/main_impl.h:125 in 54fff1ddc5 outdated

120+        *xn = n;
121+        return;
122+    }
123+    secp256k1_fe_mul(&l, &p, &u1); /* l = u*(g+s) */
124+    secp256k1_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*g*s */
125+    secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)+u*g*s */

jonasnick commented at 12:57 pm on April 23, 2023:

0    secp256k1_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*(g+s) */
1    secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)+u*(g+s) */

sipa commented at 8:46 am on April 27, 2023:

Done.

in src/modules/ellswift/tests_impl.h:402 in 54fff1ddc5 outdated

284+        CHECK(ret);
285+        CHECK(secp256k1_memcmp_var(share32a, share32b, 32) != 0);
286+        secp256k1_testrand_flip(sec32a, 32);
287+        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32b, NULL, NULL);
288+        CHECK(!ret || secp256k1_memcmp_var(share32a, share32b, 32) != 0);
289+    }

jonasnick commented at 7:34 pm on April 23, 2023:

sec32a isn’t used after being flipped. Also, the second memcmp doesn’t really seem to increase test coverage, since ell64a has already been flipped. We would want to use the unchanged ell64a in the second xdh call to check ir changing sec64b results in a different share.

sipa commented at 8:46 am on April 27, 2023:

Indeed. I think my intent was to apply the flipping to the other side. I’ve done that now.

jonasnick commented at 4:31 pm on May 3, 2023:

I don’t think the last test adds any real test coverage since ell64a was already flipped, so of course share32a will be unequal to share32b. What we could do is let the last _xdh write into share32b instead of share32a. Then we’ve isolated the flipping of sec32a.

sipa commented at 8:18 am on May 4, 2023:

Good point, done.

in src/modules/ellswift/main_impl.h:499 in 54fff1ddc5 outdated

420+    secp256k1_ellswift_swiftec_var(&p, &u, &t);
421+    secp256k1_pubkey_save(pubkey, &p);
422+    return 1;
423+}
424+
425+static int ellswift_xdh_hash_function_sha256(unsigned char *output, const unsigned char *x32, const unsigned char *ours64, const unsigned char *theirs64, void *data) {

jonasnick commented at 7:41 pm on April 23, 2023:

It looks like this default hasher is incompatible with the reference implementation’s in BIP 324. It uses a tagged hash and does not sort. Is this intentional? If not, would it make sense to add static test vectors for XDH?

sipa commented at 9:30 am on April 26, 2023:

It’s not compatible indeed, because the BIP324 hasher uses BIP340 tag “bip324_ellswift_xonly_ecdh”. For the module I wanted something more generic, so used this simpler default.

If we keep that, we should indeed have some tests covering this exact hasher too.

Alternatives are:

Not having any pre-implemented hashers (and no default, so always requiring the fn pointer).
Implementing the BIP324 hasher in this module (but maybe not as the only implemented hasher, as otherwise other prospective other protocols may be encouraged to use that one too).
Have both a generic hasher and a BIP324 hasher.

The sorting step makes the interface a bit simpler, as the hasher doesn’t need to be aware of which side is who, and I see now downside to it. However, in BIP324 we chose not to do that.

Opinions welcome.

jonasnick commented at 2:07 pm on April 26, 2023:

I didn’t consider that you don’t want people to reuse the BIP 324 hasher for domain separation reasons. In that case it makes sense to have both (and add the BIP 324 hasher including XDH test vectors in a separate PR).

However, the existing default hasher does not solve the domain separation problem. Maybe we could change the hasher to not ignore data and encourage callers to use this for domain separation?

sipa commented at 8:48 am on April 27, 2023:

Good point. Providing a default hasher that supports some degree of domain separation may be useful. We should discuss this more.

sipa commented at 7:14 pm on May 6, 2023:

I think this is addressed now: #1129 (review)

in include/secp256k1_ellswift.h:11 in 54fff1ddc5 outdated

 6+#ifdef __cplusplus
 7+extern "C" {
 8+#endif
 9+
10+/* This module provides an implementation of ElligatorSwift as well as
11+ * a version of x-only ECDH using it.

jonasnick commented at 7:42 pm on April 23, 2023:

nit: maybe mention compatibility with BIP 324 here (if it is compatible)

sipa commented at 8:48 am on April 27, 2023:

Sounds reasonable, but punting on this until the default hasher / BIP324 hasher issue is resolved.

jonasnick commented at 10:17 am on May 9, 2023:

Could mention now that it’s compatible with BIP 324 if the BIP 324 hasher is used.

sipa commented at 1:58 pm on May 10, 2023:

Done.

in src/modules/ellswift/tests_impl.h:35 in 54fff1ddc5 outdated

22+    int odd_y;
23+};
24+
25+/* Set of (point, encodings) test vectors, selected to maximize branch coverage.
26+ * Created using an independent implementation, and tested against paper author's code. */
27+static const struct ellswift_xswiftec_inv_test ellswift_xswiftec_inv_tests[] = {

jonasnick commented at 7:43 pm on April 23, 2023:

nit: mention that these static test vectors are from BIP 324

sipa commented at 8:48 am on April 27, 2023:

Done.

in src/modules/ellswift/main_impl.h:55 in 54fff1ddc5 outdated

50+     *
51+     * - ...
52+     * - If g+s=0, set s=4*s
53+     * - If x3=u-(g+s)^2/(3*s*u^2) is a valid x coordinate, return it.
54+     * - If x2=(-c0*u*(g-s)/(g+s)-u)/2 is a valid x coordinate, return it.
55+     * - Return x1=(c0*u*(g-s)/(g+s)-u)/2.

jonasnick commented at 7:44 pm on April 23, 2023:

nit: Afaict we don’t use this equation for x1. So we could just continue to write x1=-(x2+u).

sipa commented at 8:48 am on April 27, 2023:

Right, done.

in src/bench.c:276 in 54fff1ddc5 outdated

247@@ -225,5 +248,10 @@ int main(int argc, char** argv) {
248     run_schnorrsig_bench(iters, argc, argv);
249 #endif
250 
251+#ifdef ENABLE_MODULE_ELLSWIFT
252+    /* ElligatorSwift benchmarks */
253+    run_ellswift_bench(iters, argc, argv);
254+#endif

jonasnick commented at 7:47 pm on April 23, 2023:

The bench help text misses the ellswift module.

sipa commented at 8:49 am on April 27, 2023:

Fixed.

jonasnick commented at 6:10 pm on May 3, 2023:

It looks like the bench help still misses the ellswift module (see void help(...) at the start of bench.c)

sipa commented at 8:50 am on May 4, 2023:

Oh! I had added help text for the case where one of the ellswift keywords was provided without the module being compiled in, but not the normal help text. Done now (also for the ec_keygen bench from the first commit).

in src/modules/ellswift/main_impl.h:210 in 54fff1ddc5 outdated

205+        secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */
206+        secp256k1_fe_mul(&m, &s, &g); /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */
207+        if (!secp256k1_fe_is_square_var(&m)) return 0;
208+
209+        /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [second part] */
210+        secp256k1_fe_inv_var(&s, &s); /* s = -1/(u^2 + u*x + x^2) */

jonasnick commented at 7:56 pm on April 23, 2023:

It seems like (u^2 + u*x + x^2) can be 0. Should we VERIFY_CHECK this or do we assume u to be uniformly random (if so, we may want to mention this in the function doc)?

sipa commented at 11:49 am on April 25, 2023:

This is not possible, because if $u^2 + ux + x^2 = 0$, then $m = -(u^3 + 7)(u^2 + ux + x^2) = 0$ as well, and the secp256k1_fe_is_square_var(&m) check above would have failed.

I believe there is a more fundamental reason too; in the more abstract scheme this division by zero can only occur when the curve has a point for which $g(x) = 0$ (which implies an even-ordered curve), and that case needs to be excluded for other reasons too then (there are some comments in the doc about this too).

jonasnick commented at 1:57 pm on April 26, 2023:

I don’t see why the if (!secp256k1_fe_is_square_var(&m)) { return 0; } path can catch this. secp256k1_fe_is_square_var returns 1 on input 0.

sipa commented at 2:36 pm on April 26, 2023:

You’re right. m is reused with a different meaning still.

The other part still holds: a division by zero is only possible if a point for which g(x)=0 exists on the curve, which is not the case for secp256k1. But this is rather nontrivial to prove.

sipa commented at 8:50 am on April 27, 2023:

Actually, that’s not correct either, I misremembered what the reason is for this not being possible. The reason is that $u^2 + ux + x^2 = 0$ implies that $x^3 + 7 = (-u-x)^3 + 7$; that’s a contradiction because the left hand is square ($x$ is on the curve) but the right hand is non-square ($-u-x$ is not on the curve, or we would have bailed out already). I’ve added this proof as a comment to the code.

jonasnick commented at 4:22 pm on May 3, 2023:

I checked for a large number of X coordinates that VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&s)); can’t happen but

if u^2 + u*x + x^2 = 0, then x^3 + 7 = (-u-x)^3 + 7.

how does this follow exactly?

sipa commented at 6:54 am on May 4, 2023:

$(x^3 + B) - ((-u-x)^3 + B) = u^3 + 3 u^2 x + 3 u x^2 + 2 x^3 = (u + 2 x) (u^2 + u x + x^2)$.

So if $u^2 + u x + x^2 = 0$, then $x^3 + B = (-u-x)^3 + B$.

sipa commented at 8:53 am on May 4, 2023:

Added this as more elaborate comment to the code.

in src/modules/ellswift/main_impl.h:29 in 54fff1ddc5 outdated

24+static void secp256k1_ellswift_xswiftec_frac_var(secp256k1_fe *xn, secp256k1_fe *xd, const secp256k1_fe *u, const secp256k1_fe *t) {
25+    /* The implemented algorithm is the following (all operations in GF(p)):
26+     *
27+     * - c0 = sqrt(-3) = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852
28+     * - If u=0, set u=1.
29+     * - If t=0, set t=1.

jonasnick commented at 8:02 pm on April 23, 2023:

Do we not abort here because we want to decode any t and u?

sipa commented at 11:08 am on April 25, 2023:

Indeed, it avoids the need for a caller to have special cases; literally any 64 byte value decodes to a valid non-infinity point on the curve.

in src/modules/ellswift/main_impl.h:252 in 54fff1ddc5 outdated

247+        secp256k1_fe_add(&v, &m); /* v=r/s-u */
248+        secp256k1_fe_half(&v); /* v=(r/s-u)/2 */
249+    }
250+
251+    /* Let w=sqrt(s). */
252+    VERIFY_CHECK(secp256k1_fe_sqrt(&m, &s)); /* m = sqrt(s) = w */

jonasnick commented at 1:34 pm on April 24, 2023:

The function calls inside both VERIFY_CHECKs should be moved outside because --coverage makes VERIFY_CHECK no-ops.

sipa commented at 8:52 am on April 27, 2023:

Fixed.

in src/modules/ellswift/main_impl.h:317 in 54fff1ddc5 outdated

312+            buf4[3] = cnt >> 24;
313+            ++cnt;
314+            secp256k1_sha256_write(&hash, buf4, 4);
315+            secp256k1_sha256_finalize(&hash, u32);
316+            if (!secp256k1_fe_set_b32(u, u32)) continue;
317+            if (secp256k1_fe_is_zero(u)) continue;

jonasnick commented at 3:07 pm on April 24, 2023:

Wouldn’t it be better to VERIFY_CHECK instead of continuing? We can’t test the branch and it impacts our coverage metric.

sipa commented at 1:12 pm on April 27, 2023:

Done.

in src/modules/ellswift/main_impl.h:417 in 54fff1ddc5 outdated

390+    /* Set up hasher state */
391+    secp256k1_sha256_initialize(&hash);
392+    secp256k1_sha256_write(&hash, PREFIX, sizeof(PREFIX));
393+    secp256k1_sha256_write(&hash, seckey32, 32);
394+    secp256k1_sha256_write(&hash, rnd32 ? rnd32 : ZERO, 32);
395+    secp256k1_sha256_write(&hash, ZERO, 32 - 9 - 4);

jonasnick commented at 3:22 pm on April 24, 2023:

Why hash ZERO here?

sipa commented at 1:13 pm on April 27, 2023:

The earlier code here required hash buffers that had very strict size requirements, and this was just padding. I’ve now relaxed the requirements, added rationale for it, and moved some of the code to a new function. Please have a look to see if it’s clear now.

jonasnick commented at 7:26 pm on May 3, 2023:

It’s clear now.

in src/modules/ellswift/main_impl.h:366 in 54fff1ddc5 outdated

339+    ARG_CHECK(ell64 != NULL);
340+    ARG_CHECK(pubkey != NULL);
341+    ARG_CHECK(rnd32 != NULL);
342+
343+    if (secp256k1_pubkey_load(ctx, &p, pubkey)) {
344+        static const unsigned char PREFIX[128 - 9 - 4 - 32 - 33] = "secp256k1_ellswift_encode";

jonasnick commented at 3:23 pm on April 24, 2023:

Why do we pad the prefix instead of using the regular sha256 padding?

sipa commented at 1:14 pm on April 27, 2023:

We were not; this is just a domain separation prefix. There is still the normal SHA256 padding (applied by secp256k1_sha256_finalize).

sipa commented at 5:31 pm on April 29, 2023:

I’ve switched to BIP340-style tagged hashes for domain separation now.

jonasnick commented at 4:21 pm on May 3, 2023:

Sorry, what I meant was that we were padding manually up to blocksize - 9 (as well as using regular padding) for some reason. According to the other comment that was for old code reasons.

in include/secp256k1_ellswift.h:85 in 54fff1ddc5 outdated

80+ *  Returns: 1 when pubkey is valid.
81+ *  Args:    ctx:        pointer to a context object
82+ *  Out:     ell64:      pointer to a 64-byte array to be filled
83+ *  In:      pubkey:     a pointer to a secp256k1_pubkey containing an
84+ *                       initialized public key
85+ *           rnd32:      pointer to 32 bytes of entropy (must be unpredictable)

jonasnick commented at 3:34 pm on April 24, 2023:

Is “unpredictable” sufficiently clear for a user? Maybe “chosen uniformly at random”.

sipa commented at 9:36 pm on April 29, 2023:

I’ve rewritten this, and added more comments.

jonasnick commented at 4:58 pm on May 3, 2023:

Looks good.

in include/secp256k1_ellswift.h:126 in 54fff1ddc5 outdated

121+ *
122+ * This function can be used instead of calling secp256k1_ec_pubkey_create followed
123+ * by secp256k1_ellswift_encode. It is safer, as it can use the secret key as
124+ * entropy for the encoding. That means that if the secret key itself is
125+ * unpredictable, no additional auxrand32 is needed to achieve indistinguishability
126+ * of the encoding.

jonasnick commented at 3:40 pm on April 24, 2023:

This sounds like auxrand32 is not needed, but in general, wouldn’t it be better to provide it? If you encode your public key in two different context, you presumably want the encodings to look be different. On the other hand, given the two encodings, it’s anyway easy to distinguish them from pseudorandomness because they decode to the same pubkey.

sipa commented at 9:43 pm on April 29, 2023:

If the public keys being sent are distinguishable from uniformly random, the result will inevitable by distinguishable already (and you shouldn’t be using ellswift in the first place probably). I think mentioning the “if the secret key itself is indistinguishable” was more confusing than useful as a result.

But more exactly, there are two properties one may hope to aim for with the encoding functions in this module:

Statistically close to uniform: actual (information theoretical) uniformity would probably require ~384 bits of entropy as input (clearly not supported by these functions), and also internal RNGs that can use that. The 256 bits that can be provided do get you a decent part of the way there.
Computational indistinguishability from uniform. For this ~128 bits suffices for secp256k1_ellswift_encode, and 0 bits suffices for secp256k1_ellswift_create (assuming uniformly random public keys with unknown private keys).

I’ve added more comments to recommend 256 bits of entropy in both cases, without going into too much technical detail.

jonasnick commented at 7:27 pm on May 3, 2023:

Thanks for the context. The new docs sound good to me.

jonasnick commented at 6:57 pm on April 24, 2023: contributor

PR looks good! I checked that the implementation matches the algorithm description in the comments and BIP 324, but I did not read the markdown description of the algorithm in detail nor did I compare it with the paper.

I also created a code coverage report. One can see that the module is covered 100% once API tests (for ARG_CHECKS and secp256k1_ellswift_create with rnd32 == NULL) and two VERIFY_CHECK for unreachable conditions are added.

sipa force-pushed on Apr 27, 2023

sipa force-pushed on Apr 29, 2023

in src/modules/ellswift/main_impl.h:167 in 974d00c8e1 outdated

161+ *   - no result for which u^3 + t^2 + 7 = 0 will be returned.
162+ *
163+ * The rather unusual encoding of bits in c (a large "if" based on the middle bit, and then
164+ * using the low and high bits to pick signs of square roots) is to match the paper's
165+ * encoding more closely: c=0 through c=3 match branches 1..4 in the paper, while c=4 through
166+ * c=7 are copies of those with an additional negation of sqrt(w).

sipa commented at 9:18 am on May 1, 2023:

Self-nit: this is actually unnecessary.

Both (current) call sites for the encoder logic do encode a known Y coordinate parity, which means that c=0 to c=3 would suffice (the additional conditional negation based on bit 4 in c is used, but then effectively replaced by whatever makes the y parity match the t parity).

Together, that does mean a slightly simpler structure is possible:

secp256k1_ellswift_xswiftec_inv_var only takes c=0 through c=3, and always outputs an encoding which represents a Y coordinate that’s deterministic.
secp256k1_ellswift_xelligatorswift_var can use a branch pool consisting of 128 2-bit values rather than 64 4-bit values (of which one bit is ignored).
secp256k1_ellswift_xelligatorswift_var can be merged into secp256k1_ellswift_elligatorswift_var (as the X-only version would on itself not yield a uniform distribution anymore).

Opinions?

sipa commented at 1:59 pm on May 10, 2023:

Decided not to do this, because the performance gains are tiny (saves one field negation), but is further removed from the explanation (and probably simpler described as-is).

in src/group_impl.h:749 in 961baf4e93 outdated

744+     secp256k1_fe_mul(&r, xd, xn); /* r = xd*xn */
745+     secp256k1_fe_sqr(&t, xn); /* t = xn^2 */
746+     secp256k1_fe_mul(&r, &r, &t); /* r = xd*xn^3 */
747+     secp256k1_fe_sqr(&t, xd); /* t = xd^2 */
748+     secp256k1_fe_sqr(&t, &t); /* t = xd^4 */
749+     VERIFY_CHECK(SECP256K1_B <= 8);

real-or-random commented at 10:13 am on May 3, 2023:

nit: I think this is at least misleading. The magnitude bound is 32, so

0     VERIFY_CHECK(SECP256K1_B <= 31);

should suffice With B=31, t will have magnitude 31 after the next line, and then r will have 1+31 = 32, which is fine because secp256k1_fe_is_square_var doesn’t have a magnitude precondition.

I plan to include this in a bunch of fixups you’ll be able to cherry-pick. (But feel free to go ahead and just fix it.)

sipa commented at 8:47 am on May 4, 2023:

Fixed.

in configure.ac:189 in 08ed2b4264 outdated

184@@ -185,6 +185,10 @@ AC_ARG_ENABLE(module_schnorrsig,
185     AS_HELP_STRING([--enable-module-schnorrsig],[enable schnorrsig module [default=yes]]), [],
186     [SECP_SET_DEFAULT([enable_module_schnorrsig], [yes], [yes])])
187 
188+AC_ARG_ENABLE(module_ellswift,
189+    AS_HELP_STRING([--enable-module-ellswift],[enable ElligatorSwift module (experimental)]), [],

real-or-random commented at 2:34 pm on May 3, 2023:

We should talk about whether we want this to be experimental.

(And if the answer yes, a check for --enable-experimental is missing.)

sipa commented at 8:47 am on May 4, 2023:

Good question.

jonasnick commented at 1:57 pm on May 9, 2023:

I’m fine with the module being non-experimental. If it happens that we have to change the API, we can make a new (minor) release.

sipa commented at 1:56 pm on May 10, 2023:

We decided to not make it experimental. If anything, the most likely place where API changes may be expected still is in the hashers, but adding new hashers while deprecating but maintaining the old ones isn’t a high burden.

theuni commented at 3:22 pm on May 25, 2023:

It was decided this this would not be experimental, but it’s still described as such. I assume that’s not intentional? Edit: It’s also missing default help.

sipa commented at 5:42 pm on May 31, 2023:

Fixed.

in include/secp256k1_ellswift.h:77 in 974d00c8e1 outdated

71+ *  SHA256(key1 || key2 || x32), where (key1, key2) = sorted([ours64, theirs64]), and
72+ *  ignores data. The sorting is lexicographic. */
73+SECP256K1_API extern const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_xdh_hash_function_sha256;
74+
75+/** A default secp256k1_ellswift_xdh_hash_function, currently secp256k1_ellswift_xdh_hash_function_sha256. */
76+SECP256K1_API extern const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_xdh_hash_function_default;

real-or-random commented at 3:35 pm on May 3, 2023:

I know we have this also in the module ECDH, but what’s the purpose for exporting a variable for the default? I think in case of ECDH, a hash function that can change due to an API change is exactly not what you want as a user, because it breaks interop.

Of course, us changing this variable will be a breaking API change. But the way I imagine a change of defaults (if it will ever occur), is not changing secp256k1_ellswift_xdh_hash_function_default (and the behavior of NULL), because that’s just hard breaking. I imagine we’d instead rather deprecate secp256k1_ellswift_xdh and add a new function with a different default hash.

So, I don’t see much value in adding this default variable as another layer of abstraction. If the user wants to call the hash function explicitly, they could still call secp256k1_ellswift_xdh_hash_function_sha256 (and be sure what they get!).

(Now that I think about it, having this in the ECDH module may have originated from the way we do this for nonce functions. But in that case, it makes much more sense, and we could swap out the hash function under the hood without any change in interop.)

sipa commented at 8:25 am on May 4, 2023:

You’re right. It’s a bad idea to provide any kind of default, the hasher is part of the scheme’s definition, and users ought to be explicit about that.

My current thinking is the following:

A generic BIP340-tagged-hash based hasher, which takes some encoded tag through data, and sorts the ours/theirs encodings lexicographically (so it’s usable in contexts where there is no clear first/second participant). Not sure how to encode the tag though… could be just a C-style string (strlen…) or some fixed length.
A BIP324-compatible hasher, which takes initiator/responder int as data.

I find it a bit unfortunate that one hasher can’t be used for everything. A possibility would be to use a more complex encoding which provides both tag and order through data, but that’d restrict the hasher to situations where the participants have a well-defined ordering.

sipa commented at 3:15 pm on May 6, 2023:

I’ve implemented this.

real-or-random commented at 3:37 pm on May 3, 2023: contributor

Making my way through the commits.

Here’s a branch with fixups: https://github.com/real-or-random/secp256k1/tree/202206_ellswift_dh Currently, the only commit has some nits in the public header.

in src/modules/ellswift/main_impl.h:388 in 974d00c8e1 outdated

373+        secp256k1_fe_normalize_var(t);
374+    }
375+}
376+
377+/** Set hash state to the BIP340 tagged hash midstate for "secp256k1_ellswift_encode". */
378+static void secp256k1_ellswift_sha256_init_encode(secp256k1_sha256* hash) {

jonasnick commented at 7:22 pm on May 3, 2023:

nit: should we add a test for both midstate init functions similar to https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/schnorrsig/tests_impl.h#L50?

sipa commented at 8:48 am on May 4, 2023:

Done in a separate commit.

in src/modules/ellswift/main_impl.h:471 in 974d00c8e1 outdated

456+    /* Set up hasher state. The used RNG is H(privkey [|| auxrand32] || cnt++), using BIP340 tagged
457+     * hash with tag "secp256k1_ellswift_create". */
458+    secp256k1_ellswift_sha256_init_create(&hash);
459+    secp256k1_sha256_write(&hash, seckey32, 32);
460+    if (auxrand32) secp256k1_sha256_write(&hash, auxrand32, 32);
461+    secp256k1_declassify(ctx, &hash, sizeof(hash)); /* hasher gets to declassify private key */

jonasnick commented at 7:23 pm on May 3, 2023:

since hash contains the plain seckey32 in its buffer, wouldn’t it be more robust to declassify the hash output in secp256k1_ellswift_xelligatorswift_var?

sipa commented at 8:44 am on May 4, 2023:

Fair point, but this would require passing down ctx several layers down the stack. Do you think that’s worth it?

sipa commented at 3:14 pm on May 6, 2023:

I’ve added some padding after the private key. This means the key material stays much shorter in the hashing buffer, and makes it perhaps more acceptable to declassify the hash state.

jonasnick commented at 10:18 am on May 9, 2023:

Looks good!

sipa force-pushed on May 4, 2023

sipa force-pushed on May 5, 2023

in src/bench.c:137 in 84a735dd67 outdated

132+        size_t len = 33;
133+        secp256k1_pubkey pubkey;
134+        CHECK(secp256k1_ec_pubkey_create(data->ctx, &pubkey, data->key));
135+        CHECK(secp256k1_ec_pubkey_serialize(data->ctx, pub33, &len, &pubkey, SECP256K1_EC_COMPRESSED));
136+        memcpy(data->key, pub33 + 1, 32);
137+        data->key[17] ^= i;

stratospher commented at 10:00 am on May 5, 2023:

84a735d: curious to know why we do this? data->key would be different everytime because of memcpy in previous line. (maybe this creates even more diffusion?)

sipa commented at 9:56 am on May 9, 2023:

I think my reasoning may have been that I wanted to avoid using just valid X coordinates as private keys, but that really doesn’t add anything. Removed.

stratospher commented at 7:08 pm on May 9, 2023:

oh, interesting.

in src/bench.c:229 in 84a735dd67 outdated

225@@ -207,6 +226,7 @@ int main(int argc, char** argv) {
226     if (d || have_flag(argc, argv, "ecdsa") || have_flag(argc, argv, "verify") || have_flag(argc, argv, "ecdsa_verify")) run_benchmark("ecdsa_verify", bench_verify, NULL, NULL, &data, 10, iters);
227 
228     if (d || have_flag(argc, argv, "ecdsa") || have_flag(argc, argv, "sign") || have_flag(argc, argv, "ecdsa_sign")) run_benchmark("ecdsa_sign", bench_sign_run, bench_sign_setup, NULL, &data, 10, iters);
229+    if (d || have_flag(argc, argv, "ec") || have_flag(argc, argv, "keygen") || have_flag(argc, argv, "ec_keygen")) run_benchmark("ec_keygen", bench_keygen_run, bench_sign_setup, NULL, &data, 10, iters);

stratospher commented at 10:24 am on May 5, 2023:

84a735d: is it important to set up data->key and data->msg(not used) using bench_sign_setup every time in the count loop? (just wondering, i tried NULL instead of bench_sign_setup and didn’t notice any difference in benchmarking results)

sipa commented at 9:56 am on May 9, 2023:

Fair point, I’ve introduce a separate bench_keygen_setup. I’ve also merged the different bench data types, because the former code was possibly illegally casting bench_verify_data* to bench_sign_data*.

in src/tests.c:3968 in 54a33377f6 outdated

3932+        ret_on_curve = secp256k1_ge_x_on_curve_var(&r);
3933+        ret_frac_on_curve = secp256k1_ge_x_frac_on_curve_var(&n, &zf);
3934+        ret_set_xo = secp256k1_ge_set_xo_var(&q, &r, 0);
3935+        CHECK(ret_on_curve == ret_frac_on_curve);
3936+        CHECK(ret_on_curve == ret_set_xo);
3937+        if (ret_set_xo) CHECK(secp256k1_fe_equal_var(&r, &q.x));

stratospher commented at 6:55 am on May 6, 2023:

c2dc037: this CHECK would pass when ret_set_xo=0 also since the x coordinate assignment happens before 0 or 1 is returned in secp256k1_ge_set_xo_var().

sipa commented at 9:45 am on May 9, 2023:

It would, but I don’t think a caller should assume anything about the behavior of secp256k1_ge_set_xo_var’s output in case failure is returned. It’s of course just an internal function, and there are no API guarantees or anything to account for, but I still think it’s better design to avoid that.

stratospher commented at 5:35 am on May 10, 2023:

oh! true, it’s possible the function behaves unpredictably in a different environment. agree with keeping it as it is.

in include/secp256k1_ellswift.h:46 in 213927943d outdated

41+ * - The paper uses an additional encoding bit for the parity of y. Here the
42+ *   parity of t is used (negating t does not affect the decoded x coordinate,
43+ *   so this is possible).
44+ */
45+
46+/** A pointer to a function used by secp256k1_ellswift_xdh to hashing the shared

stratospher commented at 7:29 am on May 6, 2023:

6128b71: micro nit - s/hashing/hash

sipa commented at 9:56 am on May 9, 2023:

Done.

in include/secp256k1_ellswift.h:128 in 213927943d outdated

119+/** Compute an ElligatorSwift public key for a secret key.
120+ *
121+ *  Returns: 1: secret was valid, public key was stored.
122+ *           0: secret was invalid, try again.
123+ *  Args:    ctx:        pointer to a context object, initialized for signing.
124+ *  Out:     ell64:      pointer to a 64-byte area to receive the ElligatorSwift

stratospher commented at 7:47 am on May 6, 2023:

6128b71: s/area/array

sipa commented at 9:56 am on May 9, 2023:

That’s a strange typo. Fixed.

in include/secp256k1_ellswift.h:127 in 213927943d outdated

118+
119+/** Compute an ElligatorSwift public key for a secret key.
120+ *
121+ *  Returns: 1: secret was valid, public key was stored.
122+ *           0: secret was invalid, try again.
123+ *  Args:    ctx:        pointer to a context object, initialized for signing.

stratospher commented at 7:50 am on May 6, 2023:

6128b71: signing not needed i think

sipa commented at 9:55 am on May 9, 2023:

Indeed, this predated the context relaxations. Fixed.

fanquake cross-referenced this on May 6, 2023 from issue BIP324: Cipher suite by dhruv

fanquake cross-referenced this on May 6, 2023 from issue BIP324: Add encrypted p2p transport {de}serializer by dhruv

in src/modules/ellswift/main_impl.h:128 in 213927943d outdated

123+        *xn = n;
124+        return;
125+    }
126+    secp256k1_fe_mul(&l, &p, &u1); /* l = u*(g+s) */
127+    secp256k1_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*(g+s) */
128+    secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)+u*(g+s) */

stratospher commented at 2:12 pm on May 6, 2023:

6128b71:

0    secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)-u*(g+s) */

sipa commented at 9:55 am on May 9, 2023:

Nice. Fixed.

in CMakeLists.txt:269 in 213927943d outdated

265@@ -260,6 +266,7 @@ message("  ECDH ................................ ${SECP256K1_ENABLE_MODULE_ECDH}
266 message("  ECDSA pubkey recovery ............... ${SECP256K1_ENABLE_MODULE_RECOVERY}")
267 message("  extrakeys ........................... ${SECP256K1_ENABLE_MODULE_EXTRAKEYS}")
268 message("  schnorrsig .......................... ${SECP256K1_ENABLE_MODULE_SCHNORRSIG}")
269+message("  ElligatorSwift....................... ${SECP256K1_ENABLE_MODULE_ELLSWIFT}")

stratospher commented at 2:32 pm on May 6, 2023:

6128b71: micro nit

0message("  ElligatorSwift ...................... ${SECP256K1_ENABLE_MODULE_ELLSWIFT}")

sipa commented at 9:55 am on May 9, 2023:

Was already fixed, I think?

stratospher commented at 7:08 pm on May 9, 2023:

doesn’t look like it. (there’s a single space after schnorrsig/extrakeys etc.. but not after ElligatorSwift.)

sipa commented at 1:54 pm on May 10, 2023:

Fixed now.

sipa force-pushed on May 6, 2023

sipa commented at 7:02 pm on May 6, 2023: contributor

~~Hmm, I don’t understand what’s wrong here. The Windows builds seem to not be able to find the exported bip324 hash function?~~

Nevermind, just remembered and integrated #1209.

sipa force-pushed on May 6, 2023

in doc/ellswift.md:318 in 77d2ece870 outdated

313+* In the branch for $x_1$ and $x_2$ (where $c \in \\{0, 1, 4, 5\\}$):
314+  * When $g(u) = 0$, we would have $s=w=Y=0$, which is not on $S_u.$ This is only possible on even-ordered curves.
315+    Excluding this also removes the one condition under which the simplified check for $x_3$ on the curve
316+    fails (namely when $g(x_1)=g(x_2)=0$ but $g(x_3)$ is not square).
317+    This does exclude some valid encodings: when both $g(u)=0$ and $u^2+ux+x^2+a=0$ (also implying $g(x)=0$),
318+    the $S_u'$ equation degenerates to $0 = 0$, and many valid $t$ values may exist. Yet, these cannot be targetted uniformly by the

stratospher commented at 5:03 am on May 7, 2023:

8183a34: s/targetted/targeted

sipa commented at 9:55 am on May 9, 2023:

Done.

in doc/ellswift.md:38 in 77d2ece870 outdated

33+are taken modulo $p$), and then evaluating $F_u(t)$, which for every $u$ and $t$ results in a valid
34+x-coordinate on the curve. The functions $F_u$ will be defined in [Section 2](#2-the-decoding-function).
35+
36+**Encoding** a given $x$ coordinate is conceptually done as follows:
37+* Loop:
38+  * Pick a uniformy random field element $u.$

stratospher commented at 5:05 am on May 7, 2023:

8183a34: s/uniformy/uniformly

sipa commented at 9:55 am on May 9, 2023:

Fixed.

in include/secp256k1_ellswift.h:153 in 6128b71166 outdated

148+ *                      sent to the other party.
149+ *           seckey32:  a pointer to the 32-byte secret key corresponding to
150+ *                      ours64 (the correspondence is not checked)
151+ *           hashfp:    pointer to a hash function. If NULL,
152+ *                      secp256k1_ellswift_xdh_hash_function_default is used
153+ *                      (in which case, 32 bytes will be written to output).

theStack commented at 10:17 am on May 8, 2023:

Since hashfp is not allowed to be NULL (as indicated by SECP256K1_ARG_NONNULL(6) below and ARG_CHECK(hashfp != NULL); in the implementation), the second sentence is obsolete:

0 *           hashfp:    pointer to a hash function.

sipa commented at 7:27 am on May 9, 2023:

Done.

in include/secp256k1_ellswift.h:155 in 6128b71166 outdated

150+ *                      ours64 (the correspondence is not checked)
151+ *           hashfp:    pointer to a hash function. If NULL,
152+ *                      secp256k1_ellswift_xdh_hash_function_default is used
153+ *                      (in which case, 32 bytes will be written to output).
154+ *           data:      arbitrary data pointer passed through to hashfp (ignored
155+ *                      by secp256k1_ellswift_xdh_hash_function_default).

theStack commented at 10:22 am on May 8, 2023:

Seems like secp256k1_ellswift_xdh_hash_function_default doesn’t exist anymore:

0 *           data:      arbitrary data pointer passed through to hashfp.

sipa commented at 7:27 am on May 9, 2023:

Done.

sipa force-pushed on May 9, 2023

in doc/ellswift.md:324 in 8183a34037 outdated

319+    encoder anyway as there will generally be more than 8.
320+  * When $g(x) = 0$, the same $t$ would be produced as in the $x_3$ branch (where $c \in \\{2, 3, 6, 7\\}$) which we give precedence
321+    as it can deal with $g(u)=0$.
322+    This is again only possible on even-ordered curves.
323+* In the branch for $x_3$ (where $c \in \\{2, 3, 6, 7\\}$):
324+  * When $u = -u-v$ and $c \in \\{3, 7\\}$, the same $t$ would be returned as in the $c \in \\{2, 6\\}$ cases.

stratospher commented at 7:55 am on May 9, 2023:

8183a34: should be v = -u -v?

sipa commented at 9:54 am on May 9, 2023:

Nice catch. Fixed.

stratospher commented at 8:29 am on May 9, 2023: contributor

I’ve reviewed the first 3 commits so far. And the writeup which was super helpful for reviewing the 3rd commit! (especially for understanding the encoding special cases) The logic described in the writeup and code do match. Also cross checked the constants till now (c1-c4, hash states for encode, create, xdh) by constructing them in python.

in include/secp256k1_ellswift.h:97 in 8183a34037 outdated

92+ * It is recommended that rnd32 consists of 32 uniformly random bytes, not
93+ * known to any adversary trying to detect whether public keys are being
94+ * encoded, though 16 bytes of randomness (padded to an array of 32 bytes,
95+ * e.g., with zeros) suffice to make the result indistinguishable from
96+ * uniform. The randomness in rnd32 must be independent of pubkey. In
97+ * particular, it must not be derived deterministically from pubkey.

jonasnick commented at 9:32 am on May 9, 2023:

nit: this confused me because must and must not sound like necessary requirements. It’s fine to use some hardened derivation of the secret key as rnd32 (which is not independent of the pubkey) and it’s fine to derive rnd32 deterministically from pubkey and some secret data.

sipa commented at 10:04 am on May 9, 2023:

How about: “must not be a deterministic function of just the public key”?

sipa commented at 10:58 am on May 9, 2023:

I’ve made some edits here.

jonasnick commented at 1:03 pm on May 9, 2023:

:+1:

sipa force-pushed on May 9, 2023

in src/modules/ellswift/main_impl.h:402 in 97eefc4d50 outdated

397+    hash->s[7] = 0xd626b715ul;
398+
399+    hash->bytes = 64;
400+}
401+
402+int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64, const secp256k1_pubkey *pubkey, const unsigned char *ent32) {

jonasnick commented at 10:12 am on May 9, 2023:

The ent32 arg is called rnd32 in the include file

sipa commented at 10:58 am on May 9, 2023:

I’ve renamed it consistently to rnd32 and auxrnd32 everywhere.

sipa force-pushed on May 9, 2023

sipa commented at 11:00 am on May 9, 2023: contributor

I’ve made the following updates to the write-up:

  0@@ -35,7 +35,7 @@ x-coordinate on the curve. The functions $F_u$ will be defined in [Section 2](#2
  1 
  2 **Encoding** a given $x$ coordinate is conceptually done as follows:
  3 * Loop:
  4-  * Pick a uniformy random field element $u.$
  5+  * Pick a uniformly random field element $u.$
  6   * Compute the set $L = F_u^{-1}(x)$ of $t$ values for which $F_u(t) = x$, which may have up to *8* elements.
  7   * With probability $1 - \dfrac{\\#L}{8}$, restart the loop.
  8   * Select a uniformly random $t \in L$ and return $(u, t).$
  9@@ -183,7 +183,7 @@ It is not possible that an encoding found through the $x_1$ expression decodes t
 10 take precedence), for the same reason: if both $x_1$ and $x_2$ decodings were valid, $x_3$ would be valid as well, and thus take
 11 precedence over both. Because of this, the $g(-u-x)$ being square test for $x_1$ and $x_2$ is the only test necessary to guarantee the found $t$
 12 values round-trip back to the input $x$ correctly. This is the reason for choosing the $(x_3, x_2, x_1)$ precedence order in the decoder;
 13-any other order requires more complicated round-trip checks in the encoder.
 14+any order which does not place $x_3$ first requires more complicated round-trip checks in the encoder.
 15 
 16 ### 3.1 Switching to *v, w* coordinates
 17 
 18@@ -204,9 +204,9 @@ $$
 19 
 20 We can now write the expressions for finding $(v, w)$ given $x$ explicitly, by solving each of the $\\{x_1, x_2, x_3\\}$
 21 expressions for $v$ or $w$, and using the $S_u'$ equation to find the other variable:
 22-* Assuming $x = x_1$, we find $v = x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}.$
 23-* Assuming $x = x_2$, we find $v = -u-x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}.$
 24-* Assuming $x = x_3$, we find $w = \pm\sqrt{x-u}$ and $v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2).$
 25+* Assuming $x = x_1$, we find $v = x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
 26+* Assuming $x = x_2$, we find $v = -u-x$ and $w = \pm\sqrt{-g(u)/(u^2 + uv + v^2 + a)}$ (two solutions).
 27+* Assuming $x = x_3$, we find $w = \pm\sqrt{x-u}$ and $v = -u/2 \pm \sqrt{-w^2(4g(u) + w^2h(u))}/(2w^2)$ (four solutions).
 28 
 29 ### 3.2 Avoiding computing all inverses
 30 
 31@@ -271,7 +271,7 @@ Ignoring the negligible cases, we get:
 32 
 33 Whenever a square root of a non-square is taken, $\bot$ is returned; for both square roots this happens with roughly
 34 50% on random inputs. Similarly, when a division by 0 would occur, $\bot$ is returned as well; this will only happen
 35-with negligible probability. The division in the first branch in fact cannot occur at all, $u^2 + uv + v^2 + a = 0$
 36+with negligible probability. A division by 0 in the first branch in fact cannot occur at all, because $u^2 + uv + v^2 + a = 0$
 37 implies $g(-u-x) = g(x)$ which would mean the $g(-u-x)$ is square condition has triggered
 38 and $\bot$ would have been returned already.
 39 
 40@@ -304,8 +304,8 @@ There can be 0, 1, or 2 $(v, w)$ pairs before invoking $P_u^{'-1}$, and each res
 41 
 42 ### 3.4 Dealing with special cases
 43 
 44-As mentioned before there are a few cases to deal with which only happen in a negligibly small subset of inputs (besides division by zero).
 45-For cryptographically sized curves, if only random inputs are going to be considered, it is unnecessary to deal with these. Still, for completeness
 46+As mentioned before there are a few cases to deal with which only happen in a negligibly small subset of inputs.
 47+For cryptographically sized fields, if only random inputs are going to be considered, it is unnecessary to deal with these. Still, for completeness
 48 we analyse them here. They generally fall into two categories: cases in which the encoder would produce $t$ values that
 49 do not decode back to $x$ (or at least cannot guarantee that they do), and cases in which the encoder might produce the same
 50 $t$ value for multiple $c$ inputs (thereby biasing that encoding):
 51@@ -315,24 +315,26 @@ $t$ value for multiple $c$ inputs (thereby biasing that encoding):
 52     Excluding this also removes the one condition under which the simplified check for $x_3$ on the curve
 53     fails (namely when $g(x_1)=g(x_2)=0$ but $g(x_3)$ is not square).
 54     This does exclude some valid encodings: when both $g(u)=0$ and $u^2+ux+x^2+a=0$ (also implying $g(x)=0$),
 55-    the $S_u'$ equation degenerates to $0 = 0$, and many valid $t$ values may exist. Yet, these cannot be targetted uniformly by the
 56+    the $S_u'$ equation degenerates to $0 = 0$, and many valid $t$ values may exist. Yet, these cannot be targeted uniformly by the
 57     encoder anyway as there will generally be more than 8.
 58   * When $g(x) = 0$, the same $t$ would be produced as in the $x_3$ branch (where $c \in \\{2, 3, 6, 7\\}$) which we give precedence
 59     as it can deal with $g(u)=0$.
 60     This is again only possible on even-ordered curves.
 61 * In the branch for $x_3$ (where $c \in \\{2, 3, 6, 7\\}$):
 62-  * When $u = -u-v$ and $c \in \\{3, 7\\}$, the same $t$ would be returned as in the $c \in \\{2, 6\\}$ cases.
 63-    It is equivalent to checking whether the square root is zero.
 64-    This cannot occur in the $x_1$ / $x_2$ branch, as it would trigger the $g(-u-x)$ is square condition.
 65+  * When $s=0$, a division by zero would occur.
 66+  * When $v = -u-v$ and $c \in \\{3, 7\\}$, the same $t$ would be returned as in the $c \in \\{2, 6\\}$ cases.
 67+    It is equivalent to checking whether $r=0$.
 68+    This cannot occur in the $x_1$ or $x_2$ branches, as it would trigger the $g(-u-x)$ is square condition.
 69     A similar concern for $w = -w$ does not exist, as $w=0$ is already impossible in both branches: in the first
 70-    it requires $g(u)=0$ which is already outlawed; in the second it would trigger division by zero.
 71-* In the implementation of $P_u^{'-1}$, special cases can occur:
 72+    it requires $g(u)=0$ which is already outlawed on even-ordered curves and impossible on others; in the second it would trigger division by zero.
 73+* In the implementation of $P_u^{'-1}$, special cases can occur.
 74   * For $a=0$ curves, $u=0$ and $t=0$ need to be avoided as they would trigger division by zero in the decoder.
 75     The latter is only possible when $g(u)=0$ and can thus only occur on even-ordered curves.
 76   * For $a \neq 0$ curves, $h(u)t^2 = -1$ needs to be avoided as it would trigger division by zero in the decoder.
 77   * Also for $a \neq 0$ curves, if $w(u/2 + v) = X_0(u)$ but $w/2 \neq Y_0(u)$, no $t$ exists.
 78 
 79 **Define** a version of $G_{c,u}(x)$ which deals with all these cases:
 80+* If $u=0$, return $\bot.$
 81 * If $c \in \\{0, 1, 4, 5\\}:$
 82   * If $g(u) = 0$ or $g(x) = 0$, return $\bot$ (even curves only).
 83   * If $g(-u-x)$ is square, return $\bot.$
 84@@ -340,10 +342,11 @@ $t$ value for multiple $c$ inputs (thereby biasing that encoding):
 85   * Let $v = x.$
 86 * Otherwise, when $c \in \\{2, 3, 6, 7\\}:$
 87   * Let $s = x-u.$
 88-  * Let $r = \sqrt{-s(4g(u) + sh(u))}.$
 89+  * If $s = 0$, return $\bot.$
 90+  * Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
 91   * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
 92   * Let $v = (r/s - u)/2.$
 93-* Let $w = \sqrt{s}.$
 94+* Let $w = \sqrt{s}$; return $\bot$ if not square.
 95 * Depending on $c:$
 96   * If $c \in \\{0, 2\\}:$ return $P_u^{'-1}(v, w).$
 97   * If $c \in \\{1, 3\\}:$ return $P_u^{'-1}(-u-v, w).$
 98@@ -371,10 +374,11 @@ Specialized for odd-ordered $a=0$ curves:
 99   * Let $v = x.$
100 * Otherwise, when $c \in \\{2, 3, 6, 7\\}:$
101   * Let $s = x-u.$
102-  * Let $r = \sqrt{-s(4(u^3 + b) + 3su^2)}.$
103+  * If $s = 0$, return $\bot.$
104+  * Let $r = \sqrt{-s(4(u^3 + b) + 3su^2)}$; return $\bot$ if not square.
105   * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
106   * Let $v = (r/s - u)/2.$
107-* Let $w = \sqrt{s}.$
108+* Let $w = \sqrt{s}$; return $\bot$ if not square.
109 * Depending on $c:$
110   * If $c \in \\{0, 2\\}:$ return $w(\frac{\sqrt{-3}-1}{2}u - v).$
111   * If $c \in \\{1, 3\\}:$ return $w(\frac{\sqrt{-3}+1}{2}u + v).$
112@@ -431,10 +435,10 @@ And encoding would be done using a $G_{c,u}(x, y)$ function defined as:
113   * Let $v = x.$
114 * Otherwise, when $c \in \\{2, 3\\}:$
115   * Let $s = x-u.$
116-  * Let $r = \sqrt{-s(4g(u) + sh(u))}.$
117+  * Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
118   * If $c = 3$ and $r = 0$, return $\bot.$
119   * Let $v = (r/s - u)/2.$
120-* Let $w = \sqrt{s}.$
121+* Let $w = \sqrt{s}$; return $\bot$ if not square.
122 * Let $w' = w$ if $sign(w/2) = sign(y)$; $-w$ otherwise.
123 * Depending on $c:$
124   * If $c \in \\{0, 2\\}:$ return $P_u^{'-1}(v, w').$

sipa force-pushed on May 9, 2023

in src/ctime_tests.c:201 in 9a9900ed99 outdated

196+    VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret));
197+    CHECK(ret == 1);
198+
199+    VALGRIND_MAKE_MEM_UNDEFINED(key, 32);
200+    VALGRIND_MAKE_MEM_DEFINED(&ellswift, sizeof(ellswift));
201+    ret = secp256k1_ellswift_xdh(ctx, msg, ellswift, ellswift, key, secp256k1_ellswift_xdh_hash_function_tagged, "bench_test");

jonasnick commented at 2:07 pm on May 9, 2023:

CI fails because we need to s/_tagged/_prefix.

jonasnick commented at 2:08 pm on May 9, 2023:

… and change the data to be 64 bytes

sipa commented at 1:54 pm on May 10, 2023:

Fixed.

sipa force-pushed on May 9, 2023

in src/modules/ellswift/tests_impl.h:154 in ad60aaef5f outdated

149@@ -142,6 +150,19 @@ static const struct ellswift_decode_test ellswift_decode_tests[] = {
150     {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xfb, 0xb9, 0x82, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf6, 0xd6, 0xdb, 0x1f}, SECP256K1_FE_CONST(0x1c92ccdf, 0xcf4ac550, 0xc28db57c, 0xff0c8515, 0xcb26936c, 0x786584a7, 0x0114008d, 0x6c33a34b), 0},
151 };
152 
153+/* Set of expected ellswift_xdh BIP324 shared secrets, given private key, encodings, initiating,
154+ * taken from the BIP324 test vectors. Created using an independent implementation, and tested
155+ * against the paper authors' decoding code. */

stratospher commented at 7:48 am on May 10, 2023:

4c758e4: just clarifying that you meant testing the decoding part of xdh with the paper author’s code?

sipa commented at 8:33 pm on May 14, 2023:

Indeed, clarified.

in src/modules/ellswift/tests_impl.h:2 in dba66c9d8a outdated

0@@ -0,0 +1,315 @@
1+/***********************************************************************
2+ * Copyright (c) 2022 Pieter Wuile                                     *

stratospher commented at 7:59 am on May 10, 2023:

6048c78 :P

sipa commented at 8:30 pm on May 14, 2023:

Removed all copyright notices, as @real-or-random has suggested before.

sipa force-pushed on May 10, 2023

sipa commented at 2:05 pm on May 10, 2023: contributor

After in-person discussion, we decided to make the “prefix” hasher not sort the inputs. This makes the BIP324 hasher an optimized specialization of the prefix hasher, plus is more simple to understand conceptually.

This required making two API changes:

The secp256k1_ellswift_xdh function now takes public keys ell_a64 and ell_b64 (corresponding to party A’s pubkey and party B’s pubkey) rather than ell64_theirs and ell64_ours. It also takes a new argument party, to identify whether the caller is party A or party B.
The secp256k1_ellswift_xdh_hash_function type now takes public keys ell_a64 and ell_b64 instead of ell64_ours and ell64_theirs.

This change is a generalization, in the sense that the old sorting hasher behavior can still be implemented if desired (either using a custom hasher that performs sorting, or by having the caller sort the keys before invocation).

in src/modules/ellswift/tests_impl.h:53 in f243b80b5b outdated

41+    {0x00, SECP256K1_FE_CONST(0x78fe6b71, 0x7f2ea4a3, 0x2708d79c, 0x151bf503, 0xa5312a18, 0xc0963437, 0xe865cc6e, 0xd3f6ae97), SECP256K1_FE_CONST(0x8701948e, 0x80d15b5c, 0xd8f72863, 0xeae40afc, 0x5aced5e7, 0x3f69cbc8, 0x179a3390, 0x2c094d98), {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},
42+    {0x44, SECP256K1_FE_CONST(0x7c37bb9c, 0x5061dc07, 0x413f11ac, 0xd5a34006, 0xe64c5c45, 0x7fdb9a43, 0x8f217255, 0xa961f50d), SECP256K1_FE_CONST(0x5c1a76b4, 0x4568eb59, 0xd6789a74, 0x42d9ed7c, 0xdc6226b7, 0x752b4ff8, 0xeaf8e1a9, 0x5736e507), {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0xb94d30cd, 0x7dbff60b, 0x64620c17, 0xca0fafaa, 0x40b3d1f5, 0x2d077a60, 0xa2e0cafd, 0x145086c2), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0x46b2cf32, 0x824009f4, 0x9b9df3e8, 0x35f05055, 0xbf4c2e0a, 0xd2f8859f, 0x5d1f3501, 0xebaf756d), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},
43+    {0x00, SECP256K1_FE_CONST(0x82388888, 0x967f82a6, 0xb444438a, 0x7d44838e, 0x13c0d478, 0xb9ca060d, 0xa95a41fb, 0x94303de6), SECP256K1_FE_CONST(0x29e96541, 0x70628fec, 0x8b497289, 0x8b113cf9, 0x8807f460, 0x9274f4f3, 0x140d0674, 0x157c90a0), {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},
44+    {0x33, SECP256K1_FE_CONST(0x91298f57, 0x70af7a27, 0xf0a47188, 0xd24c3b7b, 0xf98ab299, 0x0d84b0b8, 0x98507e3c, 0x561d6472), SECP256K1_FE_CONST(0x144f4ccb, 0xd9a74698, 0xa88cbf6f, 0xd00ad886, 0xd339d29e, 0xa19448f2, 0xc572cac0, 0xa07d5562), {SECP256K1_FE_CONST(0xe6a0ffa3, 0x807f09da, 0xdbe71e0f, 0x4be4725f, 0x2832e76c, 0xad8dc1d9, 0x43ce8393, 0x75eff248), SECP256K1_FE_CONST(0x837b8e68, 0xd4917544, 0x764ad090, 0x3cb11f86, 0x15d2823c, 0xefbb06d8, 0x9049dbab, 0xc69befda), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0x195f005c, 0x7f80f625, 0x2418e1f0, 0xb41b8da0, 0xd7cd1893, 0x52723e26, 0xbc317c6b, 0x8a1009e7), SECP256K1_FE_CONST(0x7c847197, 0x2b6e8abb, 0x89b52f6f, 0xc34ee079, 0xea2d7dc3, 0x1044f927, 0x6fb62453, 0x39640c55), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},
45+    {0x00, SECP256K1_FE_CONST(0xb682f3d0, 0x3bbb5dee, 0x4f54b5eb, 0xfba931b4, 0xf52f6a19, 0x1e5c2f48, 0x3c73c66e, 0x9ace97e1), SECP256K1_FE_CONST(0x904717bf, 0x0bc0cb78, 0x73fcdc38, 0xaa97f19e, 0x3a626309, 0x72acff92, 0xb24cc6dd, 0xa197cb96), {SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},
46+    {0x77, SECP256K1_FE_CONST(0xc17ec69e, 0x665f0fb0, 0xdbab48d9, 0xc2f94d12, 0xec8a9d7e, 0xacb58084, 0x83309180, 0x1eb0b80b), SECP256K1_FE_CONST(0x147756e6, 0x6d96e31c, 0x426d3cc8, 0x5ed0c4cf, 0xbef6341d, 0xd8b28558, 0x5aa574ea, 0x0204b55e), {SECP256K1_FE_CONST(0x6f4aea43, 0x1a0043bd, 0xd03134d6, 0xd9159119, 0xce034b88, 0xc32e50e8, 0xe36c4ee4, 0x5eac7ae9), SECP256K1_FE_CONST(0xfd5be16d, 0x4ffa2690, 0x126c67c3, 0xef7cb9d2, 0x9b74d397, 0xc78b06b3, 0x605fda34, 0xdc9696a6), SECP256K1_FE_CONST(0x5e9c6079, 0x2a2f000e, 0x45c6250f, 0x296f875e, 0x174efc0e, 0x9703e628, 0x706103a9, 0xdd2d82c7), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0), SECP256K1_FE_CONST(0x90b515bc, 0xe5ffbc42, 0x2fcecb29, 0x26ea6ee6, 0x31fcb477, 0x3cd1af17, 0x1c93b11a, 0xa1538146), SECP256K1_FE_CONST(0x02a41e92, 0xb005d96f, 0xed93983c, 0x1083462d, 0x648b2c68, 0x3874f94c, 0x9fa025ca, 0x23696589), SECP256K1_FE_CONST(0xa1639f86, 0xd5d0fff1, 0xba39daf0, 0xd69078a1, 0xe8b103f1, 0x68fc19d7, 0x8f9efc55, 0x22d27968), SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0)}},

stratospher commented at 3:31 pm on May 10, 2023:

6048c78: wow! enc_bitmap = 0x77 and 6 distinct t values? :0

(4 distinct v,w pairs => 8 distinct t, do some of them end up invalid for some reason?)

sipa commented at 8:33 pm on May 14, 2023:

You can look at the BIP324 test vector where this actually comes from: line 19 in https://github.com/bitcoin/bips/blob/master/bip-0324/xswiftec_inv_test_vectors.csv. The comment explains exactly what happens in each of the 8 c branches:

case0:ok;case1:ok;case2:info[q=0]&info[X=0]&ok;case3:info[q=0]&bad[r=0];case4:ok;case5:ok;case6:info[q=0]&info[X=0]&ok;case7:info[q=0]&bad[r=0]

It’s a bit dense, but it means that the c=3 and c=7 don’t output anything because of “r=0”. If you recall, that conditions is there because in this case, the c=2 and c=3 (and also, c=6 and c=7) branches would output the same result. The “no r=0” rule invalidates one of the two to make sure this t value isn’t twice as likely to be produced as others (not that this actually matters of course, the odds of hitting an r=0 in the first place are negligible, but having this rule makes everything exhaustively testable in tiny curves too).

stratospher commented at 3:21 pm on May 17, 2023:

oh, the exactly 0, 4, or 8 t values were before the special cases were factored in! thanks, understood it now.

jonasnick commented at 6:39 pm on May 10, 2023: contributor

code review ACK 3cfa1e033dc7ca55521659bb72b7753053308ac1

I have not reviewed ellswift.md or otherwise verified that the pseudocode is correct.

sipa added the label feature on May 11, 2023

in src/modules/ellswift/main_impl.h:147 in b419113777 outdated

142+
143+/** Decode ElligatorSwift encoding (u, t) to point P. */
144+static void secp256k1_ellswift_swiftec_var(secp256k1_ge *p, const secp256k1_fe *u, const secp256k1_fe *t) {
145+    secp256k1_fe x;
146+    secp256k1_ellswift_xswiftec_var(&x, u, t);
147+    secp256k1_ge_set_xo_var(p, &x, secp256k1_fe_is_odd(t));

stratospher commented at 10:01 am on May 11, 2023:

1c369b8: should we normalize x before passing it to secp256k1_ge_set_xo_var where there’s an x**3 computation?

i haven’t understood why we normalize at some places and not at others. what’s the worst that could happen if we forget to normalize?

I understood that normalization is making the the field element into a form which is less than p + making sure less than 1 magnitude. I tried following the details of how normalization is implemented in the codebase but wasn’t able to make progress.

sipa commented at 1:13 pm on May 14, 2023:

should we normalize x before passing it to secp256k1_ge_set_xo_var where there’s an x**3 computation?

i haven’t understood why we normalize at some places and not at others.

No, the requirements are roughly:

Magnitude can never exceed 32 (for all field operations)
On input to mul or sqr, magnitude cannot exceed 8.
add and negate increase magnitude, so things that involve additions/negations usually want magnitude 1.
is_odd and is_equal need full normalization (because they operate on canonical integer representation)

Since #1066, all those rules should be explained exactly in field.h (and checked programmatically in the wrappers in field_impl.h).

what’s the worst that could happen if we forget to normalize?

Well if we actually forget and as a result violate normalization/magnitude constraints, in production non-VERIFY code, the computation will just be wrong. Very bad.

But it’s also extremely easy to verify: the magnitude/normalization properties of field values (almost) never depend on runtime values; they’re just a function of what operations have been performed. And in VERIFY mode, the normalization and magnitude values are tracked and checked explicitly, so if all code paths are exercised in the tests, it shouldn’t be possible to trigger a violation.

stratospher commented at 3:21 pm on May 17, 2023:

thank you for explaining, went through the implementation again and i understand why/where normalisation is done much better now! (have a related question which i’ve posted below)

in src/modules/ellswift/main_impl.h:169 in b419113777 outdated

164+ * The rather unusual encoding of bits in c (a large "if" based on the middle bit, and then
165+ * using the low and high bits to pick signs of square roots) is to match the paper's
166+ * encoding more closely: c=0 through c=3 match branches 1..4 in the paper, while c=4 through
167+ * c=7 are copies of those with an additional negation of sqrt(w).
168+ */
169+static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_fe *x_in, const secp256k1_fe *u_in, int c) {

stratospher commented at 10:32 am on May 11, 2023:

1c369b8: would ensuring that this is called with valid x coordinates be desirable/too strict? the call site would use pubkeys and so valid x coordinates anyways. just curious about how functions are designed here.

sipa commented at 8:29 pm on May 14, 2023:

Good idea, added in a VERIFY_CHECK.

in src/modules/ellswift/tests_impl.h:245 in f243b80b5b outdated

203+        /* Compare with original. */
204+        ge_equals_ge(&g, &g2);
205+    }
206+    /* Verify the behavior of secp256k1_ellswift_create */
207+    for (i = 0; i < 400 * COUNT; i++) {
208+        unsigned char rnd32[32], sec32[32];

stratospher commented at 7:21 pm on May 11, 2023:

6048c78: micro nit: maybe call rnd32, rnd32a, rnd32b as auxrnd32 in the tests if you do end up touching this commit again.

sipa commented at 8:35 pm on May 14, 2023:

Done.

in src/modules/ellswift/tests_impl.h:358 in f243b80b5b outdated

281+        CHECK(ret);
282+        CHECK(secp256k1_memcmp_var(share32a, share32b, 32) == 0);
283+        /* Verify that the shared secret doesn't match if a secret key or remote pubkey changes. */
284+        secp256k1_testrand_flip(ell64a, 64);
285+        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32b, 1, &ellswift_xdh_hash_x32, NULL);
286+        CHECK(ret);

stratospher commented at 4:33 am on May 12, 2023:

6048c78: secp256k1_ellswift_xdh would successfully compute even if ell64 and secret key are invalid right? confused because it’s ret check here when ell64 has changed but !ret check when secret key has changed.

sipa commented at 8:40 pm on May 14, 2023:

Yeah, checking if the encoding matches would be expensive, and shouldn’t be needed (if the other side is honest the shared secret will never match if the encoding is wrong, and if both sides are dishonest we don’t care about security).

stratospher commented at 3:21 pm on May 17, 2023:

oh, makes sense! missed the part about both sides being dishonest before.

in src/modules/ellswift/tests_impl.h:344 in f243b80b5b outdated

285+        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32b, 1, &ellswift_xdh_hash_x32, NULL);
286+        CHECK(ret);
287+        CHECK(secp256k1_memcmp_var(share32a, share32b, 32) != 0);
288+        secp256k1_testrand_flip(sec32a, 32);
289+        ret = secp256k1_ellswift_xdh(CTX, share32b, ell64a, ell64b, sec32a, 0, &ellswift_xdh_hash_x32, NULL);
290+        CHECK(!ret || secp256k1_memcmp_var(share32a, share32b, 32) != 0);

stratospher commented at 4:35 am on May 12, 2023:

6048c78: would it be worth having another variable to store the original share32 value and then comparing the new value with the original one? (share32a has already changed at this point - so doesn’t make sense comparing them i think)

sipa commented at 9:03 pm on May 14, 2023:

Good idea. Done, and also added more tests of this type (checking with different encoding of the same key, and checking swapping of the two sides).

stratospher commented at 3:21 pm on May 17, 2023:

new tests look good!

sipa force-pushed on May 12, 2023

sipa commented at 5:42 am on May 12, 2023: contributor

Rebased after #1207.

Changes:

 0diff --git a/src/modules/ellswift/main_impl.h b/src/modules/ellswift/main_impl.h
 1index 679fa870..61334c8d 100644
 2--- a/src/modules/ellswift/main_impl.h
 3+++ b/src/modules/ellswift/main_impl.h
 4@@ -355,7 +355,7 @@ static void secp256k1_ellswift_xelligatorswift_var(unsigned char *u32, secp256k1
 5         /* Compute a new u value by hashing. */
 6         secp256k1_ellswift_prng(u32, hasher, cnt++);
 7         /* overflow is not a problem (we prefer uniform u32 over uniform u). */
 8-        (void)secp256k1_fe_set_b32(&u, u32);
 9+        secp256k1_fe_set_b32_mod(&u, u32);
10         /* Since u is the output of a hash, it should practically never be 0. We could apply the
11          * u=0 to u=1 correction here too to deal with that case still, but it's such a low
12          * probability that we do not bother. */
13@@ -489,9 +489,8 @@ int secp256k1_ellswift_decode(const secp256k1_context *ctx, secp256k1_pubkey *pu
14     ARG_CHECK(pubkey != NULL);
15     ARG_CHECK(ell64 != NULL);
16 
17-    secp256k1_fe_set_b32(&u, ell64);
18-    secp256k1_fe_normalize_var(&u);
19-    secp256k1_fe_set_b32(&t, ell64 + 32);
20+    secp256k1_fe_set_b32_mod(&u, ell64);
21+    secp256k1_fe_set_b32_mod(&t, ell64 + 32);
22     secp256k1_fe_normalize_var(&t);
23     secp256k1_ellswift_swiftec_var(&p, &u, &t);
24     secp256k1_pubkey_save(pubkey, &p);
25@@ -562,10 +561,8 @@ int secp256k1_ellswift_xdh(const secp256k1_context *ctx, unsigned char *output,
26 
27     /* Load remote public key (as fraction). */
28     theirs64 = party ? ell_a64 : ell_b64;
29-    secp256k1_fe_set_b32(&u, theirs64);
30-    secp256k1_fe_normalize_var(&u);
31-    secp256k1_fe_set_b32(&t, theirs64 + 32);
32-    secp256k1_fe_normalize_var(&t);
33+    secp256k1_fe_set_b32_mod(&u, theirs64);
34+    secp256k1_fe_set_b32_mod(&t, theirs64 + 32);
35     secp256k1_ellswift_xswiftec_frac_var(&xn, &xd, &u, &t);
36 
37     /* Load private key (using one if invalid). */
38diff --git a/src/modules/ellswift/tests_impl.h b/src/modules/ellswift/tests_impl.h
39index 95ff51cd..1cc14f7b 100644
40--- a/src/modules/ellswift/tests_impl.h
41+++ b/src/modules/ellswift/tests_impl.h
42@@ -285,7 +285,8 @@ void run_ellswift_tests(void) {
43          * because the "hasher" function we use here ignores the ell arguments. */
44         ret = secp256k1_ellswift_xdh(CTX, share32, ell64, ell64, sec32, i & 1, &ellswift_xdh_hash_x32, NULL);
45         CHECK(ret);
46-        secp256k1_fe_set_b32(&share_x, share32);
47+        (void)secp256k1_fe_set_b32_limit(&share_x, share32); /* no overflow is possible */
48+        secp256k1_fe_verify(&share_x);
49         /* Compute seckey*pubkey directly. */
50         secp256k1_ecmult(&resj, &decj, &sec, NULL);
51         secp256k1_ge_set_gej(&res, &resj);

sipa cross-referenced this on May 12, 2023 from issue BIP324 tracking issue by sipa

in src/modules/ellswift/main_impl.h:505 in 4c758e426e outdated

494@@ -495,6 +495,53 @@ int secp256k1_ellswift_decode(const secp256k1_context *ctx, secp256k1_pubkey *pu
495     return 1;
496 }
497 
498+static int ellswift_xdh_hash_function_prefix(unsigned char *output, const unsigned char *x32, const unsigned char *ell_a64, const unsigned char *ell_b64, void *data) {
499+    secp256k1_sha256 sha;
500+
501+    (void)data;

stratospher commented at 8:56 am on May 12, 2023:

4c758e4: noticed this (void)variable; pattern used in many files - this seems to be done when the variable isn’t used later on in the function. but data is used later on in the function here. curious to know what this statement actually does?

sipa commented at 8:30 pm on May 14, 2023:

It’s a standard pattern to silence the compiler’s “variable may be unused” warning; it has no actual effect on the compiled code. In this case, it’s because we intentionally ignore a variable.

stratospher commented at 3:21 pm on May 17, 2023:

interesting! but data is being used 2 lines below?

stratospher commented at 6:55 pm on May 17, 2023:

btw, there’s another unresolved question in the reply thread here.

sipa commented at 7:02 pm on May 17, 2023:

Oops, I missed this.

The (void)data; line must have been a leftover from before the change to not sort the inputs in the prefix hashers. Fixed now.

in src/modules/ellswift/tests_impl.h:248 in 6048c780b2 outdated

243+        secp256k1_ellswift_decode(CTX, &pub, ell64);
244+        secp256k1_pubkey_load(CTX, &dec, &pub);
245+        secp256k1_gej_set_ge(&decj, &dec);
246+        /* Compute the X coordinate of seckey*pubkey using ellswift_xdh. Note that we
247+         * pass ell64 as claimed (but incorrect) encoding for sec32 here; this works
248+         * because the "hasher" function we use here ignores the ell arguments. */

stratospher commented at 9:05 am on May 12, 2023:

6048c78: micro nit: s/ell/ell64

sipa commented at 8:38 pm on May 14, 2023:

Fixed.

sipa force-pushed on May 14, 2023

in src/bench.c:227 in 54107dbd90 outdated

220@@ -208,6 +221,15 @@ int main(int argc, char** argv) {
221     }
222 #endif
223 
224+#ifndef ENABLE_MODULE_ELLSWIFT
225+    if (have_flag(argc, argv, "ellswift") || have_flag(argc, argv, "ellswift_encode") || have_flag(argc, argv, "ellswift_decode") ||
226+        have_flag(argc, argv, "encode") || have_flag(argc, argv, "decode")) {
227+        fprintf(stderr, "./bench: ElligatorSwift smodule not enabled.\n");

stratospher commented at 5:21 am on May 16, 2023:

54107db: nit: s/smodule/module

sipa commented at 3:57 pm on May 17, 2023:

Fixed.

in src/bench.c:226 in 54107dbd90 outdated

220@@ -208,6 +221,15 @@ int main(int argc, char** argv) {
221     }
222 #endif
223 
224+#ifndef ENABLE_MODULE_ELLSWIFT
225+    if (have_flag(argc, argv, "ellswift") || have_flag(argc, argv, "ellswift_encode") || have_flag(argc, argv, "ellswift_decode") ||
226+        have_flag(argc, argv, "encode") || have_flag(argc, argv, "decode")) {

stratospher commented at 5:25 am on May 16, 2023:

54107db: “ellswift_keygen” and “ellswift_ecdh” too?

sipa commented at 3:57 pm on May 17, 2023:

Done.

in src/modules/ellswift/bench_impl.h:96 in 54107dbd90 outdated

91+void run_ellswift_bench(int iters, int argc, char **argv) {
92+    bench_ellswift_data data;
93+    int d = argc == 1;
94+
95+    /* create a context with signing capabilities */
96+    data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN);

stratospher commented at 10:13 am on May 16, 2023:

54107db: code comments say this is a deprecated context flag. should it be SECP256K1_CONTEXT_NONE instead?

sipa commented at 3:58 pm on May 17, 2023:

Done.

in src/modules/ellswift/main_impl.h:409 in 231bb7324f outdated

406+    VERIFY_CHECK(ctx != NULL);
407+    ARG_CHECK(ell64 != NULL);
408+    ARG_CHECK(pubkey != NULL);
409+    ARG_CHECK(rnd32 != NULL);
410+
411+    if (secp256k1_pubkey_load(ctx, &p, pubkey)) {

stratospher commented at 8:52 am on May 17, 2023:

231bb73: when does sizeof(secp256k1_ge_storage) != 64 happen inside secp256k1_pubkey_load?

(normalisation happens when size=64 but not when size!=64. and we need normalisation here)

sipa commented at 4:03 pm on May 17, 2023:

Interesting!

I believe the practical answer to “when does sizeof(secp256k1_ge_storage) != 64 happen?” is “Never”. It’s there because there is no guarantee about alignment requirements (or even sizes of types like uint64_t) in compilers, which may cause secp256k1_ge_storage to be bigger than just the sum of the data sizes. However, it’s unlikely that we’ll ever hit such a compiler.

To prepare for that, perhaps we want a normalize call inside secp256k1_pubkey_load, so that this cost is not born by the callers of that function (given that it’s unlikely to matter for real environments).

stratospher commented at 6:53 pm on May 17, 2023:

nice, fascinated by the level of details!

real-or-random commented at 11:02 am on June 15, 2023:

We should keep track of this.

To prepare for that, perhaps we want a normalize call inside secp256k1_pubkey_load, so that this cost is not born by the callers of that function (given that it’s unlikely to matter for real environments).

Yes, we want this. There’s even a bug currently in secp256k1_pubkey_load because the ARG_CHECK at the end of the function assumes normalization. @stratospher Interested in opening a PR to add the normalization call to secp256k1_pubkey_load?

stratospher commented at 7:07 pm on June 15, 2023:

yes! opened 1349.

in src/modules/ellswift/main_impl.h:466 in 70d80aef2f outdated

461@@ -462,6 +462,7 @@ int secp256k1_ellswift_create(const secp256k1_context *ctx, unsigned char *ell64
462 
463     /* Compute (affine) public key */
464     ret = secp256k1_ec_pubkey_create_helper(&ctx->ecmult_gen_ctx, &seckey_scalar, &p, seckey32);
465+    secp256k1_declassify(ctx, &p, sizeof(p)); /* not constant time in produced pubkey */

stratospher commented at 3:15 pm on May 17, 2023:

70d80ae: why don’t variables in the ellswift_xdh code which interact with private key not use secp256k1_declassify? i don’t understand the context for what kind of memory needs to be marked as not secret here.

sipa commented at 4:17 pm on May 17, 2023:

In the ctime tests, any computation that depends on a marked-secret variable will get marked as secret as well (automatically). Passing marked-secret variable to functions that branch or make memory accesses dependent on them is illegal.

So in short, declassify needs to happen when we have a variable that is:

(1) Automatically marked a secret (because of a dependency on secret ones). If not, declassify has no effect.
(2) Isn’t actually secret (in the sense that we’re ok with leaking it to attackers). If not, declassify risks actually letting a relevant leak go undetected.
(3) Is used as input to a non-constant time function. If not, it’s not leaked anyway, and it being classified or not doesn’t matter.

In this code that is the case:

(1) The public key is computed as a function of the provided private key (which is secret) so it gets automatically marked as secret too.
(2) The public key is obviously not actually secret - it’s a public key, and we’ll likely even send it over the wire in a ellswift/ecdh use case.
(3) The ellswift encoding function is not constant time in the input X and Y coordinates, so we’d hit a violation if we didn’t declassify.

In secp256k1_ellswift_xdh, lots of variables are secret:

The secret key (because duh)
The shared X coordinate px that comes out of secp256k1_ecmult_const_xonly, because it depends on the secret key, and it shouldn’t be declassified because it’s actually secret (attacker could figure out the shared secret based on it).
The shared secret that comes out of the hash function.

It works, because all the functions operating on these secret variables are actually constant time in them (and have to be, because they’re designed to operate on secrets).

stratospher commented at 6:53 pm on May 17, 2023:

thanks for the detailed explanation! understood when declassify needs to be used now.

sipa force-pushed on May 17, 2023

in include/secp256k1_ellswift.h:163 in 231bb7324f outdated

145+ *  In:      ell_a64:   pointer to the 64-byte encoded public key of party A
146+ *                      (will not be NULL)
147+ *           ell_b64:   pointer to the 64-byte encoded public key of party B
148+ *                      (will not be NULL)
149+ *           seckey32:  a pointer to the 32-byte secret key corresponding to
150+ *                      ours64 (the correspondence is not checked)

stratospher commented at 5:17 am on May 21, 2023:

ad74020: ours64 needs to be updated too.

sipa commented at 1:31 pm on June 17, 2023:

Done.

sipa commented at 12:39 pm on May 25, 2023: contributor

It seems that some of the changes to the writeup I made two weeks ago to be more explicit about all the edge cases are specific to a=0 curves. I’ll look over them again.

in CMakeLists.txt:76 in 614509cbc6 outdated

70@@ -71,6 +71,12 @@ if(SECP256K1_ENABLE_MODULE_EXTRAKEYS)
71   add_compile_definitions(ENABLE_MODULE_EXTRAKEYS=1)
72 endif()
73 
74+option(SECP256K1_ENABLE_MODULE_ELLSWIFT "Enable ElligatorSwift module." ON)
75+if(SECP256K1_ENABLE_MODULE_ELLSWIFT)
76+  add_definitions(-DENABLE_MODULE_ELLSWIFT=1)

theuni commented at 3:20 pm on May 25, 2023:

I’m assuming this is older than our add_compile_definitions switch-over. Mind updating it to match?

sipa commented at 5:42 pm on May 31, 2023:

Fixed.

theuni commented at 3:24 pm on May 25, 2023: contributor

Quick glimpse at the buildsystem… changes look good to me.

sipa force-pushed on May 25, 2023

sipa commented at 8:41 pm on May 25, 2023: contributor

Made these changes to the doc:

 0--- a/doc/ellswift.md
 1+++ b/doc/ellswift.md
 2@@ -327,14 +327,13 @@ $t$ value for multiple $c$ inputs (thereby biasing that encoding):
 3     This cannot occur in the $x_1$ or $x_2$ branches, as it would trigger the $g(-u-x)$ is square condition.
 4     A similar concern for $w = -w$ does not exist, as $w=0$ is already impossible in both branches: in the first
 5     it requires $g(u)=0$ which is already outlawed on even-ordered curves and impossible on others; in the second it would trigger division by zero.
 6-* In the implementation of $P_u^{'-1}$, special cases can occur.
 7-  * For $a=0$ curves, $u=0$ and $t=0$ need to be avoided as they would trigger division by zero in the decoder.
 8-    The latter is only possible when $g(u)=0$ and can thus only occur on even-ordered curves.
 9-  * For $a \neq 0$ curves, $h(u)t^2 = -1$ needs to be avoided as it would trigger division by zero in the decoder.
10-  * Also for $a \neq 0$ curves, if $w(u/2 + v) = X_0(u)$ but $w/2 \neq Y_0(u)$, no $t$ exists.
11+* Curve-specific special cases also exist that need to be rejected, because they result in $(u,t)$ which is invalid to the decoder, or because of division by zero in the encoder:
12+  * For $a=0$ curves, when $u=0$ or when $t=0$. The latter can only be reached by the encoder when $g(u)=0$, which requires an even-ordered curve.
13+  * For $a \neq 0$ curves, when $X_0(u)=0$, when $h(u)t^2 = -1$, or when $2w(u + 2v) = 2X_0(u)$ while also either $w \neq 2Y_0(u)$ or $h(u)=0$.
14 
15 **Define** a version of $G_{c,u}(x)$ which deals with all these cases:
16-* If $u=0$, return $\bot.$
17+* If $a=0$ and $u=0$, return $\bot.$
18+* If $a \neq 0$ and $X_0(u)=0$, return $\bot.$
19 * If $c \in \\{0, 1, 4, 5\\}:$
20   * If $g(u) = 0$ or $g(x) = 0$, return $\bot$ (even curves only).
21   * If $g(-u-x)$ is square, return $\bot.$
22@@ -347,15 +346,19 @@ $t$ value for multiple $c$ inputs (thereby biasing that encoding):
23   * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
24   * Let $v = (r/s - u)/2.$
25 * Let $w = \sqrt{s}$; return $\bot$ if not square.
26+* If $a \neq 0$ and $w(u+2v) = 2X_0(u)$ and either $w \neq 2Y_0(u)$ or $h(u) = 0$, return $\bot.$
27 * Depending on $c:$
28-  * If $c \in \\{0, 2\\}:$ return $P_u^{'-1}(v, w).$
29-  * If $c \in \\{1, 3\\}:$ return $P_u^{'-1}(-u-v, w).$
30-  * If $c \in \\{4, 6\\}:$ return $P_u^{'-1}(v, -w).$
31-  * If $c \in \\{5, 7\\}:$ return $P_u^{'-1}(-u-v, -w).$
32+  * If $c \in \\{0, 2\\}$, let $t = P_u^{'-1}(v, w).$
33+  * If $c \in \\{1, 3\\}$, let $t = P_u^{'-1}(-u-v, w).$
34+  * If $c \in \\{4, 6\\}$, let $t = P_u^{'-1}(v, -w).$
35+  * If $c \in \\{5, 7\\}$, let $t = P_u^{'-1}(-u-v, -w).$
36+* If $a=0$ and $t=0$, return $\bot$ (even curves only).
37+* If $a \neq 0$ and $h(u)t^2 = -1$, return $\bot.$
38+* Return $t.$
39 
40 Given any $u$, using this algorithm over all $x$ and $c$ values, every $t$ value will be reached exactly once,
41 for an $x$ for which $F_u(t) = x$ holds, except for these cases that will not be reached:
42-* (Obviously) all cases where $P_u(t)$ is not defined:
43+* All cases where $P_u(t)$ is not defined:
44   * For $a=0$ curves, when $u=0$, $t=0$, or $g(u) = -t^2.$
45   * For $a \neq 0$ curves, when $h(u)t^2 = -1$, $X_0(u) = 0$, or $Y_0(u) (1 - h(u) t^2) = 2X_0(u)t.$
46 * When $g(u)=0$, the potentially many $t$ values that decode to an $x$ satisfying $g(x)=0$ using the $x_2$ formula. These were excluded by the $g(u)=0$ condition in the $c \in \\{0, 1, 4, 5\\}$ branch.

sipa force-pushed on May 26, 2023

sipa force-pushed on May 31, 2023

sipa commented at 5:47 pm on May 31, 2023: contributor

Rebased, and addressed @theuni’s comments. Ready for more review, I think.

hebasto commented at 3:20 pm on June 1, 2023: member

ACK fe26466f040a6ddc242cea54037c2c4cd85a0bc9 on changes in Autotools, CMake and CI related stuff.

in src/modules/ellswift/main_impl.h:261 in fe26466f04 outdated

258+
259+        /* If s=0, fail. */
260+        if (secp256k1_fe_normalizes_to_zero_var(&s)) return 0;
261+
262+        /* If s is not square, fail. */
263+        if (!secp256k1_fe_is_square_var(&s)) return 0;

real-or-random commented at 5:29 pm on June 14, 2023:

Could we drop the s == 0 check here? I assume it happens with negligible probability on honest inputs, and it’s subsumed by the is_square(q) check below.

If no:

Do we want to add an EXPECT to the s == 0 check? (Not sure if it changes much, but I saw you did the same above in the other function.)
Do we want to swap these checks for an earlier return?

sipa commented at 9:34 pm on June 14, 2023:

Could we drop the s == 0 check here? I assume it happens with negligible probability on honest inputs

That’s a good question in general. The current code is written to deal perfectly with all possible inputs, because that’s what matches my exhaustive analysis on small curves. You’re right that this specific s=0 case can only happen with negligible probability on actual secp256k1 (it requires u=x, so with uniformly random u a probability of 1/2^256).

Other than some cryptographically-unreachable code, this one does have a unit test exercising it though (an internal one; the API can’t reach it).

and it’s subsumed by the is_square(q) check below.

That’s not correct. The tests fail if you comment it out.

sipa commented at 9:52 pm on June 14, 2023:

If no:

Do we want to add an EXPECT to the s == 0 check? (Not sure if it changes much, but I saw you did the same above in the other function.)

Do we want to swap these checks for an earlier return?

I’ve made these changes (and moved the s==0 check even further, so that other more-likely-to-fail check go before it).

real-or-random commented at 9:32 am on June 15, 2023:

and it’s subsumed by the is_square(q) check below.

That’s not correct. The tests fail if you comment it out.

Oh. When I wrote this, I had assumed, for a moment, that we abort if q is a square. But we abort if it’s not a square.

real-or-random commented at 12:18 pm on June 15, 2023:

I’ve made these changes (and moved the s==0 check even further, so that other more-likely-to-fail check go before it).

Perhaps update the pseudocode in the comment (and in the md?) accordingly.

sipa commented at 1:33 pm on June 17, 2023:

Done.

in src/modules/ellswift/main_impl.h:281 in fe26466f04 outdated

276+        if (!secp256k1_fe_is_square_var(&q)) return 0;
277+        ret = secp256k1_fe_sqrt(&r, &q); /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */
278+        VERIFY_CHECK(ret);
279+
280+        /* If (c & 1) = 1 and r = 0, fail. */
281+        if ((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r)) return 0;

real-or-random commented at 5:29 pm on June 14, 2023:

Add EXCEPT here?

sipa commented at 9:52 pm on June 14, 2023:

Done.

in src/modules/ellswift/main_impl.h:275 in fe26466f04 outdated

273+        secp256k1_fe_add(&q, &g); /* q = 4*(u^3+7)+3*s*u^2 */
274+        secp256k1_fe_mul(&q, &q, &s); /* q = s*(4*(u^3+7)+3*u^2*s) */
275+        secp256k1_fe_negate(&q, &q, 1); /* q = -s*(4*(u^3+7)+3*u^2*s) */
276+        if (!secp256k1_fe_is_square_var(&q)) return 0;
277+        ret = secp256k1_fe_sqrt(&r, &q); /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */
278+        VERIFY_CHECK(ret);

real-or-random commented at 5:32 pm on June 14, 2023:

I think you could drop the is_square check and simply use the return value of fe_sqrt. (Apparently, the entire return value of fe_sqrt is undocumented, this should be fixed.)

If you agree but feel that this belongs to a separate PR, I suggest opening an issue about the docs and mentioning this possible optimization,

sipa commented at 9:36 pm on June 14, 2023:

We could, but that’s actually slower. The is_square_var should trigger for 50% of inputs, and an is_square_var takes less than half the time of an sqrt.

real-or-random commented at 9:51 am on June 15, 2023:

Makes sense. See #1347 for the missing docs.

in src/modules/ellswift/main_impl.h:369 in fe26466f04 outdated

364+#ifdef VERIFY
365+        VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&u));
366+#endif
367+        /* Find a remainder t, and return it if found. */
368+        if (secp256k1_ellswift_xswiftec_inv_var(t, x, &u, branch)) {
369+            secp256k1_fe_normalize_var(t);

real-or-random commented at 5:35 pm on June 14, 2023:

This line can be dropped (or better, replaced by an assertion), as the last operation in secp256k1_ellswift_xswiftec_inv_var is a mul.

sipa commented at 9:45 pm on June 14, 2023:

The only caller, secp256k1_ellswift_elligatorswift_var, calls secp256k1_fe_is_odd(t) on this value, which requires full normalization (not just magnitude 1). The normalize call could be moved there, but it needs to be somewhere.

sipa commented at 9:52 pm on June 14, 2023:

Done, and moved the normalize_var call to secp256k1_ellswift_elligatorswift_var.

real-or-random commented at 9:38 am on June 15, 2023:

Yep, I missed that we need full normalization.

real-or-random commented at 5:36 pm on June 14, 2023: contributor

Here are some minor remarks about performance.

Continuing to go through the main parts of the code. I’ll probably also follow up with a fixup commit with some nits in the code comments later this week.

sipa force-pushed on Jun 14, 2023

sipa commented at 9:55 pm on June 14, 2023: contributor

Made the following changes:

 0--- a/src/modules/ellswift/main_impl.h
 1+++ b/src/modules/ellswift/main_impl.h
 2@@ -256,9 +256,6 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
 3         s = m; /* s = -u */
 4         secp256k1_fe_add(&s, &x); /* s = x-u */
 5 
 6-        /* If s=0, fail. */
 7-        if (secp256k1_fe_normalizes_to_zero_var(&s)) return 0;
 8-
 9         /* If s is not square, fail. */
10         if (!secp256k1_fe_is_square_var(&s)) return 0;
11 
12@@ -278,7 +275,10 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
13         VERIFY_CHECK(ret);
14 
15         /* If (c & 1) = 1 and r = 0, fail. */
16-        if ((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r)) return 0;
17+        if (EXPECT((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r), 0)) return 0;
18+
19+        /* If s=0, fail. */
20+        if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&s), 0)) return 0;
21 
22         /* Let v=(r/s-u)/2. */
23         secp256k1_fe_inv_var(&v, &s); /* v=1/s [cannot be div by 0] */
24@@ -360,15 +360,12 @@ static void secp256k1_ellswift_xelligatorswift_var(unsigned char *u32, secp256k1
25         secp256k1_fe_set_b32_mod(&u, u32);
26         /* Since u is the output of a hash, it should practically never be 0. We could apply the
27          * u=0 to u=1 correction here too to deal with that case still, but it's such a low
28-         * probability that we do not bother. */
29+         * probability event that we do not bother. */
30 #ifdef VERIFY
31         VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&u));
32 #endif
33         /* Find a remainder t, and return it if found. */
34-        if (secp256k1_ellswift_xswiftec_inv_var(t, x, &u, branch)) {
35-            secp256k1_fe_normalize_var(t);
36-            break;
37-        }
38+        if (EXPECT(secp256k1_ellswift_xswiftec_inv_var(t, x, &u, branch), 0)) break;
39     }
40 }
41 
42@@ -380,6 +377,7 @@ static void secp256k1_ellswift_xelligatorswift_var(unsigned char *u32, secp256k1
43  */
44 static void secp256k1_ellswift_elligatorswift_var(unsigned char *u32, secp256k1_fe *t, const secp256k1_ge *p, const secp256k1_sha256 *hasher) {
45     secp256k1_ellswift_xelligatorswift_var(u32, t, &p->x, hasher);
46+    secp256k1_fe_normalize_var(t);
47     if (secp256k1_fe_is_odd(t) != secp256k1_fe_is_odd(&p->y)) {
48         secp256k1_fe_negate(t, t, 1);
49         secp256k1_fe_normalize_var(t);

in src/modules/ellswift/main_impl.h:418 in d710e6b900 outdated

413+
414+        /* Set up hasher state; the used RNG is H(pubkey || "\x00"*31 || rnd32 || cnt++), using BIP340 tagged
415+         * hash with tag "secp256k1_ellswift_encode". */
416+        secp256k1_ellswift_sha256_init_encode(&hash);
417+        p64[0] = 0x02 ^ secp256k1_fe_is_odd(&p.y);
418+        secp256k1_fe_get_b32(p64 + 1, &p.x);

real-or-random commented at 11:05 am on June 15, 2023:

Do you think it’s better to call secp256k1_eckey_pubkey_serialize here? Or even the API facing secp256k1_ec_pubkey_serialize, which also takes care of loading the pubkey?

sipa commented at 1:33 pm on June 17, 2023:

Good call. I’ve made it call secp256k1_eckey_pubkey_serialize. Using the API facing one would not be convenient, as we do need the secp256k1_ge form further down in the function.

in src/modules/ellswift/main_impl.h:430 in d710e6b900 outdated

422+        /* Compute ElligatorSwift encoding and construct output. */
423+        secp256k1_ellswift_elligatorswift_var(ell64, &t, &p, &hash); /* puts u in ell64[0..32] */
424+        secp256k1_fe_get_b32(ell64 + 32, &t); /* puts t in ell64[32..64] */
425+        return 1;
426+    }
427+    /* Only returned in case the provided pubkey is invalid. */

real-or-random commented at 11:12 am on June 15, 2023:

0    /* Only reached in case the provided pubkey is invalid. */
1    memset(ell64, 0, 64);

sipa commented at 1:29 pm on June 17, 2023:

Done.

real-or-random commented at 12:38 pm on June 20, 2023:

I think you overlooked this one. My primary suggestion was to add a call to memset, the comment change was rather a by-product thereof. :)

sipa commented at 3:25 pm on June 20, 2023:

Done.

in include/secp256k1_ellswift.h:85 in d710e6b900 outdated

80+ *  The data argument is ignored. */
81+SECP256K1_API_VAR const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_xdh_hash_function_bip324;
82+
83+/** Construct a 64-byte ElligatorSwift encoding of a given pubkey.
84+ *
85+ *  Returns: 1 when pubkey is valid.

real-or-random commented at 12:05 pm on June 15, 2023:

0 *  Returns: 1 always.

(There are no invalid pubkeys in terms of the API, similar to #1341 )

sipa commented at 1:31 pm on June 17, 2023:

Done.

in include/secp256k1_ellswift.h:105 in d710e6b900 outdated

 96+ * uniform. The randomness in rnd32 must not be a deterministic function of
 97+ * the pubkey (it can be derived from the private key, though).
 98+ *
 99+ * This function runs in variable time.
100+ */
101+SECP256K1_API int secp256k1_ellswift_encode(

real-or-random commented at 12:12 pm on June 15, 2023:

Do we want to add a warning to make sure we can swap the RNG? Suggestion:

“It is not guaranteed that the computed ell64 is stable across versions of the library, even if all arguments to this function including rnd32 are the same.”

If yes, this should be added to secp256k1_ellswift_create too

sipa commented at 1:30 pm on June 17, 2023:

Done.

in include/secp256k1_ellswift.h:130 in d710e6b900 outdated

121+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
122+
123+/** Compute an ElligatorSwift public key for a secret key.
124+ *
125+ *  Returns: 1: secret was valid, public key was stored.
126+ *           0: secret was invalid, try again.

real-or-random commented at 12:14 pm on June 15, 2023:

(Not this PR, I see this is copied from the other docs:) Ha, we should change this, “try again” is terrible advice. Hey, if your RNG outputs 32 zeroes, then don’t worry, just call it in a loop. :D

bitcoinfinancier approved

sipa force-pushed on Jun 17, 2023

sipa commented at 1:27 pm on June 17, 2023: contributor

Made these changes:

  0diff --git a/doc/ellswift.md b/doc/ellswift.md
  1index 9a1672b7..7fbb7c17 100644
  2--- a/doc/ellswift.md
  3+++ b/doc/ellswift.md
  4@@ -341,9 +341,9 @@ $t$ value for multiple $c$ inputs (thereby biasing that encoding):
  5   * Let $v = x.$
  6 * Otherwise, when $c \in \\{2, 3, 6, 7\\}:$
  7   * Let $s = x-u.$
  8-  * If $s = 0$, return $\bot.$
  9   * Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
 10   * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
 11+  * If $s = 0$, return $\bot.$
 12   * Let $v = (r/s - u)/2.$
 13 * Let $w = \sqrt{s}$; return $\bot$ if not square.
 14 * If $a \neq 0$ and $w(u+2v) = 2X_0(u)$ and either $w \neq 2Y_0(u)$ or $h(u) = 0$, return $\bot.$
 15@@ -377,9 +377,9 @@ Specialized for odd-ordered $a=0$ curves:
 16   * Let $v = x.$
 17 * Otherwise, when $c \in \\{2, 3, 6, 7\\}:$
 18   * Let $s = x-u.$
 19-  * If $s = 0$, return $\bot.$
 20   * Let $r = \sqrt{-s(4(u^3 + b) + 3su^2)}$; return $\bot$ if not square.
 21   * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
 22+  * If $s = 0$, return $\bot.$
 23   * Let $v = (r/s - u)/2.$
 24 * Let $w = \sqrt{s}$; return $\bot$ if not square.
 25 * Depending on $c:$
 26diff --git a/include/secp256k1_ellswift.h b/include/secp256k1_ellswift.h
 27index 3d73c5f3..b0284d2b 100644
 28--- a/include/secp256k1_ellswift.h
 29+++ b/include/secp256k1_ellswift.h
 30@@ -82,7 +82,7 @@ SECP256K1_API_VAR const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_
 31 
 32 /** Construct a 64-byte ElligatorSwift encoding of a given pubkey.
 33  *
 34- *  Returns: 1 when pubkey is valid.
 35+ *  Returns: 1 always.
 36  *  Args:    ctx:        pointer to a context object
 37  *  Out:     ell64:      pointer to a 64-byte array to be filled
 38  *  In:      pubkey:     a pointer to a secp256k1_pubkey containing an
 39@@ -96,6 +96,10 @@ SECP256K1_API_VAR const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_
 40  * uniform. The randomness in rnd32 must not be a deterministic function of
 41  * the pubkey (it can be derived from the private key, though).
 42  *
 43+ * It is not guaranteed that the computed encoding is stable across versions
 44+ * of the library, even if all arguments to this function (including rnd32)
 45+ * are the same.
 46+ *
 47  * This function runs in variable time.
 48  */
 49 SECP256K1_API int secp256k1_ellswift_encode(
 50@@ -136,10 +140,14 @@ SECP256K1_API int secp256k1_ellswift_decode(
 51  * it is optional (and does result in encodings that are indistinguishable from
 52  * uniform even without any auxrnd32). It differs from the (mandatory) rnd32
 53  * argument to secp256k1_ellswift_encode in this regard.
 54-
 55+ *
 56  * This function can be used instead of calling secp256k1_ec_pubkey_create
 57  * followed by secp256k1_ellswift_encode. It is safer, as it uses the secret
 58  * key as entropy for the encoding (supplemented with auxrnd32, if provided).
 59+ *
 60+ * Like secp256k1_ellswift_encode, this function does not guaranteed that the
 61+ * computed encoding is stable across versions of the library, even if all
 62+ * arguments (including auxrnd32) are the same.
 63  */
 64 SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ellswift_create(
 65     const secp256k1_context *ctx,
 66@@ -159,10 +167,11 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ellswift_create(
 67  *                      (will not be NULL)
 68  *           ell_b64:   pointer to the 64-byte encoded public key of party B
 69  *                      (will not be NULL)
 70- *           seckey32:  a pointer to the 32-byte secret key corresponding to
 71- *                      ours64 (the correspondence is not checked)
 72+ *           seckey32:  a pointer to our 32-byte secret key
 73  *           party:     boolean indicating which party we are: zero if we are
 74- *                      party A, non-zero if we are party B
 75+ *                      party A, non-zero if we are party B. seckey32 must be
 76+ *                      the private key corresponding to that party's ell_?64.
 77+ *                      This correspondence is not checked.
 78  *           hashfp:    pointer to a hash function.
 79  *           data:      arbitrary data pointer passed through to hashfp.
 80  *
 81diff --git a/src/modules/ellswift/main_impl.h b/src/modules/ellswift/main_impl.h
 82index 44e622aa..c37379e3 100644
 83--- a/src/modules/ellswift/main_impl.h
 84+++ b/src/modules/ellswift/main_impl.h
 85@@ -8,6 +8,7 @@
 86 
 87 #include "../../../include/secp256k1.h"
 88 #include "../../../include/secp256k1_ellswift.h"
 89+#include "../../eckey.h"
 90 #include "../../hash.h"
 91 
 92 /** c1 = (sqrt(-3)-1)/2 */
 93@@ -175,10 +176,10 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
 94      *   - Let v=x.
 95      * - If (c & 2) = 2:
 96      *   - Let s=x-u.
 97-     *   - If s=0, fail.
 98      *   - If s is not square, fail.
 99      *   - Let r=sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist.
100      *   - If (c & 1) = 1 and r = 0, fail.
101+     *   - If s=0, fail.
102      *   - Let v=(r/s-u)/2.
103      * - Let w=sqrt(s).
104      * - If (c & 5) = 0: return -w*(c3*u + v)
105@@ -409,13 +410,15 @@ int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64
106     if (secp256k1_pubkey_load(ctx, &p, pubkey)) {
107         secp256k1_fe t;
108         unsigned char p64[64] = {0};
109+        size_t ser_size;
110+        int ser_ret;
111         secp256k1_sha256 hash;
112 
113-        /* Set up hasher state; the used RNG is H(pubkey || "\x00"*31 || rnd32 || cnt++), using BIP340 tagged
114-         * hash with tag "secp256k1_ellswift_encode". */
115+        /* Set up hasher state; the used RNG is H(pubkey || "\x00"*31 || rnd32 || cnt++), using
116+         * BIP340 tagged hash with tag "secp256k1_ellswift_encode". */
117         secp256k1_ellswift_sha256_init_encode(&hash);
118-        p64[0] = 0x02 ^ secp256k1_fe_is_odd(&p.y);
119-        secp256k1_fe_get_b32(p64 + 1, &p.x);
120+        ser_ret = secp256k1_eckey_pubkey_serialize(&p, p64, &ser_size, 1);
121+        VERIFY_CHECK(ser_ret && ser_size == 33);
122         secp256k1_sha256_write(&hash, p64, sizeof(p64));
123         secp256k1_sha256_write(&hash, rnd32, 32);
124 
125@@ -424,7 +427,7 @@ int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64
126         secp256k1_fe_get_b32(ell64 + 32, &t); /* puts t in ell64[32..64] */
127         return 1;
128     }
129-    /* Only returned in case the provided pubkey is invalid. */
130+    /* Only reached in case the provided pubkey is invalid. */
131     return 0;
132 }

sipa force-pushed on Jun 17, 2023

in src/modules/ellswift/tests_impl.h:338 in 4860ab0e22 outdated

333+        CHECK(ret);
334+
335+        /* Compute the shared secret both ways and compare with each other. */
336+        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32b, 1, hash_function, data);
337+        CHECK(ret);
338+        ret = secp256k1_ellswift_xdh(CTX, share32b, ell64a, ell64b, sec32a, 0, hash_function, data);

jonasnick commented at 1:54 pm on June 17, 2023:

Shouldn’t the first share be called share32b and the second share32a? Without this a few of the tests below don’t make sense.

If we change the names of the shares as suggested, we would also need to replace share32b with share32a in

0        ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b, sec32a_bad, 0, hash_function, data);
1        CHECK(!ret || secp256k1_memcmp_var(share32_bad, share32b, 32) != 0);

sipa commented at 5:35 pm on June 17, 2023:

@jonasnick I don’t think it matters, because share32a == share32b thoughout. Still, I’ve reworked these, and expanded them into performing all mutations on both sides.

sipa force-pushed on Jun 17, 2023

sipa commented at 5:34 pm on June 17, 2023: contributor

Made the following changes:

 0diff --git a/src/modules/ellswift/tests_impl.h b/src/modules/ellswift/tests_impl.h
 1index 1454cd6d..86ca0986 100644
 2--- a/src/modules/ellswift/tests_impl.h
 3+++ b/src/modules/ellswift/tests_impl.h
 4@@ -294,10 +294,10 @@ void run_ellswift_tests(void) {
 5     }
 6     /* Verify the joint behavior of secp256k1_ellswift_xdh */
 7     for (i = 0; i < 200 * COUNT; i++) {
 8-        unsigned char auxrnd32a[32], auxrnd32b[32], auxrnd32a_bad[32];
 9-        unsigned char sec32a[32], sec32b[32], sec32a_bad[32];
10+        unsigned char auxrnd32a[32], auxrnd32b[32], auxrnd32a_bad[32], auxrnd32b_bad[32];
11+        unsigned char sec32a[32], sec32b[32], sec32a_bad[32], sec32b_bad[32];
12         secp256k1_scalar seca, secb;
13-        unsigned char ell64a[64], ell64b[64], ell64a_bad[64];
14+        unsigned char ell64a[64], ell64b[64], ell64a_bad[64], ell64b_bad[64];
15         unsigned char share32a[32], share32b[32], share32_bad[32];
16         unsigned char prefix64[64];
17         secp256k1_ellswift_xdh_hash_function hash_function;
18@@ -327,33 +327,60 @@ void run_ellswift_tests(void) {
19         secp256k1_scalar_get_b32(sec32b, &secb);
20 
21         /* Construct ElligatorSwift-encoded public keys for those keys. */
22+        /* For A: */
23         ret = secp256k1_ellswift_create(CTX, ell64a, sec32a, auxrnd32a);
24         CHECK(ret);
25+        /* For B: */
26         ret = secp256k1_ellswift_create(CTX, ell64b, sec32b, auxrnd32b);
27         CHECK(ret);
28 
29         /* Compute the shared secret both ways and compare with each other. */
30-        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32b, 1, hash_function, data);
31+        /* For A: */
32+        ret = secp256k1_ellswift_xdh(CTX, share32a, ell64a, ell64b, sec32a, 0, hash_function, data);
33         CHECK(ret);
34-        ret = secp256k1_ellswift_xdh(CTX, share32b, ell64a, ell64b, sec32a, 0, hash_function, data);
35+        /* For B: */
36+        ret = secp256k1_ellswift_xdh(CTX, share32b, ell64a, ell64b, sec32b, 1, hash_function, data);
37         CHECK(ret);
38+        /* And compare: */
39         CHECK(secp256k1_memcmp_var(share32a, share32b, 32) == 0);
40 
41-        /* Verify that the shared secret doesn't match if public key encoding changes. */
42+        /* Verify that the shared secret doesn't match if other side's public key is incorrect. */
43+        /* For A (using a bad public key for B): */
44+        memcpy(ell64b_bad, ell64b, sizeof(ell64a_bad));
45+        secp256k1_testrand_flip(ell64b_bad, sizeof(ell64b_bad));
46+        ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b_bad, sec32a, 0, hash_function, data);
47+        CHECK(ret); /* Mismatching encodings don't get detected by secp256k1_ellswift_xdh. */
48+        CHECK(secp256k1_memcmp_var(share32_bad, share32a, 32) != 0);
49+        /* For B (using a bad public key for A): */
50         memcpy(ell64a_bad, ell64a, sizeof(ell64a_bad));
51         secp256k1_testrand_flip(ell64a_bad, sizeof(ell64a_bad));
52         ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a_bad, ell64b, sec32b, 1, hash_function, data);
53-        CHECK(ret); /* Invalid encodings don't get detected by secp256k1_ellswift_xdh. */
54+        CHECK(ret);
55         CHECK(secp256k1_memcmp_var(share32_bad, share32b, 32) != 0);
56 
57-        /* Verify that the shared secret doesn't match if the private key changes. */
58+        /* Verify that the shared secret doesn't match if the private key is incorrect. */
59+        /* For A: */
60         memcpy(sec32a_bad, sec32a, sizeof(sec32a_bad));
61         secp256k1_testrand_flip(sec32a_bad, sizeof(sec32a_bad));
62         ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b, sec32a_bad, 0, hash_function, data);
63+        CHECK(!ret || secp256k1_memcmp_var(share32_bad, share32a, 32) != 0);
64+        /* For B: */
65+        memcpy(sec32b_bad, sec32b, sizeof(sec32b_bad));
66+        secp256k1_testrand_flip(sec32b_bad, sizeof(sec32b_bad));
67+        ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b, sec32b_bad, 1, hash_function, data);
68         CHECK(!ret || secp256k1_memcmp_var(share32_bad, share32b, 32) != 0);
69 
70         if (hash_function != ellswift_xdh_hash_x32) {
71             /* Verify that the shared secret doesn't match when a different encoding of the same public key is used. */
72+            /* For A (changing B's public key): */
73+            memcpy(auxrnd32b_bad, auxrnd32b, sizeof(auxrnd32b_bad));
74+            secp256k1_testrand_flip(auxrnd32b_bad, sizeof(auxrnd32b_bad));
75+            ret = secp256k1_ellswift_create(CTX, ell64b_bad, sec32b, auxrnd32b_bad);
76+            CHECK(ret);
77+            ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b_bad, sec32a, 0, hash_function, data);
78+            CHECK(ret);
79+            CHECK(secp256k1_memcmp_var(share32_bad, share32a, 32) != 0);
80+            /* For B (changing A's public key): */
81             memcpy(auxrnd32a_bad, auxrnd32a, sizeof(auxrnd32a_bad));
82             secp256k1_testrand_flip(auxrnd32a_bad, sizeof(auxrnd32a_bad));
83             ret = secp256k1_ellswift_create(CTX, ell64a_bad, sec32a, auxrnd32a_bad);
84@@ -363,6 +390,11 @@ void run_ellswift_tests(void) {
85             CHECK(secp256k1_memcmp_var(share32_bad, share32b, 32) != 0);
86 
87             /* Verify that swapping sides changes the shared secret. */
88+            /* For A (claiming to be B): */
89+            ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b, sec32a, 1, hash_function, data);
90+            CHECK(ret);
91+            CHECK(secp256k1_memcmp_var(share32_bad, share32a, 32) != 0);
92+            /* For B (claiming to be A): */
93             ret = secp256k1_ellswift_xdh(CTX, share32_bad, ell64a, ell64b, sec32b, 0, hash_function, data);
94             CHECK(ret);
95             CHECK(secp256k1_memcmp_var(share32_bad, share32b, 32) != 0);

in src/modules/ellswift/main_impl.h:299 in 16d251380f outdated

294+
295+    /* Return logic. */
296+    if ((c & 5) == 0 || (c & 5) == 5) {
297+        secp256k1_fe_negate(&m, &m, 1); /* m = -w */
298+    }
299+    /* Now m = {w if c&5=0 or c&5=5; -w otherwise}. */

theStack commented at 0:19 am on June 18, 2023:

comment nit:

0    /* Now m = {-w if c&5=0 or c&5=5; w otherwise}. */

sipa commented at 1:06 am on June 18, 2023:

Done.

theStack commented at 0:32 am on June 18, 2023: contributor

Noticed that the commit message of 16d251380fb3e619ff7da0a983735ff78d301307 contains some typos/inaccuracies:

 0diff --git a/commitmsg.txt b/commitmsg.txt
 1index b1bd953..fadc3fe 100644
 2--- a/commitmsg.txt
 3+++ b/commitmsg.txt
 4@@ -12,11 +12,11 @@
 5     interpret them as field elements u and t. Then:
 6     * Let c=0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852.
 7     * Let u'=u unless u==0, in which case let u'=1.
 8-    * Let t'=t unless t==1, in which case let t'=1.
 9-    * Let t''=t unless u'^3 + + 7 + t'^2 == 0, in which case let t''=2*t'.
10+    * Let t'=t unless t==0, in which case let t'=1.
11+    * Let t''=t' unless u'^3 + 7 + t'^2 == 0, in which case let t''=2*t'.
12     * Let X=(u'^3 + 7 - t''^2)/(2*t'')
13     * Let Y=(u'^3 + 7 + t''^2)/(2*c*t''*u')
14-    * Let x be the first element out of [u+4*Y^2, (-X/Y-u)/2, (X/Y-u)/2] for which
15+    * Let x be the first element out of [u'+4*Y^2, (-X/Y-u')/2, (X/Y-u')/2] for which
16       x^3 + 7 is square (there will always be at least one).
17     * Let y be the square root of x^3 + 7 which has the same parity as t.
18     * Return the point with affine coordinates (x, y)

Could probably simply take the version of the decoding algorithm included in include/secp256k1_ellswift.h (or even completely remove it from the commit body, as it’s added to the header in the same commit anyways?).

sipa force-pushed on Jun 18, 2023

sipa commented at 1:06 am on June 18, 2023: contributor

Made this change:

 0--- a/src/modules/ellswift/main_impl.h
 1+++ b/src/modules/ellswift/main_impl.h
 2@@ -296,7 +296,7 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
 3     if ((c & 5) == 0 || (c & 5) == 5) {
 4         secp256k1_fe_negate(&m, &m, 1); /* m = -w */
 5     }
 6-    /* Now m = {w if c&5=0 or c&5=5; -w otherwise}. */
 7+    /* Now m = {-w if c&5=0 or c&5=5; w otherwise}. */
 8     secp256k1_fe_mul(&u, &u, c&1 ? &secp256k1_ellswift_c4 : &secp256k1_ellswift_c3);
 9     /* u = {c4 if c&1=1; c3 otherwise}*u */
10     secp256k1_fe_add(&u, &v); /* u = {c4 if c&1=1; c3 otherwise}*u + v */

sipa commented at 1:07 am on June 18, 2023: contributor

@theStack Thanks. I’ve dropped the scheme definition from the commit message. It’s well documented in the code, the .h file, and the .md document.

real-or-random referenced this in commit 30574f22ea on Jun 18, 2023

in include/secp256k1_ellswift.h:148 in 5e9b62c1a7 outdated

130+ *
131+ * This function can be used instead of calling secp256k1_ec_pubkey_create
132+ * followed by secp256k1_ellswift_encode. It is safer, as it uses the secret
133+ * key as entropy for the encoding (supplemented with auxrnd32, if provided).
134+ *
135+ * Like secp256k1_ellswift_encode, this function does not guaranteed that the

theStack commented at 10:53 pm on June 19, 2023:

0 * Like secp256k1_ellswift_encode, this function does not guarantee that the

sipa commented at 3:24 pm on June 20, 2023:

Done.

in src/modules/ellswift/bench_impl.h:97 in d4ec51cf0f outdated

92+    bench_ellswift_data data;
93+    int d = argc == 1;
94+
95+    /* create a context with signing capabilities */
96+    data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
97+    memset(data.rnd64, 11, sizeof(data.rnd64));

theStack commented at 10:55 pm on June 19, 2023:

seems like this can be removed, as the initialization happens in bench_ellswift_setup?

sipa commented at 3:24 pm on June 20, 2023:

Done.

theStack commented at 11:54 pm on June 19, 2023: contributor

Verified that the code in the decoding/encoding functions secp256k1_ellswift_xswiftec_frac_var and secp256k1_ellswift_xswiftec_inv_var match the algorithm written in comments each (https://github.com/sipa/secp256k1/blob/55efb1cb525c1b264c57c35203d1b83109948d5e/src/modules/ellswift/main_impl.h#L74-L84 and https://github.com/sipa/secp256k1/blob/55efb1cb525c1b264c57c35203d1b83109948d5e/src/modules/ellswift/main_impl.h#L170-L189). Still planning to do a pen-and-paper review for the algorithm simplifications steps / substitutions pointed out in secp256k1_ellswift_xswiftec_frac_var.

Left two nits below (unrelated to the functions above), regarding API doc and the ellswift benchmark.

real-or-random approved

real-or-random commented at 2:02 pm on June 20, 2023: contributor

ACK 55efb1cb525c1b264c57c35203d1b83109948d5e

Here’s a branch with some fixup comments, with commits prepared for git rebase --interactive --autosquash: https://github.com/real-or-random/secp256k1/tree/202206_ellswift_dh You are welcome to apply or reject; ACK anyway. My initial plan was to have only comment nits, but I found two further refinements on the way, see the commits there.

*edit: It’s probably clear to you, but I recommend first taking whatever fixup commits you want from my branch, and then addressing other review commits from @theStack here in order to minimize conflicts.

Add benchmark for key generation a597a5a9ce

Add functions to test if X coordinate is valid 79e5b2a8b8

sipa force-pushed on Jun 20, 2023

sipa commented at 3:10 pm on June 20, 2023: contributor

Squashed in @real-or-random’s fixups:

  0diff --git a/include/secp256k1_ellswift.h b/include/secp256k1_ellswift.h
  1index b0284d2b..d20fc0cc 100644
  2--- a/include/secp256k1_ellswift.h
  3+++ b/include/secp256k1_ellswift.h
  4@@ -60,11 +60,11 @@ extern "C" {
  5  *           data:       arbitrary data pointer that is passed through
  6  */
  7 typedef int (*secp256k1_ellswift_xdh_hash_function)(
  8-  unsigned char *output,
  9-  const unsigned char *x32,
 10-  const unsigned char *ell_a64,
 11-  const unsigned char *ell_b64,
 12-  void *data
 13+    unsigned char *output,
 14+    const unsigned char *x32,
 15+    const unsigned char *ell_a64,
 16+    const unsigned char *ell_b64,
 17+    void *data
 18 );
 19 
 20 /** An implementation of an secp256k1_ellswift_xdh_hash_function which uses
 21diff --git a/src/group_impl.h b/src/group_impl.h
 22index 8f6e05e0..dcd171f5 100644
 23--- a/src/group_impl.h
 24+++ b/src/group_impl.h
 25@@ -823,8 +823,7 @@ static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge* ge) {
 26 #endif
 27 }
 28 
 29-static int secp256k1_ge_x_on_curve_var(const secp256k1_fe *x)
 30-{
 31+static int secp256k1_ge_x_on_curve_var(const secp256k1_fe *x) {
 32     secp256k1_fe c;
 33     secp256k1_fe_sqr(&c, x);
 34     secp256k1_fe_mul(&c, &c, x);
 35diff --git a/src/modules/ellswift/main_impl.h b/src/modules/ellswift/main_impl.h
 36index b021be3f..103ab40b 100644
 37--- a/src/modules/ellswift/main_impl.h
 38+++ b/src/modules/ellswift/main_impl.h
 39@@ -24,112 +24,112 @@ static const secp256k1_fe secp256k1_ellswift_c4 = SECP256K1_FE_CONST(0x851695d4,
 40 static void secp256k1_ellswift_xswiftec_frac_var(secp256k1_fe *xn, secp256k1_fe *xd, const secp256k1_fe *u, const secp256k1_fe *t) {
 41     /* The implemented algorithm is the following (all operations in GF(p)):
 42      *
 43-     * - c0 = sqrt(-3) = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852
 44-     * - If u=0, set u=1.
 45-     * - If t=0, set t=1.
 46-     * - If u^3+7+t^2 = 0, set t=2*t.
 47-     * - Let X=(u^3+7-t^2)/(2*t)
 48-     * - Let Y=(X+t)/(c0*u)
 49-     * - If x3=u+4*Y^2 is a valid x coordinate, return x3.
 50-     * - If x2=(-X/Y-u)/2 is a valid x coordinate, return x2.
 51-     * - Return x1=(X/Y-u)/2 (which is now guaranteed to be a valid x coordinate).
 52+     * - Let c0 = sqrt(-3) = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852.
 53+     * - If u = 0, set u = 1.
 54+     * - If t = 0, set t = 1.
 55+     * - If u^3+7+t^2 = 0, set t = 2*t.
 56+     * - Let X = (u^3+7-t^2)/(2*t).
 57+     * - Let Y = (X+t)/(c0*u).
 58+     * - If x3 = u+4*Y^2 is a valid x coordinate, return it.
 59+     * - If x2 = (-X/Y-u)/2 is a valid x coordinate, return it.
 60+     * - Return x1 = (X/Y-u)/2 (which is now guaranteed to be a valid x coordinate).
 61      *
 62      * Introducing s=t^2, g=u^3+7, and simplifying x1=-(x2+u) we get:
 63      *
 64      * - Let c0 = ...
 65-     * - If u=0, set u=1.
 66-     * - If t=0, set t=1.
 67-     * - Let s=t^2
 68-     * - Let g=u^3+7
 69-     * - If g+s=0, set t=2*t, s=4*s
 70-     * - Let X=(g-s)/(2*t)
 71-     * - Let Y=(X+t)/(c0*u) = (g+s)/(2*c0*t*u)
 72-     * - If x3=u+4*Y^2 is a valid x coordinate, return x3.
 73-     * - If x2=(-X/Y-u)/2 is a valid x coordinate, return it.
 74-     * - Return x1=-(x2+u).
 75+     * - If u = 0, set u = 1.
 76+     * - If t = 0, set t = 1.
 77+     * - Let s = t^2
 78+     * - Let g = u^3+7
 79+     * - If g+s = 0, set t = 2*t, s = 4*s
 80+     * - Let X = (g-s)/(2*t).
 81+     * - Let Y = (X+t)/(c0*u) = (g+s)/(2*c0*t*u).
 82+     * - If x3 = u+4*Y^2 is a valid x coordinate, return it.
 83+     * - If x2 = (-X/Y-u)/2 is a valid x coordinate, return it.
 84+     * - Return x1 = -(x2+u).
 85      *
 86      * Now substitute Y^2 = -(g+s)^2/(12*s*u^2) and X/Y = c0*u*(g-s)/(g+s). This
 87      * means X and Y do not need to be evaluated explicitly anymore.
 88      *
 89      * - ...
 90-     * - If g+s=0, set s=4*s
 91-     * - If x3=u-(g+s)^2/(3*s*u^2) is a valid x coordinate, return it.
 92-     * - If x2=(-c0*u*(g-s)/(g+s)-u)/2 is a valid x coordinate, return it.
 93-     * - Return x1=-(x2+u).
 94+     * - If g+s = 0, set s = 4*s.
 95+     * - If x3 = u-(g+s)^2/(3*s*u^2) is a valid x coordinate, return it.
 96+     * - If x2 = (-c0*u*(g-s)/(g+s)-u)/2 is a valid x coordinate, return it.
 97+     * - Return x1 = -(x2+u).
 98      *
 99      * Simplifying x2 using 2 additional constants:
100      *
101-     * - c1 = (c0-1)/2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40
102-     * - c2 = (-c0-1)/2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
103+     * - Let c1 = (c0-1)/2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40.
104+     * - Let c2 = (-c0-1)/2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
105      * - ...
106-     * - If x2=u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it.
107+     * - If x2 = u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it.
108      * - ...
109      *
110      * Writing x3 as a fraction:
111      *
112      * - ...
113-     * - If x3=(3*s*u^3-(g+s)^2)/(3*s*u^2)
114+     * - If x3 = (3*s*u^3-(g+s)^2)/(3*s*u^2) ...
115      * - ...
116 
117      * Overall, we get:
118      *
119-     * - c1 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40
120-     * - c2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
121-     * - If u=0, set u=1.
122-     * - If t=0, set s=1, else set s=t^2
123-     * - Let g=u^3+7
124-     * - If g+s=0, set s=4*s
125-     * - If x3=(3*s*u^3-(g+s)^2)/(3*s*u^2) is a valid x coordinate, return it.
126-     * - If x2=u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it.
127-     * - Return x1=-(x2+u)
128+     * - Let c1 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40.
129+     * - Let c2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
130+     * - If u = 0, set u = 1.
131+     * - If t = 0, set s = 1, else set s = t^2.
132+     * - Let g = u^3+7.
133+     * - If g+s = 0, set s = 4*s.
134+     * - If x3 = (3*s*u^3-(g+s)^2)/(3*s*u^2) is a valid x coordinate, return it.
135+     * - If x2 = u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it.
136+     * - Return x1 = -(x2+u).
137      */
138     secp256k1_fe u1, s, g, p, d, n, l;
139     u1 = *u;
140     if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&u1), 0)) u1 = secp256k1_fe_one;
141     secp256k1_fe_sqr(&s, t);
142     if (EXPECT(secp256k1_fe_normalizes_to_zero_var(t), 0)) s = secp256k1_fe_one;
143-    secp256k1_fe_sqr(&l, &u1); /* l = u^2 */
144-    secp256k1_fe_mul(&g, &l, &u1); /* g = u^3 */
145-    secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3 + 7 */
146-    p = g; /* p = g */
147-    secp256k1_fe_add(&p, &s); /* p = g+s */
148+    secp256k1_fe_sqr(&l, &u1);                                   /* l = u^2 */
149+    secp256k1_fe_mul(&g, &l, &u1);                               /* g = u^3 */
150+    secp256k1_fe_add_int(&g, SECP256K1_B);                       /* g = u^3 + 7 */
151+    p = g;                                                       /* p = g */
152+    secp256k1_fe_add(&p, &s);                                    /* p = g+s */
153     if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&p), 0)) {
154-        secp256k1_fe_mul_int(&s, 4); /* s = 4*s */
155-        /* recompute p = g+s */
156-        p = g; /* p = g */
157-        secp256k1_fe_add(&p, &s); /* p = g+s */
158-    }
159-    secp256k1_fe_mul(&d, &s, &l); /* d = s*u^2 */
160-    secp256k1_fe_mul_int(&d, 3); /* d = 3*s*u^2 */
161-    secp256k1_fe_sqr(&l, &p); /* l = (g+s)^2 */
162-    secp256k1_fe_negate(&l, &l, 1); /* l = -(g+s)^2 */
163-    secp256k1_fe_mul(&n, &d, &u1); /* n = 3*s*u^3 */
164-    secp256k1_fe_add(&n, &l); /* n = 3*s*u^3-(g+s)^2 */
165-    if (secp256k1_ge_x_frac_on_curve_var(&n, &d)) {
166-        /* Return n/d = (3*s*u^3-(g+s)^2)/(3*s*u^2) */
167+        secp256k1_fe_mul_int(&s, 4);
168+        /* Recompute p = g+s */
169+        p = g;                                                   /* p = g */
170+        secp256k1_fe_add(&p, &s);                                /* p = g+s */
171+    }                                              
172+    secp256k1_fe_mul(&d, &s, &l);                                /* d = s*u^2 */
173+    secp256k1_fe_mul_int(&d, 3);                                 /* d = 3*s*u^2 */
174+    secp256k1_fe_sqr(&l, &p);                                    /* l = (g+s)^2 */
175+    secp256k1_fe_negate(&l, &l, 1);                              /* l = -(g+s)^2 */
176+    secp256k1_fe_mul(&n, &d, &u1);                               /* n = 3*s*u^3 */
177+    secp256k1_fe_add(&n, &l);                                    /* n = 3*s*u^3-(g+s)^2 */
178+    if (secp256k1_ge_x_frac_on_curve_var(&n, &d)) {              
179+        /* Return x3 = n/d = (3*s*u^3-(g+s)^2)/(3*s*u^2) */
180         *xn = n;
181         *xd = d;
182         return;
183     }
184     *xd = p;
185-    secp256k1_fe_mul(&l, &secp256k1_ellswift_c1, &s); /* l = c1*s */
186-    secp256k1_fe_mul(&n, &secp256k1_ellswift_c2, &g); /* n = c2*g */
187-    secp256k1_fe_add(&n, &l); /* n = c1*s+c2*g */
188-    secp256k1_fe_mul(&n, &n, &u1); /* n = u*(c1*s+c2*g) */
189-    /* Possible optimization: in the invocation below, d^2 = (g+s)^2 is computed,
190+    secp256k1_fe_mul(&l, &secp256k1_ellswift_c1, &s);            /* l = c1*s */
191+    secp256k1_fe_mul(&n, &secp256k1_ellswift_c2, &g);            /* n = c2*g */
192+    secp256k1_fe_add(&n, &l);                                    /* n = c1*s+c2*g */
193+    secp256k1_fe_mul(&n, &n, &u1);                               /* n = u*(c1*s+c2*g) */
194+    /* Possible optimization: in the invocation below, p^2 = (g+s)^2 is computed,
195      * which we already have computed above. This could be deduplicated. */
196     if (secp256k1_ge_x_frac_on_curve_var(&n, &p)) {
197-        /* Return n/p = u*(c1*s+c2*g)/(g+s) */
198+        /* Return x2 = n/p = u*(c1*s+c2*g)/(g+s) */
199         *xn = n;
200         return;
201     }
202-    secp256k1_fe_mul(&l, &p, &u1); /* l = u*(g+s) */
203-    secp256k1_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*(g+s) */
204-    secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)-u*(g+s) */
205+    secp256k1_fe_mul(&l, &p, &u1);                               /* l = u*(g+s) */
206+    secp256k1_fe_add(&n, &l);                                    /* n = u*(c1*s+c2*g)+u*(g+s) */
207+    secp256k1_fe_negate(xn, &n, 2);                              /* n = -u*(c1*s+c2*g)-u*(g+s) */
208 #ifdef VERIFY
209     VERIFY_CHECK(secp256k1_ge_x_frac_on_curve_var(xn, &p));
210 #endif
211-    /* Return n/p = -(u*(c1*s+c2*g)/(g+s)+u) */
212+    /* Return x3 = n/p = -(u*(c1*s+c2*g)/(g+s)+u) */
213 }
214 
215 /** Decode ElligatorSwift encoding (u, t) to X coordinate. */
216@@ -182,12 +182,12 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
217      *   - If s=0, fail.
218      *   - Let v=(r/s-u)/2.
219      * - Let w=sqrt(s).
220-     * - If (c & 5) = 0: return -w*(c3*u + v)
221-     * - If (c & 5) = 1: return  w*(c4*u + v)
222-     * - If (c & 5) = 4: return  w*(c3*u + v)
223-     * - If (c & 5) = 5: return -w*(c4*u + v)
224+     * - If (c & 5) = 0: return -w*(c3*u + v).
225+     * - If (c & 5) = 1: return  w*(c4*u + v).
226+     * - If (c & 5) = 4: return  w*(c3*u + v).
227+     * - If (c & 5) = 5: return -w*(c4*u + v).
228      */
229-    secp256k1_fe x = *x_in, u = *u_in, u2, g, v, s, m, r, q;
230+    secp256k1_fe x = *x_in, u = *u_in, g, v, s, m, r, q;
231     int ret;
232 
233     secp256k1_fe_normalize_weak(&x);
234@@ -205,28 +205,28 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
235         /* If -u-x is a valid X coordinate, fail. This would yield an encoding that roundtrips
236          * back under the x3 formula instead (which has priority over x1 and x2, so the decoding
237          * would not match x). */
238-        m = x; /* m = x */
239-        secp256k1_fe_add(&m, &u); /* m = u+x */
240-        secp256k1_fe_negate(&m, &m, 2); /* m = -u-x */
241-        /* test if (-u-x) is a valid X coordinate. If so, fail. */
242+        m = x;                                          /* m = x */
243+        secp256k1_fe_add(&m, &u);                       /* m = u+x */
244+        secp256k1_fe_negate(&m, &m, 2);                 /* m = -u-x */
245+        /* Test if (-u-x) is a valid X coordinate. If so, fail. */
246         if (secp256k1_ge_x_on_curve_var(&m)) return 0;
247 
248         /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [first part] */
249-        secp256k1_fe_sqr(&s, &m); /* s = (u+x)^2 */
250-        secp256k1_fe_negate(&s, &s, 1); /* s= -(u+x)^2 */
251-        secp256k1_fe_mul(&m, &u, &x); /* m = u*x */
252-        secp256k1_fe_add(&s, &m); /* s = -(u^2 + u*x + x^2) */
253-
254-        /* Note that at this point, s=0 is impossible. If it were the case:
255-         *    s = -(u^2 + u*x + x^2) = 0.
256-         * => u^2 + u*x + x^2 = 0
257-         * => (u + 2*x) * (u^2 + u*x + x^2) = 0
258+        secp256k1_fe_sqr(&s, &m);                       /* s = (u+x)^2 */
259+        secp256k1_fe_negate(&s, &s, 1);                 /* s = -(u+x)^2 */
260+        secp256k1_fe_mul(&m, &u, &x);                   /* m = u*x */
261+        secp256k1_fe_add(&s, &m);                       /* s = -(u^2 + u*x + x^2) */
262+
263+        /* Note that at this point, s = 0 is impossible. If it were the case:
264+         *             s = -(u^2 + u*x + x^2) = 0
265+         * =>                 u^2 + u*x + x^2 = 0
266+         * =>   (u + 2*x) * (u^2 + u*x + x^2) = 0
267          * => 2*x^3 + 3*x^2*u + 3*x*u^2 + u^3 = 0
268-         * => (x + u)^3 + x^3 = 0
269-         * => x^3 = -(x + u)^3
270-         * => x^3 + B = (-u - x)^3 + B
271+         * =>                 (x + u)^3 + x^3 = 0
272+         * =>                             x^3 = -(x + u)^3
273+         * =>                         x^3 + B = (-u - x)^3 + B
274          *
275-         * However, We know x^3 + B is square (because x is on the curve) and
276+         * However, we know x^3 + B is square (because x is on the curve) and
277          * that (-u-x)^3 + B is not square (the secp256k1_ge_x_on_curve_var(&m)
278          * test above would have failed). This is a contradiction, and thus the
279          * assumption s=0 is false. */
280@@ -237,15 +237,15 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
281         /* If s is not square, fail. We have not fully computed s yet, but s is square iff
282          * -(u^3+7)*(u^2+u*x+x^2) is square (because a/b is square iff a*b is square and b is
283          * nonzero). */
284-        secp256k1_fe_sqr(&g, &u); /* g = u^2 */
285-        secp256k1_fe_mul(&g, &g, &u); /* g = u^3 */
286-        secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */
287-        secp256k1_fe_mul(&m, &s, &g); /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */
288+        secp256k1_fe_sqr(&g, &u);                       /* g = u^2 */
289+        secp256k1_fe_mul(&g, &g, &u);                   /* g = u^3 */
290+        secp256k1_fe_add_int(&g, SECP256K1_B);          /* g = u^3+7 */
291+        secp256k1_fe_mul(&m, &s, &g);                   /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */
292         if (!secp256k1_fe_is_square_var(&m)) return 0;
293 
294         /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [second part] */
295-        secp256k1_fe_inv_var(&s, &s); /* s = -1/(u^2 + u*x + x^2) [cannot be div by 0] */
296-        secp256k1_fe_mul(&s, &s, &g); /* s = -(u^3 + 7)/(u^2 + u*x + x^2) */
297+        secp256k1_fe_inv_var(&s, &s);                   /* s = -1/(u^2 + u*x + x^2) [no div by 0] */
298+        secp256k1_fe_mul(&s, &s, &g);                   /* s = -(u^3 + 7)/(u^2 + u*x + x^2) */
299 
300         /* Let v = x. */
301         v = x;
302@@ -253,61 +253,60 @@ static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_
303         /* c is in {2, 3, 6, 7}. In this case we look for an inverse under the x3 formula. */
304 
305         /* Let s = x-u. */
306-        secp256k1_fe_negate(&m, &u, 1); /* m = -u */
307-        s = m; /* s = -u */
308-        secp256k1_fe_add(&s, &x); /* s = x-u */
309+        secp256k1_fe_negate(&m, &u, 1);                 /* m = -u */
310+        s = m;                                          /* s = -u */
311+        secp256k1_fe_add(&s, &x);                       /* s = x-u */
312 
313         /* If s is not square, fail. */
314         if (!secp256k1_fe_is_square_var(&s)) return 0;
315 
316         /* Let r = sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. */
317-        secp256k1_fe_sqr(&u2, &u); /* u2 = u^2 */
318-        secp256k1_fe_mul(&g, &u2, &u); /* g = u^3 */
319-        secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */
320-        secp256k1_fe_normalize_weak(&g);
321-        secp256k1_fe_mul_int(&g, 4); /* g = 4*(u^3+7) */
322-        secp256k1_fe_mul_int(&u2, 3); /* u2 = 3*u^2 */
323-        secp256k1_fe_mul(&q, &s, &u2); /* q = 3*s*u^2 */
324-        secp256k1_fe_add(&q, &g); /* q = 4*(u^3+7)+3*s*u^2 */
325-        secp256k1_fe_mul(&q, &q, &s); /* q = s*(4*(u^3+7)+3*u^2*s) */
326-        secp256k1_fe_negate(&q, &q, 1); /* q = -s*(4*(u^3+7)+3*u^2*s) */
327+        secp256k1_fe_sqr(&g, &u);                       /* g = u^2 */
328+        secp256k1_fe_mul(&q, &s, &g);                   /* q = s*u^2 */
329+        secp256k1_fe_mul_int(&q, 3);                    /* q = 3*s*u^2 */
330+        secp256k1_fe_mul(&g, &g, &u);                   /* g = u^3 */
331+        secp256k1_fe_mul_int(&g, 4);                    /* g = 4*u^3 */
332+        secp256k1_fe_add_int(&g, 4 * SECP256K1_B);      /* g = 4*(u^3+7) */
333+        secp256k1_fe_add(&q, &g);                       /* q = 4*(u^3+7)+3*s*u^2 */
334+        secp256k1_fe_mul(&q, &q, &s);                   /* q = s*(4*(u^3+7)+3*u^2*s) */
335+        secp256k1_fe_negate(&q, &q, 1);                 /* q = -s*(4*(u^3+7)+3*u^2*s) */
336         if (!secp256k1_fe_is_square_var(&q)) return 0;
337-        ret = secp256k1_fe_sqrt(&r, &q); /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */
338+        ret = secp256k1_fe_sqrt(&r, &q);                /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */
339         VERIFY_CHECK(ret);
340 
341         /* If (c & 1) = 1 and r = 0, fail. */
342         if (EXPECT((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r), 0)) return 0;
343 
344-        /* If s=0, fail. */
345+        /* If s = 0, fail. */
346         if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&s), 0)) return 0;
347 
348-        /* Let v=(r/s-u)/2. */
349-        secp256k1_fe_inv_var(&v, &s); /* v=1/s [cannot be div by 0] */
350-        secp256k1_fe_mul(&v, &v, &r); /* v=r/s */
351-        secp256k1_fe_add(&v, &m); /* v=r/s-u */
352-        secp256k1_fe_half(&v); /* v=(r/s-u)/2 */
353+        /* Let v = (r/s-u)/2. */
354+        secp256k1_fe_inv_var(&v, &s);                   /* v = 1/s [no div by 0] */
355+        secp256k1_fe_mul(&v, &v, &r);                   /* v = r/s */
356+        secp256k1_fe_add(&v, &m);                       /* v = r/s-u */
357+        secp256k1_fe_half(&v);                          /* v = (r/s-u)/2 */
358     }
359 
360-    /* Let w=sqrt(s). */
361-    ret = secp256k1_fe_sqrt(&m, &s); /* m = sqrt(s) = w */
362+    /* Let w = sqrt(s). */
363+    ret = secp256k1_fe_sqrt(&m, &s);                    /* m = sqrt(s) = w */
364     VERIFY_CHECK(ret);
365 
366     /* Return logic. */
367     if ((c & 5) == 0 || (c & 5) == 5) {
368-        secp256k1_fe_negate(&m, &m, 1); /* m = -w */
369+        secp256k1_fe_negate(&m, &m, 1);                 /* m = -w */
370     }
371     /* Now m = {-w if c&5=0 or c&5=5; w otherwise}. */
372     secp256k1_fe_mul(&u, &u, c&1 ? &secp256k1_ellswift_c4 : &secp256k1_ellswift_c3);
373     /* u = {c4 if c&1=1; c3 otherwise}*u */
374-    secp256k1_fe_add(&u, &v); /* u = {c4 if c&1=1; c3 otherwise}*u + v */
375+    secp256k1_fe_add(&u, &v);                           /* u = {c4 if c&1=1; c3 otherwise}*u + v */
376     secp256k1_fe_mul(t, &m, &u);
377     return 1;
378 }
379 
380 /** Use SHA256 as a PRNG, returning SHA256(hasher || cnt).
381  *
382- * hasher is a SHA256 object which a incrementing 4-byte counter is added to generate randomness.
383- * Adding 13 bytes (4 bytes for counter, plus 9 bytes for the SHA256 padding) cannot cross a
384+ * hasher is a SHA256 object to which an incrementing 4-byte counter is written to generate randomness.
385+ * Writing 13 bytes (4 bytes for counter, plus 9 bytes for the SHA256 padding) cannot cross a
386  * 64-byte block size boundary (to make sure it only triggers a single SHA256 compression). */
387 static void secp256k1_ellswift_prng(unsigned char* out32, const secp256k1_sha256 *hasher, uint32_t cnt) {
388     secp256k1_sha256 hash = *hasher;
389diff --git a/src/tests.c b/src/tests.c
390index 3ce87bfe..8ada3f86 100644
391--- a/src/tests.c
392+++ b/src/tests.c
393@@ -3945,7 +3945,7 @@ static void test_ge(void) {
394         free(ge_set_all);
395     }
396 
397-    /* Test all elements have X coordinates on the curve. */
398+    /* Test that all elements have X coordinates on the curve. */
399     for (i = 1; i < 4 * runs + 1; i++) {
400         secp256k1_fe n;
401         CHECK(secp256k1_ge_x_on_curve_var(&ge[i].x));
402@@ -3954,7 +3954,7 @@ static void test_ge(void) {
403         CHECK(secp256k1_ge_x_frac_on_curve_var(&n, &zf));
404     }
405 
406-    /* Test correspondence secp256k1_ge_x{,_frac}_on_curve_var with ge_set_xo. */
407+    /* Test correspondence of secp256k1_ge_x{,_frac}_on_curve_var with ge_set_xo. */
408     {
409         secp256k1_fe n;
410         secp256k1_ge q;

sipa force-pushed on Jun 20, 2023

sipa commented at 3:24 pm on June 20, 2023: contributor

Addressed comments by @theStack and @real-or-random:

 0diff --git a/include/secp256k1_ellswift.h b/include/secp256k1_ellswift.h
 1index d20fc0cc..3851f930 100644
 2--- a/include/secp256k1_ellswift.h
 3+++ b/include/secp256k1_ellswift.h
 4@@ -145,7 +145,7 @@ SECP256K1_API int secp256k1_ellswift_decode(
 5  * followed by secp256k1_ellswift_encode. It is safer, as it uses the secret
 6  * key as entropy for the encoding (supplemented with auxrnd32, if provided).
 7  *
 8- * Like secp256k1_ellswift_encode, this function does not guaranteed that the
 9+ * Like secp256k1_ellswift_encode, this function does not guarantee that the
10  * computed encoding is stable across versions of the library, even if all
11  * arguments (including auxrnd32) are the same.
12  */
13diff --git a/src/modules/ellswift/bench_impl.h b/src/modules/ellswift/bench_impl.h
14index 1b0ce6a7..b16a3a36 100644
15--- a/src/modules/ellswift/bench_impl.h
16+++ b/src/modules/ellswift/bench_impl.h
17@@ -94,7 +94,6 @@ void run_ellswift_bench(int iters, int argc, char **argv) {
18 
19     /* create a context with signing capabilities */
20     data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
21-    memset(data.rnd64, 11, sizeof(data.rnd64));
22 
23     if (d || have_flag(argc, argv, "ellswift") || have_flag(argc, argv, "encode") || have_flag(argc, argv, "ellswift_encode")) run_benchmark("ellswift_encode", bench_ellswift_encode, bench_ellswift_setup, NULL, &data, 10, iters);
24     if (d || have_flag(argc, argv, "ellswift") || have_flag(argc, argv, "decode") || have_flag(argc, argv, "ellswift_decode")) run_benchmark("ellswift_decode", bench_ellswift_decode, bench_ellswift_setup, NULL, &data, 10, iters);
25diff --git a/src/modules/ellswift/main_impl.h b/src/modules/ellswift/main_impl.h
26index 103ab40b..374c70cd 100644
27--- a/src/modules/ellswift/main_impl.h
28+++ b/src/modules/ellswift/main_impl.h
29@@ -427,6 +427,7 @@ int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64
30         return 1;
31     }
32     /* Only reached in case the provided pubkey is invalid. */
33+    memset(ell64, 0, 64);
34     return 0;
35 }

Add ellswift module implementing ElligatorSwift

The scheme implemented is described below, and largely follows the paper
"SwiftEC: Shallue–van de Woestijne Indifferentiable Function To Elliptic Curves",
by Chavez-Saab, Rodriguez-Henriquez, and Tibouchi
(https://eprint.iacr.org/2022/759).

A new 64-byte public key format is introduced, with the property that *every*
64-byte array is an encoding for a non-infinite curve point. Each curve point
has roughly 2^256 distinct encodings. This permits disguising public keys as
uniformly random bytes.

The new API functions:
* secp256k1_ellswift_encode: convert a normal public key to an ellswift 64-byte
  public key, using additional entropy to pick among the many possible
  encodings.
* secp256k1_ellswift_decode: convert an ellswift 64-byte public key to a normal
  public key.
* secp256k1_ellswift_create: a faster and safer equivalent to calling
  secp256k1_ec_pubkey_create + secp256k1_ellswift_encode.
* secp256k1_ellswift_xdh: x-only ECDH directly on ellswift 64-byte public keys,
  where the key encodings are fed to the hash function.

The scheme itself is documented in secp256k1_ellswift.h.

c47917bbd6

Add tests for ellswift module

These include both test vectors taken from BIP324, as randomized unit tests.

9695deb351

Add _prefix and _bip324 ellswift_xdh hash functions df633cdeba

Add ctime tests for ellswift module 2d1d41acf8

Add benchmarks for ellswift module 1bcea8c57f

Add ellswift testing to CI 4f091847c2

Add doc/ellswift.md with ElligatorSwift explanation 90e360acc2

sipa force-pushed on Jun 20, 2023

sipa commented at 3:32 pm on June 20, 2023: contributor

And dropped some trailing spaces:

 0diff --git a/src/modules/ellswift/main_impl.h b/src/modules/ellswift/main_impl.h
 1index 374c70cd..00bb8a3d 100644
 2--- a/src/modules/ellswift/main_impl.h
 3+++ b/src/modules/ellswift/main_impl.h
 4@@ -98,14 +98,14 @@ static void secp256k1_ellswift_xswiftec_frac_var(secp256k1_fe *xn, secp256k1_fe
 5         /* Recompute p = g+s */
 6         p = g;                                                   /* p = g */
 7         secp256k1_fe_add(&p, &s);                                /* p = g+s */
 8-    }                                              
 9+    }
10     secp256k1_fe_mul(&d, &s, &l);                                /* d = s*u^2 */
11     secp256k1_fe_mul_int(&d, 3);                                 /* d = 3*s*u^2 */
12     secp256k1_fe_sqr(&l, &p);                                    /* l = (g+s)^2 */
13     secp256k1_fe_negate(&l, &l, 1);                              /* l = -(g+s)^2 */
14     secp256k1_fe_mul(&n, &d, &u1);                               /* n = 3*s*u^3 */
15     secp256k1_fe_add(&n, &l);                                    /* n = 3*s*u^3-(g+s)^2 */
16-    if (secp256k1_ge_x_frac_on_curve_var(&n, &d)) {              
17+    if (secp256k1_ge_x_frac_on_curve_var(&n, &d)) {
18         /* Return x3 = n/d = (3*s*u^3-(g+s)^2)/(3*s*u^2) */
19         *xn = n;
20         *xd = d;

Davidson-Souza commented at 7:14 pm on June 20, 2023: none

tACK 90e360a. Full testing backlog:

Iterated through the implementation, checking all the math (the verbose comments helped a lot!)
Indepently generated all constants using python/sage (Python 3.10.10 and SageMath version 9.8, Release Date: 2023-02-11)
A “manual mutation test” for the valgrind ctime tests, adding some dummy, secret dependent branching, it indeed causes memcheck to complain about uninitialized values. Using VALGRIND_MAKE_MEM_DEFINED silences those warnings, as expected.
Executed all tests, including the memcheck ones (OS and hardware below). Compilation using both gcc and clang, configure script bellow.
The documentation is sound and very helpful

Test environments:

Config script: [CC=clang] ./configure --with-valgrind=yes --enable-module-ecdh --enable-module-ellswift --enable-experimental --no-recursion

Machine 1: Arch Linux on a AMD Ryze 5 (Linux 6.1.21-hardened1-1-hardened #1 SMP PREEMPT_DYNAMIC x86_64 GNU/Linux ) gcc version 12.2.1 20230201
clang version 14.0.7 GNU libc stable release version 2.37. valgrind-3.20.0

Machine 2: Raspbian on a Raspbery Pi 4b (Linux raspberrypi 6.1.21-v8+ #1642 SMP PREEMPT aarch64 GNU/Linux) gcc version 10.2.1 20210110 (Debian 10.2.1-6) Debian clang version 11.0.1-2 valgrind-3.16.1 (Debian GLIBC 2.31-13+rpt2+rpi1+deb11u5) stable release version 2.31

Benchmarks (only for the new module)

Machine 1, clang

0ellswift_encode               ,    23.8       ,    24.1       ,    24.9    
1ellswift_decode               ,    10.9       ,    11.4       ,    11.6    
2ellswift_keygen               ,    55.3       ,    58.8       ,    61.7    
3ellswift_ecdh                 ,    63.3       ,    64.1       ,    65.3

Machine 1, gcc

0ellswift_encode               ,    22.6       ,    22.7       ,    22.9    
1ellswift_decode               ,    10.7       ,    10.8       ,    11.0    
2ellswift_keygen               ,    54.3       ,    54.7       ,    55.9    
3ellswift_ecdh                 ,    62.7       ,    63.2       ,    64.1

Machine 2, clang

0ellswift_encode               ,    63.7       ,    63.7       ,    63.8    
1ellswift_decode               ,    33.7       ,    33.8       ,    34.0    
2ellswift_keygen               ,   177.0       ,   177.0       ,   178.0    
3ellswift_ecdh                 ,   233.0       ,   234.0       ,   234.0

Machine 2, gcc

0ellswift_encode               ,    66.4       ,    66.4       ,    66.5    
1ellswift_decode               ,    34.9       ,    34.9       ,    34.9    
2ellswift_keygen               ,   182.0       ,   182.0       ,   183.0    
3ellswift_ecdh                 ,   230.0       ,   231.0       ,   231.0

real-or-random approved

real-or-random commented at 9:51 pm on June 20, 2023: contributor

ACK 90e360acc2511f313964e394005bafb377b4f191

in include/secp256k1_ellswift.h:149 in c47917bbd6 outdated

144+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
145+
146+/** Given a private key, and ElligatorSwift public keys sent in both directions,
147+ *  compute a shared secret using x-only Elliptic Curve Diffie-Hellman (ECDH).
148+ *
149+ *  Returns: 1: shared secret was succesfully computed

stratospher commented at 7:44 am on June 21, 2023:

0 *  Returns: 1: shared secret was successfully computed

jonasnick approved

jonasnick commented at 11:40 am on June 21, 2023: contributor

ACK 90e360acc2511f313964e394005bafb377b4f191

jonasnick merged this on Jun 21, 2023

jonasnick closed this on Jun 21, 2023

jonasnick commented at 2:37 pm on June 21, 2023: contributor

This has been merged as it received adequate reviews and enough ACKs (as discussed in IRC). Post-merge ACKs are still welcome. If any issues still arise, they can be addressed in follow-up PRs.

real-or-random added the label needs-changelog on Jun 21, 2023

sipa referenced this in commit 901336eee7 on Jun 21, 2023

sipa cross-referenced this on Jun 21, 2023 from issue Add ellswift to CHANGELOG by sipa

in doc/ellswift.md:91 in 90e360acc2

86+
87+$$
88+\begin{array}{lcl}
89+X(u, t) & = & \left\\{\begin{array}{ll}
90+  \dfrac{g(u) - t^2}{2t} & a = 0 \\
91+  \dfrac{g(u) + h(u)(Y_0(u) + X_0(u)t)^2}{X_0(u)(1 + h(u)t^2)} & a \neq 0

stratospher commented at 1:45 pm on June 22, 2023:

swiftEC paper shows this: $\dfrac{g(u) + h(u)(Y_0(u) - X_0(u)t)^2}{X_0(u)(1 + h(u)t^2)}$

in doc/ellswift.md:164 in 90e360acc2

159+
160+$$
161+P_u^{-1}(X, Y) = \left\\{\begin{array}{ll}
162+Yu\sqrt{-3} - X & a = 0 \\
163+\dfrac{Y-Y_0(u)}{X-X_0(u)} & a \neq 0 \land X \neq X_0(u) \\
164+\dfrac{-X_0(u)}{h(u)Y_0(u)} & a \neq 0 \land X = X_0(u) \land Y = Y_0(u)

stratospher commented at 2:00 pm on June 22, 2023:

~~tried using WolframAlpha(my first time) for this condition - link.~~

EDIT: sorry for the spam! got it when i plugged in the right equation.

in doc/ellswift.md:349 in 90e360acc2

344+  * Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
345+  * If $c \in \\{3, 7\\}$ and $r=0$, return $\bot.$
346+  * If $s = 0$, return $\bot.$
347+  * Let $v = (r/s - u)/2.$
348+* Let $w = \sqrt{s}$; return $\bot$ if not square.
349+* If $a \neq 0$ and $w(u+2v) = 2X_0(u)$ and either $w \neq 2Y_0(u)$ or $h(u) = 0$, return $\bot.$

stratospher commented at 2:38 pm on June 23, 2023:

~~(from L332 actually) how does this happen? (when Y = 0 in x1, x2 computation or something else?)~~

EDIT: L332 needs to be updated to $w(u+2v) = 2X_0(u)$. (this happens when X = X0)

in doc/ellswift.md:445 in 90e360acc2

440+  * Let $s = x-u.$
441+  * Let $r = \sqrt{-s(4g(u) + sh(u))}$; return $\bot$ if not square.
442+  * If $c = 3$ and $r = 0$, return $\bot.$
443+  * Let $v = (r/s - u)/2.$
444+* Let $w = \sqrt{s}$; return $\bot$ if not square.
445+* Let $w' = w$ if $sign(w/2) = sign(y)$; $-w$ otherwise.

stratospher commented at 6:02 pm on June 23, 2023:

why not $sign(w)$?

real-or-random referenced this in commit ac43613d25 on Jun 25, 2023

real-or-random removed the label needs-changelog on Jun 25, 2023

theStack referenced this in commit 0c9f6b6ea2 on Jun 25, 2023

theStack cross-referenced this on Jun 25, 2023 from issue tests: refactor: take use of `secp256k1_ge_x_on_curve_var` by theStack

theStack referenced this in commit 7d8d5c86df on Jun 25, 2023

achow101 referenced this in commit 679f825ba3 on Jun 26, 2023

real-or-random referenced this in commit 4494a369b6 on Jun 27, 2023

stratospher commented at 8:10 pm on June 27, 2023: contributor

post-merge ACK 90e360a. rereviewed the code and skimmed through the swiftEC paper.

hebasto cross-referenced this on Jun 28, 2023 from issue build: Improvements to symbol visibility logic on Windows by real-or-random

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

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

jonasnick cross-referenced this on Jul 26, 2023 from issue Upstream PRs 1314, 1317, 1318, 1316, 1327, 1310, 1328, 1333, 1330, 1334, 1337, 1341, 1339, 1350, 1349, 1338, 1129, 1347, 1336, 1295, 1354, 1355, 1356 by jonasnick

ElligatorSwift + integrated x-only DH #1129

Test environments:

Benchmarks (only for the new module)