FROST-GKR: a global trace protocol for batched Poseidon2b

The repeated-permutation problem

Hash-based proof systems execute the same cryptographic permutation many times. The inputs change; the round constants, nonlinear layer and linear maps do not. A conventional layer-by-layer arithmetization often throws away that regularity. Each permutation gets its own columns and its own sequence of reductions, even when fifty-nine instances perform exactly the same sixty-six-round computation.

Poseidon2b is the binary-field cryptographic permutation studied here. It transforms a four-word state through sixty-six fixed rounds and is reused for hashing throughout the ParanO(1)d proof stack.

The Goldwasser–Kalai–Rothblum (GKR) method supplies the multilinear-extension and sumcheck machinery used to reduce a large computation to a small set of verifier-selected evaluations.

FROST-GKR starts from a different object. It assigns one slot to each independent Poseidon2b execution, then places the complete batch on one Boolean product domain whose other coordinates are the round and state lane. The protocol does not descend through separate circuit layers. It commits to a global execution trace and reduces relations over that trace to openings of the same committed columns.

Three committed columns

For B live Poseidon2b executions, let L = 2^s be the padded slot count. Poseidon2b has width four and sixty-six nonlinear rounds. FROST reserves 128 round positions and uses four lane positions, so the complete table has:

The witness has only three multilinear columns:

• z contains the state entering a round and the final state row;
• s_in contains an active S-box input; the S-box is the permutation's nonlinear substitution map;
• s_out contains the corresponding S-box output.

All three columns are committed before the verifier samples a relation challenge. Public selectors identify live slots, live rounds and active S-box lanes. The degree-seven map is evaluated directly over GF(2¹²⁸): Frobenius squaring makes x² and x⁴ linear operations, while x³ and x⁷ require two general multiplications. This is an implementation advantage; the formal sumcheck degree remains seven.

Two constraint reductions

The protocol has two algebraic jobs. First it must prove every local Poseidon2b round equation. Then it must prove that materialized next-round and lane-projected views are actually derived from the original commitment.

A zero-check asks whether a polynomial relation vanishes at every point of the encoded execution domain. The sumcheck protocol reduces that global statement, one Boolean variable at a time, to a small set of evaluations at verifier-chosen points. A polynomial commitment scheme (PCS) then binds those final evaluations to the trace columns fixed before the challenges were sampled.

The global relation

One degree-nine zero-check enforces the S-box, round constants, full and partial linear layers, and adjacency for every live slot. For a slot padded batch, the main sumcheck has n rounds regardless of the number of live permutations except through the logarithmic slot dimension.

The terminal contains one direct evaluation of Z and eleven evaluations of shifted or lane-projected views. Those eleven claims cannot simply be relabelled as openings of S_in, S_out and Z: incrementing a binary round index is not an affine transformation of the multilinear variables.

The shifted-view reduction

A second, degree-two sumcheck batches the eleven linear functionals and reduces them to direct evaluations of the three committed polynomials at a fresh point. The resulting opening interface is small and explicit: two point claims on Z, one on S_in and one on S_out. A polynomial commitment with native multipoint openings may handle them directly; the paper also describes a generic three-column terminal batching layer.

What the protocol proves

The internal relation certifies that every live slot is a correct Poseidon2b execution. An application still has to constrain the exposed input and output rows. It may fix a public input, equate one slot output with the next slot input, or bind the final output to a public digest. These endpoint equations use the same committed state column, so sequential chains, trees and sponge constructions compose without repeating the internal permutation relation.

FROST-GKR is the algebraic reduction layer, parameterized by an evaluation-binding multilinear polynomial commitment. A complete argument combines its internal reduction with the application's endpoint relation and the selected PCS; the soundness accounting keeps those three terms separate.

Soundness and exact accounting

For a trace with n variables, the interactive algebraic error of the internal reductions is bounded by:

At the evaluated instance, n = 15 and F = GF(2¹²⁸), so the term is below 2⁻¹¹⁹ before adding endpoint-relation and polynomial-commitment soundness. The generic transcript uses 22n + 18 field elements when full round-polynomial coefficient vectors are transmitted.

The 59-permutation measurement

The publication artifact compares FROST-GKR with a product-chain baseline that runs a separate sequence of algebraic reductions for every permutation. Both prove the same batch of fifty-nine width-four Poseidon2b permutations. Before timing, the harness constructs honest proofs, verifies both protocols, checks the final multilinear-extension (MLE) claims directly and accounts for every field element in the algebraic proof.

The paper reports a clean publication rerun with a 1,605.931 ms legacy median and a 150.218 ms FROST median. The preserved repository result records a separate twenty-sample run on an Intel Core i7-1365U: 1,495.629 ms and 142.475 ms respectively. Both measure the reduction layer, not a complete succinct argument.

Publication and artifact

FROST-GKR is research by O(1) Lab. The paper is authored by Andrew Boyle and includes the complete trace relation, composition theorem, completeness and interactive soundness arguments, exact transcript accounting and the reference comparison.

Read the full paper (PDF) or inspect the reproducible benchmark artifact.