Unravel the Mysteries of Merkle Trees and zkSync

What does the zkSync L2 chain have in common with Bitcoin and Ethereum? They all rely on the genius concept of Merkle Trees, born in the 1980s. But how does it apply to zkSync, you ask?

Join me as I delve into the workings of Merkle Trees and how it employs this ingenious tech to ensure the integrity and security of its data.

Deciphering Merkle Trees

Within the zkSync protocol lies the Merkle Trees technology fashioned to help securely store information on the blockchain. The cryptographic hashes associated with Merkle Тrees help ensure the integrity of the data stored on the blockchain.

Merkle Trees is a concept born in the 1980s. American computer scientist Raph Merkle proposed this binary hash tree philosophy in 1987 through a paper titled A Digital Signature Based on a Conventional Encryption Function."

The mathematician and scientist Ralph Merkle is widely hailed as one of the founders of public key cryptography, the cornerstone of the blockchain space. A Merkle Tree is a data structure blockchain used to encode blockchain data more safely and efficiently.

For instance, Bitcoin blocks help in generating a hash. On average, completing a block takes 10 minutes and includes thousands of transactions. To generate the hash, Bitcoin runs each transaction, then a pair of transactions; later, the pairs are linked until we get a hash for the block. This process, visualized, takes the form of a tree! Well, that is at least how Merkle Trees operate. But how do they work on the zkSync chain?

zkSync and State Merkle Trees

At the heart of zkSync lies the State Merkle Tree system, an iteration of the standard Merkle Tree. This system represents balances and accounts. The height of the accounts tree is represented by the symbol 'Ha' and has a value of 24, while the balance is donated by 'Hb' with a value of 8. Each of the main account trees has corresponding leaves. Balance trees are the subtrees hosted on Accounts, and each balance tree has balanced leaves.

A Leaf's hash

In this State Merkle Trees system, a Leaf's hash represents the rescue hash of the bit string. But how do you obtain the bit string? The simplest way of obtaining the bit string is encoding each of the fields in bits, in the order from least to most significant.

The account leaf

In this system, accounts can be inserted into account trees as leaves. After inserting, the account gets an AccountId, the least available ID. Account leaf comprises different fields and types, including a nonce, pubkey_hash, state tree root, and address. Notably, the state_tree_root combines the root hash of the balance_tree_root, a zero field element designated for future subtree root hash, and the rescue hash. This combination, in its entirety, is padded to 256 bits.

Moreover, the empty leaf contains state_tree_root computed using the empty balances subtree. The empty balances subtree of the account has zero in each leaf.

The Balance Leaf

The Balance leaf, on the other hand, contains a field named value, with the type being StateAmount. An empty leaf will have a value equal to zero.

zkSync Block Pub Data Format

Lastly, the zkSync block pub data format consists of a Rollup operations pub data sequence, with a constant value as the maximum block size. What if the size of operations is not enough to fill the block? In that case, the remaining space is filled using an empty Noop operation.

Optimistic Rollups Merkle Trees System

Optimistic Rollups are layer 2 solutions that offload transaction processing weight from Ethereum's L1 blockchain. They bolster transaction throughput.

These rollups leverage Merkle proofs in transaction validation while running them completely off-chain. The blocks consist of a cryptographic proof, the Merkel Tree root, and the summary for the new account. Typically, Optimistic rollups run assuming that each transaction on L2 is valid. They bring simplicity and lower transaction costs while causing an extension of withdrawal times. Notice the optimistic rollups leverage Merkel Trees to validate transactions off-chain.

These rollups deploy a contract in L1, which manages the rollup state and handles deposits, balances, withdrawals, and disputes. Furthermore, these systems utilize sequencers or operators whose defined role is collecting and aggregating transactions off-chain. These operators will bundle a myriad of transactions into a single 'rollup block. The operators later submit the bundled block to the mainchain by providing the Merkle tree root and additional "call data." The data helps in verifying the rollup block's validity later.

Plasma Chain

Merkle proofs are also applicable in another class of L2 solutions, Plasma.

Plasma's rollup solution combines fraud proofs and Merkle Trees to validate transactions off-chain. By marrying smart contracts and Merkle Trees, Plasma can create child chains, and copies of the parent blockchain (Ethereum). Offloading transactions makes the transactions cheaper and faster as each Merkle Trees-enabled Chains is independent. So transactions first occur on the mainchain. In fraud cases in the plasma child chain, users exit and return to the parent chain. However, the critical point is that Plasma mainly leverages Merkle Trees in service delivery.

Final Word

In summary, Merkle Trees are the fundamental technologies designed to ensure the integrity and efficiency of data stored. In Bitcoin, Merkle is vital in generating hashes for blocks, and securing the myriads of transactions.

zkSync leverages State Merkle Trees, a variant of Merkle trees, to represent balances and accounts. The construction of leaves in this system, whether account or balance leaves, follows a specific procedure, promoting clarity and structural integrity.

Other technologies like Optimistic Rollups and Plasma leverage Merkle Trees, which help offload transactions from the Ethereum main chain, bolstering throughput and reducing costs. Merkle Trees continue to shape the blockchain space, confirming their place as the cornerstone of the realm.