STARK Protocol

Polynomial Constraint System Architecture

Following arithmetization, the computation is represented through a structured polynomial system.

Core Components

  • ​Execution Trace Polynomials

    Encode state transitions across computation steps as: \[ T_i(x) = \sum_{k=0}^{N-1} t_{i,k} \cdot L_k(x),\] where \(L_k(x)\) are Lagrange basis polynomials over domain H. ​

  • Constraint Polynomials Encode verification conditions as algebraic relations: \[C_j(x) = R_j(T_1(x),T_2(x), \cdots, T_m(x), T_1(g \cdot x), T_2(g \cdot x), \cdots, T_m(g \cdot x)) = 0,\] for all \(x \in H\), where \(g\) is the generator of H.

Constraint Aggregation

For proof efficiency, we combine constraints using: \[C_{comb}(x) = \sum_j \alpha_j C_j(x),\] where \( \alpha_j\) are derived through the Fiat-Shamir transformation.

Mixed Matrix Commitment Scheme (MMCS)

Polynomial Commitments in STARK

STARK uses Merkle trees for polynomial commitments:

  • Setup: No trusted setup is needed, but a hash function for Merkle tree construction must be predefined. We use Poseidon2 as the predefined hash function.

  • Commit: Evaluate polynomials at all roots of unity in its domain, construct a Merkle tree with these values as leaves, and publish the root as the commitment.

  • Open: The verifier selects a random challenge point, and the prover provides the value and Merkle path for verification.

Batch Commitment Protocol

The "Mixed Matrix Commitment Scheme" (MMCS) is a generalization of a vector commitment scheme used in zkMIPS. It supports:

  • Committing to matrices.
  • Opening rows.
  • Batch operations - committing to multiple matrices simultaneously, even when they differ in dimensions.

When opening a particular row index:

  • For matrices with maximum height: use the full row index.
  • For smaller matrices: truncate least-significant bits of the index.

These semantics are particularly useful in the FRI protocol.

Low-Degree Extension (LDE)

Suppose the trace polynomials are initially of length \(N\). For security, we evaluate them on a larger domain (e.g., \(2^k \cdot N\)), called the LDE domain.

Using Lagrange interpolation:

  • Compute polynomial coefficients.
  • Extend evaluations to the larger domain,

zkMIPS implements this via Radix2DitParallel - a parallel FFT algorithm that divides butterfly network layers into two halves.

Low-Degree Enforcement

Quotient Polynomial Construction

To prove \(C_{comb}(x)\) vanishes over subset \(H\), construct quotient polynomial \(Q(x)\): \[Q(x) = \frac{C_{comb}(x)} {Z_{H}(x)} = \frac{\sum_j \alpha_j C_j(x)}{\prod_{h \in H}(x-h)}.\]

The existence of such a low-degree \(Q(x)\) proves \(C_{comb}(x)\) vanishes over \(H\).

FRI Protocol

The Fast Reed-Solomon Interactive Oracle Proof (FRI) protocol proves the low-degree of \(P(x)\). zkMIPS optimizes FRI by leveraging:

  • Algebraic structure of quartic extension \(\mathbb{F}_{p^4}\).
  • KoalaBear prime field \(p = 2^{31} - 2^{24} + 1\).
  • Efficient Poseidon2 hash computation.

Three-Phase FRI Procedure

  • Commitment Phase:

    • The prover splits \(P(x)\) into two lower-degree polynomials \(P_0(x)\), \(P_1(x)\), such that: \(P(x) = P_0(x^2) + x \cdot P_1(x^2)\).

    • The verifier sends a random challenge \(\alpha \in \mathbb{F}_{p^4}\)

    • The prover computes a new polynomial: \(P'(x) = P_0(x) + \alpha \cdot P_1(x)\), and sends the commitment of the polynomials to the verifier.

  • ​Recursive Reduction:

    • Repeat splitting process for \(P'(x)\).
    • Halve degree each iteration until constant term or degree ≤ d.

  • ​Verification Phase:

    • Verifier checks consistency between committed values at random point \(z\) in initial subgroup.

Verifing

Verification contents

To ensure the correctness of the folding process in a FRI-based proof system, the verifier performs checks over multiple rounds using randomly chosen points from the evaluation domain. In each round, the verifier essentially re-executes a step of the folding process and verifies that the values provided by the prover are consistent with the committed Merkle root. The detailed interaction for a single round is as follows:

  1. The verifier randomly selects a point \(t \in \Omega\).
  2. The prover returns the evaluation \(p(t)\) along with the corresponding Merkle proof to verify its inclusion in the committed polynomial.

Then, for each folding round \(i = 1\) to \(\log d\) (d: polynomial degree):

  1. The verifier updates the query point using the rule \(t \leftarrow t^2\), simulating the recursive domain reduction of FRI.

  2. The prover returns the folded evaluation \(P_{\text{fold}}(t)\) and the corresponding Merkle path.

  3. The verifier checks whether the folding constraint holds: \(P_{\text{fold}}(t) = P_e(t) + t \cdot P_o(t)\), where \(P_e(t)\) and \(P_o(t)\) are the even and odd parts of the polynomial at the given layer.

  4. This phase will end until a predefined threshold or the polynomial is reduced to a constant.

Grinding Factor & Repeating Factor

Given the probabilistic nature of STARK verification, the protocol prevents brute-force attacks by requiring either:

  • A Proof of Work (PoW) accompanying each proof, or
  • multiple verification rounds.

This approach significantly increases the computational cost of malicious attempts. In zkMIPS, we employ multiple verification rounds to achieve the desired security level.