Rollups, more specifically ZK Rollups are known as ”hybrid” Layer 2 models, as they move computations off-chain while keeping data on-chain. Rollups begin with a commitment, or “state root,” to a smart contract on the Layer 1 EVM. This state root is derived from the state of all deposits and accounts in the rollup, using a Merkle Tree accumulator. Once this state root has been updated, a batch of the transactions is posted with the state root.

As mentioned above, ZK Rollups store all addresses and balances in a Merkle Tree, or balance tree, wherein the root of this balance tree is stored in an on-chain smart contract. Every new batch produces a new on-chain Merkle Tree proposal that updates all balances from transfers included in the batch. This smart contract will then verify a zk-SNARK proof that is posted with the batch and, if verified, will accept the new Merkle root, becoming the canonical state of the root contract. A great graphical representation of how this works is shown below:

Source: Simon Brow from FCAT Blockchain Incubator

When a deposit is made to a rollup, tokens are transferred to a rollup contract, creating a sort of queue, that will eventually be submitted into the balance tree when a certain number of deposits have been submitted. More specifically, upon deposit, a smart contract takes all of the information about the deposit and creates a hash, and places this hash at the end of the queue. The contract will then recursively hash the last two deposits in the queue to iteratively build up a Merkle Tree of deposit hashes which becomes a sub-tree of the balance tree.

An example of how these operations, derived from an article from FCAT Blockchain Incubator, works is as follows:

• Deposit made to the rollup contract, creating a deposit queue with one deposit:

  Hash(pubkey, amount, token type) = 0x1234abcd...    //First Deposit
  

• Another deposit follows in similar fashion:

  Hash(pubkey, amount, token type) = 0x9876fec...    //Second Deposit
  

• With the subsequent deposit, the deposit queue looks like this:

  [0x1234abcd, 0x9876fedc]
  

• The second deposit transaction continues the process by hashing the last two elements in the queue, as there is now an even number of deposits:

  Hash([0x1234abcd, 0x9876fedc]) = 0x6663333    //New hash element
  

• Now the deposit looks like this:

  [0x6663333]
  

This new hash now represents the two deposits made to the rollup, but how is a coordinator supposed to track which deposit this hash represents and how many deposits this hash contains? Well, each deposit emits an event that the coordinator can subscribe to, allowing them to keep track of the individual deposit details. Additionally, each contract maintains a count size of the deposit queue and the deposit sub-tree height.

Note that all rolled-up deposits and balances are stored in a Merkle Tree of a fixed size, initialized with all zeros, known as a Sparse Merkle Tree. This is important for understanding the next topic of understanding processing deposits.

Continuing through this example, let's take a look at processing deposits. A coordinate will start by taking the first element of a pending deposit queue and inserting it into the rollup’s sparse balance tree at its corresponding height. This results in a new Merkle root for the balance tree in which coordinators post to the rollup contract. In addition to this addition to the Merkle root, a coordinator also submits a proof for the corresponding level of the balance tree, thus replacing the root of the deposit subtree below.

Source: Simon Brow from FCAT Blockchain Incubator

Depositors at this stage can use the Merkle proof above to independently verify the status of their deposit.

Due to the nature of this space, a smart contract is not going to blindly trust that a coordinator is acting as an honest prover and thus the need for zero-knowledge comes into play. A coordinator must show that the transactions they bundled and processed were conducted correctly and will verify this. The coordinator must compile the following inputs into a ZK Proof Circuit in order for this proof to be valid:

• A Merkle Tree with all of the batch’s transactions
  • Note here that if the space requirement is not met, the coordinator will include dummy transactions to meet the minimum size requirement
• A collection of Merkle proofs for transactions to prove account existence for each sender and receiver
• A collection of intermediate roots derived from the updating of the balance tree root

There are some more in-depth technicalities here that are required before the smart contract is satisfied by the conditions that involve arithmetic circuits, but as that has already been covered in the sub-page at the end of the page we will not be covering them.