This writing is a synthesized version of ‘All you wanted to know about PLONK’ by Not a Monad Tutorial. As someone without extensive experience in cryptography and calculus, this exercise was extremely insightful in learning about the underlying mathematics of ZKPs.
Zero-knowledge proofs (ZKPs) are cryptographic primitives used to prove the validity of computations without revealing sensitive information. STARKs and SNARKs are two popular ZKP protocols that allow us to transform computer programs into polynomial equations and prove their correct execution.
PLONK is an efficient and flexible cryptographic proving system within the ZK community. It relies on arithmetization, which converts logical circuits into polynomial expressions. The solutions to these equations correspond to the outputs of the circuit.
In PLONK, both the inputs and outputs of the program are considered public inputs, and the system can be used to delegate program executions to untrusted parties or as proof of knowledge. The arithmetization process in PLONK takes the circuit of a program and produces a set of polynomial equations that can be used to generate and verify proofs.
Let's say we want to prove to a verifier that we know the solution to the equation: x^2 - 5x + 6 = 0
We can use PLONK to arithmetize this equation by turning it into a circuit of logical gates and then into a set of polynomial equations.
Circuit of Logical Gates: A circuit of logical gates is a collection of logical gates wired together to perform a specific computational task. The circuit takes inputs, performs operations on those inputs using the gates, and produces outputs. Each gate in the circuit performs a specific logical operation, such as AND, OR, or NOT. The circuit's inputs and outputs can be represented as binary values (0 or 1), and the gates operate on those values to produce the desired output.
Polynomial Equations: Polynomial equations are mathematical expressions that describe a relationship between variables using only addition, subtraction, and multiplication operations. The variables in a polynomial equation can represent any value, such as integers, real numbers, or finite field elements. For example, the equation 2x^2 + 3x - 5 = 0 is a polynomial equation with one variable (x), and the solutions to this equation are the values of x that make the equation true. In circuit design, polynomial equations often describe the behavior of logical gates and other circuit components. By representing the gates as polynomial equations, circuit designers can use algebraic techniques to analyze the circuit's behavior and optimize its performance.
First, we can represent the equation as a circuit with the following gates:
The output of the final gate will be 0 if and only if x is a solution to the original equation.
Next, we can use arithmetization to turn this circuit into a set of polynomial equations. We can represent each gate in the circuit as a polynomial equation, with the inputs to the gate as the coefficients of the polynomial. For example, the polynomial equation for the subtraction gate would be:
p(x) = x * x - 5 * x - a