Proof systems

This post is a reframing of the evolution of proof systems from the contemporary perspective of LDE polynomial commitment protocols.

While proof systems have thus far always been presented end-to-end, they often break down into two parts: an arithmetization technique and a polynomial commitment scheme. Despite being presented integral, these are mostly interchangeable and it is perfectly reasonable to for example use Plonk arithmetization on the FRI commitment protocol.

flowchart LR; pr([Claim]) subgraph Arithmetization Pinocchio Groth16 Sonic Marlin Plonk Stark end pr --> Pinocchio --> lp pr --> Groth16 --> lp pr --> Sonic --> lp pr --> Marlin --> lp pr --> Plonk --> lp pr --> Stark --> lp lp([Polynomial\ncommitment\nprotocol]) subgraph "Scheme" KZG IPA FRI DARK end lp --> KZG --> fs lp --> IPA --> fs lp --> FRI --> fs lp --> DARK --> fs fs[Fiat-Shamir] --> nip([Proof])

The choice of Polynomial Commitment scheme determines the field $\F$ that is used in the arithmetization layer. While it is possible to use math outside of $\F$ in the claim, this requires costly emulation using $\F$-math. Much research has been devoted to making this emulation more efficient.

Basic Architecture



Polynomial Commitment Protocols

Commitment Schemes

Interactive proofs


Non-interactive proofs.



This is the system used by Circom, Zorkates, Groth16 and most Ethereum projects that do not develop their own proof system.

The computation is first reduced to an algebraic circuit of basic operations over a field. The circuit is represented by a triplet of matrices $(A, B, C) ∈ \F^{n × m}$ such that a valid witness $\vec s ∈ \F^n$ satisfies.

$n$ is the number of variables in the system, $m$ is the number of gate relationships.

$$ \vec s ⋅ A \circ \vec s ⋅ B - \vec s ⋅ C = 0 $$

We pick a basis $\vec x ∈ \F^m$ and compute $3⋅n + 1$ polynomials $A_i, B_i, C_i, Z ∈ \F[X_{<m}]$ such that

$$ \begin{aligned} A_i(x_j) &= A_{ij} & B_i(x_j) &= B_{ij} & C_i(x_j) &= C_{ij} & Z(x_i) &= 0 \end{aligned} $$

Given a witness $\vec s$, we then compute $A, B, C ∈ \F[X_{<m}]$ such that

$$ \begin{aligned} A(X) &= \sum_i s_i ⋅A_i(X) & B(X) &= \sum_i s_i ⋅B_i(X) & C(X) &= \sum_i s_i ⋅C_i(X) \end{aligned} $$

The circuit is satisfied iff there exists a $H ∈ \F[X_{<m}]$ such that

$$ A(X) ⋅ B(X) - C(X) = H(X) ⋅ Z(X) $$





Polynomial Commitment


We want to proof

$$ \forall_i F(x_i) = 0 $$

on some domain $\vec x ∈ \F^n$. We construct the unique $Z(X) ∈ \F[X_{<n}]$ such that $Z(x_i) = 0$.

$$ F(X) = 0 $$

Pick a random $z ∈ \F$.





Remco Bloemen
Math & Engineering