Introduce secp256k1 module with field and group classes to test framework

sipa commented at 5:12 pm on October 1, 2022: member

This PR rewrites a portion of test_framework/key.py, in a compatible way, by introducing classes that encapsulate field element and group element logic, in an attempt to be more readable and reusable.

To maximize readability, the group element logic does not use Jacobian coordinates. Instead, group elements just store (affine) X and Y coordinates directly. To compensate for the performance loss this causes, field elements are represented as fractions. This undoes most, but not all, of the performance loss, and there is a few % slowdown (as measured in feature_taproot.py, which heavily uses this).

The upside is that the implementation for group laws (point doubling, addition, subtraction, …) is very close to the mathematical description of elliptic curves, and this extends to potential future extensions (e.g. ElligatorSwift as needed by #27479).

fanquake added the label Tests on Oct 1, 2022

sipa force-pushed on Oct 1, 2022

DrahtBot commented at 7:02 pm on October 1, 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, stratospher, achow101
Concept ACK	hebasto, pinheadmz, real-or-random

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:

#27653 (test: add unit test coverage for Python ECDSA implementation by theStack)
#24005 (test: add python implementation of Elligator swift by stratospher)

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/key.py:226 in 4d6be31336 outdated

394+
395+    def __sub__(self, a):
396+        """Subtract two points, or subtract infinity from a point."""
397+        if a is None:
398+            return self
399+        return self + (-a)

amovfx commented at 9:09 pm on October 1, 2022:

I’m curious as to why the return value isnt self - a? is it because this function calls the previously declared __add__ and requires a negative input to evaluate properly? or (-a) is calling the __mul__

sipa commented at 9:18 pm on October 1, 2022:

self - a would just trigger infinite recursion, as it’s equivalent to self.__sub__(a).

Writing self + (-a) on the other hand is self.__add__(a.__neg__()).

There is no “negative input”; these objects represent field elements (integers modulo 2^256 - 2^32 - 977), which have no concept of positive/negative. This function is implementing how to compute self - a; we do that by adding self to the negation of a.

amovfx commented at 9:15 pm on October 1, 2022: none

Reviewed to learn.

sipa force-pushed on Oct 6, 2022

sipa force-pushed on Dec 13, 2022

sipa commented at 4:22 pm on December 13, 2022: member

Rebased.

sipa force-pushed on Dec 13, 2022

in test/functional/test_framework/key.py:44 in 8851fea72a outdated

123+            if isinstance(a, FE):
124+                self.num = (a.num * b.den) % FE.SIZE
125+                self.den = (a.den * b.num) % FE.SIZE
126+            else:
127+                self.num = (a * b.den) % FE.SIZE
128+                self.den = a.num

stratospher commented at 9:53 am on December 22, 2022:

shouldn’t this be b.num?

sipa commented at 8:20 pm on January 4, 2023:

Indeed. Fixed!

in test/functional/test_framework/key.py:132 in 8851fea72a outdated

211+    def is_square(self):
212+        """Determine if this field element has a square root."""
213+        # Compute the Jacobi symbol of (self / p). Since our modulus is prime, this
214+        # is the same as the Legendre symbol, which determines quadratic residuosity.
215+        # See https://en.wikipedia.org/wiki/Jacobi_symbol for the algorithm.
216+        n, k, t = (self.num * self.den) % FE.SIZE, FE.SIZE, 0

stratospher commented at 12:01 pm on January 3, 2023:

i didn’t understand how n = (self.num * self.den) % FE.SIZE? (and not n = int(self) % FE.SIZE)

sipa commented at 8:21 pm on January 4, 2023:

Ah!

The squareness of num/den = (num*den) / den^2 is the same as that of num*den, because they’re related by a factor den^2, which is always square.

I’ve added a comment to clarify.

DrahtBot added the label Needs rebase on Jan 3, 2023

sipa force-pushed on Jan 4, 2023

DrahtBot removed the label Needs rebase on Jan 4, 2023

in test/functional/test_framework/key.py:111 in 5b4477d629 outdated

192+    def sqrt(self):
193+        """Compute the square root of a field element.
194+
195+        Due to the fact that our modulus is of the form (p % 4) == 3, the Tonelli-Shanks
196+        algorithm (https://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm) is simply
197+        raising the argument to the power (p + 3) / 4.

theStack commented at 1:04 pm on March 31, 2023:

That’s a typo I guess?

0        raising the argument to the power (p + 1) / 4.

sipa commented at 7:35 am on May 12, 2023:

Nice catch, fixed.

theStack commented at 8:55 pm on April 2, 2023: contributor

Concept ACK, +1 on increased readability and reusability :100: (found my way here through #24748)

The slow-down is unfortunately pretty significant on the two x86_64 machines I tested, feature_taproot.py taking almost twice as long compared to master here. Results measured via time:

Machine / OS	master	pr26222 (rebased)
AMD EPYC 7702P (6) / Ubuntu 22.04.1 LTS	40.496s	1m16.587s
Intel (Broadwell) (2) / OpenBSD 7.2	2m57.43s	5m45.90s

For the fun of it, I looked a bit into other ways how to compensate the performance loss. Considering that scalar multiplication with G is a frequent operation, precomputing G’s doubled-up values (G, 2G, 4G, …, (2^254)G, (2^255)G) in a lookup table seemed promising, with the goal of needing only ~128 point additions on average (one for each bit set in the scalar), without any extra double operations. Using that, the execution time is still not matching, but at least pretty close to the master branch (45.334s for first, 3m23.48s for second machine), without too much additional code (~25 LOC):

 0index 7434ba49e..1ad1bc3e4 100644
 1--- a/test/functional/test_framework/key.py
 2+++ b/test/functional/test_framework/key.py
 3@@ -233,6 +233,8 @@ class GE:
 4 
 5     def __mul__(self, a):
 6         """Multiply a point with an integer (scalar multiplication)."""
 7+        if self == SECP256K1_G:  # optimize generator multiplication using precomputed data
 8+            return fast_g.mul(a)
 9         r = None
10         for i in range(a.bit_length() - 1, -1, -1):
11             if r is not None:
12@@ -596,6 +598,31 @@ def sign_schnorr(key, msg, aux=None, flip_p=False, flip_r=False):
13     e = int.from_bytes(TaggedHash("BIP0340/challenge", R.to_bytes_xonly() + P.to_bytes_xonly() + msg), 'big') % GE.ORDER
14     return R.to_bytes_xonly() + ((k + e * sec) % GE.ORDER).to_bytes(32, 'big')
15 
16+
17+class FastG:
18+    """Speed up scalar multiplication with the generator point G
19+       by using a precomputed lookup table with its powers of 2:
20+       g_table = [G, G*2, G*4, G*(2^3), G*(2^4), ..., G*(2^255)]
21+       The points corresponding to each bit set in the scalar are
22+       added up, i.e. on average ~128 point additions take place.
23+    """
24+    def __init__(self):
25+        self.g_table = []  # g_table[i] = G * (2^i)
26+        g_i = SECP256K1_G
27+        for bit in range(256):
28+            self.g_table.append(g_i)
29+            g_i = g_i.double()
30+
31+    def mul(self, a):
32+        result = None
33+        for bit in range(a.bit_length()):
34+            if (a & (1 << bit)):
35+                result += self.g_table[bit]
36+        return result
37+
38+fast_g = FastG()
39+
40+
41 class TestFrameworkKey(unittest.TestCase):
42     def test_schnorr(self):
43         """Test the Python Schnorr implementation."""

(see branch https://github.com/theStack/bitcoin/tree/pr26222_followup_precompute_g_doubles)

Not 100% sure if we even want optimizations like this in test framwork (also, immediately generating data at module import seems kind of hacky), but it may be worth it in this case? I’m pretty sure there are more efficient ways to pursue this idea (e.g. extending the lookup table for larger chunks than only 1-bit pieces to need even less additions), but probably the extra implementation / code clutter / maintenance effort is not worth it. Any other ideas? Happy to hear shadowy secp256k1 super-magicians’ thoughts here :)

DrahtBot added the label Needs rebase on Apr 28, 2023

sipa force-pushed on May 12, 2023

DrahtBot removed the label Needs rebase on May 12, 2023

sipa force-pushed on May 12, 2023

sipa commented at 7:39 am on May 12, 2023: member

@theStack I’ve included your commit to add the precomputed G table. The speedup is significant enough that it’s worth it, I think.

You’ve indeed discovered one of the techniques that are used for speeding up EC multiplications with precomputed tables. Libsecp256k1 today uses a more advanced version of that idea, where all multiples of the form i*16^j*G for all i=0..15, and j=0..63 are precomputed, leaving us with ~63 point additions. An even more advanced approach is discussed in https://github.com/bitcoin-core/secp256k1/pull/1058, if you’re interested. All of that is IMO out of scope for the test framework, though.

fanquake requested review from stratospher on May 12, 2023

fanquake commented at 8:48 am on May 12, 2023: member

cc @real-or-random

hebasto commented at 12:56 pm on May 12, 2023: member

To maximize readability…

Concept ACK on that. At least, non-cryptography abstract algebra background is enough to review the code :)

Partially reviewed. The class FE looks good.

in test/functional/test_framework/key.py:328 in 28ab6c326a outdated

513+        """Determine whether the provided field element is a valid X coordinate."""
514+        return (FE(x)**3 + 7).is_square()
515+
516+    def __str__(self):
517+        """Convert this group element to a string."""
518+        return f"({self.x},{self.y})"

pinheadmz commented at 2:53 pm on May 12, 2023:

Not using hex here?

instagibbs commented at 5:53 pm on May 12, 2023:

it’s defined by FE as hex, so should be fine?

pinheadmz commented at 3:57 pm on May 12, 2023: member

concept ACK

Did as much code review as my tiny brain could handle. I agree that this implementation is easy to read and follow. I checked as much as I could against NIST params and equations from Guide to Elliptic Curve Cryptography

Comparing run time of feature_taproot.py between master and branch, over a few trials with and without RAM disk, the new code only cost me about 5 seconds or about 5% of total runtime.

instagibbs commented at 6:15 pm on May 12, 2023: member

Reads fine to me from my not-even-cryptographer-on-tv level of understanding.

Goes from 27 to 31 seconds on my machine with the precomputed table, which is very easy to understand. Without the table it hikes up to 53 seconds.

real-or-random commented at 9:24 pm on May 12, 2023: contributor

Concept ACK on making the code simple

Since this is something like a reference implementation, I think GE should get the infinity handling right. If you agree that’s a good idea, then it’s perhaps better to have a more explicit representation for infinity than None.

sipa force-pushed on May 13, 2023

sipa commented at 6:35 am on May 13, 2023: member

@real-or-random Makes sense, that simplifies some things too. Done.

in test/functional/test_framework/key.py:179 in b415ad49cf outdated

356+        return f"FE(0x{int(self):x})"
357+
358+class GE:
359+    """Objects of this class represent points (group elements) on the secp256k1 curve.
360+
361+    The point at infinity is represented as None."""

real-or-random commented at 8:34 am on May 13, 2023:

outdated comment

sipa commented at 12:05 pm on May 13, 2023:

Done.

in test/functional/test_framework/key.py:207 in b415ad49cf outdated

384+        x3 = l**2 - 2 * self.x
385+        y3 = l * (self.x - x3) - self.y
386+        return GE(x3, y3)
387+
388+    def __add__(self, a):
389+        """Add two points, or a point and infinity, together."""

real-or-random commented at 8:38 am on May 13, 2023:

This one too. I suggest iterating over the all doc comments, also to make “group element” vs “point” consistent. (__repr__ uses group element.)

sipa commented at 12:05 pm on May 13, 2023:

Done.

sipa force-pushed on May 13, 2023

sipa commented at 12:14 pm on May 13, 2023: member

I’ve made a number of changes.

(Done earlier) Made the GE class represent infinity explicitly.
The new classes / code are in a new module test_framework.secp256k1, which removes the implementation details from test_framework.key, and also feels a bit better namespace-wise (secp256k1.GE is probably more informative to an unfamiliar reviewer than just GE, at least indicating it has something to do with elliptic curve cryptography).
Dropped a number of unused functions / operators.
Swapped the order of arguments in scalar multiplication (it’s int * GE now instead of GE * int).
Renamed GE.mmul to just GE.mul, as it can be used for both single or multi-multiplication.
Shortened/simplified the FE.__init__ method a bit.
Some simplifications that may worsen performance slightly, but help readability:
- GE.__rmul__ is now written in function of GE.mul, avoiding duplication of logic.
- GE.double is gone; to perform doubling, simply add a point to itself.
- GE.mul (and thus also GE.__rmul__) now reduces the input scalars mod the curve order, which means it can deal with negative inputs or inputs exceeding the order. This makes the ECDSA and Schnorr verification formula closer to its typical mathematical description.
Added/rewrote a lot of comments.

I’m now benchmarking feature_taproot.py on a test machine as:

master: ~42s
this PR (just first commit): ~79s
this PR (both commits): ~49s

sipa renamed this:
~~Introduce field element and group element classes to test_framework/key.py~~
Introduce secp256k1 module with field and group classes to test framework
on May 13, 2023

in test/functional/test_framework/secp256k1.py:310 in 8990668473 outdated

305+        """Determine whether the provided field element is a valid X coordinate."""
306+        return (FE(x)**3 + 7).is_square()
307+
308+    def __str__(self):
309+        """Convert this group element to a string."""
310+        if self.infinite:

stratospher commented at 4:39 pm on May 26, 2023:

8990668: s/infinite/infinity

sipa commented at 6:54 pm on May 31, 2023:

Fixed.

in test/functional/test_framework/secp256k1.py:316 in 8990668473 outdated

311+            return "(inf)"
312+        return f"({self.x},{self.y})"
313+
314+    def __repr__(self):
315+        """Get a string representation for this group element."""
316+        if self.infinite:

stratospher commented at 4:39 pm on May 26, 2023:

8990668: s/infinite/infinity maybe make infinity representation in str and repr consistent too.

sipa commented at 7:50 pm on May 26, 2023:

repr is supposed to produce a string that is valid Python code.

in test/functional/test_framework/secp256k1.py:90 in 8990668473 outdated

77+    def __neg__(self):
78+        """Negate a field element."""
79+        return FE(-self.num, self.den)
80+
81+    def __int__(self):
82+        """Convert a field element to an integer in range 0..p-1. The result is cached."""

stratospher commented at 4:48 pm on May 26, 2023:

8990668: isn’t the result updated and not cached here?

sipa commented at 7:49 pm on May 26, 2023:

I don’t understand.

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

I thought of “The result is cached.” as:

someone calls int()
we do operations inside int(), compute what num and den should be and store it locally+lazily without updating actual self.num, self.den
someone calls another FE function
the newly computed value of self.num, self.den gets actually updated only here

isn’t this what caching a variable conceptually means? (even though it doesn’t matter here where self.num, self.den gets actually updated) what did you actually mean by cached in this context?

sipa commented at 6:23 pm on May 31, 2023:

I mean that the computation won’t be repeated if called a second time (due to self.den being set to 1, which triggers the fast path). Whether that’s accomplished through actually remembering the int-converted form or some other mechanism is an implementation detail a user of the class shouldn’t need to care about.

I realize I didn’t mark the FE members num and den as private; I’ve done so now. Perhaps that helps? The way FE values are represented inside the class is an unobservable implementation detail, so calling int(FE) doesn’t “update” the FE object in any observable way - it just makes future calls more efficient.

stratospher commented at 10:32 am on June 1, 2023:

The way FE values are represented inside the class is an unobservable implementation detail, so calling int(FE) doesn’t “update” the FE object in any observable way - it just makes future calls more efficient.

thinking of it this way makes sense. thanks!

in test/functional/test_framework/secp256k1.py:139 in 8990668473 outdated

142+    @staticmethod
143+    def from_bytes(b):
144+        """Convert a 32-byte array to a field element (big endian encoding)."""
145+        v = int.from_bytes(b, 'big')
146+        if v >= FE.SIZE:
147+            return None

stratospher commented at 4:49 pm on May 26, 2023:

89906684: any particular reason why v >= FE.SIZE isn’t supported? (have only thought about ellswift_decode scenario where v could be greater than FE.SIZE)

stratospher commented at 2:07 pm on May 27, 2023:

never mind, just reviewed key.py and saw how this is being used in verify_schnorr, tweak_add_pubkey. agree that it’s better/simpler to keep it as it is.

real-or-random commented at 8:42 am on May 29, 2023:

Perhaps the comment should be explicit about the behavior when v >= FE.SIZE

sipa commented at 6:50 pm on May 31, 2023:

I’ve added a "no overflow allowed" to the comment.

in test/functional/test_framework/key.py:31 in 8990668473 outdated

222-SECP256K1 = EllipticCurve(SECP256K1_FIELD_SIZE, 0, 7)
223-SECP256K1_G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8, 1)
224-SECP256K1_ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
225-SECP256K1_ORDER_HALF = SECP256K1_ORDER // 2
226 
227 class ECPubKey():

stratospher commented at 4:04 am on May 27, 2023:

when defining classes in python, don’t we skip parentheses? using class ECPubKey: and class ECKey: instead of class ECPubKey(): and class ECKey():

sipa commented at 6:49 pm on May 31, 2023:

I guess we should; the parentheses are for listing parent classes, but I believe that an empty list or no parentheses at all don’t make a difference.

Fixed.

in test/functional/test_framework/secp256k1.py:301 in 8990668473 outdated

301+        return GE.lift_x(x)
302+
303+    @staticmethod
304+    def is_valid_x(x):
305+        """Determine whether the provided field element is a valid X coordinate."""
306+        return (FE(x)**3 + 7).is_square()

theStack commented at 1:24 am on May 31, 2023:

Regarding the goal of simple implementation, is there a strong need to keep the FE.is_square method? Right now this is the only call-site, which I think could be replaced by

0        return (FE(x)**3 + 7).sqrt() is not None

I assume trying to actually square is way slower than computing the Jacobi symbol, but since is_valid_x doesn’t appear to be in a critical code-path, that’s probably fine? At least for feature_taproot.py I didn’t see a decrease in performance.

sipa commented at 6:51 pm on May 31, 2023:

I’ve kept the FE.is_square() function, but replaced it with just a x.sqrt() is not None plus a comment that a more efficient algorithm is possible.

This leaves the option of easily adding a more efficient implementation back later if really worth it.

in test/functional/test_framework/secp256k1.py:47 in 8990668473 outdated

42+        if num == 0:
43+            den = 1
44+        self.num = num
45+        self.den = den
46+
47+    def __add__(self, a):

stratospher commented at 5:56 pm on May 31, 2023:

8990668: it would be useful to have radd and rsub back for these operations in xswiftec_inv. (to keep #24005 consistent with BIP’s reference python implementation for easy review.)

sipa commented at 6:49 pm on May 31, 2023:

Ok, I added back.

sipa force-pushed on May 31, 2023

sipa commented at 6:55 pm on May 31, 2023: member

Addressed review comments. I’ve also renamed FE.num and FE.den to FE._num and FE._den to mark them as private (to the extent that Python allows that). All interactions with these objects should be done through their methods.

in test/functional/test_framework/secp256k1.py:63 in ee6e289a4c outdated

58+        """Compute the difference of two field elements (second may be int)."""
59+        if isinstance(a, FE):
60+            return FE(self._num * a._den - self._den * a._num, self._den * a._den)
61+        return FE(self._num - self._den * a, self._den)
62+
63+    def __rsub(self, a):

stratospher commented at 7:46 am on June 1, 2023:

ee6e289:

0    def __rsub__(self, a):

theStack commented at 3:18 pm on June 19, 2023:

ping @sipa, can you address this open suggestion from @stratospher for fixing the reverse subtraction operator overload (s/__rsub/__rsub__/). With that in, I think I’m pretty close then to ACK the PR.

sipa commented at 6:03 pm on June 20, 2023:

Done.

sipa force-pushed on Jun 20, 2023

in test/functional/test_framework/secp256k1.py:268 in 9b8650d230 outdated

260+        return GE(x, y)
261+
262+    @staticmethod
263+    def from_bytes(b):
264+        """Convert a compressed or uncompressed encoding to a group element."""
265+        if len(b) == 33:

theStack commented at 10:07 pm on June 20, 2023:

nit: like from_bytes_xonly does, could throw an assertion error here if the size of the passed encoding is invalid (if a test writer e.g. accidentally passes an x-only-pubkey to from_bytes, getting an assertion is likely more helpful than only getting None):

0        assert len(b) in (33, 65)
1        if len(b) == 33:

(or alternatively, add an else: branch below with assert False, "size must be 33 or 65" or something alike)

sipa commented at 1:35 pm on June 27, 2023:

Done.

theStack approved

theStack commented at 10:20 pm on June 20, 2023: contributor

ACK ab30e81b3bb9e9b02ca1ac835eef04efdf87b4e1

test: add secp256k1 module with FE (field element) and GE (group element) classes

These are primarily designed for ease of understanding, not performance.

1830dd8820

test: EC: optimize scalar multiplication of G by using lookup table

On my machine, this speeds up the functional test feature_taproot.py by
a factor of >1.66x (runtime decrease from 1m16.587s to 45.334s).

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

d4fb58ae8a

sipa force-pushed on Jun 27, 2023

theStack approved

theStack commented at 3:50 pm on June 27, 2023: contributor

re-ACK d4fb58ae8ae9772d025ead184ef8f2c0ea50df3e

(as per $ git range-diff ab30e81b...d4fb58ae, verified that the only changes since the last ACK were a rebase on master and #26222 (review) tackled)

stratospher approved

stratospher commented at 4:33 am on June 28, 2023: contributor

tested ACK d4fb58a. really liked how this PR makes the secp256k1 code in the tests more intuitive and easier to follow!

fanquake requested review from stickies-v on Jun 28, 2023

achow101 commented at 8:20 pm on June 28, 2023: member

ACK d4fb58ae8ae9772d025ead184ef8f2c0ea50df3e

Much simpler to understand, and the more complicated stuff matches up with the descriptions in WIkipedia.

achow101 merged this on Jun 28, 2023

achow101 closed this on Jun 28, 2023

sidhujag referenced this in commit b54fe90f36 on Jun 30, 2023

fanquake referenced this in commit 61d59fed74 on Jun 30, 2023

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

achow101 referenced this in commit 5bbf735def on Sep 29, 2023

Frank-GER referenced this in commit 31cdbf032c on Oct 5, 2023

kwvg referenced this in commit 24836f16ed on Feb 14, 2024

kwvg referenced this in commit 4370b77f08 on Feb 14, 2024

kwvg referenced this in commit 8da7733a24 on Feb 14, 2024

kwvg referenced this in commit 536a6b3289 on Feb 15, 2024

PastaPastaPasta referenced this in commit ca96231181 on Feb 19, 2024

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

bitcoin locked this on Jun 27, 2024

Introduce secp256k1 module with field and group classes to test framework #26222

Reviews

Conflicts