# 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

Claims

Arithmetization

Polynomial Commitment Protocols

Commitment Schemes

Interactive proofs

Fiat-Shamir

Non-interactive proofs.

## Arithmetization

### Pinocchio

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)$$

### Groth16

• Jens Groth (2016). "On the Size of Pairing-based Non-interactive Arguments" link

### Sonic

• Mary Maller,d Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn (2019). "Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings" link

### Stark

• Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev (2018). "Scalable, transparent, and post-quantum secure computational integrity" link

### Plonk

• Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru (2019). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge" link

• Ariel Gabizon, and Zachary J. Williamson (2020). " plookup: A simplified polynomial protocol for lookup tables" link

• Ariel Gabizon and Zachary J. Williamson (2020). "" link

• Ariel Gabizon and Zachary J. Williamson (2021). "fflonk: a Fast-Fourier inspired verifier efficient version of PlonK" link

## Polynomial Commitment

https://hackernoon.com/kzg10-ipa-fri-and-darks-analysis-of-polynomial-commitment-schemes

### KZG

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$.

https://www.cryptologie.net/article/526/maller-optimization-to-reduce-proof-size/

https://cryptologie.net/article/525/pairing-based-polynomial-commitments-and-kate-polynomial-commitments/

• Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg (2010). "Constant-Size Commitments to Polynomials and Their Applications" link

### IPA

• Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell (2017). "Bulletproofs: Short Proofs for Confidential Transactions and More" link

### FRI

• Eli Ben-Sasson, Iddo Bentov†, Yinon Horesh, and Michael Riabzev (2017). "Fast Reed-Solomon Interactive Oracle Proofs of Proximity" [link](<https://eccc.weizmann.ac.il/report/2017/134/revision/2/download/)
• Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf (2019). "DEEP-FRI: Sampling Outside the Box Improves Soundness" link https://eprint.iacr.org/2020/654

## Implementations

https://minaprotocol.com/blog/kimchi-the-latest-update-to-minas-proof-system

https://eprint.iacr.org/2016/116

https://eprint.iacr.org/2018/828

https://cryptologie.net/article/527/understanding-plonk/

https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf

Remco Bloemen
Math & Engineering
https://2π.com