Source binding for compact mixed openings

What a mixed opening has to prove

Parano1d commits many execution columns together and later opens all of them at one multilinear point. A Fiat–Shamir challenge γ combines the primary openings into one polynomial:

Compact FRI can establish that C is close to the required low-degree code and has the claimed value at the opening point. The complete polynomial commitment statement also has to connect C to the columns fixed by the original commitment. That connection is source binding.

The A/A′ test

The decisive adversarial test commits one set of columns A, then constructs the openings and compact FRI oracle from a different, internally consistent set A′:

commit A
derive openings, C and the FRI oracle from A′
verify against Com(A)

A verifier that checks only the claimed value and low-degree oracle can accept a coherent proof about the wrong source. Absorbing that oracle into the transcript fixes its position in the message sequence. Source binding requires an authenticated path from the sampled oracle symbols back to Com(A).

The production commitment

Every committed column contains elements of GF(2¹²⁸). The production commitment carries two authenticated views built from the same columns:

• an interleaved cap over the original column rows;
• a source cap over the rate-one-quarter additive Reed–Solomon encodings of those columns.

A source leaf contains the two encoded positions needed by the first high-variable tensor fold for every column. Its Poseidon2b hash includes a dedicated domain tag, the row logarithm, the column count, the leaf index and all symbol pairs. Merkle nodes and cap entries are full 32-byte Poseidon2b outputs.

source_leaf = Poseidon2b(
    domain, log_rows, n_cols, leaf_index,
    col_0[pos0], col_0[pos1], …, col_n[pos0], col_n[pos1]
)

The commitment therefore fixes both the execution columns and the encoded symbols that can later answer a compact opening.

From committed symbols to the FRI oracle

The prover first absorbs every claimed opening and draws γ. It then forms C from the committed columns. Compact FRI reduces the evaluation claim by folding a fixed set of high variables. The remaining table is called H.

Before any query index is drawn, the transcript absorbs H and every authenticated intermediate fold root. The verifier reconstructs the low table

and requires the Merkle root of Code(g) to equal the round-zero root of the compact FRI proof. This equality removes any independent prover-selected round-zero oracle.

One query set closes every edge

The same Fiat–Shamir indices drive both checks. At each selected position, a batched Merkle path authenticates the encoded pair for every source column. The verifier combines those pairs with the same powers of γ, applies the prescribed tensor folds and compares the result with the corresponding symbol of Code(H). Compact FRI then continues from the root already fixed by that source-bound table.

Large single-column shapes authenticate the necessary source expansion directly. Smaller shapes authenticate intermediate folded layers. These are two implementations of the same invariant: every accepted round-zero symbol descends from a symbol in the committed source cap.

The field boundary

The committed columns, additive encoding, mixed-opening batching and Poseidon2b hashing in this construction use GF(2¹²⁸). Each 32-byte hash is absorbed as two field elements, so the complete output enters the transcript. Source binding authenticates the encoded oracle used by the compact FRI proof.

The statement obtained

For the primary opening point, acceptance implies up to the stated polynomial commitment soundness error that each returned value is the multilinear extension of the column fixed by the interleaved commitment. The proof path is explicit:

Secondary claims are shape-checked and transcript-bound by the mixed-opening protocol. Their evaluation-point relation is supplied by the outer multipoint or slice reduction that invokes it.

Tests at the commitment boundary

The production tests keep the inner computation coherent while changing the object across the commitment boundary. They reject the complete A/A′ substitution, mutations of source symbols and batched Merkle paths, changes to H or an intermediate fold root, and any mismatch between Code(H · eqright) and the compact FRI round-zero root. Separate tests flip only bytes 16 through 31 of a source cap node, sibling or folded root, confirming that all 256 hash bits are checked.

Result