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.

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:

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
Smart Contract

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

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:

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:

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.

PreviousSmart ContractsNextTransaction Tree

Last updated