BLS12-381 spends most of its time in BigInteger division and per-step field inversions #2556

More AI-assisted benchmarks I can contribute. Have a look yourself whether this could help anyone.
6 performance improvements stacked on each other.

crypto.bls.Fp2Element reduces every result with BigInteger.mod(P), a long division costing about 380 ns for a 762-bit product against 49 ns for the 381-bit multiplication itself (JDK 25), and also for sums and differences that are already within one p of the range. BLS12_381G2Point.multiply and constantTimeMultiply work in affine coordinates, so every doubling and addition computes an Fp2Element.inverse (a BigInteger.modInverse). In a JFR profile, inversion is 68% of signing and 41% of verification, mostly from hash-to-curve's cofactor clearing and the signing scalar multiplication. A Karatsuba Fp2Element.mul (3 multiplications instead of 4) alone measured no gain, because the multiplications were never the cost.

Fix (branch bls-barrett-jacobian, 88b03ee205): products are reduced by Barrett reduction (a precomputed floor(2^764 / p), two multiplications and at most one corrective subtraction for every input that occurs; a negative difference of products is shifted up by p² first), and sums and differences by one conditional subtract or add. Both G2 scalar multiplications run in Jacobian coordinates with mixed additions of the affine base point (dbl-2009-l, madd-2007-bl), so one inversion converts the result back to affine form. The public API and the affine point representation are unchanged; outputs are identical (Eth2 KAT vectors).

JDK 17 and 25 match JDK 21 (sign 3.1-3.2×, verify 2.3×); JDK 8 gains less (sign 2.1×, verify 1.7×). :core:checkstyleMain and Error Prone are clean.

Tests: Fp6Fp12Test now checks every Fp2 operation against plain BigInteger.mod arithmetic at the range edges (0, 1, p - 1, p/2), Fp2 and Fp6 multiplication against the schoolbook formulas, and two operand pairs whose negative real part a Barrett estimate overshoots without the p² shift. The new BLS12_381G2ScalarMulTest checks both scalar multiplications against an affine double-and-add, on points inside and outside the subgroup, for scalars that hit the mixed addition's doubling and inverse cases (r + 2, r), cofactor clearing, negative scalars and infinity. Breaking any reduction, the doubling or addition formulas, their special cases or the affine conversion makes them fail. The hash2curve suite (188 tests) passes on JDK 25 and 8.

Follow-up: Miller loop

Branch bls-miller-loop, 0ab6c42bc6, stacked on this one. The Miller loop lifted every coordinate into Fp12, ran affine doubling and addition there with an Fp12 inversion per step, and multiplied the accumulator by dense Fp12 lines. It now keeps T on the twist in Jacobian coordinates over Fp2 and evaluates each line at P straight into a sparse Fp12 element with three non-zero Fp2 coefficients, multiplied in by a new Fp12Element.mulBy014 (13 Fp2 products instead of 18). The lines carry Fp2 and Fp4 scale factors (the Jacobian denominators and the twist's w³), which the final exponentiation maps to 1, so pairing values are unchanged: a new BLS12_381PairingTest.testKnownAnswers pins e(G1, G2), e(sG1, tG2) and a two-pair multiPair to values from the old affine implementation, which all three versions reproduce exactly, and every mutant of the line coefficients or sparse products fails it.

Signing does no pairing and is unchanged.

Follow-up: cofactor clearing and cyclotomic squaring

Branch bls-cofactor-cyclotomic, stacked on bls-miller-loop, two commits. 5efb0733e6: hash-to-curve cleared the cofactor by multiplying by the 636-bit h_eff (32% of verification, more of signing); it now uses RFC 9380 App. G.3, [x² - x - 1]P + [x - 1]ψ(P) + ψ²(2P), two multiplications by the 64-bit x plus a few additions and ψ maps, reusing the subgroup check's ψ. a1e880ab1a: the final exponentiation's hard part (25% of verification) squared with the general Fp12 squaring; its powers now use Granger-Scott cyclotomic squaring (9 Fp2 squarings instead of 18 Fp2 products), valid because the easy part's output lies in the cyclotomic subgroup. A new test checks clearCofactor against the multiplication by h_eff on points inside and outside the subgroup; the existing hard-part-versus-direct-power test and the pairing known answers cover the cyclotomic path; every mutant tried in either change fails them.

The two commits were benchmarked together; a quick JDK 25 run of the first alone puts the cofactor clearing at about 1.6× for signing and 1.3× for verification, and the cyclotomic squaring at a further 1.1× for verification.

Follow-up: map-to-curve

Branch bls-map-to-curve, 14049d3526, stacked on bls-cofactor-cyclotomic. Map-to-curve (simplified SWU plus the 3-isogeny) tested squareness with Fp2Element.isSquare, a 762-bit exponentiation in Fp2, took the root with sqrtOrNull's further Fp2 exponentiations, and made four Fp2 inversions per hashed point. RFC 9380 fixes the sign of y with sgn0 afterwards, so any square root gives the same point: a new sqrtOrSqrtZ(w, root) (RFC 9380's sqrt_ratio(w, 1) up to the choice of root) decides squareness from the norm in Fp and builds the root from two or three 381-bit BigInteger.modPow calls, as p ≡ 3 (mod 4) allows. Writing y as √(num·den)/den with den = tv4³ lets one inversion of tv4 serve x′ and y′, and the isogeny's two denominators share one inversion, so two Fp2 inversions remain. The map gives identical points to the previous code on 20,000 inputs (u = 0, 1, I and top-of-range values included); a new testSqrtOrSqrtZ checks the verdict against isSquare and the root against w or Z·w over zero, real squares and non-squares, imaginary and random inputs, and fails for every non-equivalent mutant tried. isSquare and sqrtOrNull are unchanged, as point decompression uses them.

Follow-up: lazy reduction

Branch bls-lazy-reduction, f4c6182460, stacked on bls-map-to-curve. Each Fp6 and Fp12 output coefficient is a sum of several Fp2 products, and every product was reduced on its own. A new package-private Fp2Wide holds the unreduced Karatsuba products, which the tower formulas add, subtract and multiply by the non-residue before reducing once per coefficient with a wide Barrett reduction (floor(2^768 / p) on the absolute value, at most two corrections). This covers Fp6Element.mul, Fp12Element.mul, the sparse mulBy014 and the cyclotomic fp4Square. The reduction checks its input bound and throws rather than return a wrong residue. Pairing values are unchanged (the known-answer test passes), and the Fp2/Fp6 schoolbook checks and pairing known answers fail for every mutant tried except one benign one (a while turned into an if in the corrective loop). The hash2curve suite (191 tests) passes on JDK 25 and 8.

Signing does no Fp6/Fp12 arithmetic and is unchanged. The machine was busier during this run than during the earlier ones (load average 1.8-1.9), so these ratios are a little less precise.

Remaining (not in these changes): a fresh profile of what is left. All of this is still variable-time BigInteger arithmetic, so signing is not constant time below the scalar-multiplication loop; fixed-width Montgomery arithmetic with Mod.modOddInverse would be the step after.