Building zkRollup (Part — 1)
Published in
8 min readFeb 5, 2023
In this series, I will be building a Layer-2 rollup using Zero-Knowledge. This zkRollup will target to transfer of the base token (ETH) on the Ethereum mainnet.
Prerequisites
Before diving into this article, I consider that you have a basic understanding of the following concepts:
With these prerequisites in place, you should be able to fully understand and follow the rest of this series.
Let’s start with the simple sequence of events during a rollup transaction life cycle.
Now that we have a basic understanding of events that are taking place during a zkRollup, let’s do a small walkthrough of the technologies and frameworks we have used to build this rollup:
Snarkjs and circom are the compiler and helper packages by IDEN3 to compile and use circuits.
I am using LevelDB for persisting Layer 2 state. We can use any other DB of our choice based on our requirements.
There are 3 major sections in any zkRollup:
- Building SNARK Circuit
- On Chain Contract
- Layer 2 computation and proof building
Building SNARK Circuit
This step consists of making 3 circuits (circom)
- MultipleTransactions circuit, this circuit will execute the SingleTransaction circuit for every transaction
- A SingleTransaction circuit is where the individual transaction is getting verified
- Withdraw circuit is used to verify the withdrawal transaction (explained in the later part of this series)
MultipleTransactions circuit
The main functionality of this circuit is to build an iterator to invoke the SingleTransaction circuit for each transaction. This circuit will take the transaction count, depth of the sparse Merkle tree (SMT), and public signal inputs:
initialOnChainRoot — On chain root before the state change
finalOnChainRoot — Final On chain root if the state change is successful
pub_from — Array of “from public EdDSA address”
pub_to — Array of “to public EdDSA address”
amount — Array of the value of the transaction
token_balance_from — Array of the balance of “from public EdDSA address”
nonce_from — Array of nonce of “from public EdDSA address”
nonce_to- Array of nonce of “to public EdDSA address”
This circuit works only for 2 transactions and hence there is a “2” appended at the end of the name of the circuit, we can write a similar circuit for more transactions as well, provided we have sufficient resources available for proof generation.
pragma circom 2.0.8;
include "./SingleTransaction.circom";
template MultipleTransaction2(transactionCount, n) {
signal input intermediate_state[transactionCount];
signal input final_state_roots[transactionCount];
signal input initialOnChainRoot;
signal input finalOnChainRoot;
signal input paths2old_root_from[transactionCount][n-1];
signal input paths2old_root_to[transactionCount][n-1];
signal input paths2new_root_from[transactionCount][n-1];
signal input paths2new_root_to[transactionCount][n-1];
signal input paths2root_from_pos[transactionCount][n-1];
signal input paths2root_to_pos[transactionCount][n-1];
signal input pub_from[transactionCount][2];
signal input pub_to[transactionCount][2];
signal input nonce_from[transactionCount];
signal input nonce_to[transactionCount];
signal input amount[transactionCount];
signal input R8x[transactionCount];
signal input R8y[transactionCount];
signal input S[transactionCount];
signal input token_balance_from[transactionCount];
signal output out;
component transaction[transactionCount];
for (var i = 0; i < transactionCount; i++){
transaction[i] = SingleTransaction(n);
transaction[i].initialOnChainRoot <== initialOnChainRoot;
transaction[i].current_state <== intermediate_state[i];
for (var j = 0; j < n-1; j++){
transaction[i].paths2old_root_from[j] <== paths2old_root_from[i][j];
transaction[i].paths2old_root_to[j] <== paths2old_root_to[i][j];
transaction[i].paths2new_root_from[j] <== paths2new_root_from[i][j];
transaction[i].paths2new_root_to[j] <== paths2new_root_to[i][j];
transaction[i].paths2root_from_pos[j] <== paths2root_from_pos[i][j];
transaction[i].paths2root_to_pos[j] <== paths2root_to_pos[i][j];
}
transaction[i].pub_from_x <== pub_from[i][0];
transaction[i].pub_from_y <== pub_from[i][1];
transaction[i].nonce_from <== nonce_from[i];
transaction[i].pub_to_x <== pub_to[i][0];
transaction[i].pub_to_y <== pub_to[i][1];
transaction[i].nonce_to <== nonce_to[i];
transaction[i].R8x <== R8x[i];
transaction[i].R8y <== R8y[i];
transaction[i].S <== S[i];
transaction[i].amount <== amount[i];
transaction[i].token_balance_from <== token_balance_from[i];
final_state_roots[i] === transaction[i].out;
}
component state_root = MultiMiMC7(transactionCount,91);
for (var i = 0; i<transactionCount; i++){
state_root.in[i] <== transaction[i].out;
}
state_root.k <== 0;
finalOnChainRoot === state_root.out ;
out <== 1;
}
// component main = MultipleTransaction2(2, 2);
component main {
public [
initialOnChainRoot,
finalOnChainRoot,
pub_from,
pub_to,
amount,
token_balance_from,
nonce_from,
nonce_to
]
} = MultipleTransaction2(2, 2);SingleTransaction circuit
In order to understand this circuit we can refer to here and here.
pragma circom 2.0.0;
include "../node_modules/circomlib/circuits/mimc.circom";
include "../node_modules/circomlib/circuits/eddsamimc.circom";
template SingleTransaction(n) {
signal input current_state;
signal input initialOnChainRoot;
signal input paths2old_root_from[n-1];
signal input paths2old_root_to[n-1];
signal input paths2new_root_from[n-1];
signal input paths2new_root_to[n-1];
signal input paths2root_from_pos[n-1];
signal input paths2root_to_pos[n-1];
signal input pub_from_x;
signal input pub_from_y;
signal input R8x;
signal input R8y;
signal input S;
signal input amount;
signal input nonce_from;
signal input nonce_to;
signal input pub_to_x;
signal input pub_to_y;
signal input token_balance_from;
signal output out;
var i;
var NONCE_MAX_VALUE = 1000000000000000000;
component old_hash_from = MultiMiMC7(7,91);
old_hash_from.in[0] <== initialOnChainRoot;
old_hash_from.in[1] <== pub_from_x;
old_hash_from.in[2] <== pub_from_y;
old_hash_from.in[3] <== nonce_from;
old_hash_from.in[4] <== amount;
old_hash_from.in[5] <== pub_to_x;
old_hash_from.in[6] <== pub_to_y;
old_hash_from.k <== 0;
component old_merkle_from[n-1];
old_merkle_from[0] = MultiMiMC7(2,91);
old_merkle_from[0].in[0] <== old_hash_from.out - paths2root_from_pos[0]* (old_hash_from.out - paths2old_root_from[0]);
old_merkle_from[0].in[1] <== paths2old_root_from[0] - paths2root_from_pos[0]* (paths2old_root_from[0] - old_hash_from.out);
old_merkle_from[0].k <== 0 ;
for (i=1; i<n-1; i++){
old_merkle_from[i] = MultiMiMC7(2,91);
old_merkle_from[i].in[0] <== old_merkle_from[i-1].out - paths2root_from_pos[i]* (old_merkle_from[i-1].out - paths2old_root_from[i]);
old_merkle_from[i].in[1] <== paths2old_root_from[i] - paths2root_from_pos[i]* (paths2old_root_from[i] - old_merkle_from[i-1].out);
old_merkle_from[i].k <== 0 ;
}
current_state === old_merkle_from[n-2].out;
component old_hash_to = MultiMiMC7(4,91);
old_hash_to.in[0] <== initialOnChainRoot;
old_hash_to.in[1] <== pub_to_x;
old_hash_to.in[2] <== pub_to_y;
old_hash_to.in[3] <== nonce_to;
old_hash_to.k <== 0;
component old_merkle_to[n-1];
old_merkle_to[0] = MultiMiMC7(2,91);
old_merkle_to[0].in[0] <== old_hash_to.out - paths2root_to_pos[0]* (old_hash_to.out - paths2old_root_to[0]);
old_merkle_to[0].in[1] <== paths2old_root_to[0] - paths2root_to_pos[0]* (paths2old_root_to[0] - old_hash_to.out);
old_merkle_to[0].k <== 0;
for (i=1; i<n-1; i++){
old_merkle_to[i] = MultiMiMC7(2,91);
old_merkle_to[i].in[0] <== old_merkle_to[i-1].out - paths2root_to_pos[i]* (old_merkle_to[i-1].out - paths2old_root_to[i]);
old_merkle_to[i].in[1] <== paths2old_root_to[i] - paths2root_to_pos[i]* (paths2old_root_to[i] - old_merkle_to[i-1].out);
old_merkle_to[i].k <== 0 ;
}
current_state === old_merkle_to[n-2].out;
component verifier = EdDSAMiMCVerifier();
verifier.enabled <== 1;
verifier.Ax <== pub_from_x;
verifier.Ay <== pub_from_y;
verifier.R8x <== R8x ;
verifier.R8y <== R8y ;
verifier.S <== S;
verifier.M <== old_hash_from.out;
component greFrom = GreaterEqThan (252) ;
greFrom.in[0] <== token_balance_from ;
greFrom.in[1] <== amount ;
greFrom.out === 1 ;
// component greTo = GreaterEqThan (252) ;
// greTo.in[0] <== token_balance_to + amount ;
// greTo.in[1] <== token_balance_to ;
// greTo.out === 1 ;
component nonceCheck = GreaterEqThan (252) ;
nonceCheck.in[0] <== NONCE_MAX_VALUE ;
nonceCheck.in[1] <== nonce_from ;
nonceCheck.out === 1 ;
// // accounts updates
component new_hash_from = MultiMiMC7(6,91);
new_hash_from.in[0] <== pub_from_x;
new_hash_from.in[1] <== pub_from_y;
new_hash_from.in[2] <== nonce_from + 1;
new_hash_from.in[3] <== amount;
new_hash_from.in[4] <== pub_to_x;
new_hash_from.in[5] <== pub_to_y;
new_hash_from.k <== 0 ;
component new_merkle_from[n-1];
new_merkle_from[0] = MultiMiMC7(2,91);
new_merkle_from[0].in[0] <== new_hash_from.out - paths2root_from_pos[0]* (new_hash_from.out - paths2new_root_from[0]);
new_merkle_from[0].in[1] <== paths2new_root_from[0] - paths2root_from_pos[0]* (paths2new_root_from[0] - new_hash_from.out);
new_merkle_from[0].k <== 0 ;
for (i=1; i<n-1; i++){
new_merkle_from[i] = MultiMiMC7(2,91);
new_merkle_from[i].in[0] <== new_merkle_from[i-1].out - paths2root_from_pos[i]* (new_merkle_from[i-1].out - paths2new_root_from[i]);
new_merkle_from[i].in[1] <== paths2new_root_from[i] - paths2root_from_pos[i]* (paths2new_root_from[i] - new_merkle_from[i-1].out);
new_merkle_from[i].k <== 0 ;
}
component new_hash_to = MultiMiMC7(4,91);
new_hash_to.in[0] <== pub_to_x;
new_hash_to.in[1] <== pub_to_y;
new_hash_to.in[2] <== nonce_to + 1;
new_hash_to.in[3] <== amount;
new_hash_to.k <== 0 ;
// log(new_hash_to.out) ;
component new_merkle_to[n-1];
new_merkle_to[0] = MultiMiMC7(2,91);
new_merkle_to[0].in[0] <== new_hash_to.out - paths2root_to_pos[0]* (new_hash_to.out - paths2new_root_to[0]);
new_merkle_to[0].in[1] <== paths2new_root_to[0] - paths2root_to_pos[0]* (paths2new_root_to[0] - new_hash_to.out);
new_merkle_to[0].k <== 0;
for (i=1; i<n-1; i++){
new_merkle_to[i] = MultiMiMC7(2,91);
new_merkle_to[i].in[0] <== new_merkle_to[i-1].out - paths2root_to_pos[i]* (new_merkle_to[i-1].out - paths2new_root_to[i]);
new_merkle_to[i].in[1] <== paths2new_root_to[i] - paths2root_to_pos[i]* (paths2new_root_to[i] - new_merkle_to[i-1].out);
new_merkle_to[i].k <== 0;
}
new_merkle_from[n-2].out === new_merkle_to[n-2].out ;
out <== new_merkle_to[n-2].out;
}
// component main = SingleTransaction(2);Once we have our circuit successfully written and compiled, we have to generate snark proof and deploy the verifier contract on-chain. There are a set of steps mentioned here.
We have used 512k contataint ptau file from following URL:
https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_19.ptau
This Ptau files for bn128 with the peraperPhase2 54 contributions and a beacon.
circom ../circuits/MultipleTransaction2.circom --r1cs --wasm --sym
snarkjs r1cs export json MultipleTransaction2.r1cs MultipleTransaction2.r1cs.json
node generate_witness.js circuit.wasm ../input.json ../witness.wtns
snarkjs plonk setup MultipleTransaction2.r1cs \
powersOfTau28_hez_final_17.ptau \
MultipleTransaction2_circuit_final.zkey
snarkjs zkey export verificationkey \
MultipleTransaction2_circuit_final.zkey \
verification_key.json
snarkjs plonk prove \
MultipleTransaction2_circuit_final.zkey \
witness.wtns \
proof.json \
public.json
snarkjs plonk verify \
verification_key.json \
public.json \
proof.json
snarkjs zkey export solidityverifier \
MultipleTransaction2_circuit_final.zkey verifier.sol
snarkjs zkey export soliditycalldata public.json proof.json >> soliditycalldata.txtIn order to generate the witness.wtns file we need to have the circuit's input defined in the input.json file.
The following code will help us generate the input signals based on the transaction object passed. In the later part of this series, I will explain how to compose the transaction object passed to generate proof and verify against the circuit.
const l2Web3 = require('../src/l2Web3.js');
const buildEddsa = require("circomlibjs").buildEddsa;
const buildMimc7 = require("circomlibjs").buildMimc7;
const wasm_tester = require("circom_tester").wasm;
const snarkjs = require("snarkjs");
const fs = require("fs");
const result = [[],[]];
const DEPTH = 2;
const transactionCount = 2;
async function generateProof(transactionObject,wasmFilePath,zKeyFilePath) {
const mimcjs = await buildMimc7();
const eddsa = await buildEddsa();
let initialOnChainRoot = await l2Web3.getOnChainRoot() ;
let circuit = await wasm_tester("../circuits/MultipleTransaction2.circom");
const pubKey_from = [[],[]];
const pubKey_to = [[],[]] ;
const nonce_from = [];
const nonce_to = [];
const amount = [];
let token_balance_from = [] ;
let token_balance_to = [] ;
let old_hash_leaf_from = new Array(transactionCount);
let old_hash_leaf_to = new Array(transactionCount);
var old_merkle = new Array(transactionCount).fill(0).map(() => new Array(DEPTH-1).fill(0));
for (var i=0; i<transactionCount; i++){
pubKey_from[i][0] = transactionObject[i][0][1] ;
pubKey_from[i][1] = transactionObject[i][0][2] ;
pubKey_to[i][0] = transactionObject[i][1][1] ;
pubKey_to[i][1] = transactionObject[i][1][2] ;
nonce_from[i] = transactionObject[i][0][3] ;
amount[i] = transactionObject[i][1][0] ;
nonce_to[i] = transactionObject[i][1][6] ;
old_hash_leaf_from[i] = mimcjs.multiHash(
[initialOnChainRoot, pubKey_from[i][0],pubKey_from[i][1], nonce_from[i], amount[i], pubKey_to[i][0],pubKey_to[i][1]]
);
old_hash_leaf_to[i] = mimcjs.multiHash(
[initialOnChainRoot, pubKey_to[i][0],pubKey_to[i][1], nonce_to[i]]
);
}
for(var i=0; i<transactionCount; i++){
old_merkle[i][0] = mimcjs.multiHash([old_hash_leaf_from[i], old_hash_leaf_to[i]]);
for (var j = 1; j < DEPTH-1; j++) {
old_merkle[i][j] = mimcjs.multiHash([old_merkle[i][j-1],0]);
}
}
let signature = [[],[]];
for (var i=0; i < transactionCount; i++){
signature[i][0] = transactionObject[i][1][3] ; // R8x
signature[i][1] = transactionObject[i][1][4] ; // R8y
signature[i][2]= transactionObject[i][1][5] ; // S
}
let new_hash_leaf_from = new Array(transactionCount);
const new_hash_leaf_to = new Array(transactionCount);
for (var i=0; i<transactionCount; i++){
new_hash_leaf_from[i] = mimcjs.multiHash(
[pubKey_from[i][0],pubKey_from[i][1], nonce_from[i] + 1n, amount[i],pubKey_to[i][0],pubKey_to[i][1]]
);
new_hash_leaf_to[i] = mimcjs.multiHash(
[pubKey_to[i][0],pubKey_to[i][1], nonce_to[i] + 1n, amount[i]]
);
}
var new_merkle = new Array(transactionCount).fill(0).map(() => new Array(DEPTH-1).fill(0));
for(var i=0; i<transactionCount; i++){
new_merkle[i][0] = mimcjs.multiHash([new_hash_leaf_from[i], new_hash_leaf_to[i]]);
for (var j = 1; j < DEPTH-1; j++) {
new_merkle[i][j] = mimcjs.multiHash([new_merkle[i][j-1],0]);
}
}
var final_state_roots = new Array(transactionCount);
for(var i=0; i<transactionCount; i++){
final_state_roots[i] = new_merkle[i][DEPTH-2];
}
var current_state = new Array(transactionCount);
var paths2old_root_from = new Array(transactionCount);
var paths2old_root_to = new Array(transactionCount);
var paths2new_root_from = new Array(transactionCount);
var paths2new_root_to = new Array(transactionCount);
var paths2root_from_pos = new Array(transactionCount);
var paths2root_to_pos = new Array(transactionCount);
var pub_from_x = new Array(transactionCount);
var pub_from_y = new Array(transactionCount);
var R8x = new Array(transactionCount);
var R8y = new Array(transactionCount);
var S = new Array(transactionCount);
var pub_to_x = new Array(transactionCount);
var pub_to_y = new Array(transactionCount);
for(var i = 0; i < transactionCount; i++){
paths2old_root_from[i] = [mimcjs.F.toObject(old_hash_leaf_to[i])];
paths2old_root_to[i] = [mimcjs.F.toObject(old_hash_leaf_from[i])];
paths2new_root_from[i] = [mimcjs.F.toObject(new_hash_leaf_to[i])];
paths2new_root_to[i] = [mimcjs.F.toObject(new_hash_leaf_from[i])];
paths2root_from_pos[i] = [0];
paths2root_to_pos[i] = [1];
current_state[i] = mimcjs.F.toObject(old_merkle[i][DEPTH-2]);
final_state_roots[i] = mimcjs.F.toObject(new_merkle[i][DEPTH-2]);
pub_from_x[i] = pubKey_from[i][0];
pub_from_y[i] = pubKey_from[i][1];
pub_to_x[i] = pubKey_to[i][0];
pub_to_y[i] = pubKey_to[i][1];
R8x[i] = signature[i][0];
R8y[i] = signature[i][1];
S[i] = signature[i][2];
token_balance_from[i] = await l2Web3.getBalance(pubKey_from[i][0],pubKey_from[i][1]) ;
token_balance_to[i] = await l2Web3.getBalance(pubKey_to[i][0],pubKey_to[i][1]) ;
}
const input = {
intermediate_state: current_state,
final_state_roots: final_state_roots,
initialOnChainRoot: initialOnChainRoot,
finalOnChainRoot: mimcjs.F.toObject(mimcjs.multiHash(final_state_roots)),
paths2old_root_from: paths2old_root_from,
paths2old_root_to: paths2old_root_to,
paths2new_root_from: paths2new_root_from,
paths2new_root_to: paths2new_root_to,
paths2root_from_pos: paths2root_from_pos,
paths2root_to_pos: paths2root_to_pos,
pub_from_x: pub_from_x,
pub_from_y: pub_from_y,
nonce_from: nonce_from,
pub_to_x: pub_to_x,
pub_to_y: pub_to_y,
nonce_to: nonce_to,
amount: amount,
R8x: R8x,
R8y: R8y,
S: S,
token_balance_from:token_balance_from,
token_balance_to:token_balance_to
}
// console.log(JSON.stringify(input));
const w = await circuit.calculateWitness(input, true);
console.log(`Output from circom = ${w[1]}`);
console.log("Started creating the proof!!!!!");
let { proof, publicSignals } = await snarkjs.plonk.fullProve(
input,wasmFilePath,zKeyFilePath
);
const solidityCallData = await snarkjs.plonk.exportSolidityCallData(proof, publicSignals);
result[0] = proof ;
result[1] = publicSignals ;
return result ;
}
module.exports = {generateProof} ;Part — 2
In the next part, I will explain how to generate input values based on the transaction passed to layer 2 and also highlight some of the major on-chain contract code of the rollup.
References
Originally published at https://medium.com on February 5, 2023.
