An incentivized and verifiable search for cryptographic parameters.

Elliptic Curve Search: Optimizing the BLS12 Family

Pairing-friendly parameters for signatures, KZG, and ZK-rollups

Ethereum's consensus signatures, KZG polynomial commitments (EIP-4844), and the majority of its ZK-rollups run on the pairing-friendly curve BLS12-381. A curve is "pairing-friendly" when it admits an efficiently computable bilinear map e — a pairing — sending two groups \(\mathbb{G}_1, \mathbb{G}_2\) of prime order \(r\) into a target group in the field \(\mathbb{F}_{p^k}\):

The integer \(k\) is the embedding degree; for BLS12 curves \(k = 12\). What makes the whole family remarkable is that every parameter of the curve is a polynomial in a single integer seed \(x\) [1][2]. For the BLS12 family (Construction 6.6 of the Freeman–Scott–Teske taxonomy), the subgroup order \(r(x)\) and the base-field prime \(p(x)\) are:

A seed \(x\) yields a usable curve precisely when both \(p(x)\) and \(r(x)\) are prime. That is the hard constraint. But among the seeds that satisfy it, some produce curves that are dramatically cheaper to compute with than others, and this is where the search creates value. Two properties of the seed drive on-chain cost:

• Low Hamming weight of \(x\). The Miller loop at the heart of every pairing iterates once per bit of \(x\), with an extra, costlier step per set bit. A sparser \(x\) means fewer line-additions and a faster pairing.
• High 2-adic valuation of \(r - 1\). ZK-SNARK provers run FFTs over the scalar field \(\mathbb{F}_r\), which requires a large multiplicative subgroup of order \(2^s\). The largest usable FFT domain has size \(2^{\,\nu_2(r-1)}\), where \(\nu_2\) is the 2-adic valuation.

The network therefore scores a valid seed by combining both drivers — maximize SNARK capacity first, break ties by pairing speed:

where \(\mathrm{wt}(\cdot)\) is the Hamming weight. This is not an arbitrary metric: it is precisely the trade-off that produced the deployed choice. The BLS12-381 seed is \(x = \texttt{-0xd201000000010000}\), which has Hamming weight \(6\) and satisfies \(2^{32} \mid (r-1)\), giving a \(381\)-bit prime \(p\), a \(255\)-bit prime \(r\), and a \(2^{32}\)-point FFT domain [3]. The same construction underlies BLS signatures [4] and the IETF pairing-friendly-curves specification [5].

Why this is safe to judge on-chain. Searching means primality-testing \(p(x)\) and \(r(x)\) across a vast seed space — expensive. Verifying a submitted seed is two modular exponentiations (via the modexp precompile) plus counting bits — a handful of operations. The contract re-derives \(p\), \(r\), and the score from scratch and accepts only if the claim holds and beats the record. Search is hard; checking is cheap. (The live contract verifies seeds in the window \(|x| < 2^{42}\), where \(p(x)\) fits in a 256-bit word; extending to the full \(381\)-bit range is a bignum/precompile upgrade, not a change of method.)

Lattice Reduction Relay: measuring post-quantum hardness

The hardness assumption behind post-quantum encryption — and a distributed way to measure it

The post-quantum key-encapsulation standard ML-KEM (NIST FIPS 203, standardized 2024), better known as CRYSTALS-Kyber, bases its security on lattice problems over the polynomial ring \(R_q = \mathbb{Z}_q[x]/(x^{256}+1)\) with \(q = 3329\) [1][2]. Its underlying assumption, Module-LWE, reduces to the difficulty of finding short vectors in structured lattices. A lattice is the set of all integer combinations of a basis \(B = \{\mathbf{b}_1, \dots, \mathbf{b}_n\} \subset \mathbb{Z}^n\):

The Shortest Vector Problem (SVP) asks for a nonzero lattice vector of minimum Euclidean norm, \(\lambda_1(\mathcal{L}) = \min_{\mathbf{v} \in \mathcal{L}\setminus\{0\}} \|\mathbf{v}\|\). This problem is NP-hard under randomized reductions [3], and it is the concrete wall that quantum computers are not known to breach — which is exactly why lattices were chosen for post-quantum standards.

The network hosts a public q-ary lattice — the same family Kyber uses — given by a basis in Hermite Normal Form with determinant \(q\):

A candidate is an integer coefficient vector \(\mathbf{c} \neq \mathbf{0}\); the corresponding lattice vector is \(\mathbf{v} = B^{\top}\mathbf{c}\), and its score is the squared length \(\|\mathbf{v}\|^2\) — smaller wins. How good any submission is gets measured against two standard yardsticks from the lattice-reduction literature [4]. The first is the Gaussian heuristic, the expected shortest length in a random lattice:

The second is the root Hermite factor \(\delta\), the single number that summarizes how good a reduction is. A vector of norm \(\|\mathbf{v}\|\) achieves

Gama and Nguyen's landmark experimental study [4] found that the celebrated LLL algorithm [5] achieves \(\delta \approx 1.021\) in practice, strong BKZ reaches \(\delta \approx 1.008\text{–}1.013\), and driving \(\delta \to 1\) is "totally out of reach" of known algorithms. Smaller \(\delta\) is exponentially harder and exponentially more valuable — precisely the kind of frontier a decentralized bounty is built to push, in the spirit of the long-running TU Darmstadt SVP Challenge [6].

Why this is safe to judge on-chain. Finding short vectors requires lattice reduction (LLL, BKZ, sieving) whose cost grows sharply with dimension. Verifying a submission is one matrix–vector product and one dot product: the contract recomputes \(\mathbf{v} = B^{\top}\mathbf{c}\) and \(\|\mathbf{v}\|^2\) exactly, and accepts only if it is nonzero and shorter than the record. The asymmetry between hard search and cheap verification is what makes the competition trustless. (The live instance uses a modest dimension and modulus so all arithmetic stays within a 256-bit word and verification is a single inexpensive transaction; scaling \(n\) and \(q\) toward cryptographic sizes is the natural next iteration.)

Rewarding contributed progress, not just a winner. Asking for the shortest vector is a lottery: for a hard instance almost nobody ever finds it, so almost nobody is ever paid. The network instead runs as a reduction relay that pays for every rung of the ladder. Lattice reduction does not leap to the answer — it produces a long sequence of successively shorter vectors, and each one is a verifiable improvement. A participant's browser runs progressive LLL locally and submits each shorter vector it finds; the contract credits a share of the pool proportional to the research progress that step contributed. Progress is measured in the logarithmic (Hermite-factor) domain, so halving the norm is worth the same at any scale, and the shares telescope: summed over the record's walk from the starting basis to the target (the Gaussian heuristic), the total paid is exactly the pool. Because the reward tracks global improvement, splitting a step across many accounts earns the same total — there is no sybil advantage — and a microscopic improvement earns a microscopic reward. Submissions use commit-reveal, so a shorter vector cannot be copied from the mempool. The result is an incremental, interactive effort in the spirit of the TU Darmstadt challenges, where the useful research output — the shortest vectors found and the Hermite factors achieved at each dimension — is recorded on-chain with reproducible provenance for anyone to cite.