Zero-Knowledge Rollup (ERC-20 Token)— Part 1

Photo by Daniele Franchi on Unsplash

Zero-Knowledge rollups (ZK-rollups) are the layer 2 solutions which can be used to compute the complexity off-chain and post the minimum amount of information on-chain. This information includes a cryptography proof (computed using Zero-Knowledge) which can be used to verify the input parameters submitted by the coordinator. This can solve the scalability issues with current layer 1 and also can be used to reduce the gas per transaction. For more details on Zero-Knowledge please refer here.

In this series of articles, we will attempt to create the contract and circuit for ZK-rollups that do ERC20 token transfers from scratch, including the following steps:-

1. Deposit ERC20 token on-chain.
2. Users send transactions to the coordinator.
3. The coordinator creates proof for the bundle of transactions(off-chain) and submits on-chain.
4. Initialise the withdrawal off-chain, and submit the proof on-chain.

We will dive into the specifics of the construction in the next parts. For the complete source code refer to this GitHub repository.

Common Terminology

1. Batch — A rollup block or a bundle of transactions.
2. Coordinator—The bundle producer.
3. Forging — Process of creating a batch off-chain and submitting the required summary on-chain.

Let’s Get Started

Preliminaries

Before we start building the circuits, make sure your system has the following. In case you don’t have any, please refer to the hyperlink to install.

1. node.js
2. ganache-cli
3. snarkjs
4. circom

Snarkjs and circom are the compiler and helper packages by IDEN3 to compile and use circuits. They are javascript based and hence very easy to use for small circuits.

To understand the basics of circom, refer to this documentation.

Asset Verifier Circuit

Verify asset transfer is a rollup circuit which is used to generate the proof for a single transaction. It includes the following from the circomlib library.

1. mimc — A block cipher and hash function family designed specifically for SNARK applications.
2. eddsamimc—Elliptic curves signature scheme.

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 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 pubkey_x;
    signal  input pubkey_y;
    signal  input R8x;
    signal  input R8y;
    signal  input S;

    signal  input nonce_from;
    signal  input to;
    signal  input nonce_to;
    signal  input amount;

    signal  input token_balance_from;
    signal  input token_balance_to;
    signal  input token_type_from;
    signal  input token_type_to;

    signal output out;

    var i;

    var NONCE_MAX_VALUE = 100;
    
    // accounts existence check
    component old_hash_from = MultiMiMC7(4,91);
    old_hash_from.in[0] <== pubkey_x;
    old_hash_from.in[1] <== token_balance_from;
    old_hash_from.in[2] <== nonce_from;
    old_hash_from.in[3] <== token_type_from;
    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] <== to;
    old_hash_to.in[1] <== token_balance_to;
    old_hash_to.in[2] <== nonce_to;
    old_hash_to.in[3] <== token_type_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;

// authorization check
    component verifier = EdDSAMiMCVerifier();   
    verifier.enabled <== 1;
    verifier.Ax <== pubkey_x;
    verifier.Ay <== pubkey_y;
    verifier.R8x <== R8x ;
    verifier.R8y <== R8y ;
    verifier.S <== S;
    verifier.M <== old_hash_from.out;
    // balance checks
    
    component greFrom = GreaterEqThan (10) ;
    greFrom.in[0] <== token_balance_from ;
    greFrom.in[1] <== token_balance_from-amount ;

    component greTo = GreaterEqThan (10) ;
    greTo.in[0] <== token_balance_to + amount ;
    greTo.in[1] <== token_balance_to ;

    component nonceCheck = GreaterEqThan (10) ;
    nonceCheck.in[0] <== NONCE_MAX_VALUE ;
    nonceCheck.in[1] <== nonce_from ;

    token_type_from === token_type_to;

//     // accounts updates
    component new_hash_from = MultiMiMC7(4,91);
    new_hash_from.in[0] <== pubkey_x;
    new_hash_from.in[1] <== token_balance_from-amount;
    new_hash_from.in[2] <== nonce_from+1;
    new_hash_from.in[3] <== token_type_from;
    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] <== to;
    new_hash_to.in[1] <== token_balance_to+amount;
    new_hash_to.in[2] <== nonce_to;
    new_hash_to.in[3] <== token_type_to;
    new_hash_to.k     <== 0 ;

 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;
}

As per our use case, we need to generate proof for multiple transactions in a bundle and not just one transaction at a time. Therefore we can build an iterator on the above circuit to solve our use case.

include "./verifyAssetTransfer.circom";

template MultipleTransaction(transactionCount, n) {

    signal input current_state[transactionCount];
    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 pubkey_x[transactionCount];
    signal  input pubkey_y[transactionCount];
    signal  input R8x[transactionCount];
    signal  input R8y[transactionCount];
    signal  input S[transactionCount];
    signal  input nonce_from[transactionCount];
    signal  input to_X[transactionCount];
    signal  input to_Y[transactionCount];
    signal  input nonce_to[transactionCount];
    signal  input amount[transactionCount];
    signal  input token_balance_from[transactionCount];
    signal  input token_balance_to[transactionCount];
    signal  input token_type_from[transactionCount];
    signal  input token_type_to[transactionCount];

    signal final_state_roots[transactionCount];

    signal output out;

    var i;

    component transaction[transactionCount];
    for (i=0; i<transactionCount; i++){
        transaction[i] = SingleTransaction(n);
        transaction[i].current_state <== current_state[i];
        transaction[i].paths2old_root_from <== paths2old_root_from[i];
        transaction[i].paths2old_root_to <== paths2old_root_to[i];
        transaction[i].paths2new_root_from <== paths2new_root_from[i];
        transaction[i].paths2new_root_to <== paths2new_root_to[i];
        transaction[i].paths2root_from_pos <== paths2root_from_pos[i];
        transaction[i].paths2root_to_pos <== paths2root_to_pos[i];
        transaction[i].pubkey_x <== pubkey_x[i];
        transaction[i].pubkey_y <== pubkey_y[i];
        transaction[i].R8x <== R8x[i];
        transaction[i].R8y <== R8y[i];
        transaction[i].S <== S[i];
        transaction[i].nonce_from <== nonce_from[i];
        transaction[i].to <== to_X[i];
        transaction[i].nonce_to <== nonce_to[i];
        transaction[i].amount <== amount[i];
        transaction[i].token_balance_from <== token_balance_from[i];
        transaction[i].token_balance_to <== token_balance_to[i];
        transaction[i].token_type_from <== token_type_from[i];
        transaction[i].token_type_to <== token_type_to[i];

        final_state_roots[i] <== transaction[i].out;
    }

    component state_root = MultiMiMC7(transactionCount,91);
    for (i=0; i<transactionCount; i++){
        state_root.in[i] <== final_state_roots[i];
    }
    state_root.k <== 0;

    out <== state_root.out;

}

Implement a main component for the above template. Currently, I have set 4 as the allowed transactions per bundle and 2 as the depth of the tree.

component main {
    public [
        pubkey_x,
        pubkey_y,
        nonce_from,
        amount,
        token_balance_from,
        to_X,
        to_Y
    ]
} = MultipleTransaction(4, 2);

Now, we need to follow the guide as per snarkjs to compile and test our final circuit.

Step 1 — Start new power of tau ceremony as per snarkjs or use the Ptau files in our GitHub repository, which is built for a circuit with constraints up to 64K. In case you change the above parameter in the main component, make sure to set up/download an appropriate Ptau file based on the new circuit constraints.

Step 2 — Compile the circuit

circom verifyAssetTransferRollup.circom --r1cs --wasm --sym

If you want to understand what is r1cs or how they are generated, please refer to this from Vitalik Buterin. View information about the circuit using the following command:-

snarkjs r1cs info verifyAssetTransferRollup.r1cs

Step 3— Export r1cs to json

snarkjs r1cs export json verifyAssetTransferRollup.r1cs verifyAssetTransferRollup.r1cs.json
cat verifyAssetTransferRollup.r1cs.json

Step 5 — Calculate the witness

verifyAssetTransferRollup_js$ node generate_witness.js verifyAssetTransferRollup.wasm ../input.json ../witness.wtns

Step 6 — Setup

I have used the groth16 proving system but you can try using PLONK referring to the steps on the snarkjs.

snarkjs groth16 setup circuit.r1cs pot16_final.ptau circuit_0000.zkey
snarkjs zkey contribute circuit_0000.zkey circuit_0001.zkey --name="1st Contributor Name" -v
snarkjs zkey contribute circuit_0001.zkey circuit_0002.zkey --name="Second contribution Name" -v -e="Another random entropy"
snarkjs zkey export bellman circuit_0002.zkey  challenge_phase2_0003
snarkjs zkey bellman contribute bn128 challenge_phase2_0003 response_phase2_0003 -e="some random text"
snarkjs zkey import bellman circuit_0002.zkey response_phase2_0003 circuit_0003.zkey -n="Third contribution name"
snarkjs zkey beacon circuit_0003.zkey circuit_final.zkey 0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f 10 -n="Final Beacon phase2"
snarkjs zkey export verificationkey circuit_final.zkey verification_key.json

Step 7 — Create the proof

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

Step 8 — Verify the proof

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

The above step will return OK! on the console, if everything is configured and executed properly.

Asset Rollup Contract

The smart contract manages deposit transactions from users and forgeBatch transactions from the coordinator.

The constructor can be used to initialise the coordinator address, ERC20 token and assetVerifier address. A struct balanceLeaf stores the current balance and transactionNonce for a unique combination of publickeyX and publickeyY.

contract AssetRollup {

    address coordinator;
    address xponentTokens;
    AssetVerifier assetVerifier;

    event Log(address indexed sender, string message);

    struct balanceLeaf {
        uint256 balance;
        uint256 transactionNonce;
    }

    mapping(uint256 => mapping(uint256 => balanceLeaf)) balanceLeaves;

    constructor(address _xponentToken, address _coordinator, address _assetVerifier) {
        coordinator = _coordinator;
        xponentTokens = _xponentToken;
        assetVerifier = AssetVerifier(_assetVerifier);
    }

}

A deposit function can be implemented to receive the ERC20 tokens and update the balance leaves for given publickeyX and publickeyY.

function deposit(uint256 _publicKey_X, uint256 _publicKey_Y, uint256 _amount) public {

    require(_amount > 0, 'Deposit amount must be greater than 0');
    IERC20(xponentTokens).transferFrom(msg.sender, address(this), _amount);
        
    balanceLeaves[_publicKey_X][_publicKey_Y].balance = balanceLeaves[_publicKey_X][_publicKey_Y].balance + _amount;

}  

The Forge Batch function can be used to verify the proof and then perform the transfer operation between the users.

function forgeBatch(
    uint256[2] memory _proofA, 
    uint256[2][2] memory _proofB, 
    uint256[2] memory _proofC, 
    uint256[29] memory _input
) public 
{

    require(assetVerifier.verifyProof(
        _proofA,
        _proofB,
        _proofC,
        _input
    ), "invalid proof submitted!!");

    uint256 pubKey_X;
    uint256 pubKey_Y;
    uint256 amount;

    emit Log(msg.sender, "Valid proof is send!!");

    for(uint8 i=0; i<4; i++){

        pubKey_X = uint256(_input[i+1]);
        pubKey_Y = uint256(_input[i+5]);
        amount = uint256(_input[i+21]);
        
        // update the from address
        balanceLeaves[pubKey_X][pubKey_Y].balance = balanceLeaves[pubKey_X][pubKey_Y].balance - amount;
        balanceLeaves[pubKey_X][pubKey_Y].transactionNonce += 1;

        // update the to address
        balanceLeaves[uint256(_input[i+13])][uint256(_input[i+17])].balance = balanceLeaves[uint256(_input[i+13])][uint256(_input[i+17])].balance + amount;

    }
    
}

Following are some helper functions to get the balance and transactionNonce for given publickeyX and publickeyY.

function getBalance(uint256 _publicKey_X, uint256 _publicKey_Y) public view returns (uint256) {
    return (balanceLeaves[_publicKey_X][_publicKey_Y].balance);
}

function getTransactionNonce(uint256 _publicKey_X, uint256 _publicKey_Y) public view returns (uint256) {
    return (balanceLeaves[_publicKey_X][_publicKey_Y].transactionNonce);
}

Next Steps

In the next part of this series we will go through the following:-

1. Build the web3 functions for the coordinator and users.
2. Withdraw circuit and contract for the users.

References

1. Rollup by IDEN3
2. Rollup by BarryWhiteHat

I’d love to hear any feedback or questions. You can ask the question by leaving a comment, and I will try my best to answer it.