# christianlundkvist/libsnark-tutorial

Tutorial and example code for using libsnark
C++ JavaScript CMake
Latest commit d7d02be Aug 6, 2018
Type Name Latest commit message Commit time
Failed to load latest commit information. depends Jun 26, 2018 src Jul 25, 2018 .gitignore Jun 27, 2018 .gitmodules Jun 26, 2018 CMakeLists.txt Jun 27, 2018 LICENSE Jun 13, 2018 README.md Aug 6, 2018

# libsnark tutorial

By Christian Lundkvist and Sam Mayo

This is a tutorial intended to cover the very basics of the libsnark software library for creating zk-SNARKs. We will demonstrate how to formulate zk-SNARK circuits, create proofs and verify the proofs. We will also cover how to verify proofs in smart contracts on Ethereum.

# Preliminaries

If you are a developer who is completely new to zk-SNARKS I’d recommend reading my previous post that introduces zk-SNARKS from a high level.

For a more in-depth description of how zk-SNARKs work under the hood, please read Vitalik’s excellent three post introduction.

# Quick intro to R1CS

A Rank One Constraint System (R1CS) is a way to express a computation that makes it amenable to zero knowledge proofs. Basically any computation can be reduced (or flattened) to an R1CS. A single rank one constraint on a vector w is defined as

``````<A, w> * <B,w> = <C, w>
``````

Where `A`, `B`, `C` are vectors of the same length as `w`, and `<>` denotes inner product of vectors. A R1CS is then a system of these kinds of equations:

``````<A_1, w> * <B_1,w> = <C_1, w>
<A_2, w> * <B_2,w> = <C_2, w>
...
<A_n, w> * <B_n,w> = <C_n, w>
``````

The vector `w` is called a witness and zk-SNARK proofs can always be reduced to proving that the prover knows a witness w such that the R1CS is satisfied.

# Building & running tests

The repo is set up according to the tutorial by Howard Wu. See that tutorial for more info about how to configure the CMake files etc. We will here just cover the basics.

To install the dependencies:

On Ubuntu 16.04 LTS:

``````sudo apt-get install build-essential cmake git libgmp3-dev libprocps4-dev python-markdown libboost-all-dev libssl-dev
``````

On Ubuntu 14.04 LTS:

``````sudo apt-get install build-essential cmake git libgmp3-dev libprocps3-dev python-markdown libboost-all-dev libssl-dev
``````

``````git clone https://github.com/christianlundkvist/libsnark-tutorial.git
cd libsnark-tutorial
mkdir build && cd build && cmake ..
make
``````

To run the tests go to the `build` directory and run:

``````./src/test
``````

# libsnark components: 1. The Protoboard

In electrical engineering, a protoboard or prototyping board is used to attach circuits and chips to quickly iterate on designs. In the libsnark tool, the protoboard is where our "circuits" (i.e. R1CS and gadgets) will be collected.

The C++ file defining the protoboard is here. We will first show how to add R1CS to the protoboard.

Recall the example in Vitalik’s blog post: We want to prove that we know a value x that satisfy the equation

``````x^3 + x + 5 == 35.
``````

We can make this a little more general, and say that given a publicly known output value `out`, we want to prove that we know `x` such that

``````x^3 + x + 5 == out.
``````

Recall that we can introduce some new variables `sym_1, y, sym_2` and flatten the above equation into the following quadratic equations:

``````x * x = sym_1
sym_1 * x = y
y + x = sym_2
sym_2 + 5 = out
``````

We can verify that the above system can be written as an R1CS with

``````w = [one, x, out, sym_1, y, sym_2]
``````

and the vectors `A_1, ..., A_4, B_1, ..., B4, C_1, ..., C_4` are given by

``````A_1 = [0, 1, 0, 0, 0, 0]
A_2 = [0, 0, 0, 1, 0, 0]
A_3 = [0, 1, 0, 0, 1, 0]
A_4 = [5, 0, 0, 0, 0, 1]
B_1 = [0, 1, 0, 0, 0, 0]
B_2 = [0, 1, 0, 0, 0, 0]
B_3 = [1, 0, 0, 0, 0, 0]
B_4 = [1, 0, 0, 0, 0, 0]
C_1 = [0, 0, 0, 1, 0, 0]
C_2 = [0, 0, 0, 0, 1, 0]
C_3 = [0, 0, 0, 0, 0, 1]
C_4 = [0, 0, 1, 0, 0, 0]
``````

The original degree 3 polynomial equation has a solution `x=3` and we can verify that the R1CS has a corresponding solution

``````w = [1, 3, 35, 9, 27, 30].
``````

Now let’s see how we can enter this R1CS into libsnark, produce proofs and verify them. We will use the `pb_variable` type to declare our variables. See the file `test.cpp` for the full code.

First lets define the finite field where all our values live, and initialize the curve parameters:

``````typedef libff::Fr<default_r1cs_ppzksnark_pp> FieldT;
default_r1cs_ppzksnark_pp::init_public_params();
``````

Next we define the protoboard and the variables we need. Note that the variable `one` is automatically defined in the protoboard.

``````protoboard<FieldT> pb;

pb_variable<FieldT> out;
pb_variable<FieldT> x;
pb_variable<FieldT> sym_1;
pb_variable<FieldT> y;
pb_variable<FieldT> sym_2;
``````

Next we need to "allocate" the variables on the protoboard. This will associate the variables to a protoboard and will allow us to use the variables to define R1CS constraints.

``````out.allocate(pb, "out");
x.allocate(pb, "x");
sym_1.allocate(pb, "sym_1");
y.allocate(pb, "y");
sym_2.allocate(pb, "sym_2");
``````

Note that we are allocating the `out` variable first. This is because libsnark divides the allocated variables in a protoboard into "primary" (i.e. public) and "auxiliary" (i.e. private) variables. To specify which variables are public and which ones are private we use the protoboard function `set_input_sizes(n)` to specify that the first `n` variables are public, and the rest are private. In our case we have one public variable `out`, so we use

``````pb.set_input_sizes(1);
``````

to specify that the variable `out` should be public, and the rest private.

Next let's add the above R1CS constraints to the protoboard. This is straightforward once we have the variables allocated:

``````// x*x = sym_1

// sym_1 * x = y

// y + x = sym_2

// sym_2 + 5 = out
``````

Now that we have our circuit in the form of R1CS constraints in the protoboard we can run the Generator and generate proving keys and verification keys for our circuit:

``````const r1cs_constraint_system<FieldT> constraint_system = pb.get_constraint_system();

r1cs_ppzksnark_keypair<default_r1cs_ppzksnark_pp> keypair = r1cs_ppzksnark_generator<default_r1cs_ppzksnark_pp>(constraint_system);
``````

Note that the above is the so-called "trusted setup". We can access the proving key through `keypair.pk` and the verification key through `keypair.vk`.

Next we want to generate a proof. For this we need to set the values of the public variables in the protoboard, and also set witness values for the private variables:

``````pb.val(out) = 35;

pb.val(x) = 3;
pb.val(sym_1) = 9;
pb.val(y) = 27;
pb.val(sym_2) = 30;
``````

Now that the values are set in the protoboard we can access the public values through `pb.primary_input()` and the private values through `pb.auxiliary_input()`. Let's use the proving key, the public inputs and the private inputs to create a proof that we know the witness values:

``````r1cs_ppzksnark_proof<default_r1cs_ppzksnark_pp> proof = r1cs_ppzksnark_prover<default_r1cs_ppzksnark_pp>(keypair.pk, pb.primary_input(), pb.auxiliary_input());
``````

Now that we have a proof we can also verify it, using the previously created `proof`, the verifying key `keypair.vk` and the public input `pb.primary_input()`:

``````bool verified = r1cs_ppzksnark_verifier_strong_IC<default_r1cs_ppzksnark_pp>(keypair.vk, pb.primary_input(), proof);
``````

At this stage the boolean `verified` should have the value `true`, given that we put in the correct values for the witness variables. The libsnark library uses gadgets to package up R1CS into more manageable pieces and to create cleaner interfaces for developers. They do this by being a wrapper around a protoboard and handling generating R1CS constraints and also generating witness values.

We're going to show how to create a gadget for the example R1CS above in order to make it a bit more manageable.

First we create a new file `src/gadget.hpp` which contains the gadget file. In our case we want the developer using the gadget to be able to set the public variable `out`, as well as the private witness variable `x`, but the gadget itself would take care of the intermediate variables `y`, `sym_1` and `sym_2`.

Thus we create a class `test_gadget`, derived from the base `gadget` class which has the variables `y`, `sym_1` and `sym_2` as private members (in the C++ sense). The variables `x` and `out` will be public class member variables.

In the following sections we go over the functions of this gadget and how to use it.

## Constructor

As any gadget, the constructor takes as input a protoboard `pb`. We also have `pb_variable` inputs `x` and `out`. We assume that the user of the gadget has already allocated `x` and `out` to the protoboard.

The constructor then allocates the intermediate variables to the protoboard:

``````sym_1.allocate(this->pb, "sym_1");
y.allocate(this->pb, "y");
sym_2.allocate(this->pb, "sym_2");
``````

## Function `generate_r1cs_constraints()`

This function adds the R1CS constraints corresponding to the circuits. These are the same constraints as we added manually earlier, just bundled up inside this function.

## Function `generate_r1cs_witness()`

This function assumes that we've already set the public value `out`, and the witness value `x`. It then computes the inferred witness values for the intermediate variables `sym_1`, `y`, `sym_2`. Thus the user of the gadget never needs to worry about the intermediate variables.

In the file `src/test-gadget.cpp` we can see how the gadget it used. This file is very similar to the file in the previous section. We start as before by generating curve parameters. After this we initialize the protoboard, and allocate the variables `out`, `x` to the protoboard:

``````protoboard<FieldT> pb;
pb_variable<FieldT> out;
pb_variable<FieldT> x;

out.allocate(pb, "out");
x.allocate(pb, "x");
``````

After this we specify which variables are public and which are private (in the zk-SNARK sense). This would be `out` as the only public variable and the rest as private variables. We also create a new `test_gadget`:

``````pb.set_input_sizes(1);
``````

Next generate the R1CS constraints by simply calling the corresponding function:

``````g.generate_r1cs_constraints();
``````

Now we add the witness values. We add the value 35 for the public variable `out` and the value 3 for the witness variable `x`. The rest of the values will be computed inside the gadget:

``````pb.val(out) = 35;
pb.val(x) = 3;
g.generate_r1cs_witness();
``````

That's it! Now we can run the Generator to generate proving and verification keys, create the proof and verify it as we did before.

# Verifying proofs on Ethereum

One of the exciting recent developments around zk-SNARKs is that it is now possible to verify a zk-SNARK proof in a smart contract on Ethereum. This opens up the possibility of private transactions and the ability to verify large computations on the blockchain.

Now that we have an example circuit, let's see how we can create a Solidity smart contract to generate proofs for that circuit on Ethereum.

## Serializing verification keys and proofs

First we need to extract the verification keys and proofs from libsnark in a way that can be consumed by Solidity smart contracts. In the file `src/util.hpp` we demonstrate how to serialize the information from the objects `r1cs_ppzksnark_verification_key` and `r1cs_ppzksnark_proof` and write that information to a file in the form of field elements that can be interpreted as `uint` types in Solidity.

We won't go into detail here about the meaning of the values `A`, `B`, `C` etc in the proof data but check out Vitalik's blog post to learn more. The main thing to illustrate is that these values are elliptic curve points and hence will be represented by two elements of the underlying field. The curve points of type `G1` has field elements that can be represented by one `uint` type, but the curve points of type `G2` has field elements that are represented by two `uint` types.

Thus each `G1` point is serialized into two integers and each `G2` point is serialized into four integers. When running the executable `./src/test-gadget` from within the build directory two files will be created: `proof_data` and `vk_data` containing the corresponding data in the form of integer values.

## Using verification keys and proofs in Solidity

We first take a look at the Solidity file `src/ethereum/contracts/Verifier.sol` which contains the verification code. This file has two important functions: `setVerifyingKey()` sets the verification key that will be used when verifying a proof and `verifyTx()` submits the proof along with the public inputs and returns `true` if the proof verifies. It is common to hardcode the verification key into the smart contract to save gas - for instance ZoKrates does this - but to simplify testing we use a setter function instead.

To see how to use the verifier smart contract from JavaScript, take a look at the test located at `src/ethereum/test/TestVerifier.js`. This file shows how to read the verification key and the proof from the files, set the verification key in the smart contract and call the smart contract to verify a proof.

Note the inputs to the function `verifyTx()` - the first inputs are the values making up the proof in the form of points of type `G1` - represented by a pair of integers, or points of type `G2` represented by a pair of integer pairs (i.e. four integers). The last input is a list of integers corresponding to the public inputs. In our case we have only one public input, the value 35 for the `out` variable which corresponds to a list with one element, ``.

## The ZoKrates tool

The software library ZoKrates builds on libsnark and aims to make it a lot easier to create circuits and verify them on Ethereum by using a domain specific language and automatically creating the required smart contracts from the verification keys. You can read more about it on their github repo.

# Conclusion

The libsnark zk-SNARK library is a powerful library for defining circuits, generating & verifying proofs, but it can be hard to get a sense of how to use it in practice. This tutorial aims to provide a sense of the high-level components of libsnark and how to use it concretely, as well as how to connect the proofs to Ethereum smart contracts.

You can’t perform that action at this time.