Zero-Knowledge Proof for Privacy over Ethereum: Permutations over Lagrange-Bases for Oecumenical Non-Interactive Arguments of Knowledge (PLONK) [step-by-step] (Part 1)
This blog mainly deals with the step-wise implementation of the PLONK proving scheme for a zk-SNARK (zero knowledge — Succinct Non-Interactive Argument of Knowledge) proof-system. The steps mainly cover topics of Elliptic Curve Cryptography and Abstract Algebra.
Introduction
PLONK is a SNARK (Succinct Non-Interactive Argument of Knowledge) that can verify a computation done by an arithmetic circuit, meaning we might have a circuit C that on input x outputs C (x) = y, and a PLONK proof (generated by the prover) will convince another party (the verifier) that the prover knows x such that C (x) evaluates to y.
Setup
PLONK is a recent zk-SNARK construction that can do much more than older SNARKs. One noteworthy feature of SNARKs is that during the setup, everytime during initialization the SNARK needs to be assigned with new random bits to the Prover. However, PLONK, here is an exception, that is in PLONKs the strings created in a trusted setup can be re-used for any other PLONK circuit of the same size (or less) than original.
But before understanding all of this, we need to understand a simple mathematical concept called Polynomial Commitment Schemes (PCCs). They are sort of tools that are used by cryptographers to load a large amount of information (execution traces of arithmetic circuits) into a single point on the Elliptic Curve (a single number).
In the world of Web3, the verifier is a blockchain. The succinctness of these proofs (keeping the data that needs to be sent to the verifier as small as possible) is very important on blockchains, as data storage and transactions on the blockchain can get very expensive.
Parameters
PLONK requires a Polynomial Commitment Scheme, and here we will use the Kate Commitment scheme (don’t worry about the name). Kate Commitment Scheme requires an Elliptic Curve on which we can compute the Elliptic Curve Pairing. Usually we go for BN-254 (just another generic name for an Elliptic Curve).
An Elliptic Curve is an equation of the form
Any (x, y) pairs satisfying the equation are points on the curve. We will use an elliptic curve over the field F101 prime field, which makes hand computation easy.
This field will allow us to make a lot of handy calculations and assumptions such as :
And so on…
The elliptic curve y² = x³ + 3 is a commonly-used elliptic curve equation, and (1,2) is an easy to find on this curve, hence, we can start our math with this point, i.e, use this as a Generator. In fact, the alt_bn128 curve that is implemented in Ethereum Mainnet uses this same curve equation and generator, but over a large prime field.
Points on the Elliptic Curve form a Group meaning two points can be added in some way to get a point on the curve. We can double a point by adding it to itself, or invert a point to find its additive items. Here is how we derive the following coordinates using the elliptic curve equation that we earlier declared:
It’s preferred that we have a table of multiples of this generator to save some work later on. Taking the generator G1 = (1, 2) and applying the doubling formula gives us 2G1, then the inversion gives us -2G1. We can double it again and then invert it to get 4G1 and — 4G1, and so on. As we are still dealing with the prime field F101. After a few doubles and inversions we’ll be able to see that the subgroup generated by (1, 2) has order 17.
In this way if we keep computing for 4, 8, 16 and so on. We find that the order of the subgroup of (1, 2) is 17.
Hence:
Hence, the order of the subgroup (1, 2) is 17.
Preparing of Elliptic Curve Pairings
Now that we have a suitable elliptic curve subgroup, we will need to do some further work to enable us to compute an elliptic curve pairing later on.
Embedding Degrees
We found an elliptic curve subgroup of order 17 where the coordinates of the points come from F101 and satisfy y² = x³ + 3. However there are more points out there that satisfy this relationship. Some may have coordinates from an extension field F101ᵏ. It’s natural to think that there maybe many other points of the order 17.
The degree of the extension field of the characteristic p that contains every point of order r on the elliptic curve is the embedding degree. It has a simple formula: the embedding degree is the smallest number k, such that r | pᵏ-1 (divides evenly without any remainder).
It turns out that the embedding degree for the curve using r = 17 is 2. Higher embedding degrees are anyday more secure, however we are sacrificing blockchain security for the sake of calculation :”). All of the elliptic curves can be found using coordinates F101² .
An observation says that if r is relatively prime to the characteristic p of the field, then there will be exactly r² points of the order Fpᵏ.
Understanding the Extension Field
The extension field F101² can be generated from F101 by adjoining a solution to 2-degree polynomial that is not found in F101 prime field. The polynomial x² + 1 can be written in the following way:
However x² + 2 irreducible in F101 and can be used to generate the extension. Let u be one of the solutions to x² + 2. Now every element of F101² can be written as a + bu, where a and b are from F101.
Subgroup 2
We will be computing an elliptic curve pairing later on in this series in order to check our Kate polynomial commitments. Elliptic curve pairings take a pair of points on an elliptic curve which have the same order and return an element of field Fpᵏ. One complication when working with pairings is that the two elliptic curve points must come from different elliptic curve subgroups that have the same order. So in addition to the subgroup we just computed above we will need to find a generator for a second subgroup that also has order 17.
There are a few different techniques for finding a second subgroup. Because our embedding degree is 2, there must be some points of order 17 with coordinates in F101². Since 17 is prime, if we can find just one of them we can be sure that it is a generator of the second subgroup. A suitable generator is (36, 31u) (a much larger calculation, hence the default is often hard-coded). Remembering that u² = -2 we can easily verify this is a point on one curve by checking that y² = x³ + 3 in F101².
Running the Trusted Setup
Kate commitments require a trusted setup ceremony where a structured reference string (SRS) is created.
The reference string is a list of elliptic curve points are parameterised by a secret number s. Any circuit can use similar SRS as long as it has enough elements. According the original PLONK paper, a circuit with n gates requires an SRS with atleast n+5 elements as below:
The elliptic curve points G1 and G2 are the generators of the two subgroups we intend to use in our pairing.
We can use something random to generate s. Since the number s is a coefficient multiplying the generator from our elliptic curve group, it needs to be less than the order of the group (17). A 20-sided die can be an ideal example for this (except 1 or >16 of course).
Using this random number we create the structured reference string. Our SRS will have 9 elements (since 2 to the power 3 is 8 and we need a minimum of 4 gates). Lets first find the powers of s that will serve as coefficients for our 2 generators.
Then we will use our table of elliptic curve points to construct the first part of the SRS with generator G1. Normally this would be a much lengthier process, but we we are using s as a very small value and cheat table for our elliptic curve.
For the second part, using G2 of the SRS we only need to compute 2G2. We can so this using the doubling formula.
In general the point sG2 can be computed much more efficiently using twisted curve methods, but in our case a simpler doubling is quicker. Putting sG2 together with the rest of our points gives the complete SRS.
Now our setup is done. This list of elliptic curve points are converted structured reference string and now can be implemented in the arithmetic circuits.
Composing a PLONK-style circuit
Circuits in PLONK will end up being expressed as polynomials. The more gates there are in the circuit, the higher the degree of polynomials we may end up working with. In order to save some more serious hand cramping we’re using a small circuit.
A circuit that is pretty small but still interesting is one that test if three numbers form a Pythagorean triplet or not. The numbers (3,4,5), (5,12,13) and (9,12,15) form a Pythagorean triplet. Thus the equation is a² + b² = c².
Each gate, or constraint, of a SNARK circuit is an equation that can express a limited amount of arithmetic. In both PLONK and rank-one constraint systems (R1CS) there can only be one multiplication of variables in each gate. While R1CS can do unlimited additions in a single gate, PLONK can only do one. (Two additions if you count the addition of a constant.) Since the Pythagorean Theorem equation above has three multiplications and one addition we will need four PLONK gates to express it. Here is a simplified version of the four gate equations that express the Pythagorean equation:
Composing these equations gives x1² + x3² = x5², the Pythagorean Theorem equation we are trying to express.
Each xi variable is called a wire. In order to satisfy the constraints we would need to supply six numbers as wire values that make all of the equations correct. For example, x = (3,9,4,16,5,25) would work, as would x = (5,25,12,144,13,169).
To convert these equations into PLONK gates, first notice that every equation above has a variable each on the left and right side of the operation, and then an “output” variable on the other side of the equal sign. The value in the left variable will be called a, in the right, b, and the output c. (These a, b, and c have nothing to do with the a, b, and c typically used in the Pythagorean theorem. This is just an unfortunate coincidence in variable names!)
PLONK gates have more information in them than the simplified equations above. A full PLONK gate looks like this:
where the a, b, and c are the left, right, and output wires of the gate.To say a+b=c, we let qL and qR equal 1, while qO equals -1. The other coefficients wouldn’t be used, so we set qM and qC to 0.To say a×b=c, we set qO equal to -1, set qM equal 1, and set the rest of the coefficients to 0.To bind a variable to a public value, we let qR, qO, qM equal to 0, qL equal to 1, and qC equal to the public value.
Considering all inputs as private, we get these four PLONK gates representing our Pythagorean circuit:
These gates say that a1 ⋅ b1 = c1, a2 ⋅ b2 = c2, a3 ⋅ b3 = c3, and a4 + b4 = c4. Suppose you want to use these gates to check that (3,4,5) is a Pythagorean triple. The ai (left) values will be (3,4,5,9), the bi (right) values will be (3,4,5,16), and the ci (out) values will be (9,16,25,25). Each equation should be satisfied after substituting in these values. We collect all the qLi, ai, and so on into vectors:
The vectors above condense all the necessary information in a nice way so we don’t have to write out those full gate equations. The q vectors are called “selectors” and encode the structure of the circuit. The a, b, and c vectors are “assignments” to the circuit variables and represent the Prover’s private inputs.
The a, b, and c vectors written above form an example assignment to our circuit that tests whether (3,4,5) is a Pythagorean triple. We could have used assignments based on any other Pythagorean triple.
In the next part, we will use this arithmetic to generate the proof from the Prover’s side.
Hope you enjoyed reading! WAGMI!!
New to trading? Try crypto trading bots or copy trading on best crypto exchanges
Join Coinmonks Telegram Channel and Youtube Channel get daily Crypto News
