PIOP Protocol

A polynomial interactive oracle proof, or PIOP, is the part of a proof system that turns "this table satisfies these rules" into a few questions about polynomials at random points. Hekate's PIOP is built from sumcheck. One sumcheck per table checks every constraint, pinned cell and bus row at once, a second ties the values every table leaves to the committed tables, and the Brakedown commitment answers the last question with a few opened columns. This page follows one table's claims from the first sumcheck to the opening.

§ Three parts of a proof

A proof system of this kind has three parts: the PIOP decides what to ask, a polynomial commitment answers, and Fiat-Shamir supplies the randomness.

In a PIOP the prover sends polynomials, and the verifier may ask for the value of any of them at any point. The verifier never reads a polynomial in full. It asks for a few values at points it picks at random, and the protocol is sound when a false statement fails those checks except with negligible probability.

A polynomial commitment makes the asking real. The prover commits to every table under one 32-byte Merkle root before the questions about them, and later opens values with a proof the verifier checks against the root. Fiat-Shamir removes the conversation: each random point is a hash of the transcript up to that point, which the verifier recomputes from the proof bytes.

The commitment is hash-based, and nothing in the system needs a trusted setup.

The rest of this page follows the figure from top to bottom. The tables take the first sumcheck one after another, the chiplets first and the main table last, and the rest together.

§ A column is a polynomial

A column of $2^n$ rows is a function of $n$ bits, the bits of the row number, and it has exactly one multilinear extension: the polynomial of degree at most 1 in each variable that agrees with the column on every row.

The extension is a weighted sum of the rows. At a point $r$, row $x$ gets the weight $\mathrm{eq}(r, x)$:

$$\tilde f(r) = \sum_{x \in \{0,1\}^n} \mathrm{eq}(r, x)\, f(x), \qquad \mathrm{eq}(r, x) = \prod_{i} \big( r_i x_i + (1 - r_i)(1 - x_i) \big)$$

On a row $y$ of the table, $\mathrm{eq}(y, x)$ is 1 for $x = y$ and 0 for every other row, which is why the extension agrees with the column there. Off the rows, every row contributes. Four values in ordinary integers, at the point (2, 3):

The weights add up to 1 at every point. Hekate does the same arithmetic in GF(2^128), where $1 - r$ is $1 + r$, and a random point has coordinates anywhere in a field of $2^{128}$ elements.

Two different columns have different extensions, and two different multilinear polynomials in $n$ variables agree at a random point with probability at most $n/2^{128}$, by the Schwartz-Zippel lemma. One value at a random point stands for the whole column, and each step below trades a claim about every row for a claim about such values.

§ Sumcheck

Sumcheck reduces a claim about a sum over every row to a claim about one value at a random point, in one round per bit of the row number.

In each round the prover sends a polynomial in one variable, the verifier checks that its values at 0 and 1 add up to the current claim, and it draws a random value for that variable. After $n$ rounds the claim is the value of the summed polynomial at one random point. A false claim survives a round only if the random value lands on one of the at most $d$ points where two different polynomials of degree $d$ agree: probability $d/2^{128}$ or less. Prover Engine works through two rounds by hand, and its table of 3, 5, 2 and 6 ends at the 16 computed above.

§ One sumcheck per table

Each table proves all its rules with one sumcheck: every constraint, pinned cell and bus endpoint enters a single sum, scaled by its own power of a random $\alpha$.

• Constraints. "Every constraint is zero on every row" becomes $\sum_x \mathrm{eq}(\tau, x)\, C(x) = 0$ for a random point $\tau$. The sum is the extension of the constraint's values at $\tau$, and it is zero for every $\tau$ only when every value is zero. This term is called ZeroCheck.
• Pinned cells. A boundary or a published cell, column $c$ equal to $v$ on row $k$, becomes $\sum_x \mathrm{eq}(k, x)\,(c(x) - v)$, which equals $c(k) - v$ and must be zero. The weight $\mathrm{eq}(k, x)$ is 1 on row $k$ and 0 on every other row.
• Bus rows. Every bus endpoint on the table adds a helper column $h$ with $h \cdot (\gamma + \mathit{key}) = s$ on every row, a ZeroCheck term like the constraints.
• Bus sums. The same endpoint adds $\sum_x h(x)$, its share of the bus, which is the one term expected to be nonzero. A lookup bus weights each row by $\mathrm{eq}(r_{\text{bus}}, x)$, which binds its two sides row by row.

The sum starts from the bus sums the prover claims, combined with their powers of $\alpha$, and the transcript absorbs those claims before $\alpha$ is drawn. Every other term adds up to zero in an honest proof. Batching is sound because $\alpha$ comes after every term is fixed by the commitment: a random combination of values that are not all zero is nonzero except with a probability of about the number of terms divided by $2^{128}$. LogUp Buses explains the helper column and where the bus sums go.

The round polynomials have the degree of the heaviest term: the heaviest constraint plus one for the $\mathrm{eq}$ factor, and at least 3 on a table with a bus, where $h \cdot \mathit{key} \cdot \mathrm{eq}$ multiplies three factors. The verifier knows that degree from the program and rejects a round polynomial of any other length.

§ The check at one point

After the last round, the claim is the value of the summed polynomial at one random point $r_{\text{final}}$, and the verifier computes that value itself from the values of the columns there.

The prover claims the value of every column at $r_{\text{final}}$, on this row and on the next, and of every helper column $h$. The verifier evaluates every constraint on those claims and computes the rest of the terms on its own:

• $\mathrm{eq}(\tau, r_{\text{final}})$, and $\mathrm{eq}(k, r_{\text{final}})$ for each pinned cell, as products of $n$ factors.
• Each fixed column, from its shape. A fixed column is a function of the row number that the program declares, and the verifier evaluates the shape's extension directly; a claimed value that differs rejects the proof.
• Each clock on a bus, from the row number or from the count of messages before it.

When the result differs from the claim the last round left, the proof is rejected. What remains are the column claims, and the next two steps prove them.

§ The next row is a weight

A constraint that reads the next row needs the next row's value at $r_{\text{final}}$, and Hekate proves it from the same committed column under a shifted weight.

The next-row column holds row $x + 1$ in row $x$, and the row after the last is row 0. Its extension gives each row the weight its predecessor had: $\sum_x c(x)\, \mathrm{eq}(r, x - 1)$, where row 0 takes the weight of the last row.

No second column is committed. The verifier computes the shifted weight's extension in time linear in $n$, and the next-row claim goes to the same commitment as the others. The wrap is why a transition constraint on the last row reads row 0, and why a selector switches it off there, as AIR Constraints shows.

§ Many claims, one point

A second sumcheck, the evaluation argument, turns the column claims of every table into claims about the committed data at one new point.

The transcript absorbs the claimed values of every table, and only then does the verifier draw $\eta$. The claims combine into one sum over the committed columns: each value scaled by a power of $\eta$ and weighted by its point, $\mathrm{eq}$ for this row and the shifted weight for the next. The sumcheck has degree 2 and ends at a new random point $r'$, where the claim is about the committed data itself.

Columns declared as packed bits take one more reduction. Keccak's 1600 state bits, for example, are committed as 25 columns of 64 bits, while its constraints, and the claims, are about single bits. Ring switching, a reduction by Diamond and Posen, connects the two. Asking the packed column for its value at a point would not do: one packed value mixes its bits, and the separate claims cannot be recovered from it. Instead, the claimed values of a column's bits, written out in binary, form a matrix of bits. The verifier reads that matrix along its other axis, folds it with fresh randomness, and obtains a claim about the packed column. The evaluation sumcheck carries that claim with the rest, and at $r'$ each table sends values of the committed data: one for the columns committed whole and one for the columns packed from bits, if it has any. When there are several, a random $\lambda$ folds them into one claim for the opening. Zero-Knowledge Ring-Switching without the Transpose treats the reduction in full.

§ Opening the commitment

Brakedown answers the last claim with a vector and a few opened columns.

The committed tables form one grid of values, and the commitment is a Merkle tree over the columns of its Reed-Solomon encoding, as Prover Engine draws it. To answer at $r'$, the prover sends $q$: the grid's rows combined with weights from one part of $r'$. The verifier checks $q$ two ways.

1. $q$ combined with weights from the rest of $r'$ must give the claimed value.
2. At random column positions, the prover opens the encoded grid with one Merkle multiproof. Each opened column, combined with the same row weights as $q$, must equal the encoding of $q$ at that position.

A $q$ that does not come from the committed grid disagrees with the code at a large share of positions, and every opened column is another chance to catch it. The helper columns of the tables with a bus open at the same positions.

§ Where soundness comes from

Each reduction can let a false claim through with a small probability, and the proof's soundness is set by the weakest of them.

Two kinds of terms add up:

• Random points. A false claim survives a random point with a probability of the degree, or the size of the object, divided by $2^{128}$: each sumcheck round, the batching with $\alpha$ and $\eta$, ZeroCheck's $\tau$, and the bus challenge $\gamma$, which must not make any denominator zero on any row of any bus. Opening more columns does not shrink these terms, and none reaches 128 bits: each loses the logarithm of its degree or size.
• Opened columns. Each opened column catches a false $q$ with a fixed probability that depends on the code, and this term grows with the number of columns opened.

The probabilities add, and a sum of small powers of two is close to the largest of them: the bits of the whole proof are about the minimum over the terms. Config::prod() targets 100 bits, and the verifier rejects a commitment geometry estimated below that floor. The estimate that chose its own geometry tells how Hekate's own accounting was corrected to follow published theorems.

§ Zero knowledge

With zero knowledge on, the default, the PIOP runs on masked values. Every round polynomial, column claim and bus sum carries a one-time pad, and the verifier replays the reductions on the masked numbers. Each table's sum also gains a random column minus its next row, which adds zero over the rows. Each final check becomes rows of an outer statement, which a zk-Ligero argument proves at the end, and in that mode the outer argument also settles the bus sums. Zero Knowledge specifies the pads, the outer statement and the zk-Ligero argument.

§ Next steps

• Prover Engine: the prover's four steps, with sumcheck worked by hand.
• LogUp Buses: the bus terms in a table's sum, and how a bus connects two tables.
• Verifier Logic: run the verifier, one proof or a batch.
• Zero Knowledge: the pads, the outer statement and the zk-Ligero argument.
• Zero-Knowledge Ring-Switching without the Transpose: ring switching under one-time pads.