Ragged multi-instance GKR for Poseidon2b: one walk, unequal regions, no max-width padding

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: Exploring the Design Space for a Post-Quantum Public Key Registry for Ethereum Validators Cryptography Authors: Thomas Coratger , Tom Wambsgans , Ladislaus , Thomas Thiery , Justin Drake Credits to Benedikt Wagner and Dmitry Khovratovich for all the theoretical work, ideas, discussions and papers that have been published on eprint and that are linked in this post. As outlined in the Strawmap roadmap , securing Ethereum against the looming threat of large-scale quantum computers is a top priority. A critical milestone in this transition is migrating our proof-of-stake consensus from BLS signatures to… GPU-Accelerated WHIR Proving on Apple Silicon Privacy GPU-Accelerated WHIR Proving on Apple Silicon: Benchmarks and Lessons from Client-Side Metal Compute Acknowledgments Thank you to Moven Tsai for the Apple M3 MacBook and iPhone benchmark results in Section 4, and to Alex Kuzmin for WHIR discussions. TL;DR We accelerated the WHIR prover on Apple Silicon GPUs using Metal compute shaders, achieving up to 2.03x speedup over highly optimized CPU code (SIMD + LTO + target-cpu=native) on an M1 chip, up to 2.58x on a supplementary Apple M3 MacBook run… 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: W := \max_{1 \leq a \leq A} w_a. For the nine regions above, W = 17 . I embed its native relation into the W -variable hypercube with \chi_a(x) := \prod_{j=w_a}^{W-1}(1+x_j). 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: \sum_{x \in \{0,1\}^{W}} f_a(x_{<w_a})\chi_a(x_{\geq w_a}) = \sum_{u \in \{0,1\}^{w_a}} f_a(u). 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 O\!\left(L\sum_{a=1}^{A}2^{w_a}\right), plus lower-order per-region work in the added coordinates. Physical max-width padding instead costs O\!\left(LA2^W\right), 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: Using GKR inside a SNARK to reduce the cost of hash verification down to 3 constraints zk-s[nt]arks Using GKR inside a SNARK to reduce the cost of hash verification down to 3 constraints (1/2) Alexandre Belling, Olivier Bégassat Link to HackMD document with proper math equation rendering Large arithmetic circuits C (e.g. for rollup root hash updates) have their costs mostly driven by the following primitives: Hashing (e.g. Merkle proofs, Fiat-Shamir needs) Binary operations (e.g. RSA, rangeproofs) Elliptic curve group operations (e.g. signature verification) Pairings (e.g. BLS, recursive S… 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: github.com/ignotusnemo/frost-gkr RAGGED.md 0c0859530 # Ragged multi-instance GKR The homogeneous FROST-GKR benchmark places repeated Poseidon2b executions in one global trace. A recursive verifier presents a second batching problem: its committed hash regions need not have the same Boolean width. For regions of widths `w_a`, two direct choices lose one side of the tradeoff: - one native GKR walk per region preserves prover work but repeats the transcript and verification path; or - one aggregate walk after padding every region to `W = max_a w_a` has one transcript but materializes every region as `2^W` rows. The implementation in `crates/gkr/src/ragged.rs` gives the aggregate walk an implicit zero extension instead. In characteristic two, region `a` is embedded with ```text chi_a(x) = product over j = w_a .. W - 1 of (1 + x_j). ``` This file has been truncated. show original Complete benchmark report: github.com/ignotusnemo/frost-gkr results/2026-08-11-i7-1365u-ragged-3-sample.md 0c0859530 # Unequal-width Poseidon2b GKR benchmark Date: 2026-08-11 ## Environment - CPU: 13th Gen Intel Core i7-1365U - Logical threads used: 12 - OS: Linux 7.0.0-28-generic x86_64 - Rust: 1.96.0, LLVM 22.1.2 - Cargo profile: `release`, repository `-C target-cpu=native` - Arithmetic backend: AVX2 + VPCLMULQDQ paired `GF(2^128)` products ## Statement - Native Boolean widths: `[14, 15, 17, 16, 12, 15, 16, 12, 13]` - Native physical rows: `360448` - Max-padded physical rows: `1179648` - Padding expansion: `3.2727x` - Poseidon2b layers: `66` This file has been truncated. show original Implementation: github.com GitHub - ignotusnemo/frost-gkr at 0c08595306facd07ca9d1c1f699d51a8f9cdd7bf FROST-GKR: Frobenius Reduction Over Shifted Tables for batched Poseidon2b relations over binary tower fields. - ignotusnemo/frost-gkr 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: Exploring the Design Space for a Post-Quantum Public Key Registry for Ethereum Validators Cryptography Authors: Thomas Coratger , Tom Wambsgans , Ladislaus , Thomas Thiery , Justin Drake Credits to Benedikt Wagner and Dmitry Khovratovich for all the theoretical work, ideas, discussions and papers that have been published on eprint and that are linked in this post. As outlined in the Strawmap roadmap , securing Ethereum against the looming threat of large-scale quantum computers is a top priority. A critical milestone in this transition is migrating our proof-of-stake consensus from BLS signatures to… 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. 1 post - 1 participant Read full topic