Account/ State Tree

The main data silo of RollupNC. Roughly analogous to the blockchain network in L1

The prevailing data structure throughout the roll-up is a single merkle tree representing the entire L2 network state. That is, the merkle root represents a set of "account" leaves inserted into an incremental merkle tree.

Account Leaves

In order to represent an abstraction of data in our merkle tree (i.e. a layer 2 account), we need a standardized 'type' that we can use to define or encode the data stored in the merkle tree. A given account is represented as:

// pseudocode
type account = {
    pubkey[2], // the x and y coordinate points representing the EdDSA pubkey
    balance, // the balance of this account (in tokenType tokens)
    nonce, // the number of transactions this account has made
    tokenType // the id of the token as registered in TokenRegistry.sol
}

In order to turn an account into an account leaf, we simply apply the Poseidon hash function with 5 inputs.

JavaScript

We can use the circomlibjs sibling function to the circomlib Poseidon hash to generate the data we need in JavaScript:

const { buildEddsa, buildPoseidon } = require('circomlibjs');

const ACCOUNT = {
        pubkey: [
                17510887784963622030507426065813392782428649726760807616388320420146084695664,
                2413177600120835155845719154164593881211291333131710625804258147767377075981n
        ],
        balance: 1570200067000000000,
        nonce: 3,
        tokenType: 7
};

async function accountLeaf(account) {
        const poseidon = await buildPosiedon();
        const data = [
                ...ACCOUNT.pubkey,
                ACCOUNT.balance,
                ACCOUNT.nonce,
                ACCOUNT.tokenType
        ];
        const hash = poseidon(data);
        return poseidon.F.toObject(hash); // convert to bigint when returning
        
};
accountLeaf(ACCOUNT).then(console.log); // outputs the account leaf
        

Smart Contract

In the smart contract, account leaves are only generated for deposits. At all other points the L1 verification of account leaves happens in Zero Knowledge. The generation of account leaves is shown here:

function deposit(
    uint256[2] memory pubkey,
    uint256 amount,
    uint256 tokenType
) public payable {
    // Ensure token can be transferred
    checkToken(amount, tokenType);
    // Store deposit leaf
    uint256 depositHash = PoseidonT6.poseidon(
        [pubkey[0], pubkey[1], amount, uint256(0), tokenType]
    );
    pendingDeposits[depositQueueEnd] = depositHash;
    .
    .
    .
}

Zero Knowledge

In the Zero Knowledge circuit, there is a specialized template/ component made for verifying the integrity of an account leaf with a Poseidon Hash: balance_leaf.circom.

pragma circom 2.0.3;

include "../../../node_modules/circomlib/circuits/poseidon.circom";

template BalanceLeaf() {

    signal input pubkey[2]; // Account EdDSA pubkey [x, y]
    signal input balance; // Account token balance
    signal input nonce; // Number of transactions made by the account
    signal input tokenType; // Token registry index for token type

    signal output out;

    component balanceLeaf = Poseidon(5);
    balanceLeaf.inputs[0] <== pubkey[0];
    balanceLeaf.inputs[1] <== pubkey[1];
    balanceLeaf.inputs[2] <== balance;
    balanceLeaf.inputs[3] <== nonce; 
    balanceLeaf.inputs[4] <== tokenType;

    out <== balanceLeaf.out;
}

Proof of Account Leaf Inclusion in Tree

This section will cover the basic of account leaf inclusion proof. The application of this proof to the effect of the Rollup is further discussed in Layer 1 Deposits to Layer 2. It will also be similar to the Transaction Leaf Inclusion Tree. We will be incrementally adding entries to an empty binary merkle tree as accounts enter L2. At any given point, proving inclusion in the on-chain state root confers the integrity of your L2 balance as encoded above.

The first thing to note is the tree depth - this is specified in update_state_verifier.circom as a main component's template parameter:

pragma circom 2.0.3;
.
.
.
// the first parameter `balDepth` specifies state tree depth
template Main(balDepth, txDepth) {
    .
    .
    .
}

// state tree depth set to 4
component main { public [txRoot, prevRoot, nextRoot] } = Main(4, 2);

For the purpose of succinct testing, we set a very small state tree depth of 4. Binary merkle trees have a size of 2^n where n is the depth of the tree, meaning our state tree can hold 16 unique accounts. For production grade L2 networks, in 2020 Loopring used a tree depth of 24 and decided to decrease to a depth of 20 (pull req).

We will use EF PSE's @zk-kit/incremental-merkle-tree (npm package docs here) to assist in the generation of merkle inclusion proofs. Consider an account tree visualized below:

Legend

See legend expandable to understand conceptually how state is encoded in this tree

Now, let us consider how to prove the following inclusion for Bob's account:

• Green is state root

• Blue is intermediate root

• Grey is sibling node

• Red is leaf being proved for inclusion

• White is data that does not need to be available to prove inclusion

JavaScript

const crypto = require('crypto');
const { buildEddsa, buildPoseidon } = require('circomlibjs');
const { IncrementalMerkleTree } = require('@zk-kit/incremental-merkle-tree');
async function main() {

    /// instantiate circomlibjs libraries
    const eddsa = await buildEddsa();
    const poseidon = await buildPoseidon();
    const F = poseidon.F;
    
    /// make zero account
    const zeroLeaf = poseidon([0, 0, 0, 0, 0])
    
    /// make sequencer account
    const sqPrv = crypto.randomBytes(32);
    const sqPub = eddsa.prv2pub(sqPrv);
    const sqLeaf = poseidon([...sqPub, 0, 0, 0])

    /// make alice account with .5 ether (token type 1) & 3 transactions
    const alicePrv = crypto.randomBytes(32);
    const alicePub = eddsa.prv2pub(alicePrv);
    const aliceLeaf = poseidon([...alicePub, 500000000000000000, 3, 1]);

    /// make bob account with 1.5 ether & 0 transactions
    const bobPrv = crypto.randomBytes(32);
    const bobPub = eddsa.prv2pub(bobPrv);
    const bobLeaf = poseidon([...bobPub, 1500000000000000000, 0, 1]);

    /// make charlie accouunt .005 ether & 2 transactions
    const charliePrv = crypto.randomBytes(32);
    const charliePub = eddsa.prv2pub(charliePrv);
    const charlieLeaf = poseidon([...charliePub, 5000000000000000, 2, 1]);

    /// create state tree using poseidon hash function with depth of 4 and empty leaf value of 0
    const stateTree = new IncrementalMerkleTree(poseidon, 4, 0);
    stateTree.insert(F.toObject(zeroLeaf));
    stateTree.insert(F.toObject(sqLeaf));
    stateTree.insert(F.toObject(aliceLeaf));
    stateTree.insert(F.toObject(bobLeaf));
    stateTree.insert(F.toObject(charlieLeaf));

    /// get proof of inclusion of Bob's account (@ index 3 in incremental tree)
    let proof = stateTree.createProof(3);
    const root =  proof.root
    const leaf = proof.leaf;
    const pathIndices = proof.pathIndices;
    const siblings = proof.siblings; // 4 siblings in quinary tree, binary tree has array of only 1 sibling per level
    console.log("Tree root being checked for leaf inclusion", root);
    console.log("Leaf being checked for inclusion in tree: ", leaf);
    console.log("Leaf path to root ", pathIndices);
    console.log("Path siblings: ", siblings);

    /// verify state tree contains a leaf given a path and siblings (merkle proof)
    proof.root = F.toObject(proof.root);
    console.log(stateTree.verifyProof(proof));
}

Smart Contract

The contract verifies merkle proofs when processing deposits and withdrawals. This is driven by the getRootFromProof contract function:

function getRootFromProof(
    uint256 _leaf,
    uint256[] memory _position,
    uint256[] memory _proof
) public pure returns (uint256) {
    uint256 hash = _leaf;
    for (uint8 i = 0; i < _proof.length; i++) {
        if (_position[i] == 0)
            hash = PoseidonT3.poseidon([hash, _proof[i]]);
        else hash = PoseidonT3.poseidon([_proof[i], hash]);
    }
    return hash;
}

These inputs can be generated as seen in the JavaScript expandable.

Zero Knowledge

The balance_existence_check.circom component (relying on a generic merkle leaf component leaf_existence.circom) is responsible for checking for the existence of a transaction leaf in zero knowledge:

pragma circom 2.0.3;

include "./get_merkle_root.circom";

template LeafExistence(depth){
// k: tree depth
// Constrain proof to a given leaf that can be proven to exist in the given root
    signal input leaf; 
    signal input root;
    signal input proof[depth];
    signal input positions[depth];

    component computedRoot = GetMerkleRoot(depth);
    computedRoot.leaf <== leaf;

    for (var i = 0; i < depth; i++){
        computedRoot.proof[i] <== proof[i];
        computedRoot.positions[i] <== positions[i];
    }
    // equality constraint
    root === computedRoot.out;
}

As expanded upon in Layer 2 Transacting, update_state_verifier.circom chains multiple balance existence checks together to perform the verifiable computation of transitions between state roots.

Priming/ Instantiation of the Account Tree

In order to operate the roll-up, two accounts must be added at instantation:

• Zero Address (burning and withdrawing)

• Sequencer Account (permissioned)

Reiterated from the JavaScript above, this can be shown as:

/// instantiate circomlibjs libraries
const eddsa = await buildEddsa();
const poseidon = await buildPoseidon();
const F = poseidon.F;
    
/// make zero account
const zeroLeaf = poseidon([0, 0, 0, 0, 0])

/// make sequencer account
const sqPrv = crypto.randomBytes(32);
const sqPub = eddsa.prv2pub(sqPrv);
const sqLeaf = poseidon([...sqPub, 0, 0, 0])

These two deposits can be batched instantly into the contract state (see Layer 1 Deposits to Layer 2) instantly; however the next batch will be limited to depth of 1 or 2.