FROST-GKR: a global trace protocol for batched Poseidon2b

The same permutation, proved again and again

Hash-based proof systems spend much of their work proving the same permutation again and again. The inputs change, but the S-box, round constants and linear maps do not. A conventional layer-by-layer arithmetization discards that regularity: every Poseidon2b execution receives its own columns and its own chain of algebraic reductions.

For Parano1d the problem was architectural. Wallet authorization, Merkle authentication, State computation, transcripts and recursive verification all reuse Poseidon2b. If every call carries a separate algebraic circuit, the hash layer grows with the protocol graph and eventually dominates the proof that is meant to verify it.

The reference workload in the FROST-GKR paper makes that wall concrete. It contains 59 width-four Poseidon2b executions. The preserved product-chain construction needs eight constraint sumchecks for each execution, 472 in total. FROST-GKR asks a different question: can the proof describe the permutation once and make the execution number another coordinate of the data?

The answer is one global committed trace. Every execution slot, every round and every state lane becomes a coordinate of a single Boolean product domain. Two structural sumchecks leave four point-value claims, which terminal batching reduces to one claim for each committed column.

One batch, three columns

Let B be the number of live permutations and L = 2^s ≥ B the padded slot count. Poseidon2b has four state lanes and 66 nonlinear rounds. FROST-GKR reserves 128 round positions, so a trace cell is indexed by

The complete domain has n = s + 9 variables and N = 2ⁿ = 512L cells. Its committed witness contains only three multilinear columns:

• state contains the state entering each round and the terminal state row;
• s_in contains every active x^7 S-box input;
• s_out contains the corresponding S-box output.

Public selectors identify live slots, active rounds and the lanes that receive the S-box. The implementation derives the selector sigma from the fixed round schedule. It may materialize that table while computing the sumcheck, but sigma is not a fourth witness commitment. The same three witness columns therefore represent full rounds, where all four lanes are nonlinear, and partial rounds, where only lane zero is nonlinear. In Parano1d the prover commits to those columns before any relation challenge is sampled. The standalone comparison stops at the same terminal multilinear claims and checks them directly.

Why it is called FROST

FROST means Frobenius Reduction over Shifted Tables. Both halves name a load-bearing part of the construction.

Over a binary field, Frobenius squaring is linear:

The direct Poseidon2b S-box can be evaluated as x³ = x²·x and x⁷ = x⁴·x³. Squaring supplies x² and x⁴; only two general field multiplications remain. The proof keeps the direct degree-seven relation instead of decomposing every S-box into a ladder of auxiliary circuit layers.

Shifted tables solve the other hard part. A round equation reads the state at round r and the state at round r + 1. Incrementing a seven-bit round index is not an affine transformation of multilinear variables. A shifted-table evaluation therefore cannot simply be renamed as an opening of the original column at a transformed point. FROST-GKR proves that connection explicitly.

How two reductions prove the whole batch

1. One global relation

A single degree-nine zerocheck enforces every active Poseidon2b cell. It covers the x^7 relation, round constants, full and partial linear layers and adjacency between consecutive states. Sumcheck reduces that global statement one Boolean variable at a time. The number of rounds is n, so adding more permutation slots changes the protocol only through the logarithmic slot dimension.

The terminal of this reduction contains one direct evaluation of state and eleven evaluations of round-shifted or lane-projected views. Those views express exactly the wiring used by the global relation.

2. Return every view to the commitment

A second degree-two sumcheck batches the eleven derived evaluations and proves that they are the correct linear functionals of the original three columns. It returns the protocol to direct claims on state, s_in and s_out at a fresh verifier point.

After both reductions, only four point-value claims remain: two on state, one on s_in and one on s_out. Three degree-two batch-evaluation arguments then produce one terminal claim per committed column. A polynomial commitment scheme opens those same columns. The proof never replaces the committed execution trace with a prover-selected derived table.

Prove the engine once, describe the topology at its endpoints

The internal relation proves that every live slot executes Poseidon2b correctly. The state column exposes the input and output row of each slot. A separate endpoint relation says what those executions mean:

• fix an input and output for an independent hash call;
• equate one slot's output with the next slot's input for a chain;
• connect child outputs to parent inputs for a Merkle tree;
• connect absorb and squeeze states for a sponge or transcript;
• bind the endpoints to wallet authorization, State or recursive-verifier data.

The expensive permutation semantics are shared by the whole batch. Only the endpoint equations change with the application graph. This is why the same protocol can cover chains, trees and unrelated hashes without rebuilding the internal Poseidon2b proof for each topology.

The concrete gain

The publication artifact compares FROST-GKR with a preserved per-permutation product-chain construction. Both prove the same sequence of 59 Poseidon2b permutations over the same field and transcript channel. Before timing, the harness constructs and verifies both honest proofs, checks their terminal multilinear claims directly and verifies the exact algebraic transcript accounting.

Why the advantage survives larger batches

For fixed Poseidon2b width and round schedule, prover work is O(N) field operations and the committed witness contains 3N elements. The two structural reductions use 2n sumcheck rounds. Doubling the padded number of permutation slots adds one Boolean variable and two reduction rounds; it does not duplicate the protocol.

With generic terminal batching, the complete algebraic transcript contains 22n + 18 field elements before commitment openings and framing. The verifier follows the logarithmic reduction instead of replaying every round of every permutation.

What the theorem establishes

For an evaluation-binding multilinear commitment and independently sampled interactive challenges, the internal algebraic error is bounded by

For the paper's 15-variable instance over GF(2¹²⁸), this term is below 2⁻¹¹⁹ before adding the endpoint-relation and polynomial-commitment terms. The theorem proves permutation semantics, completeness, topology composition and the exact failure-event ledger for both reductions.

How Parano1d uses it

FROST-GKR originated inside the Parano1d proof system and remains its common reduction for repeated Poseidon2b computation. The production implementation uses the same three committed witness columns and derives the public selector schedule inside the prover and verifier. Transaction-body hashing, Merkle authentication, fixed-field hashes and recursive verification instantiate the reduction for their own traces and bind their application statements at the endpoints. FRI-Binius/BaseFold closes the resulting multilinear claims without a trusted setup.

The later engineering step that combines nine recursive authentication regions into one ordered walk is described in One global Poseidon walk replaces nine verifier walks.

Paper and reproducible artifact

The FROST-GKR paper contains the complete trace relation, composition theorem, completeness and interactive soundness proofs and exact transcript accounting. The standalone benchmark artifact reproduces the like-for-like 59-permutation comparison.

FROST-GKR is research by Parano1d Lab and a production component of the Parano1d proof architecture.