Plonkish Arithmetization
This is a key component of the PLONK protocol, before diving in, let's explore the term "arithmetization" in the context of Zero Knowledge;
Arithmetization is the process of converting computational statements into mathematical equations, specifically polynomial equations, that can be efficiently proven and verified. It's like translating a computer program into a mathematical language that zero-knowledge proofs can understand.
Here is the basic building blocks of the concept of Arithmetization;
Variables: Represent values in computation
Constraints: Mathematical relationships between variables
Polynomials: Used to encode relationships and checks
Fields: Mathematical structures where computation occurs
Over the years many forms of Arithmetization have been laid out, let's explore a few;
Rank-1 Constrant System (R1CS)
Used in protocols like Groth16
Represents computation as:
Where:
are matrices
is the witness vector
represents element-wise multiplication
Plonkish Arithmetization
Used in PLONK and its variants
Gate format:
Where:
are witness values
are selector polynomials, indicating the gate operations
Algebraic Intermediate Representation
Used in STARKs
Represents computation as polynomial constraints over execution trace
Constraints form:
Common Steps in Arithmetization
Step 1: Statement → Circuit
Convert computation into logical/arithmetic circuit
Identify inputs, outputs, and intermediate values
Step 2: Circuit → Constraints
Transform circuit gates into mathematical constraints
Ensure constraints capture computational logic
Step 3: Constraints → Polynomials
Convert constraints into polynomial equations
Ensure polynomial degrees are manageable
Step 4: Optimization
Reduce the number of constraints
Minimize polynomial degrees
Optimize for proof size/verification time
Back to PLONK Arithmetization
Say we are given this computation;
it circuit execution trace would be as follows;
when the circuit is being executed all these variables would be taking a concrete value, forming the execution trace table with which proof would be generated;
This is how the circuit would look like when , , , and .
2
3
6
4
5
9
6
9
54
Using this execution trace, we can now introduce the constraint gate, encoding the gate operation and ensuring correct execution. This would introduce the vanilla PLONK gate equation.
where the and are the left, right, and output wires of the gate.
To say , we let and equal , while equals . The other coefficients wouldn't be used, so we set and to .
To say , we set equal to , set equal , and set the rest of the coefficients to .
To bind a variable to a public value, we let equal to , equal to 1, and equal to the public value.
so for the 3 gates we are working with the gate equations would look like this;
gate 1: ; this equation holds.
gate 2: ; this equation holds.
gate 3: ; this equation holds.
the next is to collect all these vectors so we can build just one relationship with which the protocol can progress;
Next up is to interpolate these vectors to obtain a polynomial, the nature of this interpolation is unique, and this interpolation would be done on the Domain
of the roots of unity. But our example would encounter a problem seeing that the size of the vector is which is not a power of which is needed to manipulate/obtain a multiplicative sub-group over the Domain
root of unity which would be useful in the protocol as we progress. To solve our little problem would extend the vectors Zero
before carrying out the interpolation over the root of unity when is 4;
These are the resulting vectors after the extension;
Using this technique, we can successfully prove and verify this circuit execution trace with the help of these 8 polynomials no matter how big the circuit is (Number of constraints).
But that is one more thing! we have only been able to mathematically prove that these gates are present in a circuit but we have not established how these gates are wired to other gates and signals in the circuit. This introduces us to the term "Copy Constraints".
Copy Constraints
Copy constraints are a fundamental mechanism in the PLONK protocol that ensure certain wire values are equal across different parts of a circuit. They solve the critical problem of enforcing value consistency without revealing the actual values.
Key Characteristics:
Verify that specific wire values are identical
Maintain zero-knowledge properties
Efficiently check value equality across circuit
We need to check that the wire vaules are copied correctly, this can be checked by making use of the permutation argument Bayer, Groth12.
Looking into this slide;
permutationNow we've got a good understanding of how permutation check is designed, let's explore it connected to the PLONK protocol;
The best method for explaining this concept I found was documented by the Lambdaclass team, I would be explaining this PLONKISH wire relationship using this concept also. We would be representing the circuit structure and the witnesses in the form of a matrix.
Introducing the matrix;
0
0
1
-1
0
1
1
0
-1
0
1
0
1
-1
0
0
0
0
-1
0
The Matix The claim in the previous section is not an "if and only if" statement because the following trace columns do satisfy the equations but do not correspond to a valid execution:
2
3
6
4
5
9
6
9
54
The matrix encodes the carry of the results from one gate to the right or left operand of a subsequent one. These are called wirings. Like the matrix, it's independent of the individual evaluation. It consists of indices for all input and intermediate variables. In this case, that matrix is:
1
2
0
4
5
3
0
3
6
Here is the index of , is the index of , is the index of , is the index of , is the index of , is the index of , and is the index of the output . Now we can update the claim to have an "if and only if" statement.
New PLONK Claim: Let be a matrix with columns , , . It corresponds to a proper evaluation of the circuit if and only if;
for all the following equality holds
for all such that we have , this is what is referred to as the copy constraint. Would dive in deeper as we proceed.
With this we can successfully encode the circuit execution and enforce its wiring, just what we need for the PLONK protocol.
In Zero Knowledge proof protocols, we almost always operate on polynomials and we would like to do the same here, we need to convert these Claim
equations to polynomials.
Starting with Claim 1;
for all the following equality holds Let be a primitive root of unity and let . Let be the polynomials of degree at most that interpolate the columns at the domain . This means for example that for all , and similarly for all the other columns.
With this, Claim
can be expressed as follows;
for all in domain . Interestingly, in the world of polynomials, this is also equivalent to; , where .
Transforming Claim 2; To perform this transformation, recall our discussion on the Permutation check. A permutation is a rearrangement of a set, usually denoted . For finite sets, it is a map from a set to itself that takes all values. In our case, the set will be the set of all pairs;
such that , and
The matrix induces a permutation of this set where is equal to the indices of the next occurrence of the value at position . If you are already at the last occurrence, go to the first one. By next, we mean the following occurrence, as if the columns were stacked on each other. Let's see how this works in the example circuit. Recall is;
1
2
0
4
5
3
0
3
6
The permutation expression for this case can be represented as such;
It can be easily observed Check
2 can be expressed as follows; for all ;
This mathematically implies that set and are equal given that;
This is great, but the problem we had initially was that we would like to represent Check
2 problem as a Polynomial Identity Representation (PIR) which would be more convenient for this protocol, the solution to this problem would introduce the concept of Equality of Sets.
First, explore this, a deep dive into multiset equality check, this would give a very good overview of this concept before diving into what this has to do with our polynomial identity problem.
Equality of sets
Problem: How to check if two sets and of field elements are equal?
Naive Attempt: Multiplication
You might think to multiply all elements of A and B , then compare the results:
.
If they match, and might be equal. However, this test fails in some cases. For instance:
and both yield as the product, but clearly .
Better Approach: Polynomials
Instead of comparing products, we use polynomial roots to represent the sets. For , construct the polynomial:
.
Do the same for :
.
These polynomials encode the sets $A$ and $B$ . The sets $A$ and $B$ are equal if and only if:
= ,
which holds because of the unique factorization theorem in polynomial algebra.
Checking Equality Efficiently
Instead of comparing the polynomials symbolically, we use a random evaluation strategy. Pick a random field element and evaluate:
.
If = , then with high probability, .
This relies on the Schwartz-Zippel Lemma, which states that if two distinct polynomials are evaluated at a random point, the chance of them being equal is very small.
Generalization: Using Roots of Unity
When the sets and are large, we can optimize further using a special domain based on the roots of unity. Define:
• : A primitive root of unity.
• : The evaluation points.
For , construct the polynomial that interpolates the values:
at points in . Similarly, construct for . The sets and are equal if:
.
Polynomial
To simplify, introduce a polynomial that relates and :
,
with . By evaluating recursively at , we conclude if:
.
Note: if you find $g(X)Z(\omega X)$ confusing, explore this
This method scales efficiently and leverages the structure of polynomials and roots of unity for large sets.
The next thing to do now is to extend this expression in that is would not just accommodate an equality check for two sets of field elements but rather to a set of tuples of field elements, with this we get much closer to the Plonkish permutation argument.
Lemma:
Let and be sets of pairs of field elements, where each and similarly for . We aim to determine whether and are equal using polynomial techniques.
Mapping Tuples to Field Elements:
Let be random field elements. Each pair in A is mapped to a single field element: , and similarly for .
Interpolating Polynomials:
Define , where is a root of unity. Construct polynomials and that interpolate the values: , and , respectively, over the evaluation points in .
Equality Verification:
To verify that and are equal, we check for the existence of a polynomial satisfying: , and , for all .
If such a polynomial exists, then with overwhelming probability, the sets and are equal. This probability is high due to the randomness of and and the properties of polynomials over finite fields.
With this, we are set to applying this to the PLONK problem
Recall the permutation check problem we had initially, set and are equal given that;
We cannot apply this principle we just explored yet because it was defined to work on field elements and an extension of a tuple of field elements but what we've got now are tuple indexes. The next subsections would do justice to this!
Mapping Indexed Sets to Field Elements and Verifying Equality
Recall that we aim to rephrase Check
2 in terms of polynomials. Specifically, Check
2 is equivalent to the equality of two sets and , defined as:
, .
Mapping Indexed Pairs to Field Elements
The sets and are not directly composed of field elements or pairs of field elements; instead, their elements include an index pair and a field element . To leverage the results from the previous section, we need to convert these sets into pairs of field elements.
Mapping Strategy
For each element , we leave as it is and map the index to a field element such that different index pairs map to distinct field elements. Let be a primitive root of unity. Define:
.
Thus, we map to the pair , which is a pair of field elements.
Constructing the New Sets
Using this mapping, the sets and become:
,
.
Check
2 is equivalent to the equality of these sets and .
Equality Verification via Polynomials
We now apply the polynomial-based method from the previous section to verify the equality of and .
Polynomials for Interpolation
Let be a root of unity, be random field elements, and . Define and as the polynomials interpolating the following values at :
,
.
Verifying Equality
If there exists a polynomial $Z(X)$ such that:
,
,
then the sets and are equal with overwhelming probability.
Additional Definitions for the Protocol
Let = be a primitive root of unity and . Define as the interpolations at of the sets of values:
,
,
.
Before concluding this session, it is necessary to clearly define the structure CommonPreprocessedInput
, this would be essential in the proof generation phase of this protocol.
CommonPreprocessedInput { , , , , , , , , , , }
With these, PLONKish arithmetization is complete.
references:
https://research.metastate.dev/plonk-by-hand-part-1
https://www.youtube.com/watch?v=-SXMd6S0r0I
https://blog.lambdaclass.com/all-you-wanted-to-know-about-plonk/
(these resources are life savers)
Last updated