Zero knowledge rollup using circom for beginner

Introduction
Circom is a language for arithmetic circuits that are used to generate zero knowledge proof. Circom compiler is a circom language compiler written in Rust that creates R1CS file. Circom is created by Iden3 open source project.

Definition

Circuit is a logical representation of the computational problem using polynomials.

Witness is assignment of signals to the circuit.

Signals are the variables.

Rank-1 Constraint System (R1CS) is the set of constraints describing the circuit. Example, A * B + C = 0

Constraint is to make a program that constraints the given inputs into a certain range.

Components works like functions, and we set the component inputs only once. Once component inputs are all defined, the function gets executed and we can use the component output variable.

Zero knowledge proof : One person, the prover, convince another person, the verifier, that something is true without revealing the private input.

Non-interactive zero-knowledge (NIZK) proofs are a particular type of zero-knowledge proofs in which the prover can generate the proof without interaction with the verifier.

ZK-SNARK (Zero Knowledge-Succinct ARguments of Knowledge) is the most preferable NIZK. It is a set of non-interactive zero-knowledge protocols that have succinct proof size and sub-linear verification time.

Succint: The actual proof provided to the verifier is a much smaller proof than the original proposition. This is succinctness.

Zk roll up aggregates many transactions off-chain, generates a single proof using ZK-SNARK to reduce data size. The proof is submitted on-chain, verified on-chain. Zk roll up also update account merkle tree on-chain.

Cryptography Trusted Setup: Trusted Setup generates a data that must be used in crypto operation. A trusted setup ceremony is a procedure to generate the data.

ZK-Snark algorithm: Groth16 (Filecoin, Tornado.cash, Old Zcash) is the most widely used, followed by Plonk (zkSync, Mina), and Halo (New Zcash).

Zk roll up conceptual sequence:

1. Verify sender information

hash sender public key, calculate merkle root

2. Create signature of new transaction

create a hash of sender and receiver public key, with the transaction amount

use EdDSA to sign and verify the hash

3. Update new sender balance with the transaction amount

calculate new merkle root

verify new root

4. verify receiver information

hash receiver public key, calculate merkle root

5. Update new receiver balance with the transaction amount

calculate new merkle root

verify new root

6. Publish the new root on chain

Steps to do the zk rollup:

The following steps are performed on the example code in https://github.com/victoryeo/circom_rollup
You have to install circom and snarkjs on your machine.

1. Compile the circuit

circom rollup.circom --r1cs --wasm --sym --c

It generates wasm and cpp files, and R1CS constrains.

2.a Generate the witness with webassembly

cd rollup_js

node generate_witness.js rollup.wasm ../input.json witness.wtns

2.b Generate the witness with cpp

cd rollup_cpp

make

./rollup ../input.json witness.wtns

Step 2 assigns a value to every signal, and generates the witness file from the circuit. It is equivalent to execute the circuit.

3. Perform trusted setup

Using powers of tau (multi party trusted setup)

Execute the below commands in the root folder of the project.

snarkjs powersoftau new bn128 18 pot12_0000.ptau -v

The new command is used to start a powers of tau ceremony.
Initially, i use `bn128 12`, and I go this error:

[snarkJS: circuit too big for this power of tau ceremony. 39582*2 > 2**12]

snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name=”First contribution” -v

The contribute command creates a new ptau file from old ptau file.

snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v

The prepare command is for the phase 2 of the setup.

snarkjs groth16 setup rollup.r1cs pot12_final.ptau rollup_0000.zkey

The groth16 command generates the reference zkey. In total, the above commands take 30 mins to 1 hour to run on my laptop.

snarkjs zkey contribute rollup_0000.zkey rollup_0001.zkey --name=”1st Contributor Name” -v

The zkey contribute command creates a new zkey file with new contribution.
rollup_0000.zkey is old key

rollup_0001.zkey is new key

zkey is a zero knowledge key that combines proving and verification keys.

snarkjs zkey export verificationkey rollup_0001.zkey verification_key.json

The above command generates the verification key in json format.

4. Generate a zk proof

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

The two files, proof.json and public.json are generated.

proof.json contains the proving key

public.json contains the public outputs

Step 4 generates a zk proof that holds the constraints defined in the circuit (derives the constraints from the circuit), and reveals the public output.

5. Verify a zk proof

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

Step 5 takes public output, proving key, verification key, and decides the verification outcome.

The below console output means verification is successful

[INFO] snarkJS: OK!

Circom library terms

Baby Jubjub: it defines an algo that returns an elliptic curve to be used in zk-snark proof, given a prime number p. It is used by zk-snark. Baby Jubjub is a twisted Edwards curve.

MiMC: it defines a hash function to minimize circuit size

MiMC sponge: MiMC calculation in sponge mode. Sponge mode is a function that maps variable-length input to variable-length output

BN128: BN refers to the surnames of the mathematicians who found them back in 2006, Paulo Barreto and Michael Naehrig. BN128 is 128 bit ellitic curve.

EdDSA: Edwards Digital Signature Algorithm, the signature scheme used by zk-snark.

Montgomery curve: another elliptic curve

References

Hands-on Your first ZK application!

Getting Started with Circom & Noir - HackMD

ZkRollup Tutorial

How do trusted setups work?

The end.