Ephemeral ECMH

Authorship and disclaimer

The author formulated the research question, defined the threat model (Adversary) and security arguments not related to curve selection, and directed the language models that carried out the work. The implementation and evaluation were carried out almost entirely by Claude Opus 5.5, with review and contributions from Codex Astra 6 and Claude Fable 5.1.

The author is not an expert in elliptic curve cryptography and has only a vague familiarity with binary elliptic curves. This report was written for the author as much as under his direction: the models assembled most of the security arguments for curve selection and the literature they rest on, with most of the cited works being new to the author. It is shared before the author is able to verify it fully, and has not been reviewed by a specialist.

Synopsis

This repository evaluates elliptic-curve multiset hashes (ECMH) [maitin-shepard-et-al-2016] over small curves as the cell checksum of rateless invertible Bloom lookup tables (RIBLTs) [yang-gilad-alizadeh-2024].

When the sets being reconciled contain potentially adversarial inputs, RIBLT can be susceptible to collisions. This can be addressed using a secret shared by the peers engaging in reconciliation, or by utilizing ECMH.

The aim is to relax the requirement for a shared secret and mitigate collisions caused by adversarial inputs, using only a public beacon value as a salt, but without paying the full cost of ECMH on standard curves.

Weaker curves can be randomly selected periodically based on the public randomness beacon, and this project investigates the suitability and performance of such curves (and their underlying fields) in the context of RIBLT over sets with potentially adversarial items. The question is whether such a checksum attains a work factor between $2^{48}$ and $2^{64}$ group operations for each curve, and which field, curve model, and representation minimize its cost per item.

Motivation

Set reconciliation lets two peers that hold similar sets exchange only their difference. In peer-to-peer networks the sets often accept items from any party: Erlay proposes set reconciliation for the transaction relay of Bitcoin nodes [naumenko-et-al-2019], and IBLT-based reconciliation has been evaluated for the channel and node announcements of Lightning gossip [bolt-7, chen-et-al-2026]; neither is deployed, and both networks relay by flooding. Their items may be adversarial inputs. The adversary considered here is a third party that authors items and places them in the sets of honest peers, for instance by broadcasting them, aiming to make two honest peers fail to reconcile or obtain a wrong difference; resistance to it is what Meyer and Scherer call censorship resistance [meyer-scherer-2024]. A participating peer can always disrupt reconciliation by sending corrupt data or misrepresenting its set; that is unavoidable and not considered (Adversary).

A RIBLT [yang-gilad-alizadeh-2024] recognizes a coded symbol that holds a single item by a checksum. In the reference implementation the checksum is the XOR of item hashes. An adversary who can evaluate the item hash constructs two distinct sets with equal checksums by linear algebra over ${\mathbb{F}}_2$, at negligible cost and with any hash function (yangl1996/riblt#3). Addition modulo $2^{64}$ in place of XOR has the same weakness, by lattice reduction and Wagner’s algorithm [wagner-2002].

A secret key defeats the attack when the adversary cannot evaluate the keyed hash. This is the model of short keyed hashes such as SipHash [aumasson-bernstein-2012], designed against hash flooding of hash tables. Bitcoin’s compact block relay keys the 48-bit short identifiers of a block’s transactions with a hash of the block header and a nonce [corallo-2016]: the header commits to the transactions, so the set is fixed before the key is revealed and no transaction can be chosen against it. Open sets have no such ordering. Items keep arriving after a key shared by all peers is published, and the attack on the XOR checksum applies whatever the hash. A key kept per connection, as Erlay’s salts are [naumenko-et-al-2019], or a secret key coordinated by the two peers, as the Rateless IBLT paper proposes against injected items, repeats the hashing of every item for each key, and the checksums of coded symbols no longer serve every peer, though their sums do [yang-gilad-alizadeh-2024, Section 4.3]. Meyer and Scherer count that cost against randomizing per session [meyer-scherer-2024].

The hashing can instead be shared within an epoch. In a namespace salted by a beacon value, such as a key derived from a block hash, an adversary who can neither predict nor influence that value cannot search for collisions before the namespace begins. Unlike in compact block relay, it can still author items afterwards, so the checksum must resist relation finding without a secret until the next beacon value; with a block hash as the beacon, new blocks determine how long that is.

An ECMH sums hashed points in an elliptic-curve group. For maps to the curve that satisfy the hypotheses of the known reductions, its collision resistance reduces to the discrete-logarithm problem in that group [maitin-shepard-et-al-2016]; whether the maps used here satisfy them is open (Known weaknesses). The curves in use for this purpose have about $2^{256}$ points and about 128-bit security, and hashing an item to them costs about 110 to 195 times the SHA-256 hash of the XOR checksum (see Findings). A shorter horizon and a failure confined to one namespace suggest that a work factor of $2^{48}$ to $2^{64}$ suffices, provided the application detects a sketch collision by other means and recovers, for example by re-keying or by another reconciliation method. This is an application assumption.

A small fixed curve is exposed to precomputation [bernstein-lange-2012]. With the discrete logarithms of the item hashes, the checksum becomes AdHash modulo the group order, and the attack on the XOR checksum carries over through Wagner’s algorithm or lattice reduction; without them, the group does not expose the residues modulo its order that these algorithms need. Hoyte reports such collisions modulo $2^{256}$ in about 28 hours on eight cores [hoyte-2023]. The group orders here are below $2^{128}$, where the leading-order estimate for Wagner’s algorithm is smaller by a factor of $2^{9.5}$ to $2^{11.5}$, so a discrete-logarithm break makes the attack practical. The curve is therefore derived from the beacon value as well, deterministically, by a public candidate-selection procedure. A participant must be able to derive and check the curve for each new beacon value.

Design

The checksum uses hashing to the curve, point addition, and negation; scalar multiplication occurs only in curve selection. The items are public, so the arithmetic may run in variable time and items may be hashed by try-and-increment; the map from an item’s SHA-256 digest to the group need not be uniform, only such that relations are hard to find within the subset it reaches (Adversary). Over binary fields, the complete formulas of Pornin [pornin-2022, pornin-2023] have an operation count for addition independent of the extension degree $m$, negation is one field addition, and a dense curve constant enters Pornin’s extended coordinates only through two multiplications by $\beta =B^{1/4}$ per addition. Scaling the addends by the inverse of $b=B^{1/2}$ when they are decoded removes these, leaving seven field multiplications and two squarings ($7M+2S$) per mixed addition.

The curve of a namespace is the first candidate derived from the beacon value whose group order is an admissible cofactor times a prime $r$. A participant can check that choice without counting points: a certificate gives $r$ and a nonidentity point $Q$ with $rQ=O$ for the accepted candidate, and a witness of an inadmissible order for each earlier candidate. Its conclusion is conditional on the primality of $r$, which is tested to 24 fixed Miller–Rabin bases, not proven (Parameter selection and verification).

Random short Weierstrass and Edwards curves over prime fields are the conservative alternatives: their field multiplication uses the integer multiplier of every target, and a prime field has no subfield over which a Weil descent applies.

With $m=61$, $\mathrm{GF}(2^{122})=\mathrm{GF}(2^{61}{)}^2$ admits Galbraith–Lin–Scott (GLS) curves, whose constants range over about $2^{61}$ values and whose automorphism lowers the rho cost by a factor $\sqrt{2}$ beyond that of the negation map. A $\mathrm{GF}(2^{61})$ coordinate fits one 64-bit word, and points have 16-byte encodings; the 107-bit and 109-bit families have 14-byte encodings. Weil descent constrains the choice of binary field. Candidate constructions lists the constructions compared and their operation counts.

In a RIBLT, an item’s point is added to about $2\ln m$ of the first $m$ coded symbols, and the item is hashed once per namespace, so additions outnumber hashes (Workload). The simulator reproduces the forgery of yangl1996/riblt#3 against the XOR checksum, and every curve group rejects the forged cells.

Findings

The figures below are from runs of source revision ef9e82d3 in the full profile: on an Apple M4, run 01a1196a-88e4-7cdd-97ef-f46747dd8ab0, unless they are given for an Intel Xeon W-1390P, run 01a11cd2-6ca3-73a7-8501-245c98af23fc, built for x86-64-v3 with PCLMULQDQ. Those of the portable build are from run 01a11a5b-9046-7637-b5af-cfa347a1a47d on the M4, built for -C target-cpu=generic, and run 01a12137-de75-762e-8d58-604336dcc781 on the Xeon, built for -C target-cpu=x86-64. Batched hashing processes 1024 items per batch, addition costs are throughput figures, and RIBLT encoding is per item, for $n=3500$ items into a sketch of $m=1350$ cells.

Gains from the Go-to-Rust port or the mapping-generator change (xoshiro256++ in place of ChaCha8) are not attributed to this project; matched comparisons in the Rust harness measure checksum substitution (comparison conditions).

• The binary families over $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{127})$ lead. Their fastest representation, unscaled accumulators with Pornin’s complete formulas, encodes into a RIBLT sketch at 282 and 288 ns per item and adds in 9.8 and 10.7 ns, against 165 ns per item for the XOR baseline and 5.84 µs for ristretto255. The incomplete λ-projective variants add in 12.0 and 14.9 ns and encode at 303 and 326 ns; the extended coordinates, also complete, at 324 and 329 ns.
• $\mathrm{GF}(2^{109})$ encodes a point in 14 bytes, against 16 for $\mathrm{GF}(2^{127})$, so each coded symbol’s checksum is two bytes shorter, at a nominal rho cost of $2^{53.8}$ against $2^{62.8}$. Both fields occupy two 64-bit limbs, and the smaller one is only slightly faster on the M4 and slightly slower on the Xeon; Code generation (section 4) compares their reductions, which differ by modulus.
• Pornin’s map is the faster hash, batched or not. To the unscaled addend, in batches, it takes 60.7 and 57.2 ns per item over $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{127})$, against 81.2 and 85.8 ns for try-and-increment; one item at a time, 533 and 461 ns against 874 and 869 ns, mainly for the field inversion. The RIBLT benchmarks therefore hash every binary family by Pornin’s map, as the plan derived from the group operations selects (The RIBLT plan). Summing two maps costs 916 ns over $\mathrm{GF}(2^{127})$.
• Over $\mathrm{GF}(2^{122})$ the GLS-shaped and dense families encode at 306 and 308 ns; with extended coordinates the GLS family adds about 6% faster (16.8 against 17.8 ns), at a nominal rho cost 0.5 bits lower ($2^{59.8}$ against $2^{60.3}$).
• The prime-field families hash an item in 0.62 to 1.92 µs, mainly for the square root, which batching does not share, and add in 12.5 to 45.4 ns across the implemented formulas. The fastest of them in RIBLT encoding, twisted Edwards over $\mathrm{GF}(p^2)$ with $p=2^{61}-1$, takes 900 ns per item.
• XOR of SHA-256 digests, the insecure baseline, costs 24.2 ns per item and 0.38 ns per cell. ristretto255 hashes an item in 4.72 µs and secp256k1 in 4.49 µs, 185 to 195 times the baseline.
• The binary-field figures require carry-less multiplication (PMULL or PCLMULQDQ) to be enabled in the build; the portable backend executes 13 to 19 times the instructions (Code generation). Built without it, $\mathrm{GF}(2^{127})$ stays in the class of the prime-field curves: its families encode into the sketch at 1.90 to 2.43 µs per item, against 1.42 to 1.68 µs for those over ${\mathbb{F}}_{2^{127}-1}$. The families over $\mathrm{GF}(2^{122})$ take 2.90 to 4.12 µs and those over $\mathrm{GF}(2^{109})$ 4.53 to 6.06 µs, up to about four times the prime-field curves. On the Xeon $\mathrm{GF}(2^{127})$ takes 3.60 to 4.73 µs, about twice the 1.88 to 2.24 µs over ${\mathbb{F}}_{2^{127}-1}$, $\mathrm{GF}(2^{122})$ 4.45 to 6.11 µs and $\mathrm{GF}(2^{109})$ 7.69 to 10.15 µs.
• Hashing an item anew in each namespace need not repeat SHA-256 (Adversary): projecting its 32-byte identifier, the item’s SHA-256 at 33.1 ns, to 128 bits under the namespace’s key costs 5.1 ns over $\mathrm{GF}(2^{127})$, 9.6 ns over ${\mathbb{F}}_{2^{127}-1}$ and 16.5 ns over ${\mathbb{F}}_{2^{130}-5}$, against 33.0 ns for the salted SHA-256 of the identifier. Keyed by projections of identifiers computed beforehand, the unscaled accumulators over $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{127})$ encode at 222 and 227 ns per item, against 282 and 288 ns by salted SHA-256 of the items (Costs by lifetime). Without carry-less multiplication the projection over $\mathrm{GF}(2^{127})$ costs 60.7 ns on the M4 and 114 ns on the Xeon, more than the salted hash, and the portable build’s RIBLT plan projects over ${\mathbb{F}}_{2^{127}-1}$ instead.
• Over four seeds, finding a $\mathrm{GF}(2^{127})$ curve took 2.4 to 23.6 ms and certifying it, search included, 2.4 to 23.8 ms. Verifying a certificate counts no points and takes 55 to 68 µs across the families, 45 to 55% of it in the embedding-degree bound, or up to 0.59 ms when it also checks every rejected candidate. For the prime-field families the implemented prover counts points with PARI.
• On the Xeon the unscaled accumulators over $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{127})$ encode at 422 and 414 ns per item and add in 13.5 and 13.2 ns, against 218 ns per item for the XOR baseline and 7.69 µs for ristretto255. Pornin’s map remains the faster hash: in batches it takes 110 and 98.0 ns per item against 125 ns for try-and-increment, and one item at a time 657 and 249 ns against 1154 and 401 ns, over $\mathrm{GF}(2^{127})$ about half the M4’s cost. The prime-field families hash an item in 0.70 to 2.21 µs, and the fastest of them encodes at 1.18 µs. SHA-256 takes 53.4 ns, so ristretto255 and secp256k1, at 6.03 and 6.17 µs, hash at 113 to 116 times the baseline. Projecting an identifier costs 9.7 to 26.0 ns by field, against 51.4 ns for its salted SHA-256, and keyed by projections the unscaled accumulators encode at 331 and 320 ns. Verifying a certificate takes 70 to 91 µs.
• The nominal rho costs of the families range from $2^{52.3}$ to $2^{63.3}$. The documented attacks obtain discrete logarithms and then solve additive relations; their costs and limitations are given in Known weaknesses.

License

MIT

Contents

Study

• Background - The RIBLT checksum, its linearity over ${\mathbb{F}}_2$ (yangl1996/riblt#3), why AdHash does not repair it, and keyed and group-based alternatives.
• Problem statement - The adversary, the beacon-salted setting and its reference work factor, per-namespace curves against precomputation, curve selection and certificates, design criteria and scope.
• Workload - The multiset digest, the operations a RIBLT performs on it, and their counts in repeated reconciliation.
• Candidate constructions - The fields, curve models, accumulators, encodings and hash maps compared, and the models excluded.
• Security considerations - Nominal rho costs per family, extension-field attacks, the limits of the security evidence, and the known weaknesses.
• Measurement methodology - What the benchmarks measure, the decision table and dominance rule, how to run checks, benchmarks and reports, and how results are published.

Evidence

• Field and curve code generation - Static instruction counts of field and point operations across 24 compiler targets and CPU models, from the asm-report run at revision 2d6c7e3c.
• Summary across runs - Measurements, batching, build comparisons and selection cost.
• Benchmark run Apple M4 · apple-m4 · full · ef9e82d3 - Apple M4 · rustc 1.98.1 · RUSTFLAGS=-C target-cpu=apple-m4 · ef9e82d39fbf · full profile · 2026-10-08
• Benchmark run Apple M4 · generic · full · ef9e82d3 - Apple M4 · rustc 1.98.1 · RUSTFLAGS=-C target-cpu=generic · ef9e82d39fbf · full profile · 2026-10-08
• Benchmark run Intel(R) Xeon(R) W-1390P @ 3.50GHz · x86-64-v3 · full · ef9e82d3 - Intel(R) Xeon(R) W-1390P @ 3.50GHz · rustc 1.98.1 · RUSTFLAGS=-C target-cpu=x86-64-v3 -C target-feature=+pclmulqdq · ef9e82d39fbf · full profile · 2026-10-08
• Benchmark run Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3 - Intel(R) Xeon(R) W-1390P @ 3.50GHz · rustc 1.98.1 · RUSTFLAGS=-C target-cpu=x86-64 · ef9e82d39fbf · full profile · 2026-10-09

Reference

• Annotated literature - For each key of references.bib, what the work contributes to the evaluation of ECMH-based RIBLT checksums over per-namespace curves; in the book, headed by the formatted entry.
• Repository organization - Where the field arithmetic, curves, group capabilities, benchmarks, reports, published results and reference programs live.

Background

The RIBLT checksum

A RIBLT reconciles two sets: the decoder recovers their symmetric difference rather than reading back stored values. A coded symbol holds three sums over the items mapped to it: the XOR of the items, an item count, and a checksum. The checksum is the XOR of fixed-width item hashes. Decoding peels a pure symbol, which holds exactly one item, and uses the checksum to recognize purity.

In the construction studied here the checksum is an ECMH: a coded symbol holds the signed sum of the items’ salted hashes to an elliptic curve, in place of the XOR of fixed-width hashes. The item field remains the XOR of the item bytes (Workload). A variant in which each item is itself a curve point, a 128-bit identifier recovered from the point sum, is not implemented.

Linearity of the checksum

yangl1996/riblt#3 observes that this checksum is linear over ${\mathbb{F}}_2$. An adversary who can evaluate the item hash can find a set of distinct, non-colliding items whose hashes XOR to a target value. Gaussian elimination over slightly more candidates than the hash width suffices, at negligible cost. The weakness lies in the XOR combination (XHASH [bellare-micciancio-1997]) rather than in the hash function, so it persists with SHA-256. The issue demonstrates two constructed sets that the decoder wrongly reports as equal. Whether such relations can also suppress one chosen item across every coded symbol it maps to is left open there. In either case the checksum provides no resistance to relation finding.

Replacing XOR with addition modulo $2^{64}$ (AdHash [bellare-micciancio-1997]) does not remove the weakness. Relations with small integer coefficients among hash values modulo a 64-bit integer are found efficiently by lattice reduction [maitin-shepard-et-al-2016, Appendix B]. Given an unrestricted number of terms, Wagner’s generalized birthday algorithm [wagner-2002] finds them in time subexponential in the size of the modulus. The security of AdHash rests on the hardness of a weighted knapsack problem, which requires a modulus of thousands of bits [bellare-micciancio-1997, wagner-2002]; a variant of one incremental hash of this kind was proposed with its modulus raised from $2^{160}$ to $2^{1600}$ in response to Wagner’s algorithm [phan-wagner-2006, Section 2] (Known weaknesses).

Keyed and group-based checksums

Keying the item hash with a secret prevents the attack by parties that cannot evaluate the keyed hash. Short keyed hashes such as SipHash [aumasson-bernstein-2012] serve this purpose against hash flooding of hash tables, where the key does not leave one process: the adversary neither holds the key nor obtains keyed hashes of candidates of its choosing. Under such a key a RIBLT gives up universality: coded symbols computed under one key cannot serve peers that do not share it. This repository assumes less. The salt and the set are public, the set accepts items from anyone, the adversary included, and the salt is a value of a randomness beacon outside the adversary’s control, renewed often enough that discrete logarithms in the checksum group cannot be computed while it is in use (Setting and reference work factor).

The issue discussion proposes computing the checksum in a finite abelian group in which relations with small coefficients among hash outputs are hard to find. ECMH is such a construction. An implementation over ristretto255 [riblt-ecmh] reports 256-bit checksums in place of 64-bit ones and a higher end-to-end cost. It also replaces the pseudorandom generator that maps items to coded symbols, so its timings do not isolate the cost of the group.

Problem statement

Adversary

The sets considered accept items from any party, and the peers that hold them reconcile with one another. The mempools of Bitcoin nodes, for whose transaction relay Erlay proposes set reconciliation [naumenko-et-al-2019], and the channel and node announcements of Lightning gossip [bolt-7], for which IBLT-based reconciliation has been evaluated [chen-et-al-2026], are such sets: their items are adversarial inputs. Neither proposal is deployed; both networks relay by flooding. Meyer and Scherer call the property required of reconciliation censorship resistance: a malicious party cannot generate sets that two honest nodes fail to reconcile [meyer-scherer-2024]. Hoyte states the same adversary for the fingerprints of range-based reconciliation: a third party inserts crafted elements so that innocent ones fail to synchronize [hoyte-2023].

The adversary is a third party. It can evaluate the item hash once the salt is published, and it can place items of its choosing in the sets of honest peers, for instance by broadcasting them. It authors items whose hashes satisfy a relation, aiming to make two honest peers fail to reconcile, or obtain a wrong difference, when the items lie in the symmetric difference of their sets; items common to both sets cancel. The RIBLT’s mapping of items to coded symbols admits a similar attack that does not involve the checksum (Known weaknesses).

The items, the salt and the curve are public, so the timing of the computation reveals nothing that the adversary could not compute itself, and implementations may run in variable time. Hashing may therefore use try-and-increment [boneh-lynn-shacham-2001], whose number of attempts depends on the item. RFC 9380 specifies deterministic maps instead and recommends against rejection sampling because its timing has leaked secret inputs [rfc9380, Section 1]; it requires constant-time hashing when the inputs to an encoding are secret [rfc9380, Section 10.3], which they are not here.

The item hash assumes secure hash functions of three kinds, which differ in what they bind and in how long their outputs live. An item is identified by a 256-bit digest that does not depend on the salt: tagged SHA-256 of its encoding, or an identifier the application already holds, such as a transaction’s txid. The identifier is computed once and serves every namespace. The adversary chooses it, through the preimage, and only its collision resistance, about $2^{128}$, binds an item to it.

Hashing to the curve and the RIBLT’s mapping depend on the salt, although the curve already changes with the beacon value. Each map starts from a field element and a sign, taken from at most 128 bits of a digest, before the curve enters, and two items whose elements and signs agree hash to the same point on every curve that accepts that element. Without the salt, such a pair would cost about $2^{64}$ digests once and serve in every namespace; with it, the search is repeated for each namespace. An unsalted mapping would likewise let colliding schedules be searched for before the beacon (Known weaknesses). The two keys serve different ends. The hash to the curve keeps the public salt, under which an item’s point identifies it, and resists collisions, in every session of the namespace. The schedule is better keyed by a secret that each pair of peers shares, where one is available: no third party can then search for colliding schedules, and a peer whose neighbours have converged receives independent streams from them rather than one stream repeated. The benchmarks derive both keys from one salt, which changes no cost.

Neither use needs a salted 256-bit digest of each item. Once per namespace, salted SHA-256, modelled as a random oracle, derives keys from the beacon value, or the schedule’s from a secret, under a tag for each use; once per item and namespace, a universal hash under these keys projects the identifier to 128 bits [wegman-carter-1981]. With the identifier read as two elements $m_1,m_2$ of a field of about $2^{127}$ elements and a nonzero key $k$, the projection $U_k(m_1,m_2)=m_1{k}^2+m_{2}k$ is Poly1305’s polynomial on a two-block message, without its clamping or one-time pad [bernstein-2005]. Two identifiers fixed before the salt collide for at most two keys, with probability about $2^{-126}$. Once the salt is published, the adversary can evaluate the projection, but its inputs are SHA-256 outputs, which it does not choose: a random oracle followed by a fixed function whose fibres are of nearly equal size is a random oracle into the field, and a colliding pair costs a generic search over about $2^{64}$ identifiers, as for a salted 128-bit digest. The projection’s linearity gives no shortcut. Items are mapped to the curve independently and added only as points, so a relation among projections is a relation among points only through a symmetry of the map, such as $\mathrm{Map}(-u)=-\mathrm{Map}(u)$ for simplified SWU and Elligator 2 [rfc9380, bernstein-et-al-2013]; to exploit one before the salt, two identifiers must agree up to sign as field elements in both halves, about 254 bits. The field is therefore chosen by cost: $\mathrm{GF}(2^{127})$ where the target has carry-less multiplication, ${\mathbb{F}}_{2^{127}-1}$ where it does not, with Poly1305’s ${\mathbb{F}}_{2^{130}-5}$ measured as a comparison (hash). The attempts of a try-and-increment map after the first use further keys over the same identifier, so their candidates are linear in the first attempt’s rather than independent; the deterministic maps, Pornin’s [pornin-2023], Elligator 2 and simplified SWU, use only the first. For the mapping, 128 bits suffice as well: two items stall a rateless decoder indefinitely only if their schedules agree entirely, which after the salt requires equal seeds, about $2^{64}$ identifiers. Schedules that agree on a prefix only delay decoding, at a cost that does not depend on the seed’s width; that is a property of the sketch, not of its checksum. The implementation digests items with salted SHA-256 for both uses by default. Riblt::projected keys cells by the items’ identifiers and replaces both digests by projections, each under keys of its own and in a field chosen for its cost; both are benched (Costs by lifetime).

What need not be uniform on the group, or indifferentiable from a random oracle, is the map from digests to points: relations must be hard to find within the subset of the group that it reaches. Maitin-Shepard et al. give a sufficient condition. Let the group have a direct factor of prime order $r$ whose complement can be sampled efficiently, and let the output of a random oracle be mapped to the group by an $(\alpha ,\beta )$-weak encoding: one whose preimages can be counted efficiently and sampled uniformly, of which no point has more than $\alpha$, and of which a uniformly random point has on average at least $\alpha /\beta$. Then finding a multiset collision with multiplicities below $r$ is as hard as computing discrete logarithms, at a cost of simulating the oracle of about $\beta$ scalar multiplications per query and half the success probability [maitin-shepard-et-al-2016, Section 4.1, Theorem 1, and Appendix A]. An encoding that misses a fixed fraction of the points can qualify: their characteristic-2 Shallue–van de Woestijne encoding misses about $9/32$ of them and has $\beta$ close to 3 [maitin-shepard-et-al-2016, Section 4.2]. Whether the maps used here meet these hypotheses is open (Known weaknesses).

A participating peer can always prevent reconciliation by misrepresenting its set; no checksum prevents this, and it is not considered. Corrupt coded symbols are the pollution attack of network coding, in which forwarded packets are linear combinations of a source’s packets, and there the source authenticates the space that the combinations must lie in. Homomorphic hashes of a publisher’s blocks let a receiver verify each encoded block of a rateless erasure code as it arrives [krohn-freedman-mazieres-2004], authenticated LT codes such as Falcon codes verify each symbol with a message authentication code under a key shared by sender and receiver [juels-et-al-2015], and signatures on the linear subspace spanned by a source’s packets let any node derive and verify signatures on their combinations in random linear network coding [boneh-freeman-katz-waters-2009]. A coded symbol of a RIBLT is likewise a sum, and its checksum a homomorphic hash of the items it holds, but none of these schemes applies: each authenticates data against a source or a key from which every legitimate symbol derives, whereas the items of a reconciled set are authored by any party, the adversary included, and carry no signature or key that distinguishes an honest item from an adversarial one. Whoever supplies a curve certificate stands in a separate relation to its verifier (Parameter selection and verification).

Setting and reference work factor

In the universal setting the item hash is public, and the checksum must resist relation finding without a secret. Keying the hash with a secret the peers coordinate, as the Rateless IBLT paper proposes [yang-gilad-alizadeh-2024, Section 4.3], defeats the precomputation of relations among item hashes but repeats the hashing of every item for each key; randomized for each reconciliation session, it does so in every session [meyer-scherer-2024, Section II]. This repository considers namespaces whose salt is published by a randomness beacon, such as a block hash [bonneau-clark-goldfeder-2015], and whose checksums are shared by all sessions within a bounded epoch. Bitcoin’s compact block relay keys the short identifiers of a block’s transactions with a hash of the block header and a nonce [corallo-2016]. The header commits to those transactions, so they cannot have been chosen in relation to the key: as in the keyed model, the set is fixed before the key is revealed, and a short keyed hash serves. Items reconciled within an epoch carry no such guarantee: the adversary may author them after the salt is published, so the checksum must resist relation finding for the duration of the epoch, which the regular publication of new blocks bounds. A forgery affects reconciliation within one namespace only. This study assumes that the protocol validates the items it obtains independently of reconciliation, as Bitcoin nodes validate transactions, so that a failed or wrong decoding costs a repeated reconciliation and admits no invalid item. A failure of soundness for one curve, even a discrete logarithm computed in its group, is then a failure of liveness, and a transient one: the next beacon value selects a new curve. The short horizon and the limited scope of failure motivate a reference work factor between $2^{48}$ and $2^{64}$ group operations, with the upper part of the range preferred; the families compared here lie between $2^{52}$ and $2^{63}$ (Security considerations). This range is an application assumption under evaluation; salting does not by itself imply it.

Maitin-Shepard et al. [maitin-shepard-et-al-2016, Section 4.1] reduce collision finding with bounded multiplicities to the discrete-logarithm problem in a large prime-order component of the checksum group, under the random-oracle and encoding assumptions stated there. For a prime component of order $r$, $\sqrt{r}$ group operations serve here as the generic reference cost. An order near $2^{125}$ gives a reference cost near $2^{62.5}$. Several curve models over fields of about 127 bits admit 16-byte encodings of such groups. The security assessment must also cover the hash maps and parameter selection actually used.

Precomputation and per-namespace curves

A public salt over a fixed checksum group serves here as a point of comparison, not as a design under consideration: the salt changes the item-to-point map, but the group, and any precomputation against it, serves every epoch. Bernstein and Lange [bernstein-lange-2012] give a discrete-logarithm algorithm that, after about $r^{2/3}$ operations of precomputation, uses a table of about $r^{1/3}$ entries and about $r^{1/3}$ group operations per logarithm; [bernstein-lange-2013] discusses the cost model for such precomputation. For $r$ near $2^{126}$ these scales are $2^{84}$, $2^{42}$, and $2^{42}$ respectively. They are leading-order estimates for a time–memory tradeoff, not measured costs and not the cost of a RIBLT forgery. Their significance depends on offline resources, storage, and the number of targets.

Each beacon value therefore determines both the salt and the curve. Subject to the entropy of the beacon and to the parameter-selection procedure, this prevents direct reuse of tables computed for earlier curves. It does not exclude all useful precomputation, nor does it guarantee the generic work factor in every namespace.

Parameter selection and verification

Candidate curves are derived from the beacon value by hashing, and a namespace uses the first candidate whose group order is an admissible cofactor times a prime $r$. Deriving curves from public randomness has precedent in verifiably random seeds [ansi-x9-62-1998, rfc5639], lottery draws [baigneres-et-al-2015], and a beacon whose outputs seed a stream of curves [lenstra-wesolowski-2017]; those curves serve general use at the 128-bit level, whereas here each beacon value selects a smaller one for its namespace. A participant may determine that curve by counting points itself, or may check a certificate: for the accepted candidate, $r$ and a hashed point $P$ whose cofactor multiple $Q$ is not $O$ and satisfies $rQ=O$, and for each earlier candidate a witness that its order is inadmissible, as trx proposes for its own enumeration. The verifier accepts any witness that satisfies the certificate rules. This repository’s prover derives its witnesses from hashed points, so its certificate is determined by the seed and the rejection policy (how labels are chosen, and whether by factoring). Checking a certificate requires scalar multiplications, a probable-prime test, and an embedding-degree bound, but no point counting.

The probable-prime test is Miller–Rabin to 24 fixed bases, so the primality of $r$ is probable, not proven. A candidate with the required prime-order structure has no valid rejection witness, so a certificate cannot skip it. The prover supplies $r$ for the accepted candidate; the verifier checks its admissible interval, the condition $rQ=O$ with $Q$ not $O$, and the 24 Miller–Rabin bases. The second condition establishes that the order of $Q$ divides $r$. If $r$ is prime, $Q$ has order $r$, and the family’s cofactor and the Hasse bound then establish $|E|=hr$. The fixed-base test does not prove that $r$ is prime.

The direct checker and certificate verifier share the order-parameter predicates: the probable-prime test, the Hasse interval at the required cofactor, exclusion of $r=q$, and the embedding-degree bound. Direct checking takes the full order from a trusted point counter. Certificate verification uses the nonidentity point and Hasse argument above instead; its order conclusion remains conditional on $r$ being prime.

These formats do not certify every possible outcome of direct checking. An order-admissible candidate can fail the fixed certificate-point check, and the formats have no rejection witness for an anomalous order or a failed embedding bound. A family without a full-order rejection witness also needs a factor for a rejected composite. Direct selection can proceed without those witnesses; the prover reports failure rather than skipping an uncertifiable candidate. Whenever certification succeeds, its selected index agrees with direct selection under the same candidate criteria and filters that reject only candidates failing those criteria.

The families differ in the cost of point counting. Two implementations count points here. PARI/GP [pari-gp] is a computer algebra system for number theory: a C library, PARI, with an interpreter, GP. The optional pari feature links the library and calls it for point counting and integer factorization (curvegen::pari). SageMath (Sage) [sagemath], in which the reference programs are written, also counts points through PARI. The other implementation is this repository’s own, in Rust, for binary fields only; it has no dependency on PARI.

Over binary fields, Satoh’s canonical lift [satoh-2000] and Mestre’s arithmetic–geometric mean, in the form compared and combined by Gaudry [gaudry-2002], count points in polynomial time using 2-adic arithmetic alone. The repository implements this for $\mathrm{GF}(2^{127})$, $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{122})$ (curvegen::agm), counting the dense 122-bit curves in a pentanomial basis and the Galbraith–Lin–Scott (GLS) curves [galbraith-lin-scott-2009] through their subfield curve over $\mathrm{GF}(2^{61})$. A GLS constant is $B={\beta }^4$ for $\beta$ in $\mathrm{GF}(2^{61})$, so GLS candidates are drawn from about $2^{61}$ constants, against about $2^{122}$ for the dense family; the accepted curves are a subset of each. For all three fields the Rust prover produces certificates without PARI: a candidate whose odd part is composite with no prime factor below the trial-division bound ($2^{16}$ for $\mathrm{GF}(2^{122})$, $2^{10}$ otherwise) is rejected by its full order rather than by a factor.

The known-answer certificates were produced with Sage, which derives its witnesses as the Rust prover does, from hashed points (sage/kat_common.sage). For the 109- and 122-bit families it labels a rejection by the smallest prime factor of its odd part (below $2^{16}$ in the 122-bit scripts, without a bound in the 109-bit one). Without PARI, the Rust prover reproduces the indices and orders of these certificates and the 122-bit certificates byte for byte; with PARI supplying the factors, it reproduces the 109-bit certificates byte for byte as well.

Over prime fields, the corresponding method is the Schoof–Elkies–Atkin algorithm [schoof-1995], which requires modular polynomials. The repository does not implement it: prime-field and $\mathrm{GF}(p^2)$ curves are counted by PARI, which handles curves with complex multiplication by a small discriminant separately before falling back to it. A participant in a prime-field namespace who does not run PARI or an equivalent system must therefore rely on another party’s certificate to establish which curve is in use, whereas a binary curve can be derived and checked independently by a small, self-contained program. In a setting where every participant derives the curve from a public beacon, this is an advantage of binary curves, separate from their arithmetic cost.

The cost of selection is paid once per namespace. Each run report’s Curve selection section gives, per family and seed of curvegen.csv, the wall-clock time to find a curve from a seed, to find and certify it, and to verify the certificate, and how the prover’s time divides among the phases of the search. The number of candidates before an admissible order is geometric, so the time to find varies severalfold between seeds. On an Apple M4 the Rust implementation finds a $\mathrm{GF}(2^{127})$ curve in about 20 ms on average, an order of magnitude faster than PARI on the same seeds; PARI finds the prime-field and $\mathrm{GF}(p^2)$ curves in 0.25 to 2 s on average; and certificates verify in under a millisecond on average.

Binary fields add a structural check that prime fields do not need: Weil descent through subfields. For the prime extension degrees 127 and 109 the only proper subfield is ${\mathbb{F}}_2$ [menezes-qu-2001]. For $m=109$, 2 has order 36 modulo 109 and every descent has genus at least $2^{35}$. For $m=127$, 2 has order 7, and the generalized Gaudry–Hess–Smart (GHS) descent [gaudry-hess-smart-2002, hess-2003], which extends to isogenous curves [galbraith-hess-smart-2002], reaches curves of admissible order with heuristic probability about $2^{-52}$ per epoch: 65 isogeny classes of order $2r$, against none among the 36 classes the basic descent reaches (sage/ghs.sage). No check is made; a descent compromises only the epoch whose curve it reaches. The composite degree 122 is assessed in curvegen::select122.

Design criteria

These assumptions differ from those of fixed-curve design:

• The operations that dominate the cost are one hash-to-curve per item, followed by one point addition or subtraction per coded symbol the item maps to, plus encoding and equality tests during peeling. Scalar multiplication is not among them; only curve selection and certification use it.
• Curve parameters vary by namespace. An optimization tied to particular parameters must include its setup cost and its amortization within one namespace. Constants fixed by the field or the curve model remain available.
• The arithmetic processes public data, so variable-time implementations are acceptable (Adversary).
• Point counting and parameter certification occur once per namespace and are amortized, but must remain tractable for each new beacon value (Parameter selection and verification).
• Field and curve structure require separate analysis for attacks below the reference work factor, including applicable Weil-descent methods [gaudry-hess-smart-2002, hess-2005, gaudry-2009, diem-2011, joux-vitse-2012]. The existence of a descent does not by itself establish such an attack.

Candidate constructions lists the constructions compared, at 128-bit and shorter encodings. Their arithmetic costs are measured here; their security conditions are assessed separately.

Questions outside this study

Which beacon value salts which data, and the interval in which a participant can withhold or delay a value it has observed, are questions for the protocol that uses the checksum; they are not addressed here. Whether the checksum covers sets or multisets changes the bounds on relation finding of Setting and reference work factor but not the constructions compared. Targets without carry-less multiplication, WebAssembly among them, are represented only by the portable build described in Measurement methodology. How the RIBLT performs when a peer reconciles with several others, and how far a third party can delay decoding with items whose schedules agree, are questions for the sketch rather than for its checksum.

Workload

For a namespace $N$, let $H_N$ map an item to a group element. The digest of a multiset $S$ is

D_N(S) = sum of H_N(x), with multiplicity, over x in S.

Insertion and removal add or subtract a hashed point. A prepared representation of $H_N(x)$ is reused for every coded symbol the item maps to. The measured costs are hashing to a reusable addend, signed accumulation, and encoding or decoding accumulated points.

The encoding must represent the additive closure of the hash outputs, including the identity, negatives, and sums, because coded symbols hold arbitrary sums. Prime order is not required. A subgroup or quotient group is sufficient if hashing, equality, accumulation, and canonical encoding all refer to the same group. Not every bit string needs to be a valid encoding.

The RIBLT workload implements encoding and peeling with an XOR item field, an integer count, and an ECMH checksum. It is a cost model for these operations, not a specification of a wire protocol.

Cost in repeated reconciliation

The RIBLT mapping includes an item in coded symbol $i$ with probability $1/(1+i/2)$, so an item enters $k(m)=2(H_{m+1}-1)$, about $2\ln m$, of the first $m$ symbols, and symbol $i$ holds about $n/(1+i/2)$ of $n$ items: the first symbols are dense. Reconciling a difference of $d$ items takes $m$ of about $1.35d$ symbols [yang-gilad-alizadeh-2024]. Under three assumptions,

1. weights are expected weights,
2. every round reconciles the same number $d$ of new items, and
3. each round rebuilds its symbols from the full set,

one round over a set of $n$ items costs $nk(1.35d)$ additions, about $2n\ln (1.35d)$. Hashing is per item and its result can be kept, so a set that grows to $N$ items by rounds of $d$ new items costs $N$ hashes in all, but

sum over rounds of n_j k(1.35d), about (N^2 / d) ln(1.35d) additions.

Under this model the number of additions grows quadratically in $N$ and the number of hashes linearly: a round performs $d$ hashes against $2n\ln (1.35d)$ additions. Which dominates the elapsed time also depends on their measured unit costs. Decoding adds about $dk(m)$ subtractions per round, and one equality test per examined symbol, lower order than rebuilding when $n$ is much larger than $d$. If instead each party keeps its symbol sums between rounds and adds only new items (assumption 3 dropped), encoding falls to about $2N\ln (1.35d)$ additions, linear in $N$, with one hash per $2\ln (1.35d)$ additions; decoding is then of the same order. Kept hashes and sums are valid only within one namespace: a new beacon value changes the salt, the curve and the mapping, and everything is recomputed.

Comparison with the reference implementations

The Go benchmarks of yangl1996/riblt#3 run at pinned revisions of [riblt-ecmh]: the upstream XOR checksum, the ristretto255 ECMH with the reference 64-bit mapping, and the same with a ChaCha8 mapping. All three are run by nix run .#riblt-go-bench. riblt.stream follows their BenchmarkEncodeAndDecode. The decoder holds $d/2$ items of its own and the $d$ common ones, and the encoder holds $d/2$ of its own and the $d$ common ones; symbols are 64 bytes, and insertion is outside the timed routine. riblt.encode per item corresponds to BenchmarkSketchAddSymbol at smaller $m$. ristretto255 runs as a family of the RIBLT suites, so that a small curve and the fixed group are measured in one harness.

The implementations differ in ways that affect the comparison:

• Items are hashed with tagged, salted SHA-256 (two digests for ristretto255), where riblt-ecmh hashes the bare symbol with SHA-512. The upstream XOR checksum is SipHash-2-4 under a fixed key; xor-siphash.64 keys it with the salt.
• The rateless decoder recovers an item with the addend its purity check prepared; the ristretto255 version of riblt-ecmh hashes the item to the curve again when it recovers it.
• The ristretto255 addend is the point itself, since curve25519-dalek does not expose its cached form.
• The Rust default mapping uses xoshiro256++ seeded by the whole 32-byte map digest. Rows marked map=chacha8 use ChaCha8, and map=mcg64 rows use the reference 64-bit generator. The Go ChaCha8 version of riblt-ecmh replaced that generator because two items with equal 64-bit seeds have equal mappings, and the decoder cannot separate them (yangl1996/riblt#3; Known weaknesses). Even Rust’s ChaCha8 comparison uses different output from Go’s ChaCha8Rand, so their cells differ. An unmarked mapping row uses the default of its recorded source revision; historical runs are not relabelled when the default changes.

The checksum work is hashing items to addends, adding addends to cells, checking purity while peeling, and encoding or decoding points. Rows that differ only in the group, in the same Rust harness with the same mapping, workload, batching and build, measure checksum substitution, including the choice of hash and point representation. A time ratio against Go riblt-ecmh also includes the mapping generator, the reuse policies above and the port from Go to Rust; these implementation gains are not attributed to this project. Replacing ChaCha8 with xoshiro256++ is of the same kind: it is chosen to make the checksum’s cost clearer in the end-to-end figures. Matched map=chacha8 rows provide a comparison of the generator’s effect once the new clean runs are measured; historical timings do not quantify this change.

Candidate constructions

The 107- and 109-bit families give 14-byte encodings. Their nominal rho costs range from $2^{52.3}$ to $2^{53.8}$ group operations (Security considerations). They show the cost of trading security margin for width. The two 256-bit groups are fixed-curve references at conventional security levels.

Binary Edwards curves [bernstein-lange-farashahi-2008] are excluded on inspected operation counts under equal field arithmetic; they are not implemented or measured. Every ordinary binary curve is birationally equivalent to a complete binary Edwards curve [bernstein-lange-farashahi-2008, Theorem 4.3], so the exclusion is one of cost, not availability. Their complete mixed addition costs $13M+3S+3D$, and $13M+2S+2D$ with the formulas of Kim, Lee and Negre [kim-lee-negre-2014]; the complete unscaled formulas used here [pornin-2022] cost $7M+2S$. $M$, $S$ and $D$ denote a field multiplication, a squaring and a multiplication by a curve constant, counted as a full multiplication for generic dense parameters. Mixed addition is the most frequent operation of the workload (Workload). The binary Edwards formulas with lower operation counts [bernstein-2009] are differential: they compute $P+Q$ from $P$, $Q$ and $P-Q$, as a Montgomery ladder supplies them, and a coded-symbol update adds an independent hashed point with no known difference.

The quadratic extensions $\mathrm{GF}(p^2)$ fit 16-byte encodings with one-word base arithmetic. Goldilocks [polygon-zero-2022] uses Plonky3’s implementation [plonky3]; its 2-adicity of 32 makes square roots, and so decoding and hashing, slower than over $2^{64}-59$; the benchmark report’s Goldilocks rows measure the difference. The 31-bit primes of current proof systems, M31 [haboeck-levit-papini-2024] and BabyBear [bruestle-gafni-2023], would need extensions of degree 4 to reach the same group size. Degree-4 extensions admit the heuristic index-calculus asymptotic $\tilde{O}(q^{3/2})$ [gaudry-2009], below the generic $q^2$, so group size alone does not justify the target security there; these fields are excluded from the comparison.

The variable-curve families hash by try-and-increment [boneh-lynn-shacham-2001]. Alternatives are Elligator 2 [bernstein-et-al-2013] on every Edwards and twisted Edwards family, simplified SWU [rfc9380] on every Weierstrass family, and Pornin’s map [pornin-2023, crrl] on every binary family, each wherever its preconditions hold; curve::h2c tabulates the cells and the reason for each empty one. These are map-level alternatives. A single map is not indifferentiable from a random oracle, which the checksum does not require; the Adversary section states what it does require, and a sufficient condition that is not established for these maps or for try-and-increment. The fixed-curve references use the maps named by their benchmarks. The RIBLT benchmarks hash each family by the construction its run measured cheapest (The RIBLT plan).

Security considerations

Encoded width, group order, and attack cost are distinct quantities. A 128-bit encoding does not imply 128-bit collision resistance. Generic estimates must be read together with extension-field structure, endomorphisms, the parameter selection procedure, and the distribution of the hash map. A discrete-logarithm estimate is not by itself a proof of hardness for every multiset relation problem.

The table gives the nominal cost of rho with the negation map, $\sqrt{\pi r/4}$ group operations [pollard-1978, wiener-zuccherato-1998], divided by a further $\sqrt{2}$ for the GLS automorphism group of order 4 [duursma-gaudry-morain-1999], for the largest prime $r$ dividing each family’s group order. The “Families compared” table of each run report computes the same quantity from the $r$ recorded by that run’s group suite:

For curves over $\mathrm{GF}(p^2)$, index calculus over the extension [gaudry-2009] costs about $p$ group operations up to logarithmic factors, the same as rho; the GHS descent for $\mathrm{GF}(2^{122})=\mathrm{GF}(2^{61}{)}^2$ [hankerson-karabina-menezes-2009] likewise gives no gain over rho. Candidates over $\mathrm{GF}(p^2)$ whose $j$-invariant lies in ${\mathbb{F}}_p$ are excluded as a conservative policy.

The setting is an ephemeral public namespace, with salt and curve derived from a beacon value. It is distinct from a secret-keyed namespace, in which keyed XOR checksums suffice under the adversary assumptions of Keyed and group-based checksums. Conclusions for one setting do not transfer to the other. The implementation provides tagged, salted hashing.

The parameter-selection code and the reference programs state the acceptance conditions for each family. Tests combine field reference computations, independent affine group laws, Sage/PARI fixtures, canonical-encoding checks, signed accumulation, and complete workload checks. Sampled tests are evidence, not proof, and probable-prime tests do not certify primality.

Known weaknesses

Each weakness below is accepted at the reference work factor, stated as an assumption on the application, or left open, as indicated.

Discrete logarithms reduce the checksum to an insecure AdHash. Write $G$ for a generator of the prime-order component and $h_x$ for the discrete logarithm of the hash of item $x$, so that its prime-order part is $h_{x}G$. An adversary who knows $h_x$ for a collection of items converts a relation $\sum a_{x}H(x)=O$ into the congruence $\sum a_x{h}_x\equiv 0(\mathrm{mod}r)$, with a further condition modulo the cofactor, which is at most 4. The checksum is then AdHash [bellare-micciancio-1997] with modulus $r$ [maitin-shepard-et-al-2016, Section 8], the group order and not a modulus chosen for AdHash: for the families compared, $r$ lies between about $2^{105}$ and $2^{127}$, where AdHash’s security requires thousands of bits (below). The following are leading-order estimates of the resulting attacks:

• A nonzero relation with coefficients in $\{-1,0,1\}$ gives two distinct sets with equal checksums. Wagner’s algorithm [wagner-2002] finds one in about $2^{2\sqrt{{\log }_{2}r}}$ operations on about as many hashed items, $2^{20.5}$ to $2^{22.5}$ here, for a relation of about $2^{\sqrt{{\log }_{2}r}}$ terms; list sizes and sorting contribute further factors. A relation with coefficients in $\{0,1\}$ and right side the logarithm of a target checksum $T$ gives one set with checksum $T$; with coefficients in $\{-1,0,1\}$ it gives two sets whose checksums differ by $T$.
• Relations with small integer coefficients give the corresponding multiset relations. The estimate of [maitin-shepard-et-al-2016, Appendix B] gives a coefficient vector of Euclidean norm about $2^{2\sqrt{{\log }_{2}r{\log }_{2}c}}$ from $\sqrt{{\log }_{2}r/{\log }_{2}c}$ items, for a lattice reduction algorithm of Hermite factor constant $c$. With LLL ($c$ about 1.021), this is a heuristically expected norm of 12 to 15 from 59 to 65 items, and so no coefficient larger in magnitude. Such relations are forgeries only where the application admits multiplicities; they are not in general set relations.

For comparison, additive hashes with 128-bit security against Wagner’s algorithm need 2688 bits of output when a relation may have at most $2^{25}$ terms, and 4160 bits without that bound [mihajloska-gligoroski-samardjiska-2015, Section 4; meyer-2022, Section V-B]. Against lattice reduction on multisets, at the Hermite factor constant $c$ of about 1.007 that 128-bit security requires, AdHash needs a modulus of over 400,000 bits [maitin-shepard-et-al-2016, Appendix B]. For an additive fingerprint modulo $2^{256}$, where the leading-order estimate above is about $2^{32}$ operations, Hoyte reports a $k$-dimensional birthday solver that finds collisions in about 28 hours on eight cores, with 60 GB of memory and 1.5 TB of storage [hoyte-2023]. The checksum does not expose the residues modulo $r$ that these algorithms need until the logarithms are known. Once they are, the modulus is $r$, at most $2^{127}$, and the estimate falls by a factor of $2^{9.5}$ to $2^{11.5}$, low enough that a relation among the residues can be found in practice.

In these attacks the cost is dominated by computing the logarithms; this bounds the cost of a forgery from above, not from below. For $L$ logarithms in one group, with $L$ well below $r^{1/4}$, rho with retained distinguished points costs on the order of $\sqrt{L}$ times one logarithm [bernstein-lange-2012, Section 1, after Kuhn and Struik]: about $2^3$ times the tabulated cost for the multiset relation above, and $2^{10}$ to $2^{11}$ times for Wagner’s algorithm, as order-of-magnitude estimates. Whether lattice methods find set relations from fewer logarithms is not assessed. The attack of yangl1996/riblt#3 on the XOR checksum is the case of this structure in which the relation is found by linear algebra over ${\mathbb{F}}_2$ at negligible cost. The step from a relation to a decoding failure, which depends on the cells the items map to, is not assessed here (Linearity of the checksum).

Generic work factor. The 107- and 109-bit families have rho costs of $2^{52.3}$ to $2^{53.8}$, in the lower part of the reference range. Curve-specific precomputation is limited, not excluded, by deriving a curve per beacon value (Precomputation and per-namespace curves).

Weil descent. A $\mathrm{GF}(2^{127})$ curve is reachable by the generalized GHS descent with heuristic probability about $2^{-52}$ per beacon value, and no check excludes it (Parameter selection and verification).

Probable primality. The verifier tests $r$ with Miller–Rabin to 24 fixed bases. Composites passing all of them can be constructed, so no error bound holds against a prover who chooses $r$. The conclusion that the group order is the cofactor times $r$ is conditional on the primality of $r$.

Pairing reductions. The embedding degree of $r$ is checked to exceed $2^{20}$, which excludes the reductions of Menezes–Okamoto–Vanstone and Frey–Rück to that bound; the degree is not otherwise determined. The check, a baby-step giant-step search for $q^k=1\mathrm{mod}r$, takes about $2^{11}$ products modulo $r$, which the curve-generation benchmarks time alone (curvegen/embedding). Anomalous curves, of order $q$, are rejected.

Hash to curve. Items are hashed with tagged, salted SHA-256 and a counter (hash). A deterministic map takes one 128-bit half of the first digest (hash_to_curve_map1) or sums the images of both halves (hash_to_curve_map2); try-and-increment takes the two halves of each digest in order and increments the counter when both fail. The reduction of a candidate to the field and the sign convention are defined per map. No RFC 9380 hash-to-curve suite is implemented. Uniformity on the group is not required (Adversary), but the weak-encoding hypotheses of the reduction of [maitin-shepard-et-al-2016] are not established for these maps.

Mapping-seed collisions in the RIBLT. This weakness belongs to the RIBLT’s mapping, not to the checksum, and lies outside the research question; it is stated because the RIBLT comparison rows use both mappings. The cells an item maps to are determined by its digest under the mapping tag (riblt), through the gap law of the reference implementation [yang-gilad-alizadeh-2024]. Two items whose generators start in the same state map to the same cells in the same order for every prefix of the coded symbols. If both lie in the symmetric difference, every cell they map to holds both: after the other items are peeled, its count is even and its checksum is the sum or difference of their two points, so no cell containing them becomes pure and neither item is recovered, unless a checksum collision or false singleton occurs independently. A finite peel returns failure; a rateless decoder that requests coded symbols until decoding succeeds does not terminate. No checksum collision is required, and the group’s work factor does not enter. The reference implementation seeds a 64-bit multiplicative generator with the item’s 64-bit hash. If the mapping input is public, two items with equal seeds are found by a birthday search over about $2^{32}$ digests, below the rho cost of every curve family compared, and an item sharing a chosen item’s seed costs about $2^{64}$. Between honest items, a coincidence has probability about $n^2/2^{65}$ for $n$ items in the difference. Buchanan’s implementation [riblt-ecmh] replaces the generator with ChaCha8, citing this case (yangl1996/riblt#3, comment of 2026-02-24). The implemented default seeds xoshiro256++ with the whole 256-bit map digest. Its state is the digest itself, so equal generator states require equal digests, at a cost of about $2^{128}$ for a pair, with one exception in $2^{256}$: the all-zero digest is reseeded from SplitMix64 and shares a state with the one digest that encodes that state. Since the generator runs through its $2^{256}-1$ nonzero states in one cycle, distinct states yield distinct sample streams; whether two streams place their items in the same cells of a given table is the gap recurrence’s matter, as for any generator. The generator need not be cryptographic: the digest is already a salted hash, and the mapping is public. The gap law is unchanged, and ChaCha8 (ChaCha8) and the 64-bit generator (Mcg64) remain as comparisons. Nor does the seed need 256 bits: a 128-bit seed puts equal seeds at about $2^{64}$ identifiers after the salt. Riblt::projected seeds the generator with the whole projection of the item’s identifier under keys of the mapping’s own (Adversary), in a field chosen for its cost apart from the checksum’s. Its halves are a linear map of the identifier’s halves under two keys, invertible unless a key is zero or the two are equal, so equal seeds require equal identifiers; under ${\mathbb{F}}_{2^{130}-5}$, whose halves are truncated to 128 bits, they require a coincidence of 256 bits. Either costs about $2^{128}$. The projection’s cost is benched, but it is not the default. The mapping need not depend only on the public salt of the checksum: a schedule keyed by a secret shared between the peers prevents a third party from searching offline for equal seeds, even with a 64-bit generator, while the checksum’s namespace remains public. The coincidence between honest items is unchanged by the key, since it does not depend on who can compute seeds. Schedules that agree only on a prefix delay a rateless decoder without stalling it; that delay, and any other a third party induces through the schedule, concerns the sketch rather than its checksum and is not assessed (Questions outside this study).

Side channels. Hashing, field inversion, and batched inversion run in variable time. This is acceptable only because the hashed items are public in the setting considered (Adversary); the code is unsuitable for secret inputs. Power and electromagnetic leakage are not considered.

Assumptions on the application. The beacon value is assumed unpredictable until the epoch begins; withholding, delay, and grinding by its producer, whose cost Bonneau, Clark and Goldfeder bound for block hashes [bonneau-clark-goldfeder-2015], are outside this study (Questions outside this study). A checksum collision causes a decoding error within one namespace. The protocol is assumed to validate the items it obtains independently, so that such an error, or a curve whose discrete logarithms are computed, is a failure of liveness until the next beacon value selects a new curve (Setting and reference work factor); recovery is left to the protocol.

Measurement methodology

The benchmarks report operation latency, throughput with independent accumulators, and batch costs. Batch size and representation conversion are part of the workload. A component estimate such as

hash + prepare + k * add

where $k$ is the number of coded symbols an item maps to, is a sum of separately measured operations. The RIBLT workload measures complete executions for comparison.

The benchmark report opens with a decision table. For each family it gives the nominal rho of Security considerations; the measured cost of addition, of hashing and preparation, and of encoding and decoding; the two estimates of Cost in repeated reconciliation at $n=10^5$ and $d=10^3$; and the cost of curve selection. One family dominates another if its rho is at least as large and, for each of the four operations, it either reads the same measurement or is faster beyond both confidence intervals, and it is faster on at least one. Families that no other dominates are not thereby ranked against each other.

Code-generation inspection identifies implementation effects. Static instruction counts are not timings. Binary-field performance depends on the build’s carry-less multiplication: without PMULL or PCLMULQDQ the field product falls back to a portable routine, and the binary families’ measurements do not carry over to such a build. bench-bins-generic measures that backend. Each result is bound to its source revision, compiler, target features, machine, and measurement method. The code-generation report records observations for the revisions and configurations it names.

With Nix installed, the checks run from the repository root:

nix flake check

The book builds with:

nix build .#site

A group and reconciliation measurement run:

nix run .#bench-run -- group riblt

Each run is identified by a fresh UUIDv7, which sorts by start time and needs no coordination between machines. The executables come from a Nix derivation built for a named target CPU: bench-bins is the architecture’s default (apple-m4 on aarch64, x86-64-v3 with PCLMULQDQ on x86_64), and bench-bins-generic is the baseline without carry-less multiplication. BENCH_BINS selects another such build. The runner refuses executables that need a feature the host lacks, times the suites serially, and records metadata and raw Criterion output under bench-runs/<id>/, together with a report. Other builds and measurements should not run during timing. To show whether they did, the runner samples the load averages every 5 seconds, the interval at which the kernel updates them, into load.tsv, beginning and ending with 30 seconds idle that measure the machine’s own load; the report gives each phase’s mean and recovers the threads runnable from successive 1-minute averages where the kernel does not report them.

The Go benchmarks of the reference implementations run separately (Comparison with the reference implementations):

nix run .#riblt-go-bench

A report can be regenerated from an existing run whose benchmark identifiers the reporter recognizes; runs recorded under an earlier schema need the reporter of their revision:

nix run .#bench-report -- bench-runs/ID report-output

Published runs are kept in the repository in a compact form, one directory results/<id>/ per run. benchmarks.csv has one row per benchmark: Criterion’s group, function and parameter, the estimate the report reads (the slope where Criterion fits one, otherwise the mean), its 95% confidence interval, and the declared throughput. meta.json is the run’s metadata without the host name, curvegen.csv, present when the run timed curve selection, the searches per seed, and load.tsv the load samples. Criterion’s output, the figures and the report are not kept; the classification into layers, families and operations is not stored either, and is applied by the reporter of the revision that renders the run. Only a run of a committed source is exported, since no published revision reproduces one with uncommitted edits. Each run is exported into its own directory under results/, which must not exist yet:

nix run .#bench-report -- --export bench-runs/ID results/ID

The reporter renders the directory as it renders the run’s Criterion output, to the same tables and figures, except that only the default estimate is available. The site build renders each run under results/ as a chapter of the book’s evidence, whose first paragraph states the commit, machine, build and start time recorded in meta.json.

The group plan

The group suite times each family in two passes. The first times what the insertion model and the RIBLT plan read: hashing, preparation, encoding and decoding in batches of 1024, addition, negation, the identity test, and equality on impure cells. The second times, for the families the first pass singles out, batches of 8 and 64, subtraction, equality on pure cells, and the hash of 32-byte IDs to addends under salted SHA-256 and under each projection (Adversary). A family is singled out when its modeled insertion at $m=1350$ (below) is within 50% of the least of any family; if none of these is over a field of odd characteristic, the cheapest such family is added as a contrast. The plan is recorded in group-plan.tsv and meta.json; GROUP_PLAN reuses another run’s.

The RIBLT plan

The RIBLT suite times a family under one hash construction and at a scope chosen from the group operations of the same run, which the suites before it time. For each family, the construction is the one whose modeled insertion, hash + prepare + k * add or a fused hash to the addend, costs least at $m=1350$ among the constructions the RIBLT benchmarks implement for it. The scope follows that cost’s ratio to the least of any family: within 15% every sweep, within 50% a reduced sweep of each axis’s endpoints and middle, and otherwise a single point of each benchmark. A new construction therefore enters the RIBLT measurements through its group benchmark, without a change of any family’s default hash. A family timed beyond a single point also gets the field whose projection hashes its IDs to the addend cheapest under its construction, and its encoding and peeling are timed again, at the reduced sweep’s points, with cells keyed by IDs under that projection. Their mappings are seeded by the projection that digests IDs cheapest, which does not depend on the family; the RIBLT suite times its mapping rows first to choose it. The XOR checksums and ristretto255 reproduce the Go reference implementations and are timed in full regardless. The plan is recorded in riblt-plan.tsv and meta.json; RIBLT_PLAN reuses another run’s.

Reading a run report

Values are Criterion’s estimate and 95% confidence interval, per element where the benchmark declares an element count and otherwise per iteration. A table colours each value by its ratio to its column’s minimum on matplotlib’s inferno scale, from pale yellow at the minimum to purple at 16 times or more. The minimum is bold when no other interval overlaps its own; otherwise the values that overlap it are tied, in italics. Overlap leaves an order unresolved. A tag after a row’s name marks work unlike the rest of its column: addition formulas that are not complete (they branch on the identity and on doubling), or a term another suite timed. The XOR baseline is excluded from column minima. Tooltips name the benchmark each value reads.

A modeled cost sums separately measured operations, and its interval combines their half-widths in quadrature; it has no independently measured coverage, and neither has a range over curve-selection seeds, which spans their point estimates. The insertion model uses $k(m)$ of Workload and compatible representations: a recipe either hashes, prepares the hash’s output, and adds the prepared addend, or hashes straight to the addend and skips the preparation. Pornin’s map returns the extended binary addend, and its variants to $(x,\lambda )$ and $(u,v)$ the λ and $u$ addends; Elligator 2 and SSWU return affine points, which the measured preparation takes. Preparation and addition are timed on try-and-increment inputs, so a recipe with another map is a model, not an end-to-end measurement. Every recipe also adds the salted map digest and the walk of the mapping’s indices below $m$, timed alone by riblt.mapping and the same for every family, which is why the model’s ratios between families are smaller than those of their hashes and additions. The model omits cell allocation, the key XOR and the counts; the measured RIBLT encoding includes them.

Preparation occurs once per source item, addition once per cell update, and subtraction negates an addend before adding it. Encoding and decoding occur per transmitted and received cell. Throughput runs eight independent accumulators, latency one dependent chain. A batched operation reports time per element at its batch size, 1024 unless a sweep states another. Batch inversion (Montgomery’s trick) replaces $n$ inversions with one and $3(n-1)$ multiplications; binary hashing shares them across the pending candidates of each round, and preparation, normalization and decoding where the representation needs an inversion. The prime-field hashes are bound by a square root per item, which batching does not share. An encoder can batch all its source items, a decoder only the cells of the current peeling wave. The binary w-codec families hash to reusable addends, so their preparation is a copy.

Costs by lifetime

An insertion into cells keyed by IDs is reported by how long each of its terms remains valid. The ID, an item’s SHA-256, is computed once and outlives every salt. Once per salt, a curve is accepted and each hash’s keys are derived. Once per salt and item, the ID is hashed to the addend and to the mapping’s seed, and the seed’s indices are walked below $m$. Once per cell update an addend is added, and once per transmitted cell a sum is encoded and decoded. Each term is given under salted SHA-256 of the ID and under the projections, followed by two measured encodings: by salted SHA-256 of the items themselves, and by projections of IDs computed before the timed routine. A per-salt term is amortized over the items inserted under that salt, a number the benchmarks do not fix.

Contributing a run

A run on another machine is added to results/ by pull request. The runner records the commit of the checkout it runs in, and only a run of a committed source is exported, so the run happens in a clean clone of a published commit:

git clone https://github.com/nothingmuch/ephemeral-ecmh
cd ephemeral-ecmh
nix build --no-link .#bench-bins
nix run .#bench-run -- --profile full

The run’s directory, bench-runs/ID, is named by its UUIDv7; the report describes the machine and build from meta.json. Building beforehand keeps compilation out of the timed window. The full profile (3 s warm-up, 5 s measurement and 100 samples per benchmark) takes several hours over all suites; runs under the default quick profile are preliminary. On x86_64 the native build needs AVX2 and PCLMULQDQ; BENCH_BINS and suite arguments select another build or a subset, as above. The run is then exported:

nix run .#bench-report -- --export bench-runs/ID results/ID

The Go benchmarks of the reference implementations, timed on the same machine, can accompany the run as results/ID/riblt-go.txt, which the reporter does not read:

nix run .#riblt-go-bench | tee results/ID/riblt-go.txt

The export is committed on a branch, whose pull request adds only results/ID/:

git switch -c runs/ID
git add results/ID
git commit -m "runs: ID"

Field and curve code generation

This report examines optimized field arithmetic and curve operations for implementation effects that could confound the ECMH and RIBLT comparison. It records observations from the source revision and target configurations below. Instruction counts identify code for inspection; they do not measure execution time or establish a ranking of fields. Branch counts are static branch sites, not executed branches. Native timing evidence is reported separately in the benchmark results.

Run:

• nix run .#asm-report at 2d6c7e3c (rustc 1.98.1, LLVM 22.1.8, release profile, --features asm-probes).
• 24 configurations × 239 probes. Each probe is an #[inline(never)] wrapper in src/asm_probes.rs around one field operation, or one group add, sub, equals, prepare or decode, for each of 29 group representations.
• “Closure” is the probe plus every crate-local function it reaches. Calls out of the crate are listed but not counted: crrl’s set_invert, Plonky3’s try_inverse, the allocator. Merged functions are reported as aliases.
• The listings, meta.json, summary.md and probes.tsv are archived outside the repository, in ephemeral-ecmh-archive/asm-runs/matrix-20261003.
• nix build .#asm-listings builds the same matrix from the flake source and records the source revision in place of the host and date. A listing at any revision can therefore be rebuilt without the archive.
• Probe and row names use the benchmark report’s family identifiers: the curve model (binary, weier, edwards, twisted) followed by the field, 127 for $\mathrm{GF}(2^{127})$ or for ${\mathbb{F}}_p$ with $p=2^{127}-1$, 61x2 for $\mathrm{GF}(p^2)$ with $p=2^{61}-1$, goldilocks2 for $\mathrm{GF}(p^2)$ over the Goldilocks prime, and so on. Candidate constructions describes each family. All counts are of static instructions.

Interpretation

The inspected instruction sequences are consistent with the stated arithmetic counts. The following implementation and target effects qualify the corresponding measurements. This inspection does not establish that each implementation is optimal, or that the measured ordering generalizes to other processors.

Other observations explained by the inspected code:

• The unscaled binary form has the fewest carry-less products per add and the most per equality test (§4).
• $\mathrm{GF}(2^{122})$’s multiply needs more carry-less products than $\mathrm{GF}(2^{127})$’s, from its representation (§3).
• fp127’s short sqrt is a loop (§6).
• The Goldilocks panic stubs are unreachable bounds checks, and the Goldilocks² add’s branches are upstream’s rare-carry paths (§5, §6).
• The merged $\mathrm{GF}(2^{122})$ $\lambda$ adds follow from the formulas (§4).

1. Binary-field backend selection

• Android: In the inspected LLVM configurations, the Cortex models leave out the optional crypto extension. Without it, the binary-field implementations compile to their portable backends, carry-less products from integer multiplications of masked operands (crrl’s gfb254_m64 for $\mathrm{GF}(2^{127})$, soft.rs for $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{122})$): 13 to 19 times the instruction count. Among the inspected Android models, only oryon-1 enables it by default. A deployment using the carry-less backend must establish hardware support and enable +aes, either as a baseline requirement or through runtime detection and dispatch.
• x86-64: none of the distribution baselines (v1–v4) includes PCLMULQDQ. Adding +pclmulqdq alone to v3 changes only the binary-field probes: the multiplies use PCLMULQDQ with the counts of the named cores, and binary127::add falls from 5885 to 225 instructions. The feature, not the CPU model, selects the backend.
• Benchmarks: bench-bins compiles for apple-m4 and for x86-64-v3+pclmulqdq, bench-bins-generic for generic and x86-64; all four are in this matrix. A portable build uses the path of the last two.

For comparison, edwards127::add is 361–370 on every Android model, 362 on M4 and 524 on Zen 4. These are code sizes on two different paths, not speeds.

2. Apple: the configurations compiled are byte-identical through M4

Compiled: aarch64-apple-darwin at default (apple-m1), apple-a14, a15, a16, a17, m4 and m5, and generic. No iOS target was built: the A-series models were compiled for macOS. These are compiler-tuning probes, not iOS ABI coverage or phone measurements.

• default through apple-m4: the whole listings are byte-identical.
• apple-m5: 14 of the 239 probe closures differ: the binary127 equals in every representation, and the decode, equals or prepare of the Edwards and Weierstrass families. In each, LLVM uses umin/umax where the others use cmp + cset/csel, with the neighboring instructions rescheduled.
• generic: no crypto extension, so the binary fields take the portable path (binary127::add 4707, as on Android default). The CPU model also changes the prime-curve code: 149 probes differ from apple-m4 in their closure metrics, among them the Edwards, $a=-1$ and Jacobian adds, by a few percent (edwards127::add 373 against 362). The generic benchmark subset therefore carries prime-field control rows.

Identical code removes the need to review each configuration’s code separately, not the need to measure each machine.

3. Multiplies per binary field (M4; PCLMULQDQ counts on x86 are the same)

• The code matches src/field/gf2_122/pmull.rs. The standalone probe uses 4 instructions to materialize the reduction constant; the inspected inlined callers hoist them.
• Critical path: $\mathrm{GF}(2^{122})$’s is three dependent PMULLs (product, then two folds); $\mathrm{GF}(2^{127})$’s is one PMULL plus shifts.
• Per extended point add: 44 PMULLs over $\mathrm{GF}(2^{127})$, 68 over $\mathrm{GF}(2^{109})$, 82 over $\mathrm{GF}(2^{122})$. Pentanomial reduction requires more PMULL instructions than Karatsuba saves in the multiplication step.

These counts arise from this representation and reduction schedule; they do not establish a lower bound for arithmetic in the field, and they are not timings.

4. Binary fields and representations: $\mathrm{GF}(2^{109})$ against $\mathrm{GF}(2^{127})$, dense against GLS over $\mathrm{GF}(2^{122})$

$\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{127})$ both hold an element in two 64-bit words and differ in the modulus. Degree 109 has no irreducible trinomial, so the pentanomial $z^{109}+z^5+z^4+z^2+1$ folds with two PMULLs where the trinomial $z^{127}+z^{63}+1$ folds with shifts (§3), and its $\sqrt{z}$ is dense, so a square root costs a multiplication where $\sqrt{z}=z^{64}+z^{32}$ costs two shifts. The PMULL counts do not order the timings: in the M4 native run at 7d4c6aa1 the $\mathrm{GF}(2^{109})$ add, at 68 PMULLs against 44, took 12.8 against 14.6 ns at throughput, while its square root took 2.89 against 1.26 ns.

PMULLs per operation’s closure, M4 (x86 carry-less targets equal):

• Formulas: the add counts equal the formulas’ costs at the per-field counts of §3: extended (Pornin’s complete addition) $8M+2S+2m_{\beta }$, unscaled (the same formula with $\beta$ cancelled) $7M+2S$. Equality is $1M$ in $\lambda$ coordinates, $2M$ extended and $3M$ unscaled, which compares $Su$ with $vXZ$ ($w^2=S/(XZ)=v/u$).
• Unscaled: the fewest products per add and the most per equality test. RIBLT adds once per item and cell (the cost model’s $k(m)$ adds per item); equality tests are paid per difference during peeling, which the decision model leaves out. The counts therefore point toward the unscaled form for this workload; the timing rows decide.
• Prepare: the $w$ encoding and unscaled addends are the decoded affine point itself, so preparation is a copy (3–6 instructions). The $\lambda$ form’s prepare computes $\lambda =x+y/x$: one inversion (crrl’s set_invert, uncounted, over $\mathrm{GF}(2^{127})$; 170–220 PMULLs in the crate over $\mathrm{GF}(2^{109})$ and $\mathrm{GF}(2^{122})$).
• Merged: rustc merges binary122_lambda::add, sub and equals (Curve<Gf>) with the binary122_gls_w ones (Curve<Gf61>). Curve<K> selects the representation of $B$ and its derived constants $b$ and $\beta$; $\lambda$ mixed addition uses none of them, so identical code is expected.
• GLS: only the extended add and prepare differ, by the multiplication by $\beta$: 82 versus 80 PMULLs, 20 versus 18. These counts do not imply a corresponding speedup; the GLS endomorphism concerns scalar multiplication, outside the primary RIBLT workload.

5. Point adds: branches and stack

Static counts over the add’s closure; ranges are over the configurations of each architecture.

• Branches:
  • Extended and unscaled binary adds, and the Edwards and $a=-1$ adds over fp127, fp107, $\mathrm{GF}(p^2)$ for $p=2^{61}-1$ and $p=2^{64}-59$, are branch-free.
  • $\lambda$ adds have 4–5 branches: $x_P=x_Q$ and the identity, exceptional cases of the formulas.
  • Weierstrass projective adds (Renes–Costello–Batina) have one branch, the test for an $O$ addend, which has no affine representation (two over fp107 and on x86 over $\mathrm{GF}(p^2)$). Jacobian adds have 4–7 and include the inlined doubling (746–880 instructions on M4, against 528–670 for the complete projective form), so only timings can compare them.
  • twisted128’s add has 4 branches on M4, from fp128’s carry handling, which its source documents as variable-time; its inputs are public.
  • twisted-goldilocks2’s add has 61 branch sites on aarch64 and 20 on x86. They are Plonky3’s Goldilocks reductions, which branch on carries and borrows that upstream marks rare (branch_hint). They are not exceptional cases of the point formulas, and a static count does not say how often they are taken.
• Stack:
  • The binary addition probes on carry-less targets have at most two stack accesses (on aarch64, none outside the $\mathrm{GF}(2^{122})$ adds; on x86, a push and pop of one callee-saved register); their field elements use vector registers. The portable path spills: 111–767 accesses on x86 without PCLMULQDQ.
  • The prime-curve additions spill on x86: 34–110 stack accesses, against 8–31 on aarch64 apart from weier61x2 (22–55). Register pressure from the multi-limb representations is a platform-dependent implementation effect in this comparison.

6. Prime fields and extensions

• Multiplication: the M4 prime multiply rows have no calls out of the crate. Their reduction sequences differ; counts alone do not determine which field is faster.
• fp127 sqrt: the 71-instruction body includes a loop initialized to 125. The 26× difference in static closure size relative to fp128 (1878) does not give the ratio of executed instructions or timings.
• Goldilocks:
  • Inversion is an external call to Plonky3’s try_inverse, so closure counts omit its body.
  • The base field’s and Goldilocks²’s panic_bounds_check paths come from the upstream Tonelli–Shanks table indexing, which Goldilocks²’s square root reaches through the base field’s. The source establishes i < m <= 32, so they are unreachable, not a runtime cost.
• Extensions: $\mathrm{GF}(p^2)$ for $p=2^{61}-1$ and $p=2^{64}-59$, and Goldilocks², each carry an Edwards or $a=-1$ group and, for $p=2^{61}-1$, a Weierstrass group; their decode closures (1.1–1.6k on M4) include the square root in $\mathrm{GF}(p^2)$.

7. Hash-to-curve side

• prepare:
  • Preparation for the variants whose affine representation is already the addend consists of copying it: 3–6 instructions (binary $w$ encoding and unscaled, Weierstrass).
  • For extended binary forms it costs 73–100 on M4 (computing $T$).
  • For Edwards, the single-item probe is 1.7–3.6k instructions and allocates. It delegates to to_cached_batch on one item. The inversion is intrinsic to the coordinate conversion (the affine is the Montgomery point); the Vec is an implementation choice. RIBLT’s encode and batched peel use prepare_batch, which amortizes the inversion.
• decode:
  • $\mathrm{GF}(2^{127})$’s is 193–274 with PMULL; its inversion is crrl’s set_invert, uncounted here.
  • $\mathrm{GF}(2^{122})$’s and $\mathrm{GF}(2^{109})$’s are 640–950 on carry-less targets, all in the crate (half-trace and inversion). On x86 without PCLMULQDQ they are 1900–2210 and 1340–1490.

8. Coverage limitations

• The inspected matrix has no probes for sqrt_ratio or the whole hash-to-addend batch path.
• No iOS targets, and no measured phones: core-model names do not identify a Snapdragon or Dimensity device.
• Out-of-crate callees are not counted (Run, above).

Summary across runs

Each run’s measurements stay separate; boxes span recorded 95% intervals, with a line at the estimate, read as in Reading a run report. The displayed measurements keep their benchmark identifiers.

Coverage: Apple M4 · generic · full · ef9e82d3 appears in Insertion, Scaling, Batching, Native and generic builds, Hash to curve, Insertion cost model, Curve selection time, Cost per item with selection. Intel(R) Xeon(R) W-1390P @ 3.50GHz · x86-64-v3 · full · ef9e82d3 appears in Insertion, Scaling, Batching, Hash to curve, Insertion cost model, Curve selection, Curve selection time, Cost per item with selection. Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3 appears in Insertion, Scaling, Batching, Hash to curve, Insertion cost model, Curve selection time, Cost per item with selection.

• Apple M4 · apple-m4 · full · ef9e82d3: The run started 2026-10-08T02:49:59Z on Apple M4 (macOS 27.0.1, arm64) and timed commit ef9e82d39fbf06c605e1740360370f0003dc4ca4, built by rustc 1.98.1 (48a229cea 2026-09-01) with RUSTFLAGS -C target-cpu=apple-m4, in the full profile.

• Apple M4 · generic · full · ef9e82d3: The run started 2026-10-08T07:13:46Z on Apple M4 (macOS 27.0.1, arm64) and timed commit ef9e82d39fbf06c605e1740360370f0003dc4ca4, built by rustc 1.98.1 (48a229cea 2026-09-01) with RUSTFLAGS -C target-cpu=generic, in the full profile.

• Intel(R) Xeon(R) W-1390P @ 3.50GHz · x86-64-v3 · full · ef9e82d3: The run started 2026-10-08T18:42:23Z on Intel(R) Xeon(R) W-1390P @ 3.50GHz (?, x86_64) and timed commit ef9e82d39fbf06c605e1740360370f0003dc4ca4, built by rustc 1.98.1 (48a229cea 2026-09-01) with RUSTFLAGS -C target-cpu=x86-64-v3 -C target-feature=+pclmulqdq, in the full profile.

• Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3: The run started 2026-10-09T15:12:32Z on Intel(R) Xeon(R) W-1390P @ 3.50GHz (?, x86_64) and timed commit ef9e82d39fbf06c605e1740360370f0003dc4ca4, built by rustc 1.98.1 (48a229cea 2026-09-01) with RUSTFLAGS -C target-cpu=x86-64, in the full profile.

Insertion

RIBLT encoding per item: $n=3500$ items into a sketch of $m=1350$ cells, the $1.35d$ coded symbols that decode $d=1000$ differences, under each family’s cheapest measured hash; each run’s three fastest curves, those whose intervals overlap the third, and the representative families, ristretto255 among them. The first row is the insecure XOR baseline, SHA-256 digests XORed into 32-byte cells; the dashed line carries its estimate across the families.

Apple M4 · apple-m4 · full · ef9e82d3: binary 109-u 281.8 ns (281.4–282.2); binary 127-u 287.6 ns (287.0–288.1); binary 109-w 302.2 ns (301.6–302.8). The first two recorded intervals are separated. The third estimate takes 7.2% more time than the first. Also overlapping the third interval: binary 109 λ.

Apple M4 · generic · full · ef9e82d3: edwards127 1415.2 ns (1412.4–1418.1); weier127-jacobian 1562.7 ns (1559.9–1565.6); weier127 1683.2 ns (1679.6–1686.8). The first two recorded intervals are separated. The third estimate takes 18.9% more time than the first.

Intel(R) Xeon(R) W-1390P @ 3.50GHz · x86-64-v3 · full · ef9e82d3: binary 127-u 414.3 ns (413.8–414.9); binary 109-u 422.3 ns (421.7–422.9); binary 122 GLS-u 432.0 ns (431.1–432.9). The first two recorded intervals are separated. The third estimate takes 4.3% more time than the first.

Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3: edwards127 1879.9 ns (1873.4–1887.5); weier127-jacobian 2034.9 ns (2030.2–2039.9); weier127 2235.7 ns (2227.7–2245.0). The first two recorded intervals are separated. The third estimate takes 18.9% more time than the first.

Coverage: Apple M4 · apple-m4 · full · ef9e82d3: 12 displayed curves of 32 measured rows (including baselines); Apple M4 · generic · full · ef9e82d3: 11 displayed curves of 21 measured rows (including baselines); Intel(R) Xeon(R) W-1390P @ 3.50GHz · x86-64-v3 · full · ef9e82d3: 12 displayed curves of 32 measured rows (including baselines); Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3: 11 displayed curves of 21 measured rows (including baselines).

Scaling

Encoding per item against the sketch’s cells $m$, $n=3500$ items; peeling per difference against the set difference $d$, in a sketch of $m=2d$ cells with the prefilter and batched hashes; hashing per item against the batch size, try-and-increment filled and the comparison maps open; the hashes of ristretto255 and of the XOR baseline, a SHA-256 digest, have no batched form and are a single mark at batch size 1. Bands are recorded intervals; line style tells the runs apart.

Batching

Hashing per item by construction, one item at a time and in batches of 1024; a grey line joins a construction’s two estimates. Batching shares the field inversion; the prime-field hashes are bound by a square root per item, which it does not share. ristretto255’s hash and the XOR baseline’s SHA-256 digest have no batched form: each is a single hollow box, labelled one at a time only. The table gives the time saved, $100\times (1-\text{batched}/\text{individual})$.

Native and generic builds

Generic over native time for benchmarks matched on one CPU, source and compiler; the dashed line is parity, boxes the propagated ranges. ristretto255’s point addition and the XOR baseline’s addition of 32-byte digests, both at throughput, are matched as references where both runs timed them.

Matched group models in Apple M4 · generic · full · ef9e82d3: edwards127, binary 109, binary 109 λ, binary 109-u, binary 109-w, binary 122 GLS, binary 122 GLS λ, binary 122 GLS-u, binary 122 GLS-w, binary 127, binary 127 λ, binary 127-u, binary 127-w. Other models need corresponding generic measurements.

Hash to curve

Hashing per item by construction for the representative families, one item at a time and in batches of 1024; a grey line joins a construction’s two estimates. Constructions differ in the representation they return, as the benchmark identifiers in the data state. The XOR baseline’s row is its SHA-256 digest, which maps to no curve, and the dashed line carries its estimate across the families; ristretto255’s and secp256k1’s hashes are their libraries’ maps, timed one at a time only.

Insertion cost model

Modeled insertion per item under each family’s cheapest compatible recipe, a fused hash to the addend counting as hash and prepare, and additions at throughput. A sketch of $m=1350$ cells, the $1.35d$ coded symbols that decode $d=1000$ differences, maps an item to $k(m)=13.57$ cells on average (Workload). The measured insertion includes what the model omits. ristretto255 and the XOR baseline have no batched hash: they hash one item at a time and add the hash output as is, with nothing to prepare. The XOR baseline is absent from Apple M4 · generic · full · ef9e82d3, Intel(R) Xeon(R) W-1390P @ 3.50GHz · generic · full · ef9e82d3: its addition was not timed at throughput, with eight accumulators, there. The time axis is logarithmic, as the totals span more than a factor of ten: a segment’s boundaries read as cumulative times, its length not as its share.

Curve selection

Selection work per salt $S$ as a percentage of the insertion work $Nc$ it is amortised over, $100S/(Nc)$, against the items $N$ inserted per salt, with $c$ the measured insertion per item ($n=3500$ items into a sketch of $m=1350$ cells, as in Insertion). The band spans the seeds, the fastest thick and the slowest thin; dashed curves are partial stages, lower bounds on $S$. Normalised by each family’s own $c$, the figure reads as the volume that amortises selection, but it credits a family that is slow to insert with a smaller ratio for the same $S$; the next two figures give $S$ and the cost per item in absolute time. The baselines, XOR and ristretto255, select no curve: their ratio is zero, which a log axis cannot show, and they appear in the absolute figures.

Curve selection time

The time $S$ per salt of each selection stage, on a log scale: a tick at each seed’s estimate, or at the single candidate fixture of a point count, and a band from the fastest seed to the slowest; dashed marks are partial stages, lower bounds on $S$. Unlike the ratio above, these times compare across families whatever their insertion cost. XOR has no curve and ristretto255 is a fixed group: neither selects a curve, as their rows state.

Cost per item with selection

Insertion and amortised selection per item, $c+S/N$, against the items $N$ inserted per salt, with $c$ the measured insertion per item ($n=3500$ items into a sketch of $m=1350$ cells) and $S$ the selection time per salt above. As $N$ grows each curve falls to its family’s $c$. The band spans the seeds, the fastest thick and the slowest thin; dashed curves are partial stages, lower bounds on $S$. The dotted flat lines are the insertion of the baselines, XOR and ristretto255, which select no curve, so that $c$ is their whole cost per item.

Benchmark run Apple M4 · apple-m4 · full · ef9e82d3

Run Apple M4 · apple-m4 · full · ef9e82d3 started 2026-10-08T02:49:59Z on Apple M4 (macOS 27.0.1, arm64) and timed commit ef9e82d39fbf06c605e1740360370f0003dc4ca4, built by rustc 1.98.1 (48a229cea 2026-09-01) with RUSTFLAGS -C target-cpu=apple-m4, in the full profile.

1523 benchmarks from run Apple M4 · apple-m4 · full · ef9e82d3. Reading a run report explains the values, colours and tags.

Families compared

Each family’s nominal ${\log }_2$ rho, this run’s costs (addition at throughput; hashing, preparation, encoding and decoding batched), the two regimes of Cost in repeated reconciliation for a set of $n=10^5$ items, a set difference of $d=10^3$ and a sketch of $m=1350$ cells, in which a new item updates $k=13.57$ cells on average, and the mean time over seeds to find a curve and verify its certificate. Dominance is as defined in Measurement methodology. Additions are 84 to 100% of each rebuilt estimate.

Machine

Load averages by phase while the run timed (Measurement methodology).

Group benchmark plan

Which families the group suite’s second pass timed. Its first pass timed every family’s core rows; from them and the comparison maps, bench-run chose the families whose modeled insertion at $m=1350$ was within 50% of the cheapest (lead) and, if none of them was over a field of odd characteristic, the cheapest that was (contrast). The second pass added the batch sweep, subtraction, equality on pure cells and the hashes of IDs (The group plan).

RIBLT benchmark plan

Which RIBLT benchmarks this run generated. Before the RIBLT suite ran, bench-run chose from this run’s group and hash-to-curve results, for each family below, the hash its RIBLT benchmarks use and their scope: every sweep (full), each axis’s endpoints and middle (buffer), or one point of each benchmark (spot); and for full and buffer scope, the field whose projection hashes the family’s IDs cheapest and the one whose projection seeds mappings cheapest, under which it also encodes and peels cells keyed by IDs. The plan records what was measured, not a result; the XOR checksums and ristretto255 are timed in full regardless (The RIBLT plan).

Insertion

Modeled insertion per item into a sketch of $m$ cells: a hash, a prepare, and an addition to each of the $k$ cells the item maps to on average ($m=5$: $k=2.90$; $m=20$: $k=5.29$; $m=150$: $k=9.20$; $m=1350$: $k=13.57$; $m=12150$: $k=17.96$), by compatible recipes (Reading a run report). The references (xor, ristretto255) have no batched hash: they hash one item at a time, add the hash output as is, and are in the figure and the second grid. Each total also counts, the same for every family, the salted SHA-256 map digest and the xoshiro256pp walk through the item’s indices below $m$ (riblt.mapping): 39.4 ns at $m=5$, 44.6 ns at $m=20$, 54.4 ns at $m=150$, 68.8 ns at $m=1350$, 90.0 ns at $m=12150$. The key XOR and count of each cell are not modelled; riblt.cells measures them with the rest of the cell updates.

Batching

Batched against individual time per element. The inversions-shared column divides the saving by the difference between individual and batched field inversion; it also absorbs allocation and control flow.