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.
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)
-
Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova (2013). "Pinocchio: Nearly Practical Verifiable Computation" link
-
http://www.zeroknowledgeblog.com/index.php/the-pinocchio-protocol
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/
- 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
DARK
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
