Introduction to Zero-Knowledge Proofs and Circom
In this TP, we will discover the basics of zero-knowledge proof with the circuit description language Circom
.
Circom is a circuit description language that allows to describe arithmetic circuits and compile them into rank-1 arithmetic circuits (R1CS). These circuits can then be used to generate zero-knowledge proofs.
Installation
Before we start, we will install some necessary tools.
NodeJS
First, let's install some necessary tools. Start by opening a terminal and install the curl
and git
packages:
sudo apt install curl git
We will now install NodeJS
which is a JavaScript runtime. It will allow us to run JavaScript code outside of a browser. As we need a specific version of NodeJS, we will use the nvm
tool to install it.
curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.40.1/install.sh | bash
nvm install --lts
nvm use --lts
node -v
You should see v22.X.Y
displayed with X
and Y
being 13
and 0
respectively as of the time of writing.
Circom
We will now install the circuit compiler circom
and start learning how to use it.
Go to the circom page and follow the instructions: https://docs.circom.io/getting-started/installation/.
Getting Started with Circom
Writing a Circuit
You can follow the steps and create your first circuit, multiplier2.circom
:
- Installation
- Writing circuits
- Compiling circuits
- Computing the witness
- Proving circuits with ZK
R1CS Analysis
The R1CS (Rank-1 Constraint System) file is a file that contains the constraints of the circuit. It is generated during the compilation of the circuit with circom. Analyze the R1CS file of the multiplier2.circom
circuit with the following commands:
snarkjs r1cs print multiplier2.r1cs
You should see the constraints of the circuit displayed. In this case, the R1CS has only one constraint:
[ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.a ] * [ main.b ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.c ] = 0
Note
What does the number 21888242871839275222246405745257275088548364400416034343698204186575808495616
represent?
As a reminder, .
This number is therefore , and can be read as in the finite field .
The constraint is therefore equivalent to:
-1 * a * b - (-1 * c) = 0
\\
-1 * a * b = -1*c
\\
a * b = c
Witness Analysis
The witness is a file that contains the values of the circuit variables. It is generated during the proof generation. It is a binary file, but it is possible to convert it to JSON to analyze it.
Analyze the witness generated for the multiplier2.circom
circuit with the following commands:
snarkjs wtns export json witness.wtns
cat witness.json
You should see the values of the circuit signals that respect all the constraints displayed. In this case, the witness contains the following values:
[
"1",
"21",
"3",
"7"
]
These values are those of the different signals of the circuit, including a special signal 1
that is used for multiplication constraints.
We therefore have: [1, c, a, b]
. Snarkjs always generates a witness starting with 1
, followed by the output signals, then the input signals, and finally the intermediate signals.
Your first Zero-Knowledge project
Cloning the project with Git
Before starting, clone the project with the following command:
git clone https://gitlab.isae-supaero.fr/crypto/introduction
Now, we will explore the project directory.
Project Structure
All the projects in this course have the same structure:
circuits
: Contains the different circuits to be compiled. For example, themul.circom
circuit is used to check if a number is the product of two prime numbers.src
: Contains the different classes to generate proofs and verify them. For example, theMulProver
andMulVerifier
classes inmul.prover.ts
andmul.verifier.ts
are used to generate and verify proofs for the multiplication of two prime numbers. They are associated with themul.circom
circuit.bin
: Contains the different programs to run. They use your classes you have written in thesrc
folder. For example, themul_intro.ts
program generates a proof for the multiplication of two prime numbers.test
: Contains the different tests to run. For example, themul.test.ts
contains tests for the MulProver class.zk
: This folder likely contains the Zero-Knowledge (zk) circuits and related files. It includes subfolders likecircuits
andzkeys
:circuits
: This subfolder contains the compiled WebAssembly (wasm) files for the zk-SNARK circuits, such asmul_js/mul.wasm
and theR1CS
files for the circuits, such asmul.r1cs
.zkeys
: This subfolder contains the proving for the zk-SNARK circuits, such asmul_final.zkey
.verifiers
: This subfolder contains the verification keys for the zk-SNARK circuits, such asmul_vk.json
.
scripts
: Contains the different scripts to run. For example, thebuild.ts
script compiles the circuit and generates the verification key.assets
: Contains the different files necessary for the project. For example, themul.vkey.json
file is the verification key of themul.circom
circuit. In some projects, you will find serialized proofs to verify.
Important
The scripts
and npm
commands use these folders to run the different actions. So if you want to add a new circuit, you will have to add it to the circuits
folder, and then add the corresponding classes to the src
folder.
Additionally, the project contains a package.json
file that contains the different dependencies and scripts to run. You can find the list of available commands in this file. You will also find a node_modules
folder that contains the different dependencies of the project. Finally, some commands will generate a dist
folder that contains the different binaries of the project you will run.
To carry out the exercises, you are free to use the tools of your choice (IDE, terminal, ...). However, you have at your disposal the VS Code IDE.
To open a project corresponding to a TP.
- Go to the root directory of the project
- In a terminal, type the command:
code .
- Open a terminal in the editor, and type the command:
npm install
- The project is ready, you can run the different commands of the projects with:
npm run <CMD>
A command can be for example the compilation of the project, the execution of a program, or the execution of several tests. We will see examples later.
Tips
You can find the list of available commands in the package.json
file.
Exercise 1: Multiplication of two prime numbers
The current project contains a simple circuit that checks if a number is the product of two prime numbers. Start by opening the file circuits/mul.circom
and analyze the code.
To compile the circuit, and generate the binaries of the project, run the following command:
npm run build
This command will perform several actions you learned by reading the circom documentation: For each circuit, the command will:
- Compile the circuit with the
circom
command. Ther1cs
andwasm
files will be stored in thezk/circuits/
folder. - Generate the zkey files that are the proving keys of the circuit. They will be stored in the
zk/zkeys/
folder. - Generate the verification key of the circuit. It will be stored in the
zk/verifiers/
folder.
Important
This process must use a file containing the powers of tau ceremony. A file is given in the project. The script also contributes
to the ceremony using constant and not secure data.
DO NOT USE THIS SCRIPT IN A REAL CASE.
Analyze the src
folder and observe how it is possible to generate a proof and verify it using the MulProver
and MulVerifier
classes.
You can test the circuit by running the following command:
npm run test
Generating a proof
In the bin
folder, you will find the file mul_intro.ts
. You can run (at the root of the project) this program with the following command:
npm run mul_intro
This program only displays the proof of the multiplication of two prime numbers. It first creates an instance of the MulProver
class, then generates the proof using the prove
method. This method takes as input the values of the signals of the circuit, and returns the proof. You can see the proof displayed in the terminal.
Important
The mul circuit has 2 input signals called x
and y
. If you look at the MulProver
, you will see that the prove
method takes 2 bigint
as parameters called x
and y
. These variables are given to the fullProve
method. It is mandatory to keep match names of the signals in the circuit and the parameters of the prove
method. If you don't respect this rule, the proof will not be generated.
Now, let's complete the program to verify the proof and print the result. Create a MulVerifier
instance and verify the proof using the verify
method. The method takes the proof as an argument and returns a boolean indicating if the proof is valid or not. Don't forget it's an asynchronous method, so you need to use the await
keyword. You don't have to import anything, it's already done for you.
Note
Remember, a Verifier
instance needs a verification key to verify the proof. This key is generated during the circuit compilation. You can find it in the zk/verifiers
folder under the name mul.vkey.json
.
Proof Verification
The proof Generation and Verification are 2 operations that are often separated. The prover generates the proof and sends it to the verifier. The verifier then checks the proof thanks to the verification key.
In the assets
folder, you will find 2 serialized proofs: proof1.bin
and proof2.bin
. The first proof is valid, while the second is not. We will now verify these proofs using the MulVerifier
class.
Complete the file mul_intro.ts
to read and check these proofs. remember to run the command from the root of the project.
- Open the first
.bin
file using thefs.readFileSync
function, deserialize the proof withdeserializeSnarkProof
and display the content.
const buffer_proof = fs.readFileSync('./assets/proof1.bin');
const proof = deserializeSnarkProof(buffer_proof);
console.log(proof);
You should see a single public signal, being the result of the multiplication. The input data is of course not disclosed.
- Verify the proof using the
MulVerifier
class:
const verifier = await MulVerifier.fromFile('./assets/mul.vkey.json');
const res = await verifier.verify(proof);
if (res) {
console.log('Proof is valid');
} else {
console.log('Proof is invalid');
}
The proof must be verified using the correct verification key. This key is generated during the circuit compilation. You can find it in the
assets
folder under the namemul.vkey.json
.
- Try to verify the proof with your own verification key generated during the
npm run build
compilation phase. What do you observe?
const verifier = new MulVerifier();
const res = await verifier.verify(proof);
if (res) {
console.log('Proof is valid');
} else {
console.log('Proof is invalid');
}
- Check the second proof using the correct verification key. What do you observe?
const buffer_proof2 = fs.readFileSync('./assets/proof2.bin');
const proof2 = deserializeSnarkProof(buffer_proof2);
const verifier = await MulVerifier.fromFile('./assets/mul.vkey.json');
const res = await verifier.verify(proof2);
if (res) {
console.log('Proof is valid');
} else {
console.log('Proof is invalid');
}
Exercise 2: Check that a signal is binary
- Create a file
isbin.circom
- Write a circuit that takes a signal as input and returns a signal as output.
- Check that the input signal is binary. In this case, the circuit returns the value of the input signal.
- What rule should be checked for a signal to be binary?
- How to check this rule with a multiplication?
Exercise 3: Check that a signal is equal to zero
- Create a file
iszero.circom
- Write a circuit that takes a signal as input and returns a signal as output. The output signal is 1 if the input signal is 0, otherwise, it is 0.
- How to check if the signal is equal to zero with a multiplication?
- How to return 1 if the signal is equal to zero, and 0 otherwise with a multiplication?
Exercise 4: Check that a signal is equal to another
Using the IsZero
component, write a circuit isequal.circom
that takes two signals as input and returns a binary signal as output indicating whether the two signals are equal.
Exercise 5: logical gates
AND
gate
Write a circuit And.circom
that takes two signals as input and returns a signal as output corresponding to the AND
logical operation of the two signals.
- Write the truth table of the
AND
operation and see how to obtain the result with a multiplication. - Add a constraint to check that the input signals are binary.
Not
gate
Write a circuit Not.circom
that takes a signal as input and returns a signal as output corresponding to the NOT
logical operation of the input signal.
- Your constraint must necessarily have a multiplication.
- Use the truth table of the
NOT
operation. - Add a constraint to check that the input signal is binary.
Conclusion
In this TP, you have learned how to write circuits with Circom, generate proofs, and verify them. You have also learned how to analyze the R1CS and witness files. In the follwing TPs, you will learn how to generate more complex circuits and proofs, and how to use them in real-world applications.