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][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][pairings]. 










[finite_field]: https://web.stanford.edu/class/ee392d/Chap7.pdf
[pairings]:https://eprint.iacr.org/2016/260.pdf











