zk-SNARKs Explained with Bellman
Zero knowledge proofs (ZKP) is one of the the most exciting cryptographic inventions since Public-key cryptography. zk-SNARK is a specific type of ZKP which allows one party (the prover) to convince other parties (the verifiers) that the prover faithfully executed a program with some secret information, without conveying any knowledge about the secret information itself. zk-SNARK also generates succinct (hundreds of bytes) proofs that can be verified within the range of miliseconds even though the original computation might be much larger, which means that other than the obvious privacy benefits, zk-SNARK can also be used to trustlessly outsource expensive computation.
To apply zk-SNARK, a computation needs to be expressed in terms of algebraic circuit, converted to a constraint system called R1CS, and then finally a form called “quadratic arithmetic program” (QAP). The intuition of going through this complex transformation is that:
- A computation can be viewed as series of constraints from the inputs to the outputs, but just expressing a computation in terms of constraints neither make the computation more “succinct” nor make it easier to apply cryptographic algorithms.
- QAP in a way “compresses” those constraints into one using polynomials, a form which is not only more efficient to verify but also more suitable to apply cryptographic protocols such as Pinocchio or Groth16 to achieve soundness, completeness and zero-knowledgeness.
Steps of transformation for zk-SNARK, drawn by Eran Tromer
For more detailed explanations of the QAP transformation, please take a look at
Why and How zk-SNARK works by
Maksym Petkus or Quadratic Arithmetic Programs: from Zero to
by Vitalik Buterin. To use an example in Vitalik’s article, a simple
x³ + x + 5 == 35 can be converted into the following QAP.
QAP for x³ + x + 5 == 35, as in Vitalik’s Quadratic Arithmetic Programs: from Zero to Hero
This article assumes that the readers understand the process of QAP
transformation, specifically why proving
A(τ)*B(τ)-C(τ) = H(τ)*Z(τ)
is important in terms of completenss and soundness. It also assumes
some high level understanding of the elliptic curve
purpose of the article is to explain how zk-SNARK works by walking
through how it is implemented in
Bellman (0.7.0), a rust library
used by the first widespread zk-SNARK application
ZCash. Bellman currently implements the
Groth16 proving system, which
can be roughly divided into three parts: Trusted setup, Prover
and Verifier. This article discusses each part in details.
Trusted setup is a process to create what’s called “Common Reference String” (CRS) between provers and verifiers. CRS are basically encrypted secrets that are required by both provers and verifiers to run the cryptographic protocols (e.g. Groth16) in zk-SNARK. Verifiers need to trust that the original secrets (a.k.a toxic waste) are destroyed after the setup process, otherwise the entire proof system breaks down.
First, let’s define some parameters for a computation. We can use
to denote its number of variables,
l of which are public. Take
x + 5 = 35 as an example where the solution 3 is the secret. This
program can be broken up into the following 3 constraints in the form
A * B = C:
There are 4 variables in total (i.e.
out), among which
out has a publicly known value of 35. Therefore
l should be 4 and 1 respectively.
Another important parameter for the computation is the number of
n, which determines the target polynomial
Z(x). In the
above example, the value of
n should be 3.
Assuming that the program is converted to the QAP form, which means that
we know the variable polynomials
Cᵢ(x). If the prover knows the value of all variables
(both the public ones and secret ones), then ultimately (s)he wants to prove the
following statement in such a way that reveals nothing about the secret
portion of wᵢ:
Groth16 protocol is way to achieve that. It requires two
paring friendly curves:
G2 (with the paring domain
GT). During the trusted setup, the first thing it does is to select
one random point on each curve:
Next, it generates the following 5 random field elements:
δ (delta) and
τ is the secret
value at which all the polynomials are evaluated later on. With
β, it also defines a polynomial
With the information created so far, Groth16 generates the
G2 points (values encrypted using
g2) for the prover:
For the verifier, the following points on
G2 are created,
along with a pre-computed value
g₁ᵅ * g₂ᵝ using elliptic curve
Including g₁ᵅ * g₂ᵝ in CRS improves the verification performance since
it is needed every time a proof is verified.
After all these information is created, it is mandatory that random
τ (a.k.a toxic waste) are
destroyed. In the Prover and Verifier section, we will discuss
how these information is used by both the prover and verifier in such
a way that the prover can convince the verifier that
A(x) * B(x) - C(x) = H(x) *
Z(x) is valid without revealing any secrets. For now let’s take a look
at how trusted setup is implemented in Bellman.
The code that implements trusted setup in Bellman is located in
function. The code that
τ is pretty straightforward.
In Bellman, a computation is expressed in “circuits” using the
x³ + x + 5 = 35, which has the following
We can express the 2nd constraint
x_squared * x = x_cubed in bellman like this:
cs in the example above is an instance of a
the trusted setup, circuits are converted to QAP using the
is called to allocate a variable, an empty vector is pushed to
respectively. The index of the empty vector is used to keep track of
the newly allocated variables.
These empty vectors is used to store a sequence of
constraint_number) tuple for each variable, basically
where (which constraint) and how (what coefficient) a particular
variable is used in the
function ensures that a sequence of these tuples is stored correctly for
After the circuit is
with KeypairAssembly (basically all the
the circuit are executed), what we end up with is
essentially the lagrange representation of the public variable
polynomials stored in
secret variable polynomials in
ct_aux. We now
Recall that we also need τⁱ (i in 0..n-1) as both G1 and G2 points in
the trusted setup. This is called powers of tau, which is important
for evaluating polynomials blindly at value τ. Further more, we need
τⁱZ(τ)/δ as well where
Z(x) is the target polynomial.
This is how powers of tau is calculated in bellman:
coeff is later on
with powers of tau to get
The last values we want to create during the trusted setup is
for public variables and
Lᵢ(τ)/γ for secret variabes where
Lᵢ(x) = β * Aᵢ(x) + α * Bᵢ(x) + Cᵢ(x) as we discussed
earlier. Since we already know
at this point, we basically need to evaluate
Lᵢ(x) polynomial at the
τ. This is where powers of tau (τⁱ) comes in handy. Let’s
Lᵢ(x) is in the form of
a*xᵘ+ b*xᵛ + c*xʷ, we just need to
find the corresponding τᵘ, τᵛ and τʷ to calculate
Lᵢ(τ) = a*τᵘ+
b*τᵛ + c*τʷ. Since
τⁱ is determined by the number of
constraints, we should have all the
τⁱ needed for the evaluation.
Lᵢ(τ)/δ is calculated at
τ in Bellman, specifically:
As we can see, in order to evaluate
Lᵢ(τ), we need to evaluate
Cᵢ(τ) as well. If we think about it,
Cᵢ(τ) are the lagrange representation of
C(x). Prover only needs the secret
variable portion of the
Lᵢ(τ), verifier only needs the public
variable portion of the
Lᵢ(τ). Here is the
which is created
at the end of the trusted setup for the verifier:
Finally at this point, we have created all the parameters we need, here are all the Parameters that the trusted setup process returns:
The prover knows the value of all
m variables in the computation,
both public input variables (
l in total) and secret auxiliary
m-l in total). These variables can be represented by
wᵢ represents input (public)
i is between
wᵢ represents auxiliary
(secret) variables. With this knowledge, the prover wants to
construct three values: Aₚ, Bₚ and Cₚ, as defined below:
s are randomly generated field elements by the prover.
With Aₚ, Bₚ and Cₚ, the verifier can somehow verify that the statement
A(τ)*B(τ) - C(τ) = H(τ)*Z(τ) is valid and therefore confirm that the
prover had executed the computation faithfully without revealing the
auxiliary variables. We will break down how this is achieved later
when we discuss verifiers. For now, let’s focus on how the prover
constructs Aₚ, Bₚ and Cₚ.
From the trusted setup, the prover knows the
δ. The prover also knows the “computation”, which is
expressed as R1CS circuit and then converted to Quadratic Arithmetic
Concretely, the QAP program is expressed using
Also remember that
H are defined in terms of
T, as follows
Knowing the value of all variables
wᵢ, the prover has everything
needed to construct Aₚ, Bₚ and Cₚ.
The prover code in bellman is in located in prover.rs, specifically the create_proof function.
First of all, the circuit is synthesized using the ProvingAssignment data structure, which is also a type of ConstraintSystem.
is called, the actual value of the variable is pushed to
aux_assignment vector respectively. Variables
are tracked by their position (index) in those vectors.
is called, it evaluates
C for each operation (in the
A*B=C) using the variable values in
aux_assignment. The evaluation results are pushed to
vectors respectively. After the entire circuit is
c essentially becomes the lagrange representation of
Aₚ is relatively easy to create, it is equal to
α + A(τ) + r*δ
Bₚ is computed in a very similiar
is more interesting is Cₚ since it involves a more complex
H(τ)*(Z(τ)/δ) expression. Recall that H(τ) is basically
(A(t) * B(t) - C(t)) / Z(t) and
Z(x) is the target polynomial that
is publicly known. Here is how
h in the code):
Now the prover knows H(τ)*(Z(τ)/δ), it becomes a bit easier to computed Cₚ:
As we can see in the code, Cₚ is actually computed as
L_aux(τ)/δ + H(τ)*(Z(τ)/δ) + r*B(τ) + s*A(τ) + r*s*δ + s*α + r*β,
which is in fact equivalent to
L_aux(τ)/δ + H(τ)*(Z(τ)/δ) + s*Aₚ + r*Bₚ - r*s*δ. Here is why:
At this point, Aₚ, Bₚ and Cₚ are computed and prover completes the proof.
The goal of the verifier is to take the proof from the prover, i.e. Aₚ, Bₚ and Cₚ, and verify that the following equation holds:
To see what exactly does it mean if this equation holds, we can try to expand on both the left hand side (LHS) and the right hand side (RHS) of the equation.
Aₚ*Bₚ is equivalent to
A(τ)*B(τ) + REM:
Click here to see a more detailed deduction
α*β + (L_input/γ)*γ + Cₚ*δ is equivalent to
C(τ) + H(τ)*Z(τ) + REM:
Click to see a more detailed deduction
If we can prove
LHS = RHS, then after removing
REM on both sides,
we also proved that
A(τ)*B(τ)-C(τ) = H(τ)*Z(τ), which is the end
goal of the verifier! Once this is valid, the verifier is confident
that the program is executed faithfully with correct values of the
The verification code in Bellman is located at
explained by the comments, the original equation
Aₚ*Bₚ = α*β + (L_input(τ)/γ)*γ + Cₚ*δ is converted to
Aₚ*Bₚ + (L_input(τ)/γ)*(-γ) + Cₚ*(-δ) = α*β, which only requires one
final exponentiation (verifier.rs:44).
E::miller_loop functions are two
steps needed to compute the elliptic curve
The paring of
pvk.alpha_g1_beta_g2) is already pre-computed in
the setup phase.
In this article, we walked through how zk-SNARK with Groth16 protocol is implemented in Bellman, which actually powers a nearly 1 billion dollar cryptocurrency (at the time of writing). Instead of just relying on government regulations and the mercy of big internet companies, I hope zk-SNARK and ZKP in general can be part of the solution for our privacy issues in the future.