This PR keeps the windowed table from #36327 but accumulate the selected entries in integer Jacobian coordinates, needing a single modular inversion per multiplication instead of one full affine FE addition per window. On my machine, it speeds up feature_taproot.py by ~38% (M1 Pro). Also, adds a unit test cross-checking against the generic GE.mul.
test: use Jacobian coordinates in `FastGEMul` #36896
pull brunoerg wants to merge 1 commits into bitcoin:master from brunoerg:2026-11-test-jac changing 1 files +80 −5-
brunoerg commented at 9:19 PM on November 16, 2026: contributor
-
8d1c38ca88
test: use Jacobian coordinates in FastGEMul
Keep the windowed table from #36327 but accumulate the selected entries in integer Jacobian coordinates, needing a single modular inversion per multiplication instead of one full affine FE addition per window. Speeds up fixed-base multiplication ~4x and feature_taproot.py ~38%. Add a unit test cross-checking against the generic GE.mul.
- DrahtBot added the label Tests on Nov 16, 2026
-
DrahtBot commented at 9:19 PM on November 16, 2026: contributor
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
External sites
- Code coverage & benchmarks: https://corecheck.dev/bitcoin/bitcoin/pulls/36896
- Ralph review <img src=https://review.fish.foo/assets/bitcoin/bitcoin/36896.png alt="Ralph review status"> https://git.fish.foo/bitcoin/bitcoin/pulls/36896#author-ralph
<!--021abf342d371248e50ceaed478a90ca-->
Reviews
See the guideline and AI policy for information on the review process.
Type Reviewers Concept ACK sipa If your review is incorrectly listed, please copy-paste <code><!--meta-tag:bot-skip--></code> into the comment that the bot should ignore.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
-
brunoerg commented at 9:19 PM on November 16, 2026: contributor
cc @theStack @real-or-random (per #36327)
-
real-or-random commented at 9:30 AM on November 18, 2026: contributor
Fwiw, I have no strong opinion on this. The trade-off is the same as in #36327: This PR makes the tests faster at the cost of making test-only, reference-style code more complex. (And since I don't run the Core tests regularly, I can't judge whether that's worth it.) edit: But one consideration is that the more complexity you add here in the EC backend, the smaller the set of potential future reviewers gets.
For the concrete implementation, I wonder which concrete formulas are used. The standard reference is https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html. It would be nice to have the code exactly look like the pseudocode there, and also mention the "formula name", e.g.,
add-1998-cmo-2. (And pick a formula at the top of the list, to make sure we have an efficient one.) -
rustaceanrob commented at 9:59 AM on November 18, 2026: member
If we are going for speed and correctness with is file, are bindings a consideration?
-
real-or-random commented at 10:29 AM on November 18, 2026: contributor
One further problem I want to raise is that there are so many possible choices here (which point representation, which formulas, how much to optimize, etc.). This invites bikeshedding, and we risk a stream of follow-up PRs. And in the end, this is test code...
I discussed this with Claude Opus 5.5. I believe the following three points make a better approach: it hits a well-defined sweet spot in this parameter space, taking into account not only performance but also simplicity and test coverage. If we follow this approach and document the three decisions below in a comment, the approach becomes less arbitrary and thus more robust against future bikeshedding.
No doublings
The windowed FastGEMul method in this PR never doubles the accumulator: the table already contains all multiples
j * 2^(4i) * P, somulonly ever adds an (affine) table entry to the accumulator. This means theadd_affinefunction suffices and we can drop doubling entirely. This is less code, which is a good thing for test code.<details> <summary>AI-generated (Claude Opus 5.5): why the doubling case never happens</summary>
Let
nbe the group order, and assumePhas ordern(true for every point other than infinity on secp256k1, which has cofactor 1). Aftera = a % n, the accumulator before rowiisk*Pwithk = a mod 2^(4i). Rowiaddsj * 2^(4i) * Pwith1 <= j <= 15(j = 0is skipped).- P + P would require
k ≡ j * 2^(4i) (mod n). Both sides lie in[0, n), because15 * 2^252 < n, so they would have to be equal as integers. That is impossible sincek < 2^(4i) <= j * 2^(4i). - P + (-P) would require
k + j * 2^(4i) ≡ 0 (mod n). The left side equalsa mod 2^(4i+4) <= a < n, so it would have to be 0. Thenk = 0, i.e. the accumulator is infinity, and that is the ordinaryO + Qcase, not a cancellation.</details>
Projective coordinates
libsecp256k1 uses Jacobian coordinates, but projective coordinates are a good alternative. If you want to squeeze out the last bit of performance in C, Jacobian may be better. In test code, having projective coordinates adds real value because they use a different method from the code under test.
Complete formulas
Projective coordinates offer fast "complete" formulas, i.e., a single formula that is correct for all inputs, with no special casing for infinity,
P + P, orP + (-P). That is exactly the kind of simplicity we want in test code. And Claude says they are also as fast as the formulas in this PR (benchmark below).<details> <summary>AI-generated (Claude Opus 5.5): suggested code</summary>
Renes–Costello–Batina, "Complete addition formulas for prime order elliptic curves", https://eprint.iacr.org/2015/1060, Algorithm 8 (mixed addition,
a = 0; here3b = 21). Completeness requires a prime-order curve, which secp256k1 is, and the affine input(x2, y2)must not be infinity, so theentry is not Nonecheck inmulstays.The EFD lists the general-
aversion of this formula (Algorithm 5 in the paper) asmadd-2015-rcb: https://hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-madd-2015-rcb. Algorithm 8 is its specialization toa = 0.[@staticmethod](/bitcoin-bitcoin/contributor/staticmethod/) def _proj_add_affine(x1, y1, z1, x2, y2): """Complete addition (Renes-Costello-Batina 2015/1060, Alg. 8; a = 0, 3b = 21) of projective (x1, y1, z1) (x = X/Z, y = Y/Z; (0, 1, 0) is infinity) and affine (x2, y2).""" m = FE.SIZE t0 = x1 * x2 % m t1 = y1 * y2 % m t3 = ((x2 + y2) * (x1 + y1) - t0 - t1) % m t4 = (y2 * z1 + y1) % m y3 = (x2 * z1 + x1) % m x3 = 3 * t0 % m t2 = 21 * z1 % m z3 = (t1 + t2) % m t1 = (t1 - t2) % m y3 = 21 * y3 % m return (t3 * t1 - t4 * y3) % m, (y3 * x3 + t1 * z3) % m, (z3 * t4 + x3 * t3) % mmulstarts fromx, y, z = 0, 1, 0and needs noz == 0branch inside the loop. At the end, ifz == 0it returns infinity; otherwise it returnsGE(x * z_inv % m, y * z_inv % m)withz_inv = pow(z, -1, m).Since
mulnever reaches theP + PandP + (-P)cases (see above), a direct unit test of_proj_add_affineis still needed to cover them. With a complete formula, this is just a comparison againstGEaddition forP + P,P + (-P),O + P, and random pairs, with no special cases.</details>
- P + P would require
-
real-or-random commented at 10:41 AM on November 18, 2026: contributor
If we are going for speed and correctness with is file, are bindings a consideration?
This is an area where the maintainers will have a more informed opinion but I tend to think we want exactly the opposite. Bindings and dependencies are even harder to maintain. This pure Python code can, in principle, stay there forever. We "just" need to make sure we don't turn it into a never-ending optimization game.
This demonstrates the only real advantage of external code: If it's external, people will point their bike-shedding efforts there (or better, nowhere, because the Bitcoin Core repo tends to get more attention than other repos). For example, we could improve FastGEMul in secp256k1lab and subtree it here. Or we could have Python test code in libsecp256k1, and then we get the subtree-ing for free because we already have it. As a secp256k1lab and libsecp256k1 maintainer, I'm open to talk about this but at this point, it's not clear to me whether this is the best thing for Bitcoin Core and/or the other repos.
-
rustaceanrob commented at 11:19 AM on November 18, 2026: member
Bindings and dependencies are even harder to maintain.
I tried this yesterday with claude on a branch and it seems somewhat straight forward. Cross builds in CI need an additional step otherwise the bindngs are a matter of cmake configuration and maintaining the function signatures. The list of functions we use here from secp, from my naive point of view, seem stable in their signature:
<details> <summary>List of functions</summary>
"secp256k1_context_create": (_c_ptr, [ctypes.c_uint]), "secp256k1_ec_pubkey_parse": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_size]), "secp256k1_ec_pubkey_serialize": (_c_int, [_c_ptr, _c_buf, ctypes.POINTER(_c_size), _c_buf, ctypes.c_uint]), "secp256k1_ec_pubkey_create": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_ec_pubkey_negate": (_c_int, [_c_ptr, _c_buf]), "secp256k1_ec_pubkey_tweak_mul": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_ec_pubkey_combine": (_c_int, [_c_ptr, _c_buf, ctypes.POINTER(_c_buf), _c_size]), "secp256k1_ecdsa_signature_parse_compact": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_ecdsa_signature_serialize_der": (_c_int, [_c_ptr, _c_buf, ctypes.POINTER(_c_size), _c_buf]), "secp256k1_ecdsa_signature_normalize": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_ecdsa_sign": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_buf, _c_ptr, _c_buf]), "secp256k1_ecdsa_verify": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_buf]), "secp256k1_keypair_create": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_keypair_sec": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_keypair_xonly_pub": (_c_int, [_c_ptr, _c_buf, ctypes.POINTER(_c_int), _c_buf]), "secp256k1_keypair_xonly_tweak_add": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_xonly_pubkey_parse": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_xonly_pubkey_serialize": (_c_int, [_c_ptr, _c_buf, _c_buf]), "secp256k1_xonly_pubkey_from_pubkey": (_c_int, [_c_ptr, _c_buf, ctypes.POINTER(_c_int), _c_buf]), "secp256k1_xonly_pubkey_tweak_add": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_buf]), "secp256k1_schnorrsig_sign_custom": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_size, _c_buf, ctypes.POINTER(SchnorrsigExtraparams)]), "secp256k1_schnorrsig_verify": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_size, _c_buf]), "secp256k1_ellswift_create": (_c_int, [_c_ptr, _c_buf, _c_buf, _c_buf]), "secp256k1_ellswift_decode": (_c_int, [_c_ptr, _c_buf, _c_buf]),</details>
If we expect the builds to break on every subtree update then yes the bindings would be annoying to maintain, but would that be the case?
-
real-or-random commented at 12:22 PM on November 18, 2026: contributor
I tried this yesterday with claude on a branch and it seems somewhat straight forward. Cross builds in CI need an additional step otherwise the bindngs are a matter of cmake configuration and maintaining the function signatures. The list of functions we use here from secp, from my naive point of view, seem stable in their signature:
Bindings to libsecp256k1 are probably okay in terms of maintenance. But this enters an entirely new trade-off: The non-test code uses libsecp256k1. Currently, the test code uses a different secp256k1 implementation. This means the current tests exercise both the code in Bitcoin Core and libsecp256k1 itself. And as a libsecp256k1 contributor, I can also say that the latter is a probably a good thing because it adds orthogonality to the built-in testing in libsecp256k1:
- The test cases here are "more real" than our own tests in libsecp256k1 because they come from an actual application, e.g., they might hit application-level corner cases.
- They also test how users read and understand the libsecp256k1 docs, i.e., if they misuse our API.
- They test libsecp256k1 under the specific build conditions used in official Bitcoin Core builds, e.g., they would catch a miscompilation in a compiler used here but not tested in libsecp256k1 CI.
If the tests here would also rely on libsecp256k1, all of these advantages would go away.
One could argue that for separation of concerns, the Bitcoin Core tests should only exercise the Bitcoin Core code and the libsecp256k1 tests should be responsible for testing libsecp256k1. But this separation argument never convinced me when it comes to tests. The primary thing I want from a test is that it finds bugs. In particular in projects like these, finding the bug in the first place is 100x important than letting the "right" test find it (which may save a bit of time locating the bug in the actual code but otherwise has no advantages).
-
brunoerg commented at 2:07 PM on November 18, 2026: contributor
Fwiw, I have no strong opinion on this. The trade-off is the same as in #36327: This PR makes the tests faster at the cost of making test-only, reference-style code more complex. (And since I don't run the Core tests regularly, I can't judge whether that's worth it.) edit: But one consideration is that the more complexity you add here in the EC backend, the smaller the set of potential future reviewers gets.
feature_taproot.pyis an important functional test that are strongly used in our mutation testing pipeline. It means that a speed-up of this magnitude can speed up a lot our mutation testing workflow, since we have to run feature_taproot several and several times. That was my main motivation to investigate it, and why I think it's worth. -
sipa commented at 3:20 PM on November 18, 2026: member
Potential Concept ACK, but I think we need to be clear on what we want to optimize for.
The Python EC logic here, in its first iteration, was deliberately slow, simple, different, and "schoolbook", intended to allow easy review (especially of the higher-level algorithms). Using fractions to represent field elements made sense there, as it means layers on top can ignore field element representation issues and just write algorithms as protocols tend to define them.
This of course hurts performance, which was assumed not to be a bottleneck in tests. In practice, we've already compromised a bit with extra complexity to gain performance, in #26222 and #36327.
Even more performance will mean straying further, which may be a reasonable trade-off given how slow
feature_taproot.pyis.I'd push back against using libsecp256k1 itself though, for similar reasons as @real-or-random mentions, but also because because libsecp256k1 really isn't intended to be used as a generic group operation library; while it's possible to use it as such through some of the relatively low-level early EC tweaking functions, this is breaks when e.g. the point at infinity is encountered. Perhaps it's worth using in limited settings, like just ECDSA/Schnorr signing, as that is probably the bulk of the work in
feature_taproot.py, and doesn't need exposing individual group operations.