ZeroKnowledge Proofs  Theory
Quote from Remco Bloemen remco@0x.org
Disclaimer: contains maths
If you don’t understand something
 Not your fault, this stuff is hard
 Nobody understands it fully
If you don’t understand anything
 My fault, anything can be explained at some level
If you do understand everything
 Collect your Turing Award & Fields Medal
Examples to give an Intuitive grasp of zeroknowledge proofs
Colour blind verifier
An interactive proof showing that the prover can distinguish between a red and a green billiard ball, whereas the verifier cannot distinguish them.
• The prover wants to show the verifier that they have different colours but does not want him to learn which is red and which is green.
• Step 1: The verifier takes the balls, each one in each hand, holds them in front of the prover and then hides them behind his back. Then, with probability 1/2 either swaps them (at most once) or keeps them as they are. Finally, he brings them out in front.
• Step 2: The prover has to say the verifier switched them or not.
• Step 3: Since they have different colours, the prover can always say whether they were switched or not.
But, if they were identical (the verifier is inclined to believe that), the prover would be wrong with probability 1/2.
• Finally, to convince the verifier with very high probability, the prover could repeat Step 1 to Step 3 k times to reduce the probability of the prover being successful by chance to a extremely small amount.
Wheres Wally
A proof based on a large sheet of paper through which Wally can be seen in a picture.
Sudoku
(https://blog.computationalcomplexity.org/2006/08/zeroknowledgesudoku.html)
Actors in a Zero Knowledge Proof
 Creator
 Prover  Peggy
 Verifier  Victor
zkSNARKS
A zkSNARK consists of three algorithms G, P, V defined as follows:
The Creator takes a secret parameter lambda and a program C, and generates two publicly available keys, a proving key pk, and a verification key vk. These keys are public parameters that only need to be generated once for a given program C.
The prover Peggy takes a proving key 𝑝𝑘$pk$, a public input 𝑥$x$ and a private witness 𝑤$w$. Peggy generates a proof 𝑝𝑟𝑓=𝑃(𝑝𝑘,𝑥,𝑤)$prf=P(pk,x,w)$ that claims that Peggy knows a witness 𝑤$w$ and that the witness satisfies the program C.
The verifier Victor computes 𝑉(𝑣𝑘,𝑥,𝑝𝑟𝑓)$V(vk,x,prf)$ which returns true if the proof is correct, and false otherwise. Thus this function returns true if Peggy knows a witness 𝑤$w$ satisfying
𝐶(𝑥,𝑤)=𝑡𝑟𝑢𝑒$C(x,w)=true$
Trusted Setups and Toxic Waste
Note here the secret parameter lambda This parameter sometimes makes it tricky to use zkSNARK in realworld applications. The reason for this is that anyone who knows this parameter can generate fake proofs. Specifically, given any program C and public input x a person who knows lambda can generate a proof fake_prf such that V(vk, x, fake_prf) evaluates to true without knowledge of the secret w.
A preview of the process flow in Zokrates

The Creator writes and compiles a program in a DSL

The Creator / Prover generates a trusted setup for the compiled program

The Prover computes a witness for the compiled program

The Prover generates a proof  Using the proving key, she generates a proof for a computation of the compiled program

The Creator / Prover exports a Verifier  Using the verifying key she generates a Solidity contract which contains the generated verification key and a public function to verify a solution to the compiled program
From Proof Systems to ZKP Systems
Proving Systems
A statement is a proposition we want to prove. It depends on:
 Instance variables, which are public.
 Witness variables, which are private.
Given the instance variables, we can find a short proof that we know witness variables that make the statement true (possibly without revealing any other information).
What do we require of a proof ?

Completeness: there exists an honest prover P that can convince honest verifier V of any correct statement with very high probability.

Soundness: even a dishonest prover P running in time superpolynomial cannot convince an honest verifier V of an incorrect statement Note: P does not necessarily have to run in polynomial time, but V does.
For a Zero Knowledge Proof we also need ‘zero knowledginess’
To oversimplify: represented on a computer, a ZKP is nothing more than a sequence of numbers, carefully computed by Peggy, together with a bunch of boolean checks that Victor can run in order to verify the proof of correctness for the computation.
A zeroknowledge protocol is thus the mechanism used for deriving these numbers and defining the verification checks.
Interactive v Non Interactive Proofs
Noninteractivity is only useful if we want to allow multiple independent verifiers to verify a given proof without each one having to individually query the prover.
In contrast, in noninteractive zero knowledge protocols there is no repeated communication between the prover and the verifier. Instead, there is only a single “round”, which can be carried out asynchronously.
Using publicly available data, Peggy generates a proof, which she publishes in a place accessible to Victor (e.g. on a distributed ledger).
Following this, Victor can verify the proof at any point in time to complete the “round”. Note that even though Peggy produces only a single proof, as opposed to multiple ones in the interactive version, the verifier can still be certain that except for negligible probability, she does indeed know the secret she is claiming.
Succint v Non Succint
Succinctness is necessary only if the medium used for storing the proofs is very expensive and/or if we need very short verification times.
Proof v Proof of Knowledge
A proof of knowledge is stronger and more useful than just proving the statement is true. For instance, it allows me to prove that I know a secret key, rather than just that it exists.
Argument v Proof
In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover.
Arguments are thus often called “computationally sound proofs”.
The Prover and the Verifier have to agree on what they’re proving. This means that both know the statement that is to be proven and what the inputs to this statement represent.
Schnoor Protocol
For a cyclic group 𝐺𝑞${G}_{q}$ of order 𝑞$q$ with generator 𝑔$g$.
In order to prove knowledge of 𝑥=log𝑔𝑦$x={\mathrm{log}}_{g}y$, the prover interacts with the verifier as follows:
In the first round the prover commits himself to randomness 𝑟$r$ therefore the first message 𝑡=𝑔𝑟$t={g}^{r}$ is also called commitment.
The verifier replies with a challenge 𝑐$c$ chosen at random.
After receiving 𝑐$c$, the prover sends the third and last message (the response) 𝑠=𝑟+𝑐𝑥$s=r+cx$
The verifier accepts, if 𝑔𝑠=𝑡𝑦𝑐${g}^{s}=t{y}^{c}$
Protocols which have the above threemove structure (commitment, challenge and response) are called sigma protocols
Lets look first at transforming the problem into a QAP, there are
3 steps :
 code flattening,
 conversion to a rank1 constraint system (R1CS)
 formulation of the QAP.
Code Flattening
We are aiming to create arithmetic and / or boolean circuits from our code, so we change the high level language into a sequence of statements that are of two forms
x = y (where y can be a variable or a number)
and
x = y (op) z (where op can be +, , *, / and y and z can be variables, numbers or themselves subexpressions).
For example we go from
def qeval(x):
y = x**3
return x + y + 5
to
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
Rank 1 Constraint Systems
(From http://coderserrand.com/constraintsystemsforzksnarks/)
The important thing to understand is that a R1CS is not a computer program, you are not asking it to produce a value from certain inputs. Instead, a R1CS is a verifier, it shows that an already complete computation is correct .
A rank 1 constraint system is a set of rank 1 constraints, each of the form:
𝐴𝑋𝐵=𝐶$AXB=C$
where 𝐴,𝐵,𝐶$A,B,C$ are each linear combinations c1· v1+ c2· v2+ …
The 𝑐𝑖${c}_{i}$ are constant field elements, and the 𝑣𝑖${v}_{i}$ are instance or witness variables (or 1).
The inputs and outputs of a subcircuit are not predetermined.
 𝐴𝑋𝐵=𝐶$AXB=C$ doesn’t mean 𝐶$C$ is computed from 𝐴$A$ and 𝐵$B$ just
that 𝐴,𝐵,𝐶$A,B,C$ are consistent.
More generally, an implementation of 𝑥=𝑓(𝑎,𝑏)$x=f(a,b)$ doesn’t mean that x is
computed from a and b, just that x, a, and b are consistent.
Constraint languages can be viewed as a generalization of
functional languages:
 everything is referentially transparent and sideeffect free
 there is no ordering of constraints
 composing two R1CS programs just means that their constraints are simultaneously satisfied.
Example
Assume P wants to prove to V he knows
c1, c2, c3 such that (c1 · c2) · (c1 + c3) = 7
We transform the expression above into an arithmetic circuit as depicted below
Definition: A legal assignment for the circuit is of the form:
(c1, . . . , c5), where c4 = c1 · c2 and c5 = c4 · (c1 + c3).
QAP
Gennaro et al.showed that circuit satisfiability can be efficiently reduced to QAP satisfiability so we will use a Quadratic Arithmetic Program to verify circuit computation
Our goal is to devise a set of polynomials that simultaneously encode all of the constraints, so that we can verify the satisfiability thereof with a single check on the polynomials instead of a check over each constraint. The clever trick is to build the polynomials in a way that they can generate all of the constraints.
The QAP itself is made up of 3 polynomial vectors:
𝑃𝐴,𝑃𝐵,𝑃𝐶$PA,PB,PC$
corresponding to the linear combinations of the same name in the R1CS
plus one polynomial 𝑍$Z$.
Given fixed values
(𝑐1,…,𝑐5)$({c}_{1},\dots ,{c}_{5})$
we use them as coefficients to define a left, right, and output “sum” polynomials.
We want to show that our created QAP has a legal assignment,
From our example above each multiplication gate X has an associated target point in the field 𝔽𝑝${\mathbb{F}}_{p}$ . In our example, they will be 1 and 2.
• Each wire (in our example, there are 5) has an associated left, right and
output polynomials: .
• Each polynomial evaluates to either 0 or 1 on the target points. If the polynomial is “related” to the multiplication gate associated with a target point, then it evaluates to 1. Otherwise to 0.
The important thing to retain is that since we have d constraints we can compute a polynomial of degree at most d1 for each entry in the linear combination. And this defines the main part of the QAP:
the 𝑃𝐴,𝑃𝐵,𝑃𝐶$PA,PB,PC$ polynomial vectors.
Z Polynomial
Z is defined as the polynomial that is 0 exactly at the points we chose above, 𝑟1${r}_{1}$ to 𝑟𝑑${r}_{d}$.
Z is defined as (x  1) * (x  2) * (x  3) …  the simplest polynomial that is equal to zero at all points that correspond to logic gates. It is an elementary fact of algebra that any polynomial that is equal to zero at all of these points has to be a multiple of this minimal polynomial, and if a polynomial is a multiple of Z then its evaluation at any of those points will be zero;
P(z) = <PA(z) . s> * <PB(z) . s>  <PC(z) . s>
Now, it is a property of Algebra that a polynomial is equal to the product of linear terms of its roots and a scalar. What this means is that if a polynomial has zeroes at points r1, r2, …, rd, then it can be written as
P(z) = (z  r1) (z  r2) … (z  rd) H(z),
where H(z) is some other polynomial that represents the other places at which P is 0. Now, notice the similarity with our chosen Z(z) polynomial:
Every polynomial P that is 0 at least for the points associated with all the constraints will be necessarily a multiple of Z(z), and can be written as
P(z) = Z(z) * H(z)
We converted a set of vectors into polynomials that generate them when evaluated at certain fixed points. We used these fixed points to generate a vanishing polynomial that divides any polynomial that evaluates to 0 at least on all those points. We created a new polynomial that summarizes all constraints and a particular assignment, and the consequence is that we can verify all constraints at once if we can divide that polynomial by the vanishing one without remainder. This division is complicated, but there are methods (the Fast Fourier Transform) that can perform if efficiently.
From http://coderserrand.com/howtobuildaquadraticarithmeticprogram/
Zero Knowledginess
Blind evaluation of a polynomial using Homomorphic Hiding
Suppose Alice has a polynomial P of degree d , and Bob has a point 𝑠∈𝔽𝑝$s\in {\mathbb{F}}_{p}$ that he chose randomly.
Bob wishes to learn E(P(s)), i.e., the HH of the evaluation of P at s
Two simple ways to do this are:

Alice sends P to Bob, and he computes E(P(s))by himself.

Bob sends s to Alice; she computes E(P(s)) and sends it to Bob.
However, in the blind evaluation problem we want Bob to learn E(P(s)) without learning P
which precludes the first option; and, most importantly,
we don’t want Alice to learn s, which rules out the second
Using HH, we can perform blind evaluation as follows.
 Bob sends to Alice the hidings E(1),E(s),…,E(sd).
 Alice computes E(P(s)) from the elements sent in the first step, and sends
E(P(s)) to Bob. (Alice can do this since E supports linear combinations, and P(s)is a linear combination of 1,s,…,sd.)
Note that, as only hidings were sent, neither Alice learned s nor Bob learned P
The rough intuition is that the verifier has a “correct” polynomial in mind, and wishes to check the prover knows it. Making the prover blindly evaluate their polynomial at a random point not known to them, ensures the prover will give the wrong answer with high probability if their polynomial is not the correct one. This, in turn, relies on the SchwartzZippel Lemma stating that “different polynomials are different at most points”.
but
the fact that Alice is able to compute E(P(s)) does not guarantee she will indeed send E(P(s)) to Bob, rather than some completely unrelated value.
Remember our QAP Q of degree d and size m consists of polynomials L1,…,Lm, R1,…,Rm, O1,…,Om and a target polynomial T of degree d.
An assignment (c1,…,cm) satisfies Q if, defining
𝐿:=∑𝑚𝑖=1𝑐𝑖⋅𝐿𝑖,𝑅:=∑𝑚𝑖=1𝑐𝑖⋅𝑅𝑖,𝑂:=∑𝑚𝑖=1𝑐𝑖⋅𝑂𝑖$L:=\sum _{i=1}^{m}ci\cdot Li,R:=\sum _{i=1}^{m}ci\cdot Ri,O:=\sum _{i=1}^{m}ci\cdot Oi$ and P:=L⋅R−O, we have that T divides P.
Our process then becomes

Alice chooses polynomials L,R,O,H of degree at most d

Bob chooses a random point s ∈ 𝔽𝑝${\mathbb{F}}_{p}$, and computes E(T(s))

Alice sends Bob the hidings of all these polynomials evaluated at s, i.e. E(L(s)),E(R(s)),E(O(s)),E(H(s))

Bob checks if the desired equation holds at s. That is, he checks whether E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s)).
Furthemore we use
 Random values added to our s to conceal the s value
 The Knowledge of Coefficient Assumption to prove Alice can produce a linear combination of the polynomials.
For details of these see : https://z.cash/blog/snarkexplain6/
Other Projects
From the useful
https://github.com/gluk64/awesomezeroknowledgeproofs
Starks
ZeroKnowledge (ScalableSuccint) Transparent Arguments of Knowledge
zkSTARKs were created by EliBen Sasson, a professor at the TechnionIsrael Institute of Technology.
They generally, considered a more efficient variant of the technology  potentially faster, but the proof size is much greater.
Trusted Setup
In zkSTARKs, there is no external trusted setup phase and the randomness used is public information.
Vitalik’s Blog Articles
The STARK paper
libSTARK
More resources available at starkware.co
Bulletproofs
https://crypto.stanford.edu/bulletproofs/
https://eprint.iacr.org/2017/1066.pdf
Aim to prove that asecret committed value lies in a given interval.
Bulletproofs require no trusted setup. However, verifying a bulletproof is more time consuming than verifying a SNARK proof.
They rely only on the discrete logarithm assumption, and are made noninteractive using the FiatShamir heuristic
a general dropin replacement for Sigmaprotocols.
Bulletproofs shrink the size of the cryptographic proof from over 10kB to less than 1kB. Moreover, bulletproofs support proof aggregation, so that proving that m transaction values are valid adds only O(log(m)) additional elements to the size of a single proof.
They concentrate on confidential transactions, but can be for general NP langs
The proof size islogarithmicin the numberof multiplication gates in the arithmetic circuit for verifying a witness. The proofs are much shorter than zkSNARK and allow inputs to be Pedersen commitments to elements of the witness.
The high level idea of this proving system is that
 The prover commits to a value(s) that he wants to prove knowledge of
 The prover generates the proof by enforcing the constraints over the committed values and any additional public values. The constraints might require the prover to commit to some additional variables.
 Prover sends the verifier all the commitments he made in step 1 and step 2 along with the proof from step 2.
 The verifier now verifies the proof by enforcing the same constraints over the commitments plus any public values.
DIZK
Dizk Repo
Dizk Paper
DIZK provides Javabased implementations using Apache Spark [Apa17] for:
 Proof systems
 A serial and distributed preprocessing zkSNARK for R1CS (Rank1 Constraint Systems), an NPcomplete language that resembles arithmetic circuit satisfiability. The zkSNARK is the protocol in [Gro16].
 A distributed MerlinArthur proof system for evaluating arithmetic circuits on batches of inputs; see [Wil16].
 Scalable arithmetic
 A serial and distributed radix2 fast Fourier transform (FFT); see [Sze11].
 A serial and distributed multiscalar multiplication (MSM); see [BGMW93] [Pip76] [Pip80].
 A serial and distributed Lagrange interpolation (Lag); see [BT04].
 Applications using the above zkSNARK for
 Authenticity of photos on three transformations (crop, rotation, blur); see [NT16].
 Integrity of machine learning models with support for linear regression and covariance matrices; see [Bis06] [Can69] [LRF97] [vW97].
ZCash links
Home
Zcash deep dive
Explaining Snarks Series
Rollup
Repo
There is a problem that the various libraries aren’t standardised.
libsnark
Bellman
jsnark  Java bindings to libsnark
snarkjs
Snarky
Zokrates
Ethsnarks
Circom  circuit compiler
Useful Resources
Blogs
http://coderserrand.com/zeroknowledgeproofsalaymansintroduction/
https://blog.decentriq.ch/zksnarksprimerpartone/
http://coderserrand.com/zksnarksandtheiralgebraicstructure/
Talks from the last workshop
Additional Reading
Hackathon projects
ZeroKnowledge Proofs  Theory
Quote from Remco Bloemen remco@0x.org
Examples to give an Intuitive grasp of zeroknowledge proofs
Colour blind verifier
An interactive proof showing that the prover can distinguish between a red and a green billiard ball, whereas the verifier cannot distinguish them.
• The prover wants to show the verifier that they have different colours but does not want him to learn which is red and which is green.
• Step 1: The verifier takes the balls, each one in each hand, holds them in front of the prover and then hides them behind his back. Then, with probability 1/2 either swaps them (at most once) or keeps them as they are. Finally, he brings them out in front.
• Step 2: The prover has to say the verifier switched them or not.
• Step 3: Since they have different colours, the prover can always say whether they were switched or not.
But, if they were identical (the verifier is inclined to believe that), the prover would be wrong with probability 1/2.
• Finally, to convince the verifier with very high probability, the prover could repeat Step 1 to Step 3 k times to reduce the probability of the prover being successful by chance to a extremely small amount.
Wheres Wally
A proof based on a large sheet of paper through which Wally can be seen in a picture.
Sudoku
(https://blog.computationalcomplexity.org/2006/08/zeroknowledgesudoku.html)
Actors in a Zero Knowledge Proof
zkSNARKS
A zkSNARK consists of three algorithms G, P, V defined as follows:
The Creator takes a secret parameter lambda and a program C, and generates two publicly available keys, a proving key pk, and a verification key vk. These keys are public parameters that only need to be generated once for a given program C.
The prover Peggy takes a proving key𝑝𝑘 $pk$, a public input 𝑥 $x$ and a private witness 𝑤 $w$. Peggy generates a proof 𝑝𝑟𝑓=𝑃(𝑝𝑘,𝑥,𝑤) $prf=P(pk,x,w)$ that claims that Peggy knows a witness 𝑤 $w$ and that the witness satisfies the program C.
The verifier Victor computes𝑉(𝑣𝑘,𝑥,𝑝𝑟𝑓) $V(vk,x,prf)$ which returns true if the proof is correct, and false otherwise. Thus this function returns true if Peggy knows a witness 𝑤 $w$ satisfying
Trusted Setups and Toxic Waste
Note here the secret parameter lambda This parameter sometimes makes it tricky to use zkSNARK in realworld applications. The reason for this is that anyone who knows this parameter can generate fake proofs. Specifically, given any program C and public input x a person who knows lambda can generate a proof fake_prf such that V(vk, x, fake_prf) evaluates to true without knowledge of the secret w.
A preview of the process flow in Zokrates
The Creator writes and compiles a program in a DSL
The Creator / Prover generates a trusted setup for the compiled program
The Prover computes a witness for the compiled program
The Prover generates a proof  Using the proving key, she generates a proof for a computation of the compiled program
The Creator / Prover exports a Verifier  Using the verifying key she generates a Solidity contract which contains the generated verification key and a public function to verify a solution to the compiled program
From Proof Systems to ZKP Systems
Proving Systems
A statement is a proposition we want to prove. It depends on:
Given the instance variables, we can find a short proof that we know witness variables that make the statement true (possibly without revealing any other information).
What do we require of a proof ?
Completeness: there exists an honest prover P that can convince honest verifier V of any correct statement with very high probability.
Soundness: even a dishonest prover P running in time superpolynomial cannot convince an honest verifier V of an incorrect statement Note: P does not necessarily have to run in polynomial time, but V does.
For a Zero Knowledge Proof we also need ‘zero knowledginess’
To oversimplify: represented on a computer, a ZKP is nothing more than a sequence of numbers, carefully computed by Peggy, together with a bunch of boolean checks that Victor can run in order to verify the proof of correctness for the computation.
A zeroknowledge protocol is thus the mechanism used for deriving these numbers and defining the verification checks.
Interactive v Non Interactive Proofs
Noninteractivity is only useful if we want to allow multiple independent verifiers to verify a given proof without each one having to individually query the prover.
In contrast, in noninteractive zero knowledge protocols there is no repeated communication between the prover and the verifier. Instead, there is only a single “round”, which can be carried out asynchronously.
Using publicly available data, Peggy generates a proof, which she publishes in a place accessible to Victor (e.g. on a distributed ledger).
Following this, Victor can verify the proof at any point in time to complete the “round”. Note that even though Peggy produces only a single proof, as opposed to multiple ones in the interactive version, the verifier can still be certain that except for negligible probability, she does indeed know the secret she is claiming.
Succint v Non Succint
Succinctness is necessary only if the medium used for storing the proofs is very expensive and/or if we need very short verification times.
Proof v Proof of Knowledge
A proof of knowledge is stronger and more useful than just proving the statement is true. For instance, it allows me to prove that I know a secret key, rather than just that it exists.
Argument v Proof
In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover.
Arguments are thus often called “computationally sound proofs”.
The Prover and the Verifier have to agree on what they’re proving. This means that both know the statement that is to be proven and what the inputs to this statement represent.
Schnoor Protocol
For a cyclic group𝐺𝑞 ${G}_{q}$ of order 𝑞 $q$ with generator 𝑔 $g$.𝑥=log𝑔𝑦 $x={\mathrm{log}}_{g}y$, the prover interacts with the verifier as follows:
In order to prove knowledge of
In the first round the prover commits himself to randomness𝑟 $r$ therefore the first message 𝑡=𝑔𝑟 $t={g}^{r}$ is also called commitment.𝑐 $c$ chosen at random.𝑐 $c$, the prover sends the third and last message (the response) 𝑠=𝑟+𝑐𝑥 $s=r+cx$𝑔𝑠=𝑡𝑦𝑐 ${g}^{s}=t{y}^{c}$
The verifier replies with a challenge
After receiving
The verifier accepts, if
Protocols which have the above threemove structure (commitment, challenge and response) are called sigma protocols
Transforming our Problem from High Level Language to ZKP
Lets look first at transforming the problem into a QAP, there are
3 steps :
Code Flattening
We are aiming to create arithmetic and / or boolean circuits from our code, so we change the high level language into a sequence of statements that are of two forms
x = y (where y can be a variable or a number)
and
x = y (op) z (where op can be +, , *, / and y and z can be variables, numbers or themselves subexpressions).
For example we go from
to
Rank 1 Constraint Systems
(From http://coderserrand.com/constraintsystemsforzksnarks/)
The important thing to understand is that a R1CS is not a computer program, you are not asking it to produce a value from certain inputs. Instead, a R1CS is a verifier, it shows that an already complete computation is correct .
A rank 1 constraint system is a set of rank 1 constraints, each of the form:
𝐴𝑋𝐵=𝐶 $AXB=C$𝐴,𝐵,𝐶 $A,B,C$ are each linear combinations c1· v1+ c2· v2+ …𝑐𝑖 ${c}_{i}$ are constant field elements, and the 𝑣𝑖 ${v}_{i}$ are instance or witness variables (or 1).
where
The
The inputs and outputs of a subcircuit are not predetermined.
that
More generally, an implementation of𝑥=𝑓(𝑎,𝑏) $x=f(a,b)$ doesn’t mean that x is
computed from a and b, just that x, a, and b are consistent.
Constraint languages can be viewed as a generalization of
functional languages:
Example
Assume P wants to prove to V he knows
c1, c2, c3 such that (c1 · c2) · (c1 + c3) = 7
We transform the expression above into an arithmetic circuit as depicted below
Definition: A legal assignment for the circuit is of the form:
(c1, . . . , c5), where c4 = c1 · c2 and c5 = c4 · (c1 + c3).
QAP
Gennaro et al.showed that circuit satisfiability can be efficiently reduced to QAP satisfiability so we will use a Quadratic Arithmetic Program to verify circuit computation
Our goal is to devise a set of polynomials that simultaneously encode all of the constraints, so that we can verify the satisfiability thereof with a single check on the polynomials instead of a check over each constraint. The clever trick is to build the polynomials in a way that they can generate all of the constraints.
The QAP itself is made up of 3 polynomial vectors:
𝑃𝐴,𝑃𝐵,𝑃𝐶 $PA,PB,PC$𝑍 $Z$.
corresponding to the linear combinations of the same name in the R1CS
plus one polynomial
Given fixed values
(𝑐1,…,𝑐5) $({c}_{1},\dots ,{c}_{5})$
we use them as coefficients to define a left, right, and output “sum” polynomials.
We want to show that our created QAP has a legal assignment,
From our example above each multiplication gate X has an associated target point in the field𝔽𝑝 ${\mathbb{F}}_{p}$ . In our example, they will be 1 and 2.
• Each wire (in our example, there are 5) has an associated left, right and
output polynomials: .
• Each polynomial evaluates to either 0 or 1 on the target points. If the polynomial is “related” to the multiplication gate associated with a target point, then it evaluates to 1. Otherwise to 0.
The important thing to retain is that since we have d constraints we can compute a polynomial of degree at most d1 for each entry in the linear combination. And this defines the main part of the QAP:𝑃𝐴,𝑃𝐵,𝑃𝐶 $PA,PB,PC$ polynomial vectors.
the
Z Polynomial
Z is defined as the polynomial that is 0 exactly at the points we chose above,𝑟1 ${r}_{1}$ to 𝑟𝑑 ${r}_{d}$.
Z is defined as (x  1) * (x  2) * (x  3) …  the simplest polynomial that is equal to zero at all points that correspond to logic gates. It is an elementary fact of algebra that any polynomial that is equal to zero at all of these points has to be a multiple of this minimal polynomial, and if a polynomial is a multiple of Z then its evaluation at any of those points will be zero;
Now, it is a property of Algebra that a polynomial is equal to the product of linear terms of its roots and a scalar. What this means is that if a polynomial has zeroes at points r1, r2, …, rd, then it can be written as
P(z) = (z  r1) (z  r2) … (z  rd) H(z),
where H(z) is some other polynomial that represents the other places at which P is 0. Now, notice the similarity with our chosen Z(z) polynomial:
Every polynomial P that is 0 at least for the points associated with all the constraints will be necessarily a multiple of Z(z), and can be written as
P(z) = Z(z) * H(z)
We converted a set of vectors into polynomials that generate them when evaluated at certain fixed points. We used these fixed points to generate a vanishing polynomial that divides any polynomial that evaluates to 0 at least on all those points. We created a new polynomial that summarizes all constraints and a particular assignment, and the consequence is that we can verify all constraints at once if we can divide that polynomial by the vanishing one without remainder. This division is complicated, but there are methods (the Fast Fourier Transform) that can perform if efficiently.
From http://coderserrand.com/howtobuildaquadraticarithmeticprogram/
Zero Knowledginess
Blind evaluation of a polynomial using Homomorphic Hiding
Suppose Alice has a polynomial P of degree d , and Bob has a point𝑠∈𝔽𝑝 $s\in {\mathbb{F}}_{p}$ that he chose randomly.
Bob wishes to learn E(P(s)), i.e., the HH of the evaluation of P at s
Two simple ways to do this are:
Alice sends P to Bob, and he computes E(P(s))by himself.
Bob sends s to Alice; she computes E(P(s)) and sends it to Bob.
However, in the blind evaluation problem we want Bob to learn E(P(s)) without learning P
which precludes the first option; and, most importantly,
we don’t want Alice to learn s, which rules out the second
Using HH, we can perform blind evaluation as follows.
E(P(s)) to Bob. (Alice can do this since E supports linear combinations, and P(s)is a linear combination of 1,s,…,sd.)
Note that, as only hidings were sent, neither Alice learned s nor Bob learned P
The rough intuition is that the verifier has a “correct” polynomial in mind, and wishes to check the prover knows it. Making the prover blindly evaluate their polynomial at a random point not known to them, ensures the prover will give the wrong answer with high probability if their polynomial is not the correct one. This, in turn, relies on the SchwartzZippel Lemma stating that “different polynomials are different at most points”.
but
the fact that Alice is able to compute E(P(s)) does not guarantee she will indeed send E(P(s)) to Bob, rather than some completely unrelated value.
Remember our QAP Q of degree d and size m consists of polynomials L1,…,Lm, R1,…,Rm, O1,…,Om and a target polynomial T of degree d.
An assignment (c1,…,cm) satisfies Q if, defining
𝐿:=∑𝑚𝑖=1𝑐𝑖⋅𝐿𝑖,𝑅:=∑𝑚𝑖=1𝑐𝑖⋅𝑅𝑖,𝑂:=∑𝑚𝑖=1𝑐𝑖⋅𝑂𝑖 $L:=\sum _{i=1}^{m}ci\cdot Li,R:=\sum _{i=1}^{m}ci\cdot Ri,O:=\sum _{i=1}^{m}ci\cdot Oi$ and P:=L⋅R−O, we have that T divides P.
Our process then becomes
Alice chooses polynomials L,R,O,H of degree at most d
Bob chooses a random point s ∈𝔽𝑝 ${\mathbb{F}}_{p}$, and computes E(T(s))
Alice sends Bob the hidings of all these polynomials evaluated at s, i.e. E(L(s)),E(R(s)),E(O(s)),E(H(s))
Bob checks if the desired equation holds at s. That is, he checks whether E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s)).
Furthemore we use
For details of these see : https://z.cash/blog/snarkexplain6/
Other Projects
From the useful
https://github.com/gluk64/awesomezeroknowledgeproofs
Starks
ZeroKnowledge (ScalableSuccint) Transparent Arguments of Knowledge
zkSTARKs were created by EliBen Sasson, a professor at the TechnionIsrael Institute of Technology.
They generally, considered a more efficient variant of the technology  potentially faster, but the proof size is much greater.
Trusted Setup
In zkSTARKs, there is no external trusted setup phase and the randomness used is public information.
Vitalik’s Blog Articles
The STARK paper
libSTARK
More resources available at starkware.co
Bulletproofs
https://crypto.stanford.edu/bulletproofs/
https://eprint.iacr.org/2017/1066.pdf
Aim to prove that asecret committed value lies in a given interval.
Bulletproofs require no trusted setup. However, verifying a bulletproof is more time consuming than verifying a SNARK proof.
They rely only on the discrete logarithm assumption, and are made noninteractive using the FiatShamir heuristic
a general dropin replacement for Sigmaprotocols.
Bulletproofs shrink the size of the cryptographic proof from over 10kB to less than 1kB. Moreover, bulletproofs support proof aggregation, so that proving that m transaction values are valid adds only O(log(m)) additional elements to the size of a single proof.
They concentrate on confidential transactions, but can be for general NP langs
The proof size islogarithmicin the numberof multiplication gates in the arithmetic circuit for verifying a witness. The proofs are much shorter than zkSNARK and allow inputs to be Pedersen commitments to elements of the witness.
The high level idea of this proving system is that
DIZK
Dizk Repo
Dizk Paper
DIZK provides Javabased implementations using Apache Spark [Apa17] for:
ZCash links
Home
Zcash deep dive
Explaining Snarks Series
Rollup
Repo
Libraries and toolkits
There is a problem that the various libraries aren’t standardised.
libsnark
Bellman
jsnark  Java bindings to libsnark
snarkjs
Snarky
Zokrates
Ethsnarks
Circom  circuit compiler
Useful Resources
Blogs
http://coderserrand.com/zeroknowledgeproofsalaymansintroduction/
https://blog.decentriq.ch/zksnarksprimerpartone/
http://coderserrand.com/zksnarksandtheiralgebraicstructure/
Talks from the last workshop
Additional Reading
Hackathon projects