Module dusk_plonk::notes::snark_construction

This module contains the methodology of how zk-SNARKS are constructed.

SNARKs

These notes will show an abstraction on the construction of SNARKs by showing the mathematical steps involved.

ZK-SNARK stands for Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge. Implementing a SNARK protocol allows us to prove that a presented statement is true without revealing anything other than the statement itself.

The type of SNARK we will focus on will be one with a pre-processing stage. This means that the inputs to our SNARK system is an output of a program. We will also show how SNARKs satisfy the fundamental properties of zero knowledge. Namely: Completeness, Soundess and Zero Knowledge. Completeness means that the verifier is convinced that the claims from the prover are true. Soundness means that if the information is false, then the prover cannot convince the verifier otherwise. Zero knowledge means that the proof should reveal nothing other than the statement or claim itself.

To construct their proofs, SNARKS convert an arithmetic circuit into an algebraic expression of polynomials. The arithmetic circuit here, is a mapping, performed by a system of wires and gates, where the outputs are inputs which have passed through the circuit. The input for this is standardly assumed to be a computer program and those used in the zero knowledge fields tend to have a large number of operations.

For SNARK circuits, the prover will select gates, e.g.

Multiplication gates which are represented with two input wires to the gate, and one product wire, such that:

\({\mathbb W_{L}}\) \(\cdot\) \({\mathbb W_{R}}\) = \({\mathbb W_{O}}\),

Where:

• \({\mathbb W_{L}}\) is representative of the left input wire to the gate
• \({\mathbb W_{R}}\) is representative of the right input wire to the gate
• \({\mathbb W_{O}}\) is representative of the output wire of the gate

The variables rely upon another set of contraints when inside the circuit. These are the gate constants: \({\mathbb a_{L}}\), \({\mathbb a_{R}}\), \({\mathbb a_{O}}\),

Where:

• \({\mathbb a_{L}}\) is the left input to the gate
• \({\mathbb a_{R}}\) is the right input to the gate
• \({\mathbb a_{O}}\) is the output of the gate

The wires values can be seen as the weights to each of the inputs.

They are constrained as:

\[ \begin{aligned} \mathbf{{W}}_{L} \cdot \mathbf{a}_{L} + \mathbf{{W}}_{R} \cdot \mathbf{a}_{R} - \mathbf{{W}}_{O} \cdot \mathbf{a}_{O} = 0 \end{aligned} \]

When a program is chosen, the operations are expressed in terms of circuits, like the one above.

Many programmes and their computations have a large range of operations, so the number of these gates they need to construct can be very large. Therefore, we use a technique called a 'Quadratic Arithmetic Programme' (QAP) , to bundle the constraints together. For example, many wires may be of the same value and rather than computing them differently for each programme, they can be collected together and the constraint can be checked at varying values. This step involves checks for the values at specified indices. Additionally, the index values that are being checked at are not numbers, but are instead polynomials. This polynomial is computed by the QAP from the input vectors. This QAP is intended to give the prover the necessary 'tools' to derive these polynomials for a proof, from a given arithmetic circuit.

Following on from the example above, we can show a QAP being constructed from an 'n' number of multiplication gates. The inputs to the gates will be a vector of polynomials, all evaluated for indice value at some polynomial of their reduced form, \({\mathbf Z_p}\),

Let the left input polynomial be:

\[ \begin{aligned} \vec{A} = (A_{i}(z))_{i=0}^{n}\\ \end{aligned} \]

Let the right input polynomial be:

\[ \begin{aligned} \vec{B} = (B_{i}(z))_{i=0}^{n}\\ \end{aligned} \]

Let the outputs polynomial be:

\[ \begin{aligned} \vec{C} = (C_{i}(z))_{i=0}^{n}\\ \end{aligned} \]

The coefficients of these polynomials are inside some finite field , which also contains the polynomial \({\mathbf Z_z}\). As a result, it can be checked that the \({\mathbf Z_z}\) divides the multiplication gates polynomial.

This is done by first constructing the full polynomial:

\[ \begin{aligned} \mathbf{P}(z) = \mathbf{A}(z) * \mathbf{B}(z) - \mathbf{C}(z) \end{aligned} \] When the above equation is constructed by the prover, the verifier can check claims by checking the divisibility of \({\mathbf P}(z)\) by \({\mathbf Z_z}\). This \({\mathbf Z_z}\) polynomial is often referred to as the 'target polynomial'. The added benefit of having this checked in polynomial form, is that even with large polynomials, the identity between the two will hold at most points if the identity holds between the polynomials. Which means that the check between the two can be performed at randomly chosen points to verify the proof.

In order to turn a given QAP into a zk-SNARK, a prover must rely upon a third party. Which is more commonly known as 'a trusted set up'. The trusted set up constructs the polynomial \({\mathbf Z_z}\). The prover then commits the vector values along with their secret input, known as the witness, to the equation \({\mathbf P}(z)\) = \({\mathbf A}(z)\) * \({\mathbf B}(z)\) - \({\mathbf C}(z)\)

Then, the prover completes the divisibility check between \({\mathbf P}(z)\) and \({\mathbf Z_z}\). This way, the verifier can be sure that the prover knows the witness value.

The inner workings of the SNARK also contain a 'bilinear pairing', which is referring to the fields which are used throughout the protocol. However, in detail explanations of these are out of scope for these docs, more information on the role pairing cryptography has within SNARK construction can be found here.