iden3.io

Identities of the future run on iden3

@identhree

Create your first zero-knowledge snark circuit using circom and snarkjs

Posted by Sacha Saint-Leger on April 17, 2020

In this tutorial we’ll guide you through the creation and execution of your first zero-knowledge proof using our circom and snarkjs libraries.

We assume as little background knowledge as possible and do our best to explain the relevant concepts from first-principles.

Let’s start with the basics.

Zero-knowledge basics

What’s a zero-knowledge proof?

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. Source

Zero-knowledge proofs allow us to prove something specific about ourselves without revealing any additional information.

On a philosophical level, they are part of a set of new cryptographic tools that show that transparency does not have to be in conflict with privacy.

What’s a zk-snark?

The term zk-snarks stands for zero-knowledge succinct non-interactive arguments of knowledge.

You don’t need to understand what that means. You can simply think of zk-snarks as efficient (or succinct) ways to produce a zero-knowledge proofs: proofs that are short enough to publish to a blockchain, and that can be read later by anyone who has permission to verify them (what we call a verifier).

A few examples

ICO participation

Say an ICO (initial coin offering) is only available to KYC or authorized users. With zk-snarks you can prove that you are an authorized person to participate in the ICO without revealing who you are, or how much you spent.

Anonymous Voting

Similar to the above, you can prove you are eligible to vote without revealing your sex, age, or even your name.

For example, you could vote in a national election while only revealing that you are a citizen of that country, and over 18 years old.

Covid-19 tests

You could use zk-snarks to prove that you’ve recently tested negative for Covid-19 without revealing the exact date you were tested, or the lab/hospital in which you were tested: you only reveal that you were tested within a requested window of time, at an officially recognised location; nothing more.

Libraries

We’ll be making use of two libraries: circom and snarkjs.

Circom is a library that makes it easy to build algebraic circuits.

While snarkjs is an independent implementation of the zk-snarks protocol – fully written in JavaScript.

These libraries are designed to work together: any circuit you build in circom can be used in snarkjs.

Why do we need circuits?

zk-snarks can’t be applied to any computational problem directly. The problem first needs to be converted into the right form. The first step is to convert it into an algebraic circuit.

Although it may not always be obvious how to do it, it turns out that most computational problems we care about can be converted into algebraic circuits.

zk-snark pipeline, drawn by Eran Tromer


Now that we’ve covered the basics, we’re ready to dive in.

In the following steps, we’ll cover the various techniques to write circuits, and show you how to create and verify proofs off-chain and on-chain on ethereum.

1. Installing the tools

1.1 Pre-requisites

First off, make sure you have a recent version of Node.js installed.

While any version after 8.12.0 should work fine, we recommend you install version 10.12.0 or later.

Why? These later versions of Node include native big integer libraries. snarkjs makes use of this feature (if available) to improve performance by up to 10x.

If you’re not sure which version of Node you have installed, you can run:

node -v

To download the latest version of Node, click here.

1.2 Install circom and snarkjs

To install circom and snarkjs run:

npm install -g circom
npm install -g snarkjs

Hopefully both libraries installed successfully.

If you’re on a Unix machine and you’re seeing an error that contains the phrase node-gyp rebuild it’s probably because you need to update your version of Node to the latest long term support (LTS) version, at the time of writing this is v10.15.3.

If you’re seeing one or more errors that look like:

EACCES: permission denied

It’s probably because you originally installed Node with root permissions. Because of this, writing to your npm directory (npm install -global) requires root permissions too.

To get around this quickly, run the slightly modified commands:

sudo npm install -global --unsafe-perm circom
sudo npm install -global --unsafe-perm snarkjs

To get around this the proper way, follow the steps outlined here.

2. Building a circuit

Now that we’ve installed circom and snarkjs, let’s build a circuit that proves to someone that we’re able to factor an integer c.

Specifically, let’s build a circuit that allows us to prove that we know two numbers (call them a and b) that multiply together to give c, without revealing a and b.

Before we start, let’s define what we mean by a circuit.

For our purposes, a circuit is equivalent to a statement or deterministic program which has an output and one or more inputs.

There are two types of possible inputs to a circuit: private and public. The difference being that a private input is hidden from the individual who is verifying the truthfulness of the statement (the verifier).

The idea here is that given a circom circuit and its inputs, we can run the circuit and generate a proof – using snarkjs – that we ran it correctly.

With the proof, the output, and the public input(s), we can then prove to someone (the verifier) that we know one or more private inputs that satisfy the constraints of the circuit, without revealing anything about the private input(s).

In other words, even though the verifier has zero knowledge about the private inputs to the circuit, the proof, the output, and the public inputs(s) will be enough to convince her that our statement is valid (hence the term zero-knowledge proof).

Now that we know what a circuit is and why it’s useful, let’s start by designing one.

2.1 Design the circuit

  1. Create (and move into) a new directory called factor where we’ll put all the files that we want to use in this guide.
mkdir factor
cd factor
  1. Create a new file named circuit.circom with the following content:
   template Multiplier() {
       signal private input a;
       signal private input b;
       signal output c;
       
       c <== a*b;
   }
   component main = Multiplier();

The purpose of this circuit is to allow us to prove to someone that we’re able to factor an integer c. Specifically, using this circuit we’ll be able to prove that we know two numbers (a and b) that multiply together to give c, without revealing a and b.

As you can see, this circuit has two private input signals named a, and b and one output signal named c.

The inputs and the outputs are related to each other using the <== operator. In circom, the <== operator does two things. The first is to connect signals. The second is to apply a constraint.

In our case, we’re using <== to connect c to a and b and at the same time constrain c to be the value of a*b.

2.2 Compile the circuit


We’re now ready to compile the circuit. To do this, run the following command:

circom circuit.circom --r1cs --wasm --sym

As you can see, the circom command takes one input (the circuit to compile, in our case circuit.circom) and three options:

  • --r1cs: generates circuit.r1cs (the r1cs constraint system of the circuit in binary format).

  • --wasm: generates circuit.wasm (the wasm code to generate the witness – more on that later).

  • --sym: generates circuit.sym (a symbols file required for debugging and printing the constraint system in an annotated mode).

While you don’t need to know what it is, or how it works, r1cs (or rank-1 constraint system) is the first step in converting an algebraic circuit into a zk-snark.

3. Taking the compiled circuit to snarkjs

Now that the circuit is compiled, we can use it in snarkjs to create a proof.

To see a list of all snarkjs commands, as well as descriptions about their inputs and outputs, run snarkjs --help from the command line.

3.1 View information about the circuit

To start with, let’s have a look at some of the information circuit.r1cs gives us.

From the command line run:

snarkjs info -r circuit.r1cs

You should see the following output:

# Wires: 4
# Constraints: 1
# Private Inputs: 2
# Public Inputs: 0
# Outputs: 1

This information fits with our mental map of the circuit we designed. Remember, we had two private inputs a and b, and one output c. And the one constraint we specified was that a * b = c.

To double check, you can print the constraints of the circuit by running:

snarkjs printconstraints -r circuit.r1cs -s circuit.sym

You should see the following output:

[  -1main.a ] * [  1main.b ] - [  -1main.c ] = 0

Don’t worry if this looks a little strange. You can ignore the 1main prefix and just read this as:

(-a) * b - (-c) = 0

Which, if you rearrange the equation, is the same as a * b = c.

3.2 Setup using snarkjs

The first step in generating a zero-knowledge proof requires what we call a trusted setup.

While explaining exactly what this is is beyond the scope of this guide, let’s try and develop some intuition for why we need it, without formally defining it.

The need for a trusted setup boils down to the fact that the balance between privacy for the prover, and assurance of not cheating for the verifier, is delicate.

To maintain this delicate balance, zero-knowledge protocols require the use of some randomness.

Usually, this randomness is encoded in the challenge the verifier sends to the prover, and serves to prevent the prover from cheating.

The randomness however can’t be made public, because it’s essentially a backdoor to generating fake proofs. This implies that a trusted entity should generate the randomness. Hence the term trusted setup.

Now that we have a better intuition for what we are doing, let’s go ahead and create a trusted setup for our circuit (in this case, we’ll also play the role of the trusted entity).

From the command line, run:

snarkjs setup -r circuit.r1cs

This will generate both a proving and a verification key in the form of two files: proving_key.json and verification_key.json.

3.3 Calculating a witness

Before creating the proof, we need to calculate all the signals that match the constraints of the circuit.

This set of signals is called the witness.

Why do we need a witness?

Remember, in a zk-proof, the prover needs to prove to the verifier that she knows a set of signals that match all the constraints of the circuit, without revealing any of the private inputs. This set of signals is what we call the witness.

Importantly, the witness is kept secret from the verifier. It’s only used by the prover to generate the proof that she knows the set of signals contained in the witness (including the private ones).

What do we need to calculate it?

Recall that in step 2.2, we generated a circom.wasm file that contained the wasm code to generate the witness.

We need this along with a file – let’s call it input.json – containing the inputs to the circuit.

Once we have these two files we’ll use snarkjs’s calculatewitness command to calculate the witness for us.

The calculatewitness command feeds the inputs from input.json into circuit.wasm, which executes the circuit, calculating (and keeping track) of all the intermediate signals and the final output.

This set of signals – the input, the intermediate signals, and the output – is the witness.

In our case, we don’t have any intermediate signals because we just have one constraint, a * b = c, so the witness is just the inputs a and b, and the output c.

For example, imagine that we want to prove that we are able to factor 33. We need to prove that we know two numbers a and b that multiply to give 33.

Since the only two (non-trivial) numbers that multiply to give 33 are 3 and 11, let’s create a file named input.json, with the following content:

{"a": 3, "b": 11}

Now, run the following command to calculate the witness:

snarkjs calculatewitness --wasm circuit.wasm --input input.json

You should see that a witness.json file has been created with all of the relevant signals.

If you open it up, you’ll see the following:

[
 "1",
 "33",
 "3",
 "11"
]

Where 33 is the output, and 3 and 11 are the inputs we defined in input.json.

In addition to the output, inputs, intermediate signals, you should see that the witness contains a dummy variable 1 at the beginning (the first entry of the array). To understand why this 1 is needed requires diving deep into the details of zk-proofs and as such is beyond the scope of this post. If you’re curious, see this post by Vitalik.

You might have noticed that there’s nothing about the circuit that prevents us from setting a = 1 and b = 33. We will deal with this problem later.

3.4 Create the proof

Now that we’ve generated the witness, we’re ready to create the proof.

To create the proof, run:

snarkjs proof --witness witness.json --provingkey proving_key.json

This will generate the files proof.json and public.json: proof.json contains the actual proof, whereas public.json contains the values of the public inputs and outputs – in our case just 33.

3.5 Verify the proof

In practice at this stage you would hand over both the proof.json and public.json files to the verifier.

For the purposes of this tutorial, however, we’re going to play the role of the verifier too.

With both the proof, and the public input and outputs, we can now prove to the verifier that we know one or more private signals that satisfy the constraints of the circuit, without revealing anything about those private signals.

From the verifier’s point of view, she can verify that we know the set of private signals contained in the witness – without ever having access to it. This is the core of the magic behind zk-proofs!

More formally, with proof.json the verifier is able to check that the prover knows a witness with public inputs and outputs that match the ones in public.json.

Since we’re playing the role of the verifier, let’s verify the proof:

snarkjs verify --verificationkey verification_key.json --proof proof.json --public public.json

You should see that OK has been outputted to your console. This signifies the proof is valid. If the proof were invalid, you would have seen INVALID instead.

You can check this by creating a new file called public-invalid.json with 34 as the public output instead of 33.

[
 "34"
]

And running:

snarkjs verify --verificationkey verification_key.json --proof proof.json --public public-invalid.json

You should see that the output of this command is now INVALID.

3.6 Bonus

At the end of section 3.3 we noted that there’s nothing preventing us from using a = 1 and b = c (or vice-versa) to satisify the constraints of the circuit, for any c.

We can fix this by adding some extra constraints to our circuit.

The trick here is to use the property that 0 has no inverse. This insight allows us to do the following:

If we want to prevent a or b from being set to 1 we add constraints that prevent a-1 and b-1 from having an inverse.

Since the inverse of a-1 is 1/(a-1), with the above insight, we can modify the circuit.circom as follows:

   template Multiplier() {
       signal private input a;
       signal private input b;
       signal output c;
       signal inva;
       signal invb;
       
       inva <-- 1/(a-1);
       (a-1)*inva === 1;
       
       invb <-- 1/(b-1);
       (b-1)*invb === 1;    
       
       c <== a*b;
   }
   component main = Multiplier();

And voila! That’s all there is to it :)

A couple of points on notation

You may have noticed that we introduced two new operators, <-- and ===.

<-- assigns a value to a signal without adding a constraint. Whereas === adds a constraint without assigning a value.

As we saw earlier, <== both assigns a value to a signal and adds a contraint. Which means it’s just the combination of === and <--. But since it isn’t always desirable to do both in the same step, the flexibility of circom allows us to split this step into two.

Final thoughts

It turns out there’s still a subtle problem with our circuit: since the operations take place over a finite field (Z_r), we need to guarantee that the multiplication doesn’t overflow. Luckily, we can do this by converting the inputs to binary format and checking the ranges. Don’t worry if that didn’t make much sense to you, we’ll cover this in a future tutorial!

4. Proving on-chain

As a final step, we’ll convert our proof into the right format, and publish it on-chain.

4.1 Generate a solidity version of the proof

We can use snarkjs generateverifier to generate a Solidity smart contract that verifies the zero knowledge proof.

Smart contracts are computer programs that are executed inside a peer-to-peer network, like ethereum. And Solidity is one of the most popular languages for writing smart contracts on ethereum.

From the command line run:

snarkjs generateverifier --verificationkey verification_key.json --verifier verifier.sol

As you can see, generateverifier takes a verification key as input – in our case verification_key.json – and generates a solidity version of the verifier in a file of our choice(verifier.sol).

4.2 Publish the proof

To publish the proof, we can upload verifier.sol directly into Remix.

Remix is an open source tool that helps you write (and publish) Solidity contracts straight from the browser. If this is your first time using it, have a look through this tutorial before continuing.

If you take a look inside verifier.sol you should see that it contains two contracts: Pairings and Verifier. For our purposes, we just need to deploy the Verifier contract.

Note: You may want to use a test net like Rinkeby, Kovan or Ropsten to avoid spending real money. You can also use the Javascript VM, but in some browsers, the verification takes a long time and it may hang the page.

4.3 Verify the proof

The verifier contract deployed in the last step has a function called verifyProof.

It takes as input four parameters and returns true if the proof and the inputs are valid.

To generate these parameters, run:

snarkjs generatecall --proof proof.json --public public.json

As you can see, generatecall takes two inputs: the zero-knowledge proof you want to use – proof.json – and the public inputs/outputs – public.json.

The output of the command should look something like this:

["0x03953a07c9c509de3372fdb737ad19fb79cd4291a76041172cbc9968b643d94a", "0x20bfda38f8dd6120883944368316a417432397aeef80e0603576a0eebeee23da"],
[["0x126a663a9029248f9f7ac141edee74686ab779d37f19393616919540f9c0949e", "0x09d9d071ffcf82ada05cd90ea3cd0bafc0bbcf29876daf5419800449d266b3ad"],["0x03eb926bc03778a37c4729349ad3f6be028b2a60a857ce4875f08891cd3be383", "0x08b4b648c3a2cc491f6f03b2ec3a797e7a691406b4f6967ee4bb8ec1d0306b59"]],
["0x1af6cf97cc5e672052feb44ba381147528bd9b25fa366f08a69a899f0d251faf", "0x15a911429c0e2c63cb90dd8b09f4f767e40292cf60e4e318a749da8cb601f55b"],
["0x0000000000000000000000000000000000000000000000000000000000000021"]

Note: while snarkjs accepts custom inputs, it also has defaults that make things easy. For example, in the above two steps we could could have simply run snarkjs generateverifier followed by snarkjs generatecall. And snarkjs would have included the inputs we specified, by default. To learn more about the inputs (and defaults) associated with individual commands, run snarkjs --help from the command line.

Next, you’ll need to cut and paste the output of this command into the parameters fields of the verifyProof method in Remix and click on call.

If everything works ok, this method should return true; if you change any bit in the parameters, the result will be verifiably false.

Where to go from here

If you’ve enjoyed this guide and want to deepen your understanding of our tools, we recommend you checkout the circom repository.

You may also be interested in taking a look at circomlib: a library containing useful and reusable circuits implemented in circom.

circomlib contains some useful basic circuits, as well as implementations of the Pederson Hash and Exponentiation circuits using the Baby-Jubjub elliptic Curve.

Final note

From a developer’s point of view, there are few things worse than working with a buggy compiler.

Since the compiler is still in its early stages, if you spend any meaningful time using circom, you should expect to come across bugs.

If you do, we would appreciate it if you let us know: a github issue with a small piece of code highlighting the problem should suffice.

We hope you enjoyed this guide and we hope we’ve wetted your appetite for more. We plan to build off the concepts presented here in a follow-up guide. In the meantime, happy proving! 💙

P.S. Please address any questions you may have to our telegram group (it’s also a great way to stay up-to-date with the latest circom and snarkjs developments).