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
  1. brunoerg commented at 9:19 PM on November 16, 2026: contributor

    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.

  2. 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.
    8d1c38ca88
  3. DrahtBot added the label Tests on Nov 16, 2026
  4. 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

    <!--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>&lt;!--meta-tag:bot-skip--&gt;</code> into the comment that the bot should ignore.

    <!--5faf32d7da4f0f540f40219e4f7537a3-->

  5. brunoerg commented at 9:19 PM on November 16, 2026: contributor
  6. 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.)

  7. 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?

  8. 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, so mul only ever adds an (affine) table entry to the accumulator. This means the add_affine function 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 n be the group order, and assume P has order n (true for every point other than infinity on secp256k1, which has cofactor 1). After a = a % n, the accumulator before row i is k*P with k = a mod 2^(4i). Row i adds j * 2^(4i) * P with 1 <= j <= 15 (j = 0 is skipped).

    • P + P would require k ≡ j * 2^(4i) (mod n). Both sides lie in [0, n), because 15 * 2^252 < n, so they would have to be equal as integers. That is impossible since k < 2^(4i) <= j * 2^(4i).
    • P + (-P) would require k + j * 2^(4i) ≡ 0 (mod n). The left side equals a mod 2^(4i+4) <= a < n, so it would have to be 0. Then k = 0, i.e. the accumulator is infinity, and that is the ordinary O + Q case, 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, or P + (-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; here 3b = 21). Completeness requires a prime-order curve, which secp256k1 is, and the affine input (x2, y2) must not be infinity, so the entry is not None check in mul stays.

    The EFD lists the general-a version of this formula (Algorithm 5 in the paper) as madd-2015-rcb: https://hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-madd-2015-rcb. Algorithm 8 is its specialization to a = 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) % m
    

    mul starts from x, y, z = 0, 1, 0 and needs no z == 0 branch inside the loop. At the end, if z == 0 it returns infinity; otherwise it returns GE(x * z_inv % m, y * z_inv % m) with z_inv = pow(z, -1, m).

    Since mul never reaches the P + P and P + (-P) cases (see above), a direct unit test of _proj_add_affine is still needed to cover them. With a complete formula, this is just a comparison against GE addition for P + P, P + (-P), O + P, and random pairs, with no special cases.

    </details>

  9. 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.

  10. 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?

  11. 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).

  12. 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.py is 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.

  13. 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.py is.

    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.


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-11-18 16:51 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me