We will attempt to create circuits and contract for rollup chain that does ether/ERC20 transfers and is much more scalable than current ethereum chain from scratch!
$ git clone https://github.com/vaibhavchellani/RollupNC_tutorial
$ cd RollupNC_tutorial
$ git submodule update --init --recursive
$ npm i
$ cd circomlib; git checkout 77928872169b7179c9eee545afe0a972d15b1e64; npm i; cd -;
> We should use the latest version of circomlib but for the sake of workshop we are using older version
That's it!
ZkSnarks have been used for privacy applications and for having private transactions on chains like ZCash for a few years now. Rollup utilises zkSnarks to scale ethereum by taking advantage of the succinctness provided by snarks.
We achive scalability by not having to send user signatures on-chain and instead send one proof which signifies 1000's of signature verifications and other transaction validation checks have been done correctly off-chain.
We send minified form of transactions on-chain as input to circuit to have data-available.
There are two actors involved in a rollup chain: Coordinator and User.
We will dive into specifics of the construction in the next parts.
Circom and snarkjs are these compiler and helper packages by IDEN3 to compile and use circuits. They are JS based and hence very easy to use for small circuits. We will go through some commands which we will be using in this tutorial.
Compiles your circuit and generates compiled circuit in json format for snarkjs to use.
$ circom <your_circuit_name>.circom -o circuit.json`
Generates public private inputs for your circuit
$ node generate_circuit_input.js
Note: This exists only for the course of our workshop
Generates witness for your circuit using the compiled circuit and input file created in the above step
$ snarkjs calculatewitness -c circuit.json -i input.json
Remember the infamous "Trusted Setup", to perform trusted setup on your device for a circuit use the below command. It creates a Proving and Verification key for your circuit.
$ snarkjs setup -c circuit.json --protocol groth
To generate proof for your circuit use the below command. It uses witness and proving key as inputs and generates a proof for you which can be passed around to certify correcct computation of circuit
$ snarkjs proof -w witness.json --pk proving_key.json
To verify your proof run the below command. This command will use verification_key.json, proof.json and public.json to verify that is valid. Here we are veifying that we know a witness that the public inputs and the outputs matches the ones in the public.json file. If the proof is ok, you will see an OK in the screen or INVALID otherwise.
$ snarkjs verify
This command will take the verification_key.json and generate a solidity code in verifier.sol file.
$ snarkjs generateverifier
The verifier contract deployed in the last step has a view function called verifyProof. This function will return true if the proof and the inputs are valid.
$ snarkjs generatecall
Recommended read for basic walkthrough through circom and snarkjs can be found here
This is a contrived example to familiarise ourselves with the syntax of circom
and how it works with snarkjs
.
Let's write a circuit to check:
a + b
is equal to a public input c
;b * c
is equal to private input d
;$ cd 1_simple_arithmetic
$ touch circuit.circom
// create template
template SimpleChecks() {
// declare a variables which will store private inputs
signal private input a;
signal private input b;
signal private input d;
// declare public input variables
signal input c;
// declate output variables
signal output out;
// force a + b = c
a + b === c;
// force b * c = d
// TODO : Fill in the constraint
// assign output to output variable
out <== c + d;
}
// export the template
component main = SimpleChecks();
Now that we are done with this small circuit let's see how we can generate the proof for this circuit.
Compile it
$ circom circuit.circom -o circuit.json
Generate your input for the circuit
$ node generate_circuit_input.js
Calculate the witness for the circuit
$ snarkjs calculatewitness -c circuit.json -i input.json
Perform trusted setup
$ snarkjs setup -c circuit.json --protocol groth
Generate the proof
$ snarkjs proof -w witness.json --pk proving_key.json
Verify the proof
$ snarkjs verify
Signing data and verifying signatures are an essential part of any rollup chain you want to design. We use the EdDSA signature because it's much more efficient.
This example works with useful libraries in circomlib
. Note: we are using v0.0.6 of circomlib
.
$ cd 2_verify_eddsa
$ touch circuit.circom
include "../circomlib/circuits/eddsamimc.circom";
template VerifyEdDSAMiMC() {
signal input from_x;
signal input from_y;
signal input R8x;
signal input R8y;
signal input S;
signal input M;
component verifier = EdDSAMiMCVerifier();
verifier.enabled <== 1;
verifier.Ax <== from_x;
verifier.Ay <== from_y;
verifier.R8x <== R8x
verifier.R8y <== R8y
verifier.S <== S;
verifier.M <== M;
}
component main = VerifyEdDSAMiMC();
You know the next steps, but here's some help
Compile it
$ circom circuit.circom -o circuit.json
Generate your input for the circuit
$ node generate_circuit_input.js
Calculate the witness for the circuit
$ snarkjs calculatewitness -c circuit.json -i input.json
Perform trusted setup
$ snarkjs setup -c circuit.json --protocol groth
Generate the proof
$ snarkjs proof -w witness.json --pk proving_key.json
Verify the proof
$ snarkjs verify
This example shows how to write smaller templates and use them as components in the main circuit.
To verify a Merkle proof, we need to take in a leaf and its Merkle root, along with the path from the leaf to the root. Let's break this down into two circuits:
get_merkle_root.circom
: This takes a leaf and a Merkle path and returns the computed Merkle rootleaf_existence.circom
: This compares an expected Merkle root with a computed Merkle root$ cd 3_verify_merkle
$ touch get_merkle_root.circom
Paste the below code in get_merkle_root.circom and go through the in line documentation.
include "../circomlib/circuits/mimc.circom";
template GetMerkleRoot(k){
// k is depth of tree
// merkel leaf
signal input leaf;
// path from leaf to root
signal input paths2_root[k];
// path from leaf to root with pos
signal input paths2_root_pos[k];
// the output variable
signal output out;
// hash of first two entries in tx Merkle proof
component merkle_root[k];
merkle_root[0] = MultiMiMC7(2,91);
// paths2_root_pos is a binary vector representing left or right node
// if `paths2_root_pos` is `0` `merkle_root[0].in[0]` becomes leaf
// and `merkle_root[0].in[1]` becomes `paths2_root[0]`
// if `paths2_root_pos` is `1` `merkle_root[0].in[0]` becomes `paths2_root[0]`
// and `merkle_root[0].in[1]` becomes `leaf`
merkle_root[0].in[0] <== leaf - paths2_root_pos[0]* (leaf - paths2_root[0]);
merkle_root[0].in[1] <== paths2_root[0] - paths2_root_pos[0]* (paths2_root[0] - leaf);
// hash of all other entries in tx Merkle proof
for (var v = 1; v < k; v++){
merkle_root[v] = MultiMiMC7(2,91);
merkle_root[v].in[0] <== paths2_root[v] - paths2_root_pos[v]* (paths2_root[v] - merkle_root[v-1].out);
merkle_root[v].in[1] <== //can you figure this one out?
}
// output computed Merkle root
out <== merkle_root[k-1].out;
}
component main = GetMerkleRoot(2);
Try to fill in the second line of the for
loop using the pattern from the lines before. (The solution is in sample_get_merkle_root.circom
.)
Now, make the second file leaf_existence.circom
and paste this in:
include "./get_merkle_root.circom";
// checks for existence of leaf in tree of depth k
template LeafExistence(k){
// k is depth of tree
signal input leaf;
signal input root;
signal input paths2_root_pos[k];
signal input paths2_root[k];
component computed_root = GetMerkleRoot(k);
computed_root.leaf <== leaf;
for (var w = 0; w < k; w++){
computed_root.paths2_root[w] <== // assign elements from paths2_root
computed_root.paths2_root_pos[w] <== // assign elements from paths2_root_pos
}
// equality constraint: input tx root === computed tx root
root === computed_root.out;
}
component main = LeafExistence(2);
Make sure to REMOVE component main = GetMerkleRoot(2)
from get_merkle_root.circom
.
Modify your input to work with leaf_existence.circom
.
All state in a rollup chain is stored in a tree whose root is kept on chain and can only be changed by submitting a snark proof which certifies valid state transitions off chain. For this workshop since we are doing ERC20 style transfers we can store user balance in the leaf of merkel tree. Let's find out more!
Each account is represented by a single leaf in the accounts tree. It is calculated by hashing the following components in the following order:
leaf = Hash(pubkey_x, pubkey_y, balance, nonce, token_type)
The account is represented by the following inputs:
class Account = {
pubkey_x: public key X // (253 bits)
pubkey_y: public key Y //(253 bits)
balance: balance // (128 bits)
nonce: nonce // (32 bits)
token_type: token type // (32 bits)
}
For the purpose of this workshop we are going to use this minimal account leaf structure.
class Account = {
pubkey: eddsa_pubkey,
balance: integer
}
For each SNARK, we construct a Transactions Merkle tree, whose leaves are the transactions processed by the SNARK.
class Transaction = {
from: eddsa_pubKey,
fromIndex: integer, // from index is the index of sender's leaf in the accounts tree
to: eddsa_pubKey,
amount: integer,
nonce: integer,
token_type: integer
}
For the purpose of this workshop we are going to use this minimal transaction structure.
class Transaction = {
from: eddsa_pubkey,
to: eddsa_pubkey,
amount: integer
}
Each deposit creates a leaf in the smart contract. The smart contract checks that the nonce, token_type and balance are correct. Anyone can aggregate these deposits into a deposit_tree with a deposit_root.
The coordinator can add these to the current balance tree by:
Withdrawing is like a normal transfer state transition. For withdraw users just have to send their tokens to zero address
which is like burning address for our chain. Tokens can only be received at this address.
zero address
We will start with processing a single transaction.
In ZkRollup, processing a single transaction involves:
accounts_root
accounts_root
to get intermediate_root
intermediate_root
accounts_root
to get final_root
Create a file called circuit.json
and fill in this boilerplate code.
include "./leaf_existence.circom";
include "./verify_eddsamimc.circom";
include "./get_merkle_root.circom";
include "../circomlib/circuits/mimc.circom";
// create template
template ProcessTx(k){
// STEP 0: Initialise signals
// STEP 1: Check sender's account existence
// STEP 2: Check sender's account signature
// STEP 3: Debit sender's account and create updated leaf
// STEP 4: Update accounts tree root with changes to sender's balance ie Debit sender's account
// Let's call this new root "intermediate root"
// STEP 5: Verify if receiver's account exists in intermediate root
// STEP 6: Credit receiver's account
// STEP 7: Update account's root with updates to receiver's account
// STEP 8: Output final root
}
// create main so that we can call it directly
component main = ProcessTx(1);
To initialise signals just copy paste the below code in the boiler plate.
// accounts tree initial root
signal input accounts_root;
// account tree root after 1 update
signal private input intermediate_root;
// account pubkeys
signal private input accounts_pubkeys[2**k, 2];
// account balances
signal private input accounts_balances[2**k];
// transactions input
signal private input sender_pubkey[2];
signal private input sender_balance;
signal private input receiver_pubkey[2];
signal private input receiver_balance;
signal private input amount;
signal private input signature_R8x;
signal private input signature_R8y;
signal private input signature_S;
signal private input sender_proof[k];
signal private input sender_proof_pos[k];
signal private input receiver_proof[k];
signal private input receiver_proof_pos[k];
// final account tree root as output
signal output new_accounts_root;
Check sender existence using the LeafExistence circuit we created in Part-3
. Copy paste the below code and fill out the correct signals.
// verify sender account exists in accounts_root
component senderExistence = LeafExistence(k, 3);
senderExistence.preimage[0] <== sender_pubkey[0];
senderExistence.preimage[1] <== sender_pubkey[1];
senderExistence.preimage[2] <== sender_balance;
senderExistence.root <== accounts_root;
for (var i = 0; i < k; i++){
senderExistence.paths2_root_pos[i] <== sender_proof_pos[i];
senderExistence.paths2_root[i] <== sender_proof[i];
}
Check that sender signature is correct and sender has signed the right message using the VerifyEdDSAMiMC
circuit we created in Part-2
// check that transaction was signed by sender
component signatureCheck = VerifyEdDSAMiMC(5);
signatureCheck.from_x <== sender_pubkey[0];
signatureCheck.from_y <== sender_pubkey[1];
signatureCheck.R8x <== signature_R8x;
signatureCheck.R8y <== signature_R8y;
signatureCheck.S <== signature_S;
signatureCheck.preimage[0] <== sender_pubkey[0];
signatureCheck.preimage[1] <== sender_pubkey[1];
signatureCheck.preimage[2] <== receiver_pubkey[0];
signatureCheck.preimage[3] <== receiver_pubkey[1];
signatureCheck.preimage[4] <== amount;
We need to reduce balance of sender by amount he is trying to transfer, so if sender's balance was 100 before transfer of 10, after transfer it should be 90. Also hash the new account leaf using MultiMiMC7
circuit template.
// debit sender account and hash new sender leaf
component newSenderLeaf = MultiMiMC7(3,91){
newSenderLeaf.in[0] <== sender_pubkey[0];
newSenderLeaf.in[1] <== sender_pubkey[1];
newSenderLeaf.in[2] <== sender_balance - amount;
}
Now that we have updated the sender's leaf we need to recompute the account tree root.
// create a component using `GetMerkleRoot` circuit.
component computed_intermediate_root = GetMerkleRoot(k);
computed_intermediate_root.leaf <== newSenderLeaf.out;
for (var i = 0; i < k; i++){
computed_intermediate_root.paths2_root_pos[i] <== sender_proof_pos[i];
computed_intermediate_root.paths2_root[i] <== sender_proof[i];
}
// check that computed_intermediate_root.out === intermediate_root
computed_intermediate_root.out === intermediate_root;
To proceed further with the transfer we need to first check if the receiver's leaf exists in the tree.
// verify receiver account exists in intermediate_root
component receiverExistence = LeafExistence(k, 3);
receiverExistence.preimage[0] <== receiver_pubkey[0];
receiverExistence.preimage[1] <== receiver_pubkey[1];
receiverExistence.preimage[2] <== receiver_balance;
receiverExistence.root <== intermediate_root;
for (var i = 0; i < k; i++){
receiverExistence.paths2_root_pos[i] <== receiver_proof_pos[i];
receiverExistence.paths2_root[i] <== receiver_proof[i];
}
We need to update the receiver's account balance with the amount sent by sender. Also create a new leaf hash for updated account.
// credit receiver account and hash new receiver leaf
component newReceiverLeaf = MultiMiMC7(3,91){
newReceiverLeaf.in[0] <== receiver_pubkey[0];
newReceiverLeaf.in[1] <== receiver_pubkey[1];
newReceiverLeaf.in[2] <== receiver_balance + amount;
}
We need to update the intermediate accounts root with the receiver balance update
// update accounts_root
component computed_final_root = GetMerkleRoot(k);
computed_final_root.leaf <== newReceiverLeaf.out;
for (var i = 0; i < k; i++){
computed_final_root.paths2_root_pos[i] <== receiver_proof_pos[i];
computed_final_root.paths2_root[i] <== receiver_proof[i];
}
Now we just need to send the final account tree root as output signal!
// output final accounts_root
new_accounts_root <== computed_final_root.out;
Now that we have a complete circuit its time to create inputs and verify the proof!
include "./leaf_existence.circom";
include "./verify_eddsamimc.circom";
include "./get_merkle_root.circom";
include "../circomlib/circuits/mimc.circom";
template ProcessTx(k){
// k is depth of accounts tree
// accounts tree info
signal input accounts_root;
signal private input intermediate_root;
signal private input accounts_pubkeys[2**k, 2];
signal private input accounts_balances[2**k];
// transactions info
signal private input sender_pubkey[2];
signal private input sender_balance;
signal private input receiver_pubkey[2];
signal private input receiver_balance;
signal private input amount;
signal private input signature_R8x;
signal private input signature_R8y;
signal private input signature_S;
signal private input sender_proof[k];
signal private input sender_proof_pos[k];
signal private input receiver_proof[k];
signal private input receiver_proof_pos[k];
// output
signal output new_accounts_root;
// verify sender account exists in accounts_root
component senderExistence = LeafExistence(k, 3);
senderExistence.preimage[0] <== sender_pubkey[0];
senderExistence.preimage[1] <== sender_pubkey[1];
senderExistence.preimage[2] <== sender_balance;
senderExistence.root <== accounts_root;
for (var i = 0; i < k; i++){
senderExistence.paths2_root_pos[i] <== sender_proof_pos[i];
senderExistence.paths2_root[i] <== sender_proof[i];
}
// check that transaction was signed by sender
component signatureCheck = VerifyEdDSAMiMC(5);
signatureCheck.from_x <== sender_pubkey[0];
signatureCheck.from_y <== sender_pubkey[1];
signatureCheck.R8x <== signature_R8x;
signatureCheck.R8y <== signature_R8y;
signatureCheck.S <== signature_S;
signatureCheck.preimage[0] <== sender_pubkey[0];
signatureCheck.preimage[1] <== sender_pubkey[1];
signatureCheck.preimage[2] <== receiver_pubkey[0];
signatureCheck.preimage[3] <== receiver_pubkey[1];
signatureCheck.preimage[4] <== amount;
// debit sender account and hash new sender leaf
component newSenderLeaf = MultiMiMC7(3,91){
newSenderLeaf.in[0] <== sender_pubkey[0];
newSenderLeaf.in[1] <== sender_pubkey[1];
newSenderLeaf.in[2] <== sender_balance - amount;
}
// update accounts_root
component computed_intermediate_root = GetMerkleRoot(k);
computed_intermediate_root.leaf <== newSenderLeaf.out;
for (var i = 0; i < k; i++){
computed_intermediate_root.paths2_root_pos[i] <== sender_proof_pos[i];
computed_intermediate_root.paths2_root[i] <== sender_proof[i];
}
// check that computed_intermediate_root.out === intermediate_root
computed_intermediate_root.out === intermediate_root;
// verify receiver account exists in intermediate_root
component receiverExistence = LeafExistence(k, 3);
receiverExistence.preimage[0] <== receiver_pubkey[0];
receiverExistence.preimage[1] <== receiver_pubkey[1];
receiverExistence.preimage[2] <== receiver_balance;
receiverExistence.root <== intermediate_root;
for (var i = 0; i < k; i++){
receiverExistence.paths2_root_pos[i] <== receiver_proof_pos[i];
receiverExistence.paths2_root[i] <== receiver_proof[i];
}
// credit receiver account and hash new receiver leaf
component newReceiverLeaf = MultiMiMC7(3,91){
newReceiverLeaf.in[0] <== receiver_pubkey[0];
newReceiverLeaf.in[1] <== receiver_pubkey[1];
newReceiverLeaf.in[2] <== receiver_balance + amount;
}
// update accounts_root
component computed_final_root = GetMerkleRoot(k);
computed_final_root.leaf <== newReceiverLeaf.out;
for (var i = 0; i < k; i++){
computed_final_root.paths2_root_pos[i] <== receiver_proof_pos[i];
computed_final_root.paths2_root[i] <== receiver_proof[i];
}
// output final accounts_root
new_accounts_root <== computed_final_root.out;
}
component main = ProcessTx(1);
Compile it
$ circom circuit.circom -o circuit.json
Generate your input for the circuit
$ node generate_circuit_input.js
Calculate the witness for the circuit
$ snarkjs calculatewitness -c circuit.json -i input.json
Perform trusted setup
$ snarkjs setup -c circuit.json --protocol groth
Generate the proof
$ snarkjs proof -w witness.json --pk proving_key.json
Verify the proof
$ snarkjs verify
Time to prove validity of this transaction on-chain!
This will return true if the proof and the inputs are valid.
$ snarkjs generateverifier
Once you have deployed the contract you can use the below to generate call data for the verify
function
$ snarkjs generatecall
Processing multiple transactions requires us to update the accounts_root
many times before we arrive at the final one. This means we have to pre-compute all the intermediate_roots
and pass them to the circuit to use in validating Merkle proofs.
Check out https://github.com/rollupnc/RollupNC/blob/master/snark_circuit/multiple_tokens_transfer_and_withdraw.circom to see how it was implemented.
We were able to build a circuit which can be used to process transactions and update state roots in a contract onchain.
Thanks @therealyingtong, @barrywhitehat and other collaborators of RollupNC for all the contributions to RollupNC and this workshop.