test: add python implementation of Elligator swift #24005

stratospher commented at 4:33 PM on January 7, 2022: contributor

Built on top of #26222.

This PR introduces Elligator swift encoding and decoding in the functional test framework. It's used in #24748 for writing p2p encryption tests.

in test/functional/test_framework/key.py:128 in 88ed681608 outdated

  92 | @@ -93,7 +93,9 @@ def on_curve(self, p1):
  93 |          x1, y1, z1 = p1
  94 |          z2 = pow(z1, 2, self.p)
  95 |          z4 = pow(z2, 2, self.p)
  96 | -        return z1 != 0 and (pow(x1, 3, self.p) + self.a * x1 * z4 + self.b * z2 * z4 - pow(y1, 2, self.p)) % self.p == 0
  97 | +        if z1 == 0:

sipa commented at 4:48 PM on January 7, 2022:

That's pretty ugly; it's a function for testing whether a point is on the curve. Returning anything but True or False seems pretty unintuitive.

I'd suggest instead adding an "is_infinity" function to this class instead, and using that further on.

stratospher commented at 2:42 PM on January 8, 2022:

Makes sense. Done.

in test/functional/test_framework/ellsq.py:68 in e3a80dd45c outdated

  63 | +            return None
  64 | +        u = sqrt(s)
  65 | +    if is_odd(y) == is_odd(u):
  66 | +        return u
  67 | +    else:
  68 | +        return -u

sipa commented at 4:50 PM on January 7, 2022:

Nit: missing newline at the end

stratospher commented at 2:42 PM on January 8, 2022:

Done.

in test/functional/test_framework/ellsq.py:4 in e3a80dd45c outdated

   0 | @@ -0,0 +1,68 @@
   1 | +# Source: https://github.com/sipa/writeups/tree/main/elligator-square-for-bn
   2 | +"""Test-only Elligator Squared implementation
   3 | +
   4 | +WARNING: This code is slow, uses bad randomness, does not properly protect

sipa commented at 4:50 PM on January 7, 2022:

In commit "Add Elligator Squared mapping functions f and r". Perhaps point out somewhere that this is Sage code, and won't actually work as Python. Alternatively, just merge it with the next commit that converts it to Python.

stratospher commented at 2:42 PM on January 8, 2022:

Merged with next commit.

in test/functional/test_framework/ellsq.py:10 in 5c31902d62 outdated

   4 | @@ -5,64 +5,93 @@
   5 |  keys, and is trivially vulnerable to side channel attacks. Do not use for
   6 |  anything but tests."""
   7 |  
   8 | +class fe:
   9 | +    """Prime field over 2^256 - 2^32 - 977"""
  10 | +    p = 2**256 - 2**32 - 977

sipa commented at 4:52 PM on January 7, 2022:

Perhaps this class should live in key.py instead? The rest of key.py could also benefit from this abstraction. The p here can also reuse the SECP256K1_FIELD_SIZE then.

Alternatively, you could just follow the approach key.py uses currently, and manually write the modulo reductions and modinv/modsqrt calls directly where used.

stratospher commented at 2:43 PM on January 8, 2022:

Makes sense. I've moved the class to key.py.

in test/functional/test_framework/ellsq.py:33 in 5c31902d62 outdated

  28 | +            return True
  29 | +        return False
  30 | +    def sqrt(self):
  31 | +        return fe(modsqrt(self.val, fe.p))
  32 | +
  33 | +c1 = fe(-3).sqrt()

sipa commented at 4:52 PM on January 7, 2022:

Capitalize global constants.

stratospher commented at 2:43 PM on January 8, 2022:

Done.

in test/functional/test_framework/ellsq.py:100 in 94767af462 outdated

  93 | @@ -94,4 +94,69 @@ def r(x,y,i):
  94 |      if y.is_odd() == u.is_odd():
  95 |          return u
  96 |      else:
  97 | -        return -u
  98 | \ No newline at end of file
  99 | +        return -u
 100 | +
 101 | +def SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0):
 102 | +    n = []

sipa commented at 4:55 PM on January 7, 2022:

This can be written more succintly as:

def SECP256K1_FE_CONST(*d):
    return fe(sum(d[i] << ((7-i)*32) for i in range(8)))

Alternatively, it can be avoided entirely (see suggestion below).

stratospher commented at 2:43 PM on January 8, 2022:

Pretty cool! I've implemented the suggestion.

in test/functional/test_framework/ellsq.py:116 in 94767af462 outdated

 113 | +def SECP256K1_GE_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p):
 114 | +    fe1 = SECP256K1_FE_CONST(a, b, c, d, e, f, g, h)
 115 | +    fe2 = SECP256K1_FE_CONST(i, j, k, l, m, n, o, p)
 116 | +    return (fe1, fe2)
 117 | +
 118 | +ellsq_tests = [

sipa commented at 4:57 PM on January 7, 2022:

Capitalize global constant.

stratospher commented at 2:43 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:117 in 94767af462 outdated

 114 | +    fe1 = SECP256K1_FE_CONST(a, b, c, d, e, f, g, h)
 115 | +    fe2 = SECP256K1_FE_CONST(i, j, k, l, m, n, o, p)
 116 | +    return (fe1, fe2)
 117 | +
 118 | +ellsq_tests = [
 119 | +    [SECP256K1_GE_CONST(0xc27fb7a3, 0x283a7d3e, 0xc9f96421, 0x545ef6f5, 0x8ace7b71, 0x06c8a1b9, 0x07c0ae8a, 0x7598159c, 0xe05a060e, 0x839ef79f, 0xc0c1267c, 0xa17880c9, 0x584cdd34, 0xc05f9695, 0x55482207, 0xe6851f2a), [SECP256K1_FE_CONST(0xc0ad127a, 0xa36824d6, 0x5b1f5be7, 0x4de1aa25, 0xbc4d5cbe, 0xcee15462, 0x0a12682a, 0xfc87df98), SECP256K1_FE_CONST(0xd40fd5bc, 0x51992484, 0x8f13273b, 0x1d857cba, 0x42d45e78, 0x9eaa4e47, 0xf458b83a, 0xbd5f8d1c), SECP256K1_FE_CONST(0xde636141, 0x7deb440b, 0x3a305924, 0x43635cf9, 0xcf42f9b5, 0xf5b891c1, 0x1e119f09, 0x71b570ac), SECP256K1_FE_CONST(0xd55135ce, 0x41bb4d05, 0x5b3757f4, 0xaf1d6537, 0x137376d7, 0x5270caae, 0xda68382d, 0x25d00708)]],

sipa commented at 5:03 PM on January 7, 2022:

I would avoid the round-tripping through the awkward secp256k1 8x32 notation for field elements.

and then for the first line (just concatenating the hex digits, dropping the , 0x between them).

    [(fe(0xc27fb7a3283a7d3ec9f96421545ef6f58ace7b7106c8a1b907c0ae8a7598159c), fe(0xe05a060e839ef79fc0c1267ca17880c9584cdd34c05f969555482207e6851f2a)), [fe(0xc0ad127aa36824d65b1f5be74de1aa25bc4d5cbecee154620a12682afc87df98), fe(0xd40fd5bc519924848f13273b1d857cba42d45e789eaa4e47f458b83abd5f8d1c), fe(0xde6361417deb440b3a30592443635cf9cf42f9b5f5b891c11e119f0971b570ac), fe(0xd55135ce41bb4d055b3757f4af1d6537137376d75270caaeda68382d25d00708)]],

etc.

stratospher commented at 2:43 PM on January 8, 2022:

Thanks! This looks really nice.

in test/functional/test_framework/ellsq.py:162 in 94767af462 outdated

 159 | +    [SECP256K1_GE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0x4218f20a, 0xe6c646b3, 0x63db6860, 0x5822fb14, 0x264ca8d2, 0x587fdd6f, 0xbc750d58, 0x7e76a7ee), [SECP256K1_FE_CONST(0x2c8864a8, 0xc34e87d7, 0x53ee7300, 0x8bbed54a, 0x47b37907, 0x56d0b747, 0x10341b37, 0xf598a5fe), SECP256K1_FE_CONST(0x15908d62, 0x2377bedc, 0x0fecf55f, 0xcc6425c9, 0xde992fcb, 0x01af2628, 0xac40f220, 0x88de01f0), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]],
 160 | +    [SECP256K1_GE_CONST(0xa64de96a, 0x6254cefc, 0xffbeaf89, 0x8f2c228a, 0xf6d405f3, 0xbcc6a4cc, 0xe068312a, 0xf7ccf8e1, 0x8f9b3a1b, 0x2d146ea9, 0x54bfc5e2, 0xcdfe861c, 0xcbed8431, 0xc741c5f9, 0xd32f16a3, 0x073ea496), [SECP256K1_FE_CONST(0x4591d33d, 0x1a133a87, 0x94689b1b, 0x0ca445b7, 0x8ada3bce, 0xc2e812b0, 0x8315e2b1, 0x07940ad4), SECP256K1_FE_CONST(0xa763d217, 0x6027d40e, 0x8a8ff34b, 0xd9c639b7, 0x3e2ea045, 0x92274fdc, 0xfa4051c6, 0x6d93a1b6), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]],
 161 | +    [SECP256K1_GE_CONST(0x49a0dc06, 0x8c3f117a, 0xefdc842d, 0x3d358153, 0xf677f04c, 0x6dabc9c9, 0x1b09d452, 0xfef27b66, 0x7b944da4, 0x8a175dbc, 0x444ead8d, 0xb82eff66, 0xb081a8aa, 0xe6453fed, 0x2bca9720, 0xb44dd6e5), [SECP256K1_FE_CONST(0x7bf1e2b1, 0x720c1c44, 0x0db64687, 0xf16439fa, 0x41b39833, 0x8095f24e, 0xbeec0cfa, 0x88750dc9), SECP256K1_FE_CONST(0xdc97e26d, 0x3137445d, 0x6c1269b6, 0x1a765501, 0x0c19c36a, 0x2e361066, 0xe31e2bb1, 0x0403470b), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]],
 162 | +    [SECP256K1_GE_CONST(0xd09a4047, 0xf158fe52, 0xf96c661d, 0x02c68657, 0xc4c976ea, 0x96ea85ef, 0x46d6985b, 0xd540756b, 0xe793bfaa, 0xe9300f18, 0xe6f9b55a, 0xae263223, 0x68b61d51, 0xae5022ef, 0xe266c72d, 0x574178bc), [SECP256K1_FE_CONST(0x7e6175fd, 0xfbb9fb4f, 0xaf6e2b92, 0x5ef86c4a, 0x444d819a, 0xaa82dbee, 0x545d3d9b, 0x296375be), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]],
 163 | +    [SECP256K1_GE_CONST(0x34986625, 0x04b73c7c, 0x8cecb6c3, 0x3cd493bd, 0xfc190e0f, 0x87d913d7, 0xff9ad42e, 0x222bfe95, 0x245b3a61, 0xb8d46997, 0xf14f2fea, 0x28748996, 0x91eb3254, 0x2b9907d6, 0x5eb9d21d, 0x42454021), [SECP256K1_FE_CONST(0x7f556282, 0xc3dd9d26, 0x3390d6bb, 0xddada698, 0xab8fd7c7, 0xd1a06498, 0xf42b3043, 0x7c8361ad), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]]
 164 | +]

sipa commented at 5:04 PM on January 7, 2022:

Newline at the end of file.

in test/functional/test_framework/ellsq.py:200 in 8eb51d7e80 outdated

 197 | +                    assert (ge[0] == group_ele[0] and ge[1] == group_ele[1])
 198 | +            assert len(set(preimages)) == len(preimages)
 199 | +
 200 | +    def test_ellsq_mapping(self):
 201 | +        for test_vector in ellsq_tests:
 202 | +            ge = test_vector[0]

sipa commented at 5:05 PM on January 7, 2022:

More Pythonic: ge, fe = test_vector.

stratospher commented at 2:43 PM on January 8, 2022:

Nice! Done.

in test/functional/test_framework/ellsq.py:202 in 8eb51d7e80 outdated

 199 | +
 200 | +    def test_ellsq_mapping(self):
 201 | +        for test_vector in ellsq_tests:
 202 | +            ge = test_vector[0]
 203 | +            fe = test_vector[1]
 204 | +            for j in range(1, 5):

sipa commented at 5:06 PM on January 7, 2022:

Perhaps more Pythonic: for j, field_ele in enumerate(fe): (this results in 0-based j rather than 1-based, but perhaps f() and r() should be converted to use 0-based indexing for j anyway).

stratospher commented at 2:43 PM on January 8, 2022:

Interesting! Done.

in test/functional/test_framework/ellsq.py:207 in 8eb51d7e80 outdated

 204 | +            for j in range(1, 5):
 205 | +                field_ele = r(ge[0], ge[1], j)
 206 | +                if field_ele is not None:
 207 | +                    assert(field_ele == fe[j-1])
 208 | +                    group_ele = f(field_ele)
 209 | +                    assert (ge[0] == group_ele[0] and ge[1] == group_ele[1])

sipa commented at 5:07 PM on January 7, 2022:

Newline.

stratospher commented at 2:43 PM on January 8, 2022:

Done.

DrahtBot added the label Tests on Jan 7, 2022

in test/functional/test_framework/ellsq.py:15 in 5c31902d62 outdated

  10 | +    p = 2**256 - 2**32 - 977
  11 | +    def __init__(self, x):
  12 | +        self.val = x % self.p
  13 | +
  14 | +    def __add__     (self, o): return fe( self.val +  o.val                   )
  15 | +    def __eq__      (self, o): return self.val % self.p == o.val % self.p

sipa commented at 5:09 PM on January 7, 2022:

I don't think the modulo reductions are strictly needed; any fe object's val value should already be reduced.

stratospher commented at 2:43 PM on January 8, 2022:

Interesting! Done.

in test/functional/test_framework/ellsq.py:17 in 5c31902d62 outdated

  12 | +        self.val = x % self.p
  13 | +
  14 | +    def __add__     (self, o): return fe( self.val +  o.val                   )
  15 | +    def __eq__      (self, o): return self.val % self.p == o.val % self.p
  16 | +    def __hash__    (self   ): return id(self)
  17 | +    def __mul__     (self, o): return fe((self.val *  o.val         ) % self.p)

sipa commented at 5:10 PM on January 7, 2022:

The fe constructor will do a modulo reduction; no need to repeat it here.

stratospher commented at 2:43 PM on January 8, 2022:

Interesting! Done.

in test/functional/test_framework/ellsq.py:119 in 94767af462 outdated

 116 | +    return (fe1, fe2)
 117 | +
 118 | +ellsq_tests = [
 119 | +    [SECP256K1_GE_CONST(0xc27fb7a3, 0x283a7d3e, 0xc9f96421, 0x545ef6f5, 0x8ace7b71, 0x06c8a1b9, 0x07c0ae8a, 0x7598159c, 0xe05a060e, 0x839ef79f, 0xc0c1267c, 0xa17880c9, 0x584cdd34, 0xc05f9695, 0x55482207, 0xe6851f2a), [SECP256K1_FE_CONST(0xc0ad127a, 0xa36824d6, 0x5b1f5be7, 0x4de1aa25, 0xbc4d5cbe, 0xcee15462, 0x0a12682a, 0xfc87df98), SECP256K1_FE_CONST(0xd40fd5bc, 0x51992484, 0x8f13273b, 0x1d857cba, 0x42d45e78, 0x9eaa4e47, 0xf458b83a, 0xbd5f8d1c), SECP256K1_FE_CONST(0xde636141, 0x7deb440b, 0x3a305924, 0x43635cf9, 0xcf42f9b5, 0xf5b891c1, 0x1e119f09, 0x71b570ac), SECP256K1_FE_CONST(0xd55135ce, 0x41bb4d05, 0x5b3757f4, 0xaf1d6537, 0x137376d7, 0x5270caae, 0xda68382d, 0x25d00708)]],
 120 | +    [SECP256K1_GE_CONST(0x3f5ada4e, 0x8f646ec9, 0x10ffc1a2, 0xb74d94bb, 0xb1860631, 0xa3c2a349, 0xeddf55ca, 0xfd49cce9, 0x28ad9d8d, 0x77d9cd87, 0xf80aaa34, 0x8e9ad1b4, 0x40353d7a, 0x6e717714, 0x60425319, 0x38f530c3), [SECP256K1_FE_CONST(0xac42348f, 0x1b356822, 0x5bb7d4c0, 0x0feab37e, 0xa5fb7fbb, 0x0cc3879d, 0xc74e2dda, 0xf9a393bf), SECP256K1_FE_CONST(0xda7a45b2, 0x6c87dcb6, 0x4a934c1d, 0xc841d250, 0xf98af5f0, 0x511be2a3, 0x82d17bab, 0xe1e4a533), SECP256K1_FE_CONST(0xc3d9b9a6, 0x570ca9c8, 0xa640fc75, 0x945850b2, 0xcc86b6d6, 0x399b4496, 0x4288d76d, 0x832a32d7), SECP256K1_FE_CONST(0xbf5ebc2f, 0x4060abe7, 0x884a1fa7, 0xcc0883cb, 0x97535c5a, 0x31dc6df4, 0xc6968e9d, 0x8554f3b1)]],
 121 | +    [SECP256K1_GE_CONST(0xf5f74fab, 0x3ebbbcfd, 0xdcaef6cc, 0xd14eb934, 0xf9435a4e, 0x4a1ed2d8, 0x75352c47, 0x306d6c2f, 0xea6a5b2a, 0xe109897d, 0x046e1504, 0xf7a382d6, 0x1eb49a8a, 0xae8852ef, 0x48e29466, 0x194d9e66), [SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0xe8362df2, 0x38e0405b, 0x49218747, 0x74f9ebca, 0x36dfe21b, 0x1a49ae2d, 0x0fa23fd4, 0x11a262a6), SECP256K1_FE_CONST(0x9e453426, 0xac973155, 0x19d11d63, 0xc3bb27ee, 0x89a7ec85, 0x5661dce4, 0xe428f6cc, 0x0be059cc)]],

sipa commented at 5:12 PM on January 7, 2022:

If you replace all the 0 fe elements with Null, you can simplify the equality check in the test.

stratospher commented at 2:43 PM on January 8, 2022:

Nice! Done.

in test/functional/test_framework/ellsq.py:204 in 8eb51d7e80 outdated

 201 | +        for test_vector in ellsq_tests:
 202 | +            ge = test_vector[0]
 203 | +            fe = test_vector[1]
 204 | +            for j in range(1, 5):
 205 | +                field_ele = r(ge[0], ge[1], j)
 206 | +                if field_ele is not None:

sipa commented at 5:13 PM on January 7, 2022:

If the field_ele is None, you should probably check that fe[j-1] is 0 (or better, have those fe elements be Null instead).

stratospher commented at 2:43 PM on January 8, 2022:

Done.

in test/functional/test_framework/ellsq.py:113 in c2fb7ebfbc outdated

 112 | +        fe1 = f(u)
 113 | +        # convert fe1 to jacobian form for EC operations
 114 | +        fe1 = (fe1[0].val, fe1[1].val, 1)
 115 | +        T = SECP256K1.negate(fe1)
 116 | +        Q = SECP256K1.add(T, P)
 117 | +        if SECP256K1.on_curve(Q) is None:

sipa commented at 5:14 PM on January 7, 2022:

Add a new SECP256k1.is_infinity function instead of overloading on_curve, and use that.

stratospher commented at 2:43 PM on January 8, 2022:

Done.

in test/functional/test_framework/ellsq.py:215 in 915a1c9abb outdated

 210 | @@ -211,6 +211,21 @@ def SECP256K1_GE_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p):
 211 |      [SECP256K1_GE_CONST(0x34986625, 0x04b73c7c, 0x8cecb6c3, 0x3cd493bd, 0xfc190e0f, 0x87d913d7, 0xff9ad42e, 0x222bfe95, 0x245b3a61, 0xb8d46997, 0xf14f2fea, 0x28748996, 0x91eb3254, 0x2b9907d6, 0x5eb9d21d, 0x42454021), [SECP256K1_FE_CONST(0x7f556282, 0xc3dd9d26, 0x3390d6bb, 0xddada698, 0xab8fd7c7, 0xd1a06498, 0xf42b3043, 0x7c8361ad), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000), SECP256K1_FE_CONST(0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000)]]
 212 |  ]
 213 |  
 214 | +ellsq_enc_tests = [
 215 | +    [[0x54,0xca,0xd2,0x27,0xb2,0xc9,0x8d,0x5f,0x7c,0x78,0x8c,0xfc,0x3d,0xaf,0xd6,0x52,0xf5,0x8f,0x69,0xcf,0xef,0x63,0x2b,0x82,0x2b,0x35,0xd0,0xb0,0xe2,0x4f,0xc0,0x3a,0xd2,0x8c,0xa1,0x4b,0x6f,0x62,0xd4,0x53,0x79,0xc5,0x3f,0x70,0xee,0x40,0x5c,0xa9,0x2c,0xe7,0xb6,0xf9,0x70,0x83,0x13,0x05,0xf2,0x7d,0xc4,0x1e,0xb6,0x9d,0xe0,0x6e], [0x02,0x11,0x62,0x89,0x03,0x32,0x88,0x91,0xae,0x09,0xd1,0x08,0xd8,0x92,0x43,0xe4,0x7e,0x10,0x9f,0xe7,0xb8,0xbb,0x1e,0x2d,0xf1,0xa3,0xae,0x9b,0x0e,0x78,0x08,0x54,0x9c]],

sipa commented at 5:15 PM on January 7, 2022:

You could write these as b"\x54\xca\xd2\x27\xb2..." to directly construct bytes objects.

stratospher commented at 2:43 PM on January 8, 2022:

Thanks! That looks really elegant.

sipa commented at 5:16 PM on January 7, 2022: member

Cool! Nice to see this works.

I've left a number of comments to simplify the code.

stratospher force-pushed on Jan 8, 2022

in test/functional/test_framework/key.py:127 in 56cb9c6296 outdated

  94 | @@ -95,6 +95,13 @@ def on_curve(self, p1):
  95 |          z4 = pow(z2, 2, self.p)
  96 |          return z1 != 0 and (pow(x1, 3, self.p) + self.a * x1 * z4 + self.b * z2 * z4 - pow(y1, 2, self.p)) % self.p == 0
  97 |  
  98 | +    def is_infinity(self, p1):
  99 | +        """Return true if Jacobian tuple p is at infinity"""
 100 | +        _, _, z1 = p1

sipa commented at 2:17 PM on January 8, 2022:

Alternative: return p1[2] == 0.

stratospher commented at 3:39 PM on January 8, 2022:

Nice! Done.

in test/functional/test_framework/key.py:83 in cdecacdc4f outdated

  78 | +    def __truediv__ (self, o): return fe(self.val * o.invert().val)
  79 | +
  80 | +    def invert      (self   ): return fe(pow(self.val, self.p-2, self.p))
  81 | +    def is_odd(self): return (self.val & 1) != 0
  82 | +    def is_square(self):
  83 | +        ret_val = modsqrt(self.val, fe.p)

sipa commented at 2:25 PM on January 8, 2022:

Faster alternative: return jacobi_symbol(self.val, SECP256K1_FIELD_SIZE) >= 0

stratospher commented at 3:39 PM on January 8, 2022:

Nice! Done.

in test/functional/test_framework/key.py:80 in cdecacdc4f outdated

  75 | +    def __neg__     (self   ): return fe(-self.val)
  76 | +    def __pow__     (self, s): return fe(pow(self.val, s, self.p))
  77 | +    def __sub__     (self, o): return fe(self.val - o.val)
  78 | +    def __truediv__ (self, o): return fe(self.val * o.invert().val)
  79 | +
  80 | +    def invert      (self   ): return fe(pow(self.val, self.p-2, self.p))

sipa commented at 2:26 PM on January 8, 2022:

Faster alternative: return fe(modinv(self.val, SECP256K1_FIELD_SIZE))

stratospher commented at 3:39 PM on January 8, 2022:

Nice! Done.

in test/functional/test_framework/key.py:67 in cdecacdc4f outdated

  59 | @@ -60,6 +60,33 @@ def modsqrt(a, p):
  60 |          return sqrt
  61 |      return None
  62 |  
  63 | +SECP256K1_FIELD_SIZE = 2**256 - 2**32 - 977
  64 | +
  65 | +class fe:
  66 | +    """Prime field over 2^256 - 2^32 - 977"""
  67 | +    p = SECP256K1_FIELD_SIZE

sipa commented at 2:27 PM on January 8, 2022:

p isn't needed anymore; you can also use SECP256K1_FIELD_SIZE directly.

stratospher commented at 3:39 PM on January 8, 2022:

Done.

stratospher force-pushed on Jan 8, 2022

in test/functional/test_framework/ellsq.py:5 in e755867f79 outdated

   0 | @@ -0,0 +1,245 @@
   1 | +# Source: https://github.com/sipa/writeups/tree/main/elligator-square-for-bn
   2 | +"""Test-only Elligator Squared implementation
   3 | +
   4 | +WARNING: This code is slow, uses bad randomness, does not properly protect
   5 | +keys, and is trivially vulnerable to side channel attacks. Do not use for

sipa commented at 2:33 PM on January 8, 2022:

Slow and bad randomness apply, but elligator square inherently doesn't deal with secret keys, so there is nothing to protect, and side channel attacks do not apply.

stratospher commented at 3:39 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:201 in e755867f79 outdated

 196 | +            # t should appear exactly once in preimages
 197 | +            for j in range(4):
 198 | +                field_ele = r(ge[0], ge[1], j)
 199 | +                if field_ele is not None:
 200 | +                    matches += (field_ele == t)
 201 | +            assert(matches == 1)

sipa commented at 2:34 PM on January 8, 2022:

No braces needed around matches == 1 (here and elsewhere)

stratospher commented at 3:39 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:236 in e755867f79 outdated

 183 | +    [b"\x5f\xb8\x07\xce\x10\x0c\x90\xd2\x83\x7c\xcf\xc9\x4d\x8f\x8b\xa5\xd3\x5c\xd3\xd6\xfa\xfc\xd2\xf4\x1f\x24\x5b\x59\x6e\x36\x00\x57\xa0\x47\xf8\x31\xef\xf3\x6f\x2d\x7c\x83\x30\x36\xb2\x70\x74\x5a\x2c\xa3\x2c\x29\x05\x03\x2d\x0b\xe0\xdb\xa4\xa5\x91\xc9\xfb\xd8", b"\x03\x41\x58\x28\x65\x43\x5e\xe9\xc8\xc9\x27\xc3\x49\xbd\x3e\x43\x7b\xce\x2b\x5c\xfc\xd0\xc4\x17\x77\xc3\x4c\x71\xc6\x7b\x14\x06\x93"],
 184 | +    [b"\x1e\x76\x57\x72\xbf\x72\xde\xb8\x81\x54\x16\xbd\x54\x45\xdd\x75\x50\xcd\x86\x7a\xa2\x5a\xc6\x3f\x6f\xd9\xaf\xd3\x2f\x92\x1c\xc8\x8a\x06\x1a\xb5\xf6\x98\x1b\x55\x92\x1b\x90\x5b\x6f\x4f\x3d\xf4\x82\x5d\x79\x72\xd6\x99\xe3\xb4\x21\x4e\x40\x44\xcf\xbe\x65\x34", b"\x03\x90\xd2\x94\x30\x92\xec\x7e\xd8\xff\x5a\xf7\x04\x43\x2d\x0d\xbe\xb0\x33\x7c\xbf\x58\x22\x87\x18\x32\x76\x38\x68\x1f\x70\xd7\xf0"],
 185 | +    [b"\x86\xef\x92\xfd\x28\x09\x85\x4f\x74\xf7\x5a\xeb\xbe\xa1\x8a\xee\xc0\xee\xdd\x4e\x81\x92\xc8\x8c\xd7\xcf\xf5\xdf\xc0\x8a\x57\xdc\x32\x73\xbf\x6f\x39\x2d\xee\x48\x4a\x72\x2c\x3d\xb0\x0c\x0e\xfb\x40\xd5\x1e\x8a\x72\xfc\xfb\x78\x3f\xa7\xeb\xd4\x30\x82\xdb\x71", b"\x02\x31\x74\x79\x29\x80\x2d\x79\x76\x02\x26\x71\xb2\xf7\x5a\xc0\x31\x18\x56\xb3\x84\xf4\xb9\xa8\x00\x0d\x44\xa2\xab\xc5\x90\x3a\xd4"]
 186 | +]
 187 | +
 188 | +class TestFrameworkEllsq(unittest.TestCase):

sipa commented at 2:44 PM on January 8, 2022:

You'll need to add "ellsq" to the TEST_FRAMEWORK_MODULES in test/functional/test_runner.py.

stratospher commented at 3:40 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:158 in e755867f79 outdated

 153 | +    if SECP256K1.is_infinity(P):
 154 | +        P = T
 155 | +    P = SECP256K1.affine(P)
 156 | +    return (fe(P[0]), fe(P[1]))
 157 | +
 158 | +P = SECP256K1_FIELD_SIZE

sipa commented at 2:47 PM on January 8, 2022:

Perhaps don't use P here (it's also used as a function argument further). Alternatively, just drop it and use SECP256K1_FIELD_SIZE directly.

stratospher commented at 3:40 PM on January 8, 2022:

Thanks! Done.

stratospher commented at 2:47 PM on January 8, 2022: contributor

Thanks for your really nice review @sipa! I’ve addressed your comments. Ready for further review.

in test/functional/test_framework/ellsq.py:219 in e755867f79 outdated

 214 | +                    assert (ge == group_ele)
 215 | +            assert len(set(preimages)) == len(preimages)
 216 | +
 217 | +    def test_ellsq_mapping(self):
 218 | +        for test_vector in ELLSQ_TESTS:
 219 | +            ge, fe = test_vector

sipa commented at 2:48 PM on January 8, 2022:

fe classes with class name. Maybe call it fes (since it's a list)?

stratospher commented at 3:40 PM on January 8, 2022:

Thanks! Done.

stratospher force-pushed on Jan 8, 2022

stratospher commented at 3:40 PM on January 8, 2022: contributor

Thanks again @sipa! I’ve addressed your comments. Ready for further review.

in test/functional/test_framework/ellsq.py:17 in 90d044f51c outdated

  12 | +
  13 | +C1 = fe(-3).sqrt()
  14 | +C2 = (C1 - fe(1)) / fe(2)
  15 | +B = fe(7)
  16 | +
  17 | +def f(u):

sipa commented at 6:30 PM on January 8, 2022:

Maybe give this function a more descriptive name, and a longer comment?

E.g. "Given any field element u (of type fe), return the affine X and Y coordinates of a point on the secp256k1 curve"

stratospher commented at 9:20 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:40 in 90d044f51c outdated

  35 | +        return (x, y)
  36 | +    else:
  37 | +        return (x, -y)
  38 | +
  39 | +def r(x,y,i):
  40 | +    """Reverse mapping function"""

sipa commented at 6:34 PM on January 8, 2022:

Same here, something like "Given the X and Y coordinates of a point on the secp256k1 curve (of type fe), return a value u such that f(u) = (x,y), or None. There can be up to 4 such inverses, and i selects which formula to use. Each i can independently from other i values return a value or None. All non-None values returned across all 4 i values are guaranteed to be distinct, and together they will cover all inverses of (x,y) under f."

stratospher commented at 9:20 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:130 in 90d044f51c outdated

 125 | +]
 126 | +
 127 | +def encode(P):
 128 | +    while True:
 129 | +        u = fe(random.randrange(1, SECP256K1_ORDER))
 130 | +        fe1 = f(u)

sipa commented at 6:36 PM on January 8, 2022:

Using fe1 as variable name here is a bit confusing, as the return value is a pair of fe values (the x and y coordinates of a point on the curve). Use p or ge or so?

in test/functional/test_framework/ellsq.py:137 in 90d044f51c outdated

 132 | +        fe1 = (fe1[0].val, fe1[1].val, 1)
 133 | +        T = SECP256K1.negate(fe1)
 134 | +        Q = SECP256K1.add(T, P)
 135 | +        if SECP256K1.is_infinity(Q):
 136 | +            Q = T
 137 | +        j = secrets.choice([0,1,2,3])

sipa commented at 6:36 PM on January 8, 2022:

This is a bit overkill for tests. You can use random.getrandbits(2) or random.randrange(4). The secrets dependency can be dropped too then.

in test/functional/test_framework/ellsq.py:144 in 90d044f51c outdated

 139 | +        v = r(fe(Q[0]), fe(Q[1]), j)
 140 | +        if v is not None:
 141 | +            return (u, v)
 142 | +
 143 | +def decode(u, v):
 144 | +    fe1 = f(u)

sipa commented at 6:37 PM on January 8, 2022:

These aren't field elements, but group elements (or coordinate pairs, or points).

in test/functional/test_framework/ellsq.py:35 in 90d044f51c outdated

  30 | +            x3 = fe(1) - (fe(1)+B+s)**2 / (fe(3)*s)
  31 | +            g3 = x3**3 + B
  32 | +            x, g = x3, g3
  33 | +    y = g.sqrt()
  34 | +    if y.is_odd() == u.is_odd():
  35 | +        return (x, y)

sipa commented at 6:38 PM on January 8, 2022:

The braces aren't actually necessary (here and elsewhere).

in test/functional/test_framework/ellsq.py:147 in 90d044f51c outdated

 142 | +
 143 | +def decode(u, v):
 144 | +    fe1 = f(u)
 145 | +    fe2 = f(v)
 146 | +    # convert fe1 and fe2 to jacobian form for EC operations
 147 | +    jac1 = (fe1[0].val, fe1[1].val, 1)

sipa commented at 6:40 PM on January 8, 2022:

Unnecessary variables?

in test/functional/test_framework/ellsq.py:162 in 90d044f51c outdated

 157 | +FIELD_BITS = SECP256K1_FIELD_SIZE.bit_length()
 158 | +FIELD_BYTES = (FIELD_BITS + 7) // 8
 159 | +
 160 | +def encode_bytes(P):
 161 | +    u, v = encode(P)
 162 | +    up = u.val

sipa commented at 6:40 PM on January 8, 2022:

Unnecessary variables?

in test/functional/test_framework/ellsq.py:164 in 90d044f51c outdated

 159 | +
 160 | +def encode_bytes(P):
 161 | +    u, v = encode(P)
 162 | +    up = u.val
 163 | +    vp = v.val
 164 | +    return up.to_bytes(FIELD_BYTES, 'big') + vp.to_bytes(FIELD_BYTES, 'big')

sipa commented at 6:41 PM on January 8, 2022:

What do you think about adding a to_bytes method to fe (which just returns self.val.to_bytes(32, 'big')), and then using return u.to_bytes() + v.to_bytes() here?

stratospher commented at 9:21 PM on January 8, 2022:

Thanks! Looks really neat.

DrahtBot commented at 6:42 PM on January 8, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	theStack, sipa

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#27452 (test: cover addrv2 anchors by adding TorV3 to CAddress in messages.py by pinheadmz)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in test/functional/test_framework/ellsq.py:167 in 90d044f51c outdated

 162 | +    up = u.val
 163 | +    vp = v.val
 164 | +    return up.to_bytes(FIELD_BYTES, 'big') + vp.to_bytes(FIELD_BYTES, 'big')
 165 | +
 166 | +def decode_bytes(enc):
 167 | +    u = (int.from_bytes(enc[:FIELD_BYTES], 'big') & ((1 << FIELD_BITS) - 1)) % SECP256K1_FIELD_SIZE

sipa commented at 6:43 PM on January 8, 2022:

The & ((1 << FIELD_BITS) - 1) doesn't do anything here, as FIELD_BITS is 256, an exact multiple of 8.

Similar to above, what do you think about adding a (static) from_bytes(b) method to fe (returning fe(int.from_bytes(b, 'big'))), and then using return decode(fe.from_bytes(enc[:32]), fe.from_bytes(enc[32:])) here?

stratospher commented at 9:22 PM on January 8, 2022:

Thanks! Done.

in test/functional/test_framework/ellsq.py:238 in 90d044f51c outdated

 233 | +            assert group_ele1 == group_ele2
 234 | +
 235 | +    def test_decode_test_vectors(self):
 236 | +        for test_vector in ELLSQ_ENC_TESTS:
 237 | +            ell64,  pubkey = test_vector
 238 | +            u, v = decode_bytes(ell64)

sipa commented at 6:44 PM on January 8, 2022:

u, v are confusing here; the result of decode_bytes are X and Y coordinates. Just call them x, y?

in test/functional/test_framework/ellsq.py:144 in 90d044f51c outdated

 122 | +    [(fe(0x49a0dc068c3f117aefdc842d3d358153f677f04c6dabc9c91b09d452fef27b66), fe(0x7b944da48a175dbc444ead8db82eff66b081a8aae6453fed2bca9720b44dd6e5)), [fe(0x7bf1e2b1720c1c440db64687f16439fa41b398338095f24ebeec0cfa88750dc9), fe(0xdc97e26d3137445d6c1269b61a7655010c19c36a2e361066e31e2bb10403470b), None                                                                  , None                                                                  ]],
 123 | +    [(fe(0xd09a4047f158fe52f96c661d02c68657c4c976ea96ea85ef46d6985bd540756b), fe(0xe793bfaae9300f18e6f9b55aae26322368b61d51ae5022efe266c72d574178bc)), [fe(0x7e6175fdfbb9fb4faf6e2b925ef86c4a444d819aaa82dbee545d3d9b296375be), None                                                                  , None                                                                  , None                                                                  ]],
 124 | +    [(fe(0x3498662504b73c7c8cecb6c33cd493bdfc190e0f87d913d7ff9ad42e222bfe95), fe(0x245b3a61b8d46997f14f2fea2874899691eb32542b9907d65eb9d21d42454021)), [fe(0x7f556282c3dd9d263390d6bbddada698ab8fd7c7d1a06498f42b30437c8361ad), None                                                                  , None                                                                  , None                                                                  ]]
 125 | +]
 126 | +
 127 | +def encode(P):

sipa commented at 6:45 PM on January 8, 2022:

It seems this function takes as input a point in jacobian coordinates, but still assumes the Z coordinate to be 1. Perhaps just accept an input in affine coordinates (just X, Y)?

stratospher force-pushed on Jan 8, 2022

stratospher commented at 9:23 PM on January 8, 2022: contributor

Thanks again @sipa! I’ve addressed your comments. Ready for further review.

stratospher force-pushed on Feb 3, 2022

stratospher commented at 7:33 PM on February 3, 2022: contributor

Made some changes to simplify the Elligator squared interface

interact with pubkeys instead of group elements. (added get_group_element() and set_from_curve_point() in ECPubkey for this purpose)
rename encode_bytes() to ellsq_encode() and decode_bytes() to ellsq_decode()
sort TEST_FRAMEWORK_MODULES in alphabetical order

stratospher force-pushed on Feb 4, 2022

stratospher force-pushed on Apr 2, 2022

stratospher commented at 3:21 PM on April 2, 2022: contributor

Updated the elligator squared encoding function signature from ellsq_encode(pubkey) to ellsq_encode(pubkey, randombytes) in order to test the BIP 324 test vectors in python.

stratospher force-pushed on Apr 2, 2022

in test/functional/test_framework/ellsq.py:90 in 0650f1ffcb outdated

  85 | +        if i == 2:
  86 | +            s = (z + (z**2 - fe(16)*(B+fe(1))**2).sqrt()) / fe(4)
  87 | +        else:
  88 | +            if z**2 == fe(16)*(B+fe(1))**2:
  89 | +                return None
  90 | +            s = (z - (z**2 - fe(16)*(B+fe(1))**2).sqrt()) / fe(4)

KevinMusgrave commented at 12:27 PM on April 4, 2022:

I think this might be easier to read if fe(16)*(B+fe(1))**2) and z**2 - fe(16)*(B+fe(1))**2 were assigned to variables.

stratospher commented at 7:56 AM on December 12, 2022:

thanks @KevinMusgrave, that's true. it's built on top of #26222 now and much better readability.

in test/functional/test_framework/ellsq.py:214 in 0650f1ffcb outdated

 209 | +        enc : 64 bytes encoding
 210 | +    Returns: ECPubKey object
 211 | +    """
 212 | +    x, y = decode(fe.from_bytes(enc[:32]), fe.from_bytes(enc[32:]))
 213 | +    if y.val % 2 == 0:
 214 | +        compressed_sec = b'\x02' + x.val.to_bytes(32, 'big')

rage-proof commented at 6:14 PM on May 9, 2022:

The same as in ellsq_encode, you can just use x.to_bytes() now.

stratospher commented at 7:50 AM on December 12, 2022:

thanks @rage-proof! i've updated the code to use this.

theStack commented at 6:14 PM on July 17, 2022: contributor

Concept ACK

stratospher force-pushed on Oct 3, 2022

stratospher renamed this:
~~test: add python implementation of Elligator squared~~
test: add python implementation of Elligator swift
on Oct 3, 2022

stratospher commented at 7:20 PM on October 3, 2022: contributor

updates include:
- elligator swift instead of elligator squared
- built on top of #26222
references - https://github.com/bitcoin-core/secp256k1/pull/1129, https://github.com/sipa/bitcoin/tree/202209_ellswift_py
for #24748, we'd want to keep the entropy derivations(like for u, j, in ellswift_create()) similar to how it's done in PR 1129

in test/functional/test_framework/ellswift.py:117 in fe544ad9bd outdated

 112 | +        privkey : ECKey object
 113 | +        randombytes : 32 bytes entropy
 114 | +    Returns: 64 bytes encoding
 115 | +    """
 116 | +    m = hashlib.sha256()
 117 | +    m.update(b"secp256k1_ellswift_create")

sipa commented at 7:24 PM on October 3, 2022:

Why recreate the exact PRNG used by the libsecp256k1 implementation?

I think it'd be much simpler to use the Python PRNG (the random one, or if we actually wanted it "secure", the secrets one, but I think that's overkill for a test-only implementation).

stratospher commented at 7:48 AM on December 12, 2022:

makes sense, this is much more simpler! (initially wanted to add test vectors, but wouldn't be very useful here) i've updated the PR to use BIP 324's reference implementation for consistency.

stratospher force-pushed on Dec 12, 2022

DrahtBot added the label Needs rebase on Jan 3, 2023

stratospher force-pushed on Feb 6, 2023

DrahtBot removed the label Needs rebase on Feb 6, 2023

stratospher force-pushed on Feb 6, 2023

theStack commented at 6:00 PM on March 30, 2023: contributor

Concept ACK

For reviewers it may make sense to mention in the description that this PR is based on #26222.

DrahtBot added the label Needs rebase on Apr 28, 2023

stratospher force-pushed on Jun 1, 2023

DrahtBot removed the label Needs rebase on Jun 1, 2023

theStack commented at 3:04 PM on June 2, 2023: contributor

Maybe being overly pedantic, but would it make sense to explicitly unit-test for ellswift-decoding inputs that are considered undefined in the original SwiftEC paper (i.e. the ones that get remapped, namely: u = 0, t = 0, u^3 + t^2 + 7 = 0)? E.g.:

diff --git a/test/functional/test_framework/ellswift.py b/test/functional/test_framework/ellswift.py
index b84012052a..f015ecf5b8 100644
--- a/test/functional/test_framework/ellswift.py
+++ b/test/functional/test_framework/ellswift.py
@@ -93,6 +93,18 @@ class TestFrameworkEllSwift(unittest.TestCase):
             x = xswiftec(u, t)
             self.assertTrue(GE.is_valid_x(x))

+        # Check that inputs which are considered undefined in the original
+        # SwiftEC paper can also be decoded successfully (by remapping)
+        undefined_inputs = [
+            (FE(0), FE(23)),  # u = 0
+            (FE(42), FE(0)),  # t = 0
+            (FE(5), FE(-132).sqrt()),  # u^3 + t^2 + 7 = 0
+        ]
+        assert undefined_inputs[-1][0]**3 + undefined_inputs[-1][1]**2 + 7 == 0
+        for u, t in undefined_inputs:
+            x = xswiftec(u, t)
+            self.assertTrue(GE.is_valid_x(x))
+
     def test_elligator_roundtrip(self):
         """Verify that encoding using xelligatorswift decodes back using xswiftec."""
         for _ in range(32):

Of course there is no way to check if the relevant code-paths have been triggered in xswiftec, but I at least manually checked with good-old print debugging 😅

diff --git a/test/functional/test_framework/ellswift.py b/test/functional/test_framework/ellswift.py
index b84012052a..0e9f6b3ec4 100644
--- a/test/functional/test_framework/ellswift.py
+++ b/test/functional/test_framework/ellswift.py
@@ -18,10 +18,13 @@ MINUS_3_SQRT = FE(-3).sqrt()
 def xswiftec(u, t):
     """Decode field elements (u, t) to an X coordinate on the curve."""
     if u == 0:
+        print("case1")
         u = FE(1)
     if t == 0:
+        print("case2")
         t = FE(1)
     if u**3 + t**2 + 7 == 0:
+        print("case3")
         t = 2 * t
     X = (u**3 + 7 - t**2) / (2 * t)
     Y = (X + t) / (MINUS_3_SQRT * u)

$ python3 -m unittest ./test_framework/ellswift.py
case1
case2
case3
...
----------------------------------------------------------------------
Ran 3 tests in 4.729s

OK

stratospher force-pushed on Jun 9, 2023

stratospher commented at 6:14 PM on June 9, 2023: contributor

@theStack I've updated the PR to include your suggestion. Documenting it like this might also help people who haven't gone through the algo notice this behaviour in the tests.

DrahtBot added the label CI failed on Jun 9, 2023

in test/functional/test_framework/ellswift.py:66 in 8054c413b9 outdated

  61 | +        return -w * (u * (1 + MINUS_3_SQRT) / 2 + v)
  62 | +
  63 | +def xelligatorswift(x):
  64 | +    """Given a field element X on the curve, find (u, t) that encode them."""
  65 | +    while True:
  66 | +        u = FE(random.randrange(1, GE.ORDER))

theStack commented at 10:47 PM on June 22, 2023:

nit: this obviously works fine in practice, but strictly speaking the limiting by group order is misleading, as we have a field element here. Randomizing in the full 256-bit range should be closest to the actual implementation in libsecp256k1 (the reduction then happens in the FE constructor, if needed)

        u = FE(random.randrange(1, 2**256))

See https://github.com/bitcoin-core/secp256k1/blob/3c1a0fd37f6b6f6def39498cef48ba6652ff5714/src/modules/ellswift/main_impl.h#L357-L360 ("we prefer uniform u32 over uniform u")

sipa commented at 1:49 PM on June 27, 2023:

Given that it's reduced to an FE anyway, arguably the correct value is FE(random.randrange(1, FE.SIZE)).

To be clear, there is no observable difference between using GE.ORDER, 2**256, or FE.SIZE; they're all sufficiently close together that it doesn't matter, and the ElligatorSwift code in libsecp256k1 also relies on the fact that they're so close together.

But the "we prefer uniform u32 over uniform u" doesn't really apply here, as u is a field element, not a 32-byte array. In other words, if randrange(1, 2**256) is used, and the returned value exceeds FE.SIZE, the FE() constructor will reduce it modulo FE.SIZE anyway, giving rise to slightly higher probability for values in range 0..(2**256-FE.SIZE).

theStack commented at 6:06 PM on June 27, 2023:

Thanks for clarifying, that makes sense.

stratospher commented at 6:51 PM on June 28, 2023:

interesting! done.

sipa commented at 5:52 PM on June 28, 2023: member

@stratospher Want to rebase? It'd be good to get rid of the merge commit in this PR's history.

stratospher force-pushed on Jun 28, 2023

stratospher commented at 6:51 PM on June 28, 2023: contributor

Rebased on master, updated to address review comment and to just use commits from 26222 which this depends on.

maflcko commented at 6:43 AM on June 29, 2023: member

Are you sure you rebased on current master?

stratospher force-pushed on Jun 29, 2023

DrahtBot removed the label CI failed on Jun 29, 2023

in test/functional/test_framework/ellswift.py:68 in afd762afa3 outdated

  60 | +        return w * (u * (1 - MINUS_3_SQRT) / 2 + v)
  61 | +    if case & 5 == 5:
  62 | +        return -w * (u * (1 + MINUS_3_SQRT) / 2 + v)
  63 | +
  64 | +def xelligatorswift(x):
  65 | +    """Given a field element X on the curve, find (u, t) that encode them."""

sipa commented at 3:02 PM on June 29, 2023:

Perhaps it makes sense to assert here that X is actually on the curve.

assert GE.is_valid_x(x)

stratospher commented at 6:22 PM on June 29, 2023:

true! added.

in test/functional/test_framework/ellswift.py:91 in afd762afa3 outdated

  82 | +    t = FE(int.from_bytes(pubkey_theirs[32:], 'big'))
  83 | +    d = int.from_bytes(privkey, 'big')
  84 | +    return (d * GE.lift_x(xswiftec(u, t))).x.to_bytes()
  85 | +
  86 | +
  87 | +class TestFrameworkEllSwift(unittest.TestCase):

sipa commented at 3:05 PM on June 29, 2023:

Would it make sense to include the BIP324 test vectors here? (https://github.com/bitcoin/bips/blob/master/bip-0324/ellswift_decode_test_vectors.csv and https://github.com/bitcoin/bips/blob/master/bip-0324/xswiftec_inv_test_vectors.csv). See test_schnorr_testvectors in test/functional/test_framework/key.py for an example that involves CSV files.

stratospher commented at 6:23 PM on June 29, 2023:

makes sense to have test vectors. i've included them.

sipa commented at 3:08 PM on June 29, 2023: member

Code review ACK afd762afa39569d8932dd0cf62f8d134e25fc651

in test/functional/test_framework/ellswift.py:127 in afd762afa3 outdated

 122 | +        for _ in range(32):
 123 | +            privkey1, encoding1 = ellswift_create()
 124 | +            privkey2, encoding2 = ellswift_create()
 125 | +            shared_secret1 = ellswift_ecdh_xonly(encoding1, privkey2)
 126 | +            shared_secret2 = ellswift_ecdh_xonly(encoding2, privkey1)
 127 | +            assert shared_secret1 == shared_secret2

theStack commented at 3:46 PM on June 29, 2023:

non-blocking nit:

            self.assertEqual(shared_secret1, shared_secret2)

(slightly preferred, as in the case of a mismatch the values would be shown)

stratospher commented at 6:23 PM on June 29, 2023:

done.

theStack approved

theStack commented at 3:57 PM on June 29, 2023: contributor

Code-review ACK afd762afa39569d8932dd0cf62f8d134e25fc651

Regarding #24005 (review), I've prepared at least adding the BIP324 decoding test vectors today (https://github.com/theStack/bitcoin/commit/06c942493af9df766f85dc1387daaa0441e7d10e). Feel free to pick it up either in this PR or a follow-up.

test: Add python ellswift implementation to test framework

Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>

714fb2c02a

test: Add ellswift unit tests

remove util also since unit tests there were removed in #27538

Co-authored-by: theStack <sebastian.falbesoner@gmail.com>

a31287718a

test: add ellswift test vectors from BIP324

The test vector input file is taken from:
1. https://github.com/bitcoin/bips/blob/master/bip-0324/xswiftec_inv_test_vectors.csv
2. https://github.com/bitcoin/bips/blob/master/bip-0324/ellswift_decode_test_vectors.csv

Co-authored-by: theStack <sebastian.falbesoner@gmail.com>

4f4d039a98

stratospher force-pushed on Jun 29, 2023

stratospher commented at 6:23 PM on June 29, 2023: contributor

Thanks @sipa, @theStack! I've updated to include ellswift test vectors from BIP 324 + addressed review comments.

theStack approved

theStack commented at 9:52 PM on June 29, 2023: contributor

ACK 4f4d039a98370a91e3cd5977352a9a4b260aa06b :crocodile:

Checked that since my previous ACK, review suggestions were tackled and the ellswift encoding/decoding test vectors were added (nice, wasn't aware of csv.DictReader)! Also verified that the added .csv files are identical to the ones from the BIP repository.

DrahtBot requested review from sipa on Jun 29, 2023

sipa commented at 6:16 PM on June 30, 2023: member

ACK 4f4d039a98370a91e3cd5977352a9a4b260aa06b

DrahtBot removed review request from sipa on Jun 30, 2023

fanquake merged this on Jun 30, 2023

fanquake closed this on Jun 30, 2023

sidhujag referenced this in commit 421153c7ad on Jul 1, 2023

kwvg referenced this in commit af2c149daa on Feb 14, 2024

kwvg referenced this in commit a92fc01ca6 on Feb 14, 2024

kwvg referenced this in commit f8061fde3e on Feb 14, 2024

kwvg referenced this in commit cfc2c4e987 on Feb 15, 2024

PastaPastaPasta referenced this in commit 3710439adf on Feb 19, 2024

PastaPastaPasta referenced this in commit 0f0c53aed3 on Feb 19, 2024

bitcoin locked this on Jun 29, 2024

stratospher deleted the branch on Jul 17, 2024