Two current Ethereum proving efforts are explicitly hash-heavy. A recent post-quantum validator aggregation design says that verification is dominated by hash evaluations, while a separate WHIR implementation reports Poseidon2 Merkle hashing at 58% of GPU time for a representative configuration:
While implementing a recursive prover, I ran into a batching problem that the homogeneous case hides. The prover contained many executions of one fixed Poseidon2b permutation, but those executions were split across nine committed regions with very different instance counts.
If region a contains 2^w_a permutation instances, its Boolean width is w_a. In my case, the nine widths were
[14, 15, 17, 16, 12, 15, 16, 12, 13]
The two direct approaches pull in opposite directions.
First, prove every region independently. This preserves the native witness sizes, but repeats the complete 66-layer GKR protocol nine times.
Second, combine the regions into one max-width walk. This gives one transcript, but requires padding every region to 2^17 rows. The physical witness grows from 360,448 to 1,179,648 Poseidon rows.
The construction below keeps the useful side of both approaches. It runs one aggregate GKR walk over the native-size regions and represents the missing high coordinates with an implicit selector. The result is one transcript without materializing max-width padding.
Ragged embedding
Suppose there are A regions. Let f_a be the layer relation for region a, let w_a be its Boolean width, and let W be the largest of those widths:
For the nine regions above, W = 17.
I embed its native relation into the W-variable hypercube with
When w_a = W, this is an empty product and equals one. The implementation works in characteristic two, so the selector uses 1 + x_j. Over an odd-characteristic field, each factor is instead 1 - x_j. The ragged embedding itself is not specific to Poseidon2b; the implementation and benchmarks below are.
On the Boolean hypercube, 1 + x_j is one when x_j = 0 and zero when x_j = 1. The selector therefore keeps exactly the zero suffix:
The Boolean sum is unchanged.
Each added variable has individual degree one. The Poseidon2b layer relation already has individual degree eight after multiplication by the equality polynomial, so the maximum sumcheck degree remains eight.
During the first w_a rounds, the prover folds the physical table normally. Once those coordinates are exhausted, it retains the single folded state evaluation and updates only the selector by 1 + r_j.
The dominant witness work is therefore
plus lower-order per-region work in the added coordinates. Physical max-width padding instead costs
where L = 66 is the number of Poseidon2b layers and A is the number of regions.
This is related to an earlier GKR batching discussion on this forum, which considered homogeneous copies of one base circuit:
The construction here keeps the permutation fixed but allows its committed regions to contain different numbers of instances.
Implementation
I implemented three paths for exactly the same output claims and the same 66-layer relation:
- nine independent native-width walks;
- one physically max-padded walk;
- one implicit ragged walk.
Committed rows remain in GF(2^128). Sumcheck claims, messages and challenges use a quadratic GF(2^256) extension. Fiat-Shamir challenges are sampled from a 2^255-element affine support outside the distinguished base subfield.
The prover keeps both extension coordinates in the CLMUL-friendly flat basis. On the benchmark machine, paired base-field products use AVX2 and VPCLMULQDQ. The verifier uses the public tower-field implementation, so each measured proof crosses an independent representation boundary before acceptance.
The artifact checks all of the following:
- all three constructions expose the same output claims;
- prover and verifier derive the same terminal reductions;
- every terminal is discharged against the native layer-zero columns;
- a mutated transcript is rejected;
- the SIMD field path matches the public tower arithmetic;
- the specialized MDS kernels match dense matrix evaluation;
- the complete flat 66-layer path matches native Poseidon2b.
Results
The benchmark ran on a 12-thread Intel Core i7-1365U. Release builds used target-cpu=native.
Each timed proof ran in a new worker process. The order of the three variants rotated between sample rounds, with a 20-second cooldown between workers.
Independent native walks
Physical rows 360,448
Prover median 17.609 s
Prover range 17.553–17.902 s
Verifier median 4.896 s
Raw proof 2,272,512 B
Physical max padding
Physical rows 1,179,648
Prover median 43.496 s
Prover range 32.155–46.342 s
Verifier median 0.800 s
Raw proof 363,264 B
Implicit ragged walk
Physical rows 360,448
Prover median 10.830 s
Prover range 10.621–15.044 s
Verifier median 0.802 s
Raw proof 363,264 B
Against nine independent walks, the ragged construction was 1.626 times faster at the prover median, 6.108 times faster at protocol verification, and emitted a 6.256-times smaller algebraic transcript.
The padded and ragged paths have the same transcript shape and size. Their difference is physical witness work. Ragged execution avoids the exact 3.2727-times expansion in physical rows.
The current implementation peaks at 450 MiB. The sequential independent baseline uses 163 MiB because it proves and releases one region at a time, while physical max-width padding reaches 1.32 GiB. This is a time-memory tradeoff of the current checkpoint schedule, not a lower bound of the ragged construction. Checkpoint spacing, recomputation and offloading intermediate layers remain independent implementation choices.
Raw proof bytes include the algebraic transcript. They exclude serialization framing and external polynomial-commitment openings.
Reproduction
Construction note:
Complete benchmark report:
Implementation:
cargo test --release --locked --workspace --all-targets
cargo run --release --locked -p frost-gkr-bench --bin ragged -- \
--warmups 0 \
--samples 3 \
--cooldown-seconds 20 \
--explain
Ethereum relevance
This implementation uses one fixed Poseidon2b permutation over binary tower fields. The reusable part is the ragged batching of unequal instance domains, not aggregation across different Poseidon families..
Ethereum’s current post-quantum aggregation work is still a relevant workload to compare against. leanVM recursively aggregates hash-based signatures and uses Poseidon extensively, including separate width-16 and width-24 Poseidon1 permutations over KoalaBear:
The ragged construction becomes applicable when many calls to the same permutation are partitioned into committed regions with different instance counts. In that setting, separate GKR walks repeat the layer protocol, while max-padding every region pays for the largest instance domain.
I would be interested in whether this pattern occurs in current leanVM or AIR layouts, and in comparisons with the batching strategies used there and in WHIR-based proving stacks.