Under the hood of zkSNARKs — PLONK protocol: part3

Many materials available online explain the basics of the PLONK protocol, often referencing Vitalik’s example P(x)=x³+x+5=35 from his article:

Understanding PLONK

To offer a different perspective, this article will explore a modified equation that introduces additional complexities. We will use the equation f(x,y)=2x²−x²y²+3 and set it to equal -25, with x=2 and y=3. This equation features two input parameters, a subtraction operation, a negative result, the repeated use of an operation (x²), and multiplication by a constant (as seen in 2x²). These elements provide a broader understanding of how PLONK handles various computational scenarios.

Arithmetization

The first step in transforming an equation into a Zero-Knowledge Proof (ZKP) is arithmetization. As mentioned in the previous article, to generate a proper proof for the statement, it’s essential to capture all the states of the program during its execution. Arithmetization achieves this by converting the computation into a polynomial form, which allows for the efficient generation and verification of the proof within the ZKP framework.

Under the hood of zkSNARKs — PLONK protocol: Part 2

Using Circom, we can translate our problem into code like this:

pragma circom 2.1.6;

template Example () {
    signal input x;
    signal input y;
    signal output out;

    signal xx;
    signal yy;

    xx <== x * x; // Quadratic term: x squared
    yy <== y * y; // Quadratic term: y squared

    // Intermediate signal for x*x*y*y
    signal xxyy;
    xxyy <== xx * yy;

    // Final expression
    out <== xx * 2 - xxyy + 3;
}

component main { public [ x, y ] } = Example();

/* INPUT = {
    "x": "2",
    "y": "3"
} */

This approach differs significantly from what an average developer might write in a language like Python:

x = 2
y = 3
out = 2*x**2 - x**2*y**2 + 3

Circom’s nature as a Domain Specific Language (DSL) aids in organizing code specifically for compiling into an arithmetic circuit. This structured format not only ensures that the code aligns with the mathematical requirements of the proofs but also optimizes the process of circuit generation and proof computation.

Arithmetic Circuit

So, a clear pattern emerges in the circuit structure: each operation corresponds to a separate gate, denoted by g0, g1, …, etc. Each gate has two inputs (a, b) and one output ( c). Take gates g0 and g1, for example; both represent the same x² operation. In Circom, this calculation is performed once and then reused wherever needed, such as in g0 and g1. The reason for having two identical gates relates to the permutation check, which ensures a 1-to-1 mapping of the wires (for example, output c0 connects to input a3, c1 to a4, and so on).

Another point of interest is gate g3. Here, you might notice that the second input for the constant 2 is not marked by ‘b’. This is because, in PLONK, multiplication can only involve variables, so ‘b’ is set to 0 in this case. However, constants are permissible in addition gates. The constant 2 for multiplication in gate g3 comes from a selector vector, which we will address later, and its depicting in this gate is more symbolic.

Lastly, it’s important to note that there are no subtraction gates. All calculations are performed using Finite Field arithmetic. In this system, negative numbers are transformed into positive ones through modulo operations, aligning with the field’s properties.

Constraining the gates

The next step involves describing each gate in the arithmetic circuit using polynomial equations.

In these equation, the variables a, b, and c represent the wires associated with each gate, corresponding to their inputs and output. Alongside these, we have selector variables, denoted as q, which function like activators for the gates. They determine which wires and operations are engaged in the circuit at any given point.

Each gate in our arithmetic circuit is represented by specific polynomial equations, influenced by selector variables. For example, gate g0 performs a multiplication of inputs a0 and b0. To enable this operation, the multiplication selector variable qm is set to 1, and the gate outputs c0. The output activation is facilitated by setting the output selector qo to -1, adhering to the constraint that our polynomial equations must sum to 0. Gates g1, g2, and g4 are configured similarly to g0.

In gate g3, to multiply the value a3 by the constant 2, we set the selector variable ql to 2. This gate showcases how constants are incorporated into the computations. For subtraction, as seen in gate g5, the right selector qr is set to -1, representing the subtraction operation in polynomial form. Addition is handled in gate g6, where the addition of a constant 3 is facilitated through the constant selector qc.

We have all the values for the gates so we can encode them into following vectors:

Dummy Gates

In the previous article, we discussed an optimization technique involving the vanishing polynomial in PLONK, where steps are marked using roots of unity instead of sequential numbers. This optimisation necessitates having a number of gates that is a power of 2.

Currently, our circuit comprises 7 gates. However, to meet the 2^n requirement in PLONK, the closest power of 2 is 8 (2³ = 8). This means we need to add an additional gate to make the total number 8. This extra gate is a ‘dummy gate’ — it doesn’t perform any real computation but serves as a placeholder to satisfy the power of 2 structure. By adding this dummy gate, we ensure that our circuit adheres to the optimal structure for PLONK’s efficiency mechanisms.

def pad_array(a, n):
    return a + [0]*(n - len(a))

# witness vectors
a = [2, 2, 3, 4, 4, 8, -28]
b = [2, 2, 3, 0, 9, 36, 3]
c = [4, 4, 9, 8, 36, -28, -25]

# gate vectors
ql = [0, 0, 0, 2, 0, 1, 1]
qr = [0, 0, 0, 0, 0, -1, 0]
qm = [1, 1, 1, 1, 1, 0, 0]
qc = [0, 0, 0, 0, 0, 0, 3]
qo = [-1, -1, -1, -1, -1, -1, -1]

# pad vectors to length n
a = pad_array(a, n)
b = pad_array(b, n)
c = pad_array(c, n)
ql = pad_array(ql, n)
qr = pad_array(qr, n)
qm = pad_array(qm, n)
qc = pad_array(qc, n)
qo = pad_array(qo, n)
# -- results ---
# a = [2, 2, 3, 4, 4, 8, -28, 0]
# b = [2, 2, 3, 0, 9, 36, 3, 0]
# c = [4, 4, 9, 8, 36, -28, -25, 0]
# ql = [0, 0, 0, 2, 0, 1, 1, 0]
# qr = [0, 0, 0, 0, 0, -1, 0, 0]
# qm = [1, 1, 1, 1, 1, 0, 0, 0]
# qc = [0, 0, 0, 0, 0, 0, 3, 0]
# qo = [-1, -1, -1, -1, -1, -1, -1, 0]

In the next article we will discuss permutation constraint.

Under the hood of zkSNARKs — PLONK protocol: part4

zkSNARK-under-the-hood/plonk_latest.ipynb at main · tarassh/zkSNARK-under-the-hood