Zero Knowledge Proof is an advanced cryptographic technique gaining more attention in recent times. There are various cryptographic methods invented to implement zero knowledge proofs including and not limited to zk-SNARKS, zk-STARK, Recursive ZKP etc.

Why zero knowledge proofs?

Zero knowledge proof is a cryptographic method that enables one party to communicate the knowledge of a private information to another party without revealing the actual private information to another party.

Using zero knowledge proofs , a “Prover” can provide a short proof to the “Verifier” that the Prover has a specific knowledge of some private information without revealing the actual information. For example, a Prover can prove to the Verifier that the Prover knows all the prime factors of a 10 digit number (which requires expensive computation) without revealing the factors themselves.

Key properties of zero knowledge proofs:

Below are the key properties that Zero Knowledge Proofs must satisfy,

Completeness: If a statement is true, an honest prover can convince an honest verifier that the statement is true Soundness: If a statement is false, a dishonest prover cannot convince an honest verifier that the statement is true Zero-Knowledge: If a statement is true, the verifier learns nothing other than the fact that the statement is true

Pre-requisite knowledge for deeper understanding: We will cover the implementation of a basic zero knowledge circuit in this blogpost. To understand how Zero Knowledge Proofs work from first principles, I recommend understanding/revising the following math topics in depth,

• (Number Theory) modular arithmetic, Euler’s totient function, Fermat’s Little Theorem the Chinese Remainder Theorem.
• (Abstract Algebra) Groups, rings, fields, finite fields and elliptic curve groups.
• (Cryptography) hash functions, symmetric key cryptography, public key cryptography, digital signatures, bilinear pairings, Quadratic Arithmetic Programs (QAP)

Participating Agents:

Prover: The prover is the entity that possesses a certain knowledge. The prover’s goal is to convince the verifier that they indeed have this knowledge without revealing the information itself

Verifier: The verifier is the entity to whom the prover wants to prove the possession of knowledge. The verifier receives the proof generated by the prover, and by using the verification key (generated by the trusted setup in case of groth16), verifies the validity of the proof without uncovering the actual knowledge

Trusted Setup: In the context of zk-SNARKs, there’s usually a “trusted setup phase” that generates the proving key and the verification key. This setup must be executed correctly and securely. The key security aspect of the trusted setup phase is that, after generating the keys, all the secret randomness (termed as toxic waste) used in this phase should be destroyed to maintain the zero-knowledge property

The detailed explanation of the trusted setup phase is beyond the scope of this blogpost. I’ll be covering it in the next part of this series. Here is a link to learn more about trusted setup:

Generating zero knowledge proof to prove the knowledge of roots of Cubic Polynomial

Assume a cubic equation of the format, (a * x^3) + (b * x^2) + (c * x) + d = 0 where a, b, c, d are the coefficients and x is the variable

We will create zero knowledge proof to prove that we know the roots of the cubic polynomial to a verifier without revealing the actual value of the roots to the verifier.

Task: to prove the knowledge of roots of a cubic polynomial, implementing Groth16 (zk-SNARK proving scheme) using the following tools: Circom and snarkjs,

zk-SNARK: is the abbreviation of “Zero Knowledge Succinct Non-Interactive Argument of Knowledge”

Groth16: is one of the most famous zkSNARK proving schemes. Groth16 has a smaller proof size, a faster proving & verification speed

Circom: is a rust-based compiler used to define arithmetic circuits. It provides a high-level language for constructing circuits with constraints and compiling the circuits

snarkjs: is a JavaScript library for generating and verifying zero-knowledge proofs. It’s an important tool for working with circuits compiled with Circom

Overview of steps involved in generating zk proofs:

Installing the required packages

1. Defining the arithmetic circuit
2. Compiling the circuit
3. Add the inputs
4. Compute the witness
5. Trusted setup ceremony (applicable to Groth16 proving scheme)
6. Create and export the verification key
7. Generate the zero knowledge Proof
8. Verify the Proof

Installing the required npm packages

1
2

npm install snarkjs  
npm install circom

Note: if node is not installed in the machine, refer this link to install node before installing the required npm packages

1. Defining the Arithmetic Circuit

Arithmetic circuits form the basic of generating zero knowledge proofs. The first part of creating a zero-knowledge proof using zk-SNARK is to define an arithmetic circuit. Below are the key components of an arithmetic circuit,

Inputs: can be either private or public. Private inputs are known only to the prover. Public inputs are known to both the prover and the verifier.

Signals: are the variables in our circuit. They can be inputs, outputs, or intermediate values computed within the circuit.

Constraints: are the core building blocks of an arithmetic circuit. Constraints are equations that define the relationships between the inputs and outputs of the circuit. Each constraint in an arithmetic circuit creates a rule that the computation must follow

Knowledge:

1
2
3
4
5

In this example, to prove, I know the roots of the Polynomial `x^3 + 13x^2 + 47x + 35 = 0`,

// for easier comprehension, 
// x^3 + 13x^2 + 47x + 35 = (x + 1) * (x + 5) * (x + 7)
// {-1, -5, -7} are the roots 

step1: Identify the computation: x^3 + 13x^2 + 47x + 35 = 0

step2: Express the computation as a set of equations:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// for polynomial `(a * x^3) + (b * x^2) + (c * x) + d = 0`
x^2 = x * x
x^3 = x^2 * x

term_1 = a * x^3
term_2 = b * x^2
term_3 = c * x

y = term_1 + term_2 + term_3 + d

y = 0 // if x is a root

step3: writing the equations as constraints in Circom

Note:Only quadratic expressions are allowed to be included in constraints. Other arithmetic expressions beyond quadratic or using other arithmetic operators like division or power are not allowed as constraints.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// constraints
x_square <== x * x; 
x_cube <== x_square * x;

term_1 <== x_cube * a; 
term_2 <== x_square * b ;
term_3 <== x * c;

y <== term_1 + term_2 + term_3 + d ;
y === 0;

step4: Define the input signals, intermediate signals and output signals in Circom

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

signal input x;

// coefficients of the cubic polynomial
signal input a;
signal input b;
signal input c;
signal input d;

// Intermediate signals
signal x_square;
signal x_cube;

signal term_1;
signal term_2;
signal term_3;

// output signal
signal output y;

step5: Complete circuit in Circom: Let’s name the file as circuit.circom and save it in the project directory

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

pragma circom 2.1.5;

template CubicRoot() {
// input signals
signal input x;

signal input a;
signal input b;
signal input c;
signal input d;

// intermediate signals
signal x_square;
signal x_cube;

signal term_1;
signal term_2;
signal term_3;

// output
signal output y;

// constraints
x_square <== x * x; 
x_cube <== x_square * x;

term_1 <== x_cube * a;
term_2 <== x_square * b ;
term_3 <== x * c;

y <== term_1 + term_2 + term_3 + d ;
y === 0;
}

component main {public [a,b,c,d]} = CubicRoot();

We created a template circuit CubicRoot above using the signals and constraints In Circom, we call the template thru the component main and pass the public inputs a, b, c, d to the circuit

2. Compile the circuit

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

# output
template instances: 1
non-linear constraints: 5
linear constraints: 1
public inputs: 4
public outputs: 1
private inputs: 1
private outputs: 0
wires: 11
labels: 12
Written successfully: ./circuit.r1cs
Written successfully: ./circuit.sym
Written successfully: ./circuit_js/circuit.wasm
Everything went okay, circom safe

View information about the circuit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

snarkjs r1cs info circuit.r1cs

# output:
[INFO]  snarkJS: Curve: bn-128
[INFO]  snarkJS: # of Wires: 11
[INFO]  snarkJS: # of Constraints: 6
[INFO]  snarkJS: # of Private Inputs: 1
[INFO]  snarkJS: # of Public Inputs: 4
[INFO]  snarkJS: # of Labels: 12
[INFO]  snarkJS: # of Outputs: 1

3. Add inputs

• for easier comprehension, x^3 + 13x^2 + 47x + 35 = (x + 1) * (x + 5) * (x + 7)
• x is private input.
• Private knowledge: The roots are {-1, -5, -7} coefficients a, b, c, d are public inputs
• Let’s create proof to prove the knowledge of the root -1

1
2
3

cat <<EOT > input.json
{"x": -1, "a": 1, "b": 13, "c": 47, "d": 35}
EOT

4. Generate Witness

1
2

cd circuit_js
node generate_witness.js circuit.wasm ../input.json ../witness.wtns

5. Trusted Setup Ceremony

• In this blogpost, we primarily focus on how to construct an arithmetic circuit and implement it using groth16 scheme to generate zero knowledge proofs.
• In the context of zk-SNARKs, there’s usually a “trusted setup phase” that generates the proving key and the verification key.
• This setup must be executed correctly and securely
• We use the circuit.r1cs file to start the trusted setup ceremony and create circuit_0000.zkey
• In this example, for demonstration purposes, we contribute only 3 rounds in the ceremony.
• In real world applications,
  • eg: in KZG Ceremony, it is more than 100k contributions link to KZG contribution updates : https://ceremony.ethereum.org/

Refer the official Snarkjs link for detailed explanation of the steps : https://github.com/iden3/snarkjs#guide

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# move to the project directory from the circuit_js directory
cd ..

# start setup ceremony 
snarkjs groth16 setup circuit.r1cs pot14_final.ptau circuit_0000.zkey

# contribute to the phase 2 ceremony (zkey)
snarkjs zkey contribute circuit_0000.zkey circuit_0001.zkey --name="Contribution Starts" -v

# Provide a second contribution
snarkjs zkey contribute circuit_0001.zkey circuit_0002.zkey --name="Second round" -v -e="round2" 

# Provide third contribution 
snarkjs zkey contribute circuit_0002.zkey circuit_0003.zkey --name="Third round name" -v -e="rnd3 contrib"

# verify the latest key
snarkjs zkey verify circuit.r1cs pot14_final.ptau circuit_0003.zkey

# Apply a random beacon (to create circuit_final.zkey)
snarkjs zkey beacon circuit_0003.zkey circuit_final.zkey 1313101415161718191a1b1c1d1e1e313333303435363738393a3b3c3d3e3e 10 -n="Final Beacon phase2"

# Verify the final key
snarkjs zkey verify circuit.r1cs pot14_final.ptau circuit_final.zkey

6. Create and export the verification key

1
2
3
4
5
6

snarkjs zkey export verificationkey circuit_final.zkey verification_key.json

# output
[INFO]  snarkJS: EXPORT VERIFICATION KEY STARTED
[INFO]  snarkJS: > Detected protocol: groth16
[INFO]  snarkJS: EXPORT VERIFICATION KEY FINISHED

7. Generate the zero knowledge Proof (using prover key: circuit_final.zkey )

1

snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json

• public.json will have the values of the output y for the given private input x (-1 in this example) and the public inputs
• public.json file. We can see the values of output y public inputs (values of coefficients) a, b, c, d in order,

[ "0", "1", "13", "47", "35"]

8. Verify the Proof

1
2
3
4

snarkjs groth16 verify verification_key.json public.json proof.json

# output:
snarkJS: OK!

Here we provided the value of private input x = -1 which is one of the roots of the Polynomial equation x^3 + 13x^2 + 47x + 35 = 0

We can prove the knowledge of the other roots by providing private input x = -5 and x = -7 . Thus we can generate zk proofs for the all the roots of the Cubic equation and prove the knowledge of the roots to the verifier without actually sharing the roots (private inputs).

Note: We can also build a Circom template to evaluate a particular polynomial using a circuit, provide all the three roots at once as private inputs and generate a single zero knowledge proof as well. The circuit constructed in this blogpost is a simple one for demonstration purposes.

Possible mistakes during circuit construction

Just ensure to avoid the below mistakes while constructing arithmetic circuits,

• Constraint Mismatch: describing more or fewer constraints than necessary for the circuit. This can often lead to issues when trying to generate or verify proofs.
• Input and Output Size Mismatch: mismatch between the size of inputs and outputs
• Incorrect Proving and Verification Keys: This error occurs when there is a mix-up with the proving and verification keys during the trusted setup
• Incorrect Inputs to the Prover and Verifier: This issue arises when the inputs to the prover or verifier are incorrect, or the format of the inputs does not match the expected format