- Read
- Top Stories
Latest - All Top Stories
- All About Startup Growth With Lomit Patel on the HackerNoon Podcast
- How the Future of Streaming Will Leverage Web 3.0 to Make Media Free of Every End User
- Machine Learning Magic: How to Speed Up Offline Inference for Large Datasets
- Stablecoin History: The Master of All AltCoins
- R.I.P. Alexa Dot Com: You Will Be Sorely Missed

- Write
Writer Contests Writing Prompts - Learn
Self-Paced Courses Tech Deep Dives Build Skillzz - Apply Psychology of Colors
- Auto-Generate Graphics
- Build Frontend for Ethereum dApps
- Build a Private Blockchain
- Create Generative Art with Python
- Choose the Right Kubernetes Container
- Get Featured on Product Hunt without Hunter
- Go Serverless with AWS
- Hack Smart Contracts
- Host Your Git Server on Raspberry Pi
- Implement QA Properly
- Insert Binary Tree in Rust
- Learn Anything
- Measure Technical Debt
- Protect Your Code with Gulp
- Write NFT Smart Contracts

- STARTUPS
- Noonies Awards
Important Info Award Categories Award-Winning Titles - Tech Giants
- About
Company People Software by HackerNoon - Help
- Sponsor
- Shop

PLONK is a new general-purpose zero-knowledge proof scheme called [PLONK] It is a "universal and updateable" trusted setup. Multiple parties can participate in the trusted setup such that it is secure as long as any one of them is honest. The scheme is theoretically compatible with any (achievable) tradeoff between proof size and security assumptions. If this kind of scheme becomes widely adopted, we can thus expect rapid progress in improving shared arithmetization techniques.

*Special thanks to Justin Drake, Karl Floersch, Hsiao-wei Wang, Barry Whitehat, Dankrad Feist, Kobi Gurkan and Zac Williamson for review*

Very recently, Ariel Gabizon, Zac Williamson and Oana Ciobotaru announced a new general-purpose zero-knowledge proof scheme called PLONK, standing for the unwieldy quasi-backronym "Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge". While improvements to general-purpose zero-knowledge proof protocols have been coming for years, what PLONK (and the earlier but more complex SONIC and the more recent Marlin) bring to the table is a series of enhancements that may greatly improve the usability and progress of these kinds of proofs in general.

The first improvement is that while PLONK still requires a trusted setup procedure similar to that needed for the SNARKs in Zcash, it is a "universal and updateable" trusted setup. This means two things: first, instead of there being one separate trusted setup for every program you want to prove things about, there is one single trusted setup for the whole scheme after which you can use the scheme with any program (up to some maximum size chosen when making the setup).

Second, there is a way for multiple parties to participate in the trusted setup such that it is secure as long as any one of them is honest, and this multi-party procedure is fully sequential: first one person participates, then the second, then the third... The full set of participants does not even need to be known ahead of time; new participants could just add themselves to the end. This makes it easy for the trusted setup to have a large number of participants, making it quite safe in practice.

The second improvement is that the "fancy cryptography" it relies on is one single standardized component, called a "polynomial commitment". PLONK uses "Kate commitments", based on a trusted setup and elliptic curve pairings, but you can instead swap it out with other schemes, such as FRI (which would turn PLONK into a kind of STARK) or DARK (based on hidden-order groups). This means the scheme is theoretically compatible with any (achievable) tradeoff between proof size and security assumptions.

What this means is that use cases that require different tradeoffs between proof size and security assumptions (or developers that have different ideological positions about this question) can still share the bulk of the same tooling for "arithmetization" - the process for converting a program into a set of polynomial equations that the polynpomial commitments are then used to check. If this kind of scheme becomes widely adopted, we can thus expect rapid progress in improving shared arithmetization techniques.

Let us start with an explanation of how PLONK works, in a somewhat abstracted format that focuses on polynomial equations without immediately explaining how those equations are verified. A key ingredient in PLONK, as is the case in the QAPs used in SNARKs, is a procedure for converting a problem of the form "give me a value * X* such that a specific program

Here is an example of the problem of finding *x* such that *P(x)=x^3+x5=35* (hint: *x=3* ):

We can label the gates and wires as follows:

On the gates and wires, we have two types of constraints: **gate constraints** (equations between wires attached to the same gate, eg. *a_1*b_1=c_1*) and **copy constraints** (claims about equality of different wires anywhere in the circuit, eg. *a_0=a_1=b_1=b_2=_3* or *c_0=a_1*). We will need to create a structured system of equations, which will ultimately reduce to a very small number of polynomial equations, to represent both.

In PLONK, the setup for these equations is as follows. Each equation is of the following form (think: * L*= left,

Each **Q** value is a constant; the constants in each equation (and the number of equations) will be different for each program. Each small-letter value is a variable, provided by the user: * a_1* is the left input wire of the

Plugging these constants into the equation and simplifying gives us *a_i+b_i-c_1=0*, which is exactly the constraint that we want. For a multiplication gate, we set:

For a constant gate setting *a_i* to some constant *x*, we set:

If you have read about STARKs or QAPs, the mechanism described in this next section will hopefully feel somewhat familiar, but if you have not that's okay too. The main ingredient here is to understand a *polynomial* as a mathematical tool for encapsulating a whole lot of values into a single object. Typically, we think of polynomials in "coefficient form", that is an expression like:

But we can also view polynomials in "evaluation form". For example, we can think of the above as being "the" degree <4 polynomial with evaluations (-2,1,0,1) at the coordinates (0,1,2,3) respectively.

Now here's the next step. Systems of many equations of the same form can be re-interpreted as a single equation over polynomials. For example, suppose that we have the system:

Let us define four polynomials in evaluation form: * L(x)* is the degree

Here, * Z(x)* is shorthand for

So now we know that we can represent a large set of constraints within a small number of mathematical objects (the polynomials). But in the equations that we made above to represent the gate wire constraints, the * x_1,x_2,x_3* variables are different per equation. We can handle this by making the variables themselves polynomials rather than constants in the same way. And so we get:

As before, each * Q* polynomial is a parameter that can be generated from the program that is being verified, and the

Now, let us get back to "connecting" the wires. So far, all we have is a bunch of disjoint equations about disjoint values that are independently easy to satisfy: constant gates can be satisfied by setting the value to the constant and addition and multiplication gates can simply be satisfied by setting all wires to zero! To make the problem actually challenging (and actually represent the problem encoded in the original circuit), we need to add an equation that verifies "copy constraints": constraints such as * a(5)=c(7)*,

Our strategy will be to design a "coordinate pair accumulator", a polynomial * p(x)* which works as follows. First, let

For example, letting *v_1=3* and v_2=2, we get:

The result we care about is . Now, consider the case where instead of * p(4)=-240*, we set

Now we can start to see the basic technique that we will use to prove copy constraints. First, consider the simple case where we only want to prove copy constraints within one set of wires (eg. we want to prove * a(1)=a(3)*). We'll make two coordinate accumulators: one where

To prove constraints between * a*,

We would then instead of checking equality within one run of the procedure (ie. checking * p(4)=p’(4)* as before), we would check the product of the three different runs on each side:

The product of the three * p(n)* evaluations on each side accumulates all coordinate pairs in the

And that's all there is to it!

In reality, all of this math is done not over integers, but over a prime field; check the section "A Modular Math Interlude" here for a description of what prime fields are. Also, for mathematical reasons perhaps best appreciated by reading and understanding this article on FFT implementation, instead of representing wire indices with * x=0….n-1*, we'll use powers of

Now let's write out all the equations we need to check. First, the main gate-constraint satisfaction check:

Then the polynomial accumulator transition constraint (note: think of "* =Z(x)*H(x)*" as meaning "equals zero for all coordinates within some particular domain that we care about, but not necessarily outside of it"):

Then the polynomial accumulator starting and ending constraints:

The user-provided polynomials are:

- The wire assignments
**a(x), b(X), c(x)** - The coordinate accumulators
**P_a(x), P_b(x),P_c(x),P_a'^1(x),P_b’(x),P_c’(x)** - The
**H(x) and H_1(x)…H_6(x)**

The program-specific polynomials that the prover and verifier need to compute ahead of time are:

which together represent the gates in the circuit (note that**Q_L(x), Q_r(x), Q_o(x),Q_M(x), Qc(x)**encodes public inputs, so it may need to be computed or modified at runtime)**Q_C(x)**- The "permutation polynomials"
and**o_a(x),o_b(x)**, which encode the copy constraints between the**o_c(x)**,**a**and**b**wires**c**

Note that the verifier need only store commitments to these polynomials. The only remaining polynomial in the above equations is * Z(x)=(x-1)(x-w)…(x-w^x-1)* which is designed to evaluate to zero at all those points. Fortunately, can be chosen to make this polynomial very easy to evaluate: the usual technique is to choose to satisfy

There is one nuance here: the constraint between * P_a(w^i+1)* and

The only constraint on * v_1* and

So now we've turned the program satisfaction problem into a simple problem of satisfying a few equations with polynomials, and there are some optimizations in PLONK that allow us to remove many of the polynomials in the above equations that I will not go into to preserve simplicity. But the polynomials themselves, both the program-specific parameters and the user inputs, are **big**. So the next question is, how do we get around this so we can make the proof short?

A polynomial commitment is a short object that "represents" a polynomial, and allows you to verify evaluations of that polynomial, without needing to actually contain all of the data in the polynomial. That is, if someone gives you a commitment * c* representing

Using such polynomial commitments, we could very easily check all of the above polynomial equations above - make the commitments, use them as input to generate * z*, prove what the evaluations are of each polynomial at

There are two parts: the commitment to the polynomial * P(x) → c*, and the opening to a value

is also a polynomial (using another polynomial commitment). This works because if the quotient is a polynomial (ie. it is not fractional), then * x-z* is a factor of

So how do the commitments themselves work? Kate commitments are, fortunately, much simpler than FRI. A trusted-setup procedure generates a set of elliptic curve points * G,G*8,G*8^2*....

These points are published and considered to be "the proving key" of the scheme; anyone who needs to make a polynomial commitment will need to use these points. A commitment to a degree-d polynomial is made by multiplying each of the first d+1 points in the proving key by the corresponding coefficient in the polynomial, and adding the results together.

Notice that this provides an "evaluation" of that polynomial at * _8*, without knowing

But there are more recently other types of polynomial commitments coming out too. A new scheme called DARK ("Diophantine arguments of knowledge") uses "hidden order groups" such as class groups to implement another kind of polynomial commitment. Hidden order groups are unique because they allow you to compress arbitrarily large numbers into group elements, even numbers much larger than the size of the group element, in a way that can't be "spoofed"; constructions from VDFs to accumulators to range proofs to polynomial commitments can be built on top of this. Another option is to use bulletproofs, using regular elliptic curve groups at the cost of the proof taking much longer to verify. Because polynomial commitments are much simpler than full-on zero knowledge proof schemes, we can expect more such schemes to get created in the future.

To finish off, let's go over the scheme again. Given a program * P*, you convert it into a circuit, and generate a set of equations that look like this:

There is a set of equations between the polynomials that need to be checked; you can do this by making commitments to the polynomials, opening them at some random (along with proofs that the openings are correct), and running the equations on these evaluations instead of the original polynomials. The proof itself is just a few commitments and openings and can be checked with a few equations. And that's all there is to it!

*This article was originally published as “Understanding PLONK”*