Product-chain baseline
Repeat the proof machinery for every permutation.
The same multiplication pattern is opened, challenged, and reduced again and again.
Constraint sumchecks472
Constraint rounds4,248
FROST · Frobenius Reduction Over Shifted Tables
One proof for the whole computation.
FROST-GKR turns a long, repetitive computation into one compact proof. Instead of proving each multiplication and hash separately, it packs the complete workload into one shared hypercube. A verifier checks the whole result through two global relations.
472 → 2constraint sumchecks
4,248 → 30constraint rounds
51.67×smaller algebraic proof
live protocol model
same Poseidon2b statement · different proof architecture
Why FROST-GKR exists
The computation is regular. Its proof should be too.
A product-chain GKR proof breaks the degree-seven S-box into small multiplications and proves them separately. Repeating that pattern across 59 Poseidon2b permutations creates 472 dependent constraint sumchecks. The transcript becomes more expensive than the hash computation it proves.
FROST-GKR
Merge the repeated structure before proving it.
All permutations share one table, one main relation, and one binding relation.
Constraint sumchecks2
Constraint rounds30
The accepted computation does not change. Both implementations prove the same 59-permutation Poseidon2b statement with the same field and Fiat–Shamir transcript. FROST-GKR changes how that statement is proved.
The protocol
Three ideas remove the repetition.
FROST-GKR keeps the native computation visible to the proof. It does not replace Poseidon2b with a different hash or hide complexity in another execution layer.
01 / UNIFY
One Boolean hypercube
Every value receives one address: permutation slot, Poseidon2b round, and state lane. All 59 sequential permutations now live in one regular table that a single sumcheck can traverse.
x = ( slot:6 | round:7 | lane:2 )
02 / PROVE
Keep the native x⁷ relation
Over the binary field GF(2¹²⁸), x⁷ uses two multiplications and two Frobenius squarings. FROST checks the complete nonlinear and linear round relation directly instead of proving an intermediate product chain.
main sumcheck · degree 9 · 15 rounds
03 / BIND
Bind every shifted view
Adjacent rounds are read through materialized shifted tables. A second, quadratic sumcheck proves that every shifted value came from the original committed witness, then reduces the protocol to three column openings.
shift sumcheck · degree 2 · 15 rounds
59 permutationsone shared table
→
2 constraint sumchecks30 rounds
→
3 openingss_in · s_out · state
Measured performance
Less proof machinery becomes real speed.
Like-for-like release measurements use the same 59-permutation statement, field, transcript, compiler profile, and machine.
Median prover time
10.50×
Baseline1,495.629 ms
→FROST142.475 ms
Median protocol-verifier time
14.87×
Baseline929.575 ms
→FROST62.501 ms
Raw algebraic proof size
51.67×
Baseline287,712 B
→FROST5,568 B
Measurement. Intel Core i7-1365U, Linux, native CPU features, three warmups and 20 alternating release-mode samples. Proof bytes count raw algebraic field elements and exclude serialization framing and final polynomial-commitment openings. The paper pins the comparison revision and benchmark harness.
Protocol at a glance
Compact because the structure is shared.
The number of constraint sumcheck invocations stays fixed at two. Their depth grows with the logarithm of the padded table size, rather than linearly with the number of permutation instances.
- Field
GF(2¹²⁸), represented in tower and flat polynomial bases.- Workload
- 59 sequential, width-four Poseidon2b permutations.
- Unified table
- 15 variables: six slot bits, seven round bits, two lane bits.
- Witness
- Three committed multilinear columns:
s_in,s_out, andstate. - Constraint proof
- One degree-nine main sumcheck and one degree-two shift sumcheck; 30 rounds total.
- Full accounting
- 75 sumcheck rounds including terminal claim batching, down from 4,263.
- Commitment layer
- Terminal MLE claims can be discharged by a transparent multilinear polynomial commitment.
FROST-GKR
Prove the relation, not its repetition.
One shared hypercube. One direct degree-seven relation. One shifted-table binding. The same computation, with the redundant proof structure removed.