Table of contents
Introduction
This two-part series explores the technical structure of the upcoming ZKStack protocol upgrade introducing a ZKChain ecosystem that allows easy new rollup ZKChain creation, builtin cross-chain functionality and cheaper settlement cost by settling on another ZKChain instead of L1.
Part I delineates the three critical Merkle trees implementations that form the backbone of secure cross-layer communication in the ZKChain ecosystem, namely the L2ToL1LogsTree, the ChainTree, and the SharedTree.
Part II illustrates the most important usecase of this hierarchy of trees for a ZKChain that settles on another ZKChain instead of settling directly on L1 by constructing its recursive proof for a cross-chain token transfer.
This two-part series describes the current state of the ZKChain ecosystem and its internal procedures as of time of writing. As the ecosystem evolves, some described features can be updated in the future.
Part I: Shape of the Trees
Let's dive into the details of these critical tree data structures that support the ecosystem. For each tree, we systematically explore its:
- leaves: what make up the tree
- size: how big it is and how it grows
- root: how is the root used and where it lives.
Useful Terminology
- ZKChains: Any rollup chain in the ecosystem is considered a ZKChain. A ZKChain may settle on L1, the Ethereum network, or on another ZKChain. Only in the next part of this series we will consider a ZKChain that settles on another special ZKChain instead of L1.
- Settlement Layer: The network on which a ZKChain commits, verifies and finalizes a batch. For some chains this is Ethereum (L1), while for other chains, the settlement layer may be another ZKChain. At the moment, the only ZKChain whitelisted as Settlement Layer is the
GatewayZKChain. TheGatewaychain will be explored further in the next part of this series. - Batch: A ZKChain's batch contains the chain's transactions from one or more L2 blocks and any additional information produced within these blocks which is needed to reconstruct the ZKChain's state on the settlement layer.
- DiamondProxy: A set of smart contracts per ZKChain used in the ZKsync ecosystem that enables settlement and allows upgradability while preserving storage layout. A ZKChain's states, e.g. the merkle root of a batch, are preserved in its
DiamondProxyon the settlement layer.
In part I, we describe the trees from a general perspective in relation to its settlement layer. Here we use L2 to refer to a generic ZKChain, and L1 to refer to its settlement layer.
L2ToL1LogsTree
This tree consists of all the initiated cross-chain transactions from L2 to L1 for each committed batch. Hence each batch has its own L2ToL1LogsTree. It is constructed on each L2 chain with logs produced by L2 transactions that L1 should be notified about. No matter whether the ZKChain is settling on L1 or on another ZKChain, or whether it is a Settlement Layer itself, L2ToL1LogsTree is constructed in the same manner for all ZKChains.
The Leaves: L2ToL1Log
The L2ToL1Log leaves are formed by messages or logs from L2 transactions of each batch that include, but are not limited to:
- L1-to-L2 TX Execution Status: Logs are recorded when an L1-to-L2 transaction executes successfully or fails. In case of failure, these logs can help users recover failed L1-to-L2 token transfers.
- L2-to-L1 Token Withdrawals: A log is created when an L2-to-L1 withdrawal is initiated, such as withdrawing of native token. This also applies to withdrawals from the L2AssetRouter or the L2LegacyBridge. These logs help finalize withdrawals on L1 to complete an L2-to-L1 token bridging.
- Protocol Upgrades: When L2 contracts undergo a protocol upgrade, logs facilitate updates to L1 chain storage variables, ensuring the upgrade is reflected.
- Bytecode Publication: The compressed or uncompressed bytecode of newly deployed contracts are published on L1 using L2ToL1Logs. This helps with data availability when reconstructing L2 states from the state diffs published on L1.
In general, regular L2 transactions that do not require L1 communication are not included as L2ToL1Logs. Instead, the L2 state diffs are published on L1 to ensure data availability.
The Size: 16_384
This tree is of a fixed size of 2^14 leaves, which makes it exceptionally large with a height of 14 layers. However it can be quite sparse, meaning that there are a lot of of empty leaves. In this case, its construction requires filling it all up with a default value denoting an empty leaf. Hence this tree has enough space for future high-throughput chains.
The Root: LocalLogsRootHash
By hashing up the L2ToL1LogsTree merkle tree in the usual fashion, one gets to the local root, called LocalLogsRootHash, constructed from the 16_384 leaves.
Note that, as will be explained in the next part of this series, this is not the root that is committed to the Settlement Layer when the batch is published. To obtain the batch's root, the LocalLogsRootHash is further concatenated on the right with the root of the sharedTree, to produce the fullRootHash. (The curtain on the sharedTree will be lifted soon below.)
ChainTree
When a new ZKChain is created, its ChainTree is initiated at the MessageRoot contract on L1 but also in the ZKChain's Settlement Layer (in case it differs from L1). Each ZKChain has its own ChainTree.
Although the MessageRoot contract is force deployed at all L2 ZKChains at genesis, only Settlement Layers have non-trivial ChainTrees (and SharedTrees, as we will see later). In contrast to the L2toL1LogsTree, a chain's ChainTree does not live on its own chain, but locates at its Settlement Layer's MessageRoot contract.
In general, the Settlement Layer is responsible to keep track of an up-to-date ChainTree for every ZKChain settling on top of it. Its purpose is committing all the information regarding the successfully settled batches in a single root hash.
The Leaves: chainBatchRoot
A ZKChain's ChainTree grows a new leaf when a new batch from this ZKChain is settled at the Settlement Layer. Thus, this tree represents a record of all successfully executed batches from L2 to L1. This tree is represented using the DynamicIncrementalMerkle.Byte32PushTree data structure.
A leaf is constructed by first prefixing the committed root, that is the fullRootHash (i.e. a concatenation of the root of the L2toL1LogsTree and SharedTree) from each batch, with a BATCH_LEAF_PADDING and then suffixing the corresponding batchNumber before hashing it all to a proper leaf of 32 bytes size.
The Size
Unlike the L2ToL1LogsTree with its fixed size, the ChainTree is a dynamic structure that grows incrementally with each new executed batch on the chain's Settlement Layer. The total number of the tree's leaves is equal to the number of batches that have been settled on that layer. However, if a chain has migrated from one Settlement Layer to another, then this tree will split. When a chain migrates back, the previously stalled ChainTree will continue to grow. Hence the index of a leaf of the ChainTree may not correspond to its batch number if migration has happened.
The dynamic nature allows it to efficiently adapt to the actual throughput of the chain without requiring predetermined space allocations.
The Root: chainRoot
By hashing up the ChainTree leaves in the usual fashion, one arrives at the chainRoot. For each settling ZKChain, this root is updated whenever a new batch is executed and is used immediately to update the corresponding leaf of the SharedTree.
SharedTree
Each leaf in the SharedTree corresponds to a settling ZKChain's ChainTree root. The SharedTree lives in the MessageRoot contract, meaning in the same contract where the ChainTrees of all settling ZKChains reside. Note that similarly to ChainTree, while all ZKChains share the same design and have a SharedTree, only the SharedTree of a Settlement Layer is non-trivial. ZKChains which don't act as Settlement Layer will just expose a root denoting a default SharedTree.
The purpose of the SharedTree is to commit to all of the batches information contained in the ChainTrees of all settling ZKChains into a single root hash.
The Leaves: chainRoot
The SharedTree of a Settlement Layer grows a new leaf when a new ZKChain is added or migrated for the first time to that layer. Each leaf corresponds to one chain. This tree is represented using the FullMerkle.FullTree data structure, keeping in storage all leaves and node values.
Each leaf is formed by hashing the padded version of the chainRoot with its chainId, referred as ChainIdLeaf. Each time a ZKChain's ChainTree root gets updated (i.e. whenever a batch is settled), its corresponding leaf in the SharedTree will be updated.
The Size
The SharedTree does not grow in size unless a new ZKChain is added. With each new batch settled, the ShareTree preserves its size, but updates its root. Thus, the expected size of the SharedTree is smaller in order compared to that of ChainTree and is capped at the maximum of 100. Note that in non-settlement layers, the SharedTree is essentially empty.
The Root: aggregatedRoot
Each update to any settling ChainTree triggers a corresponding update to the aggregatedRoot. On ZKChains that are not aSettlement Layer, the aggregatedRoot is always the default hash initialised with its own chainId. However on a whitelisted settlement layer, this is the commitment to the whole transaction history of all ZKChains that settle there.
Conclusion
The three Merkle trees collectively form a sophisticated cryptographic architecture that ensures secure, verifiable communication between ZKChains and their settlement layers.
In part II, we will explore the most important application of this hierarchical structure when a ZKChain settles on another ZKChain, on the so-called Gateway chain, which is the only whitelisted settlement layer at the moment. We illustrate how to construct the recursive proof for a concrete use case of cross chain token transfer.
