Scroll: zkTrie and L1/L2 Interoperability

Scroll is a Layer 2 scaling solution for Ethereum that leverages Zero Knowledge proof (ZKproof) technology, combined with EVM (Ethereum Virtual Machine) compatibility. Scroll aims to enhance Ethereum’s scalability while maintaining the same developer-friendly environment that Ethereum provides.

What is zkTrie

zkTrie is a sparse binary Merkle Patricia Trie used to store key-value efficiently. We will look into tree structure, node hashing, construction, and tree operations including insertion and deletion.

Tree Structure

Before going deeper into Sparse Binary Merkle Patricia Trie, let’s discuss Merkle Trees and Patricia Tries.

• Merkle Tree: a Merkle Tree is a tree where each leaf node represents a hash of a data block and each non-leaf node represents the hash of its child node.
• Patricia Trie: a Patricia Trie is a type of radix tree or compressed trie used to store key-value pairs efficiently. It encodes the nodes with same prefix of the key to share the common path, where the common path is determined by the value of the node key.

zkTrie Structure, from Scroll docs

The figure above shows that there are three types of nodes in the zkTrie.

• Branch Node: a branch node has two children.
• Leaf Node: A leaf node holds the data of key-value pair.
• Empty Node: an empty node is a special type of node, indicating the sub-trie that shares the same prefix is empty.

In zkTrie a Poseidon hash is used to compute the node hash because it is more friendly and efficient to prove it in the zk circuit.

Tree Construction

Given a key-value pair, you first compute a secure key for the corresponding leaf node by hashing the original key using the Poseidon hash function. This can make the key uniformly distributed over the key space.

You then encode a path of a new leaf node by traversing the secure key from Least Significant Bit (LSB) to the Most Significant Bit (MSB). At each step, if the bit is 0, you will traverse to the left child; otherwise, traverse to the right child.

Scroll limit the maximum depth of zkTrie to 248, meaning that the tree will only traverse the lower 248 bits of the key. Because the secure key space is a finite field used by Poseidon hash that doesn’t occupy the full range of 2²⁵⁶, the bit representation of the key can be ambiguous in the finite field and thus results in a soundness issue in the zk circuit. After you truncate the key to lower 248 bits, the key space can fully occupy the range 2²⁴⁸ and won’t have ambiguity in the bit representation.

You can apply an optimization to reduce the tree depth by contracting a subtree that has only one leaf node to a single leaf node. For example, in the image above, the tree has three nodes in total, with keys 0100, 0010, and 1010. Because there is only one node that has a key with suffix 00, the leaf node for key 0100 only traverses the suffix 00 and doesn’t fully expand its key which would have resulted in a depth of 4.

Tree Operations

Insertion

Insert a new leaf node to zkTrie, From Scroll docs

When we insert a new leaf node into a zkTrie, there are two cases as seen in the image above.

1. When traversing the path of the node key, it reaches an empty node (case 1(a)). In this case, you just need to replace this empty node by this leaf node and backtrace the path to update the Merkle hash of branch nodes till the root.
2. Whentraversing the path of the node key, it reaches another leaf node (case 2(b)). In this case, you need to push down the existing leaf node until the next bit in the node keys of two leaf nodes differs. At each push-down step, you need to insert an empty sibling node into the branch node. When you reach the level where the bits differ, you then place two leaf nodes b and d as the left child and the right child depending on their bits. Alas you backtrace the path and update the Merkle hash of all branch nodes

Deletion

Delete a leaf node from the zkTrie. From Scroll docs

Deletion of a leaf node is similar to insertion, There are two cases as seen in the image above.

1. The sibling node of the to-be-deleted node is a branch node (case (a)). You can simply replace node a with an empty node and update the node hash of its ancestors till the root node.
2. The sibling node of the to-be-deleted leaf node is a leaf node (case (b)). First, you replace the leaf node with an empty node and start to contract its sibling node upwards until its sibling node is not an empty node.

Note: the sibling of a leaf node in a valid zkTrie cannot be an empty node. Otherwise, you should always prune the subtree and move the leaf node upwards.

Node Hashing

I will describe how the leaf secure key and node Merkle hash are computed. We will use Poseidon hash with arity 2 for both hashing computations. In Scroll, the Poseidaon hash function is configured to take two field element inputs each time and a domain_value as the initial context for domain separation, denoted as

h{domain_value}(input1, input2)

Empty Node

The node hash of an empty node is 0.

Branch Node

The branch node hash is computed as:

branchNodeHash = h{BranchNodeType}(leftChildHash, rightChildHash)

Leaf Node

The leaf node has is computed as:

leafNodeHash = h{LeafNodeType}(nodeKey, valueHash)

The computation involves two fields, nodeKey and valueHash .

• nodeKey is hashed from the original key. The domain used in the Poseidon hash is 256.
• valueHash is calculated by hashing the leaf node value. The domain value used in the Poseidon hash is 256 * n where n is the number of elements in the leaf node value

There are two types of leaf nodes; Ethereum accounts and storage-key-value pairs. Now let’s describe the calculation method of the node key and value hash for each leaf node type.

Ethereum Account Leaf Node

An Ethereum Account leaf node consists of an Ethereum address and a state account data structure. The secure key is derived from the Ethereum address

var address byte[20] // 20 bytes in big-endian
valHi := address[0:16]
valLo := address[16:20] * 2^96 // padding 12 bytes of 0 at the end
nodeKey := h{512}(valHi, valLo)

A state account struct in the Scroll consists of the following fields (Fr indicates the finite field and is a 254-bit value)

• Nonce: u64
• Balance: u256, but treated as Fr
• StorageRoot: Fr
• KeccakCodeHash: u256
• PoseidonCodeHash: Fr
• CodeSize: u64

Before computing the value hash, the state account is first marshaled into a list of u256 values. The marshaling scheme is:

(The following scheme assumes the big-endian encoding)
[0:32]
  [0:16] Reserved with all 0
  [16:24] CodeSize, uint64 in big-endian
  [24:32] Nonce, uint64 in big-endian
[32:64] Balance
[64:96] StorageRoot
[96:128] KeccakCodeHash
[128:160] PoseidonCodehash
(total 160 bytes)

The marshal function also returns a flag value along with a vector of u256 values. The flag is a bitmap that indicates whether a u256 value cannot be treated as a field element (Fr). The flag value for state account is 8, as shown below:

         +--------------------+---------+------+----------+----------+
 index   |          0         |    1    |   2  |     3    |     4    |
         +--------------------+---------+------+----------+----------+
  u256   | nonce||codesize||0 | balance | root |  keccak  | poseidon |
         +--------------------+---------+------+----------+----------+
flag bit |          0         |    0    |   0  |     1    |     0    |
         +--------------------+---------+------+----------+----------+
         (LSB)                                                   (MSB)

The value hash is computed in two steps:

1. Convert the value that cannot be represented as a field element of the Poseidon hash to the field element.
2. Combine field elements in a binary tree structure till the tree root is treated as the value hash.

In the first step, when the bit in the flag is 1 indicating the u256 value that cannot be treated as a field element, we split the value into a high-128bit value and a low-128bit value, and then pass them to a Poseidon hash to derive a field element value, h(valueHi, valueLo).

// convert Keccak codehash to a field element
compressedKeccakCodeHash := h{512}(keccakCodeHash[0:16], keccakCodeHash[16:32])

Then the value hash is computed as follows:

domain := 256 * 5  // 5 elements to compute the valueHash
valueHash :=
    h{domain}(
        h{domain}(
            h{domain}(nonce||codesize||0, balance),
            h{domain}(
                storageRoot,
                compressedKeccakCodeHash,
            ),
        ),
        poseidonCodeHash,
    )

Storage Leaf Node

A Storage Leaf Node encodes a key-value pair where both key and value are u256 values. The secure key of this leaf node is derived from the storage key.

var storageKey byte[32]  // 32 bytes in big-endian
valHi := storageKey[0:16]
valLo := storageKey[16:32]
nodeKey := h{512}(valHi, valLo)

The storage value is a u256 value. The flag for the storage value is 1, as shown below.

         +--------------+
  index  |      0       |
         +--------------+
  u256   | storageValue |
         +--------------+
flag bit |      1       |
         +--------------+

The value hash is computed as shown below:

valueHash = h{512}(storageValue[0:16], storageValue[16:32])

That’s all about zkTrie.

L1/L2 Interoperability

The Scroll bridge enables transfer of ETH, ERC20 tokens, NFTs, and arbitrary messages between L1 and L2. It serves as a secure system/mechanism for moving various digital assets across L1 and L2.

The Scroll bridge utilizes the Gateway Router to facilitate the transfer of ETH and ERC20 tokens. This contract ensures the smooth passage of these assets between L1 and L2, allowing users to transfer their Ethereum-based tokens hassle-free.

The ERC721 and ERC1155 Gateway enables the transfer of non-fungible assets(NFTs) between the two networks, allowing users to move their NFTs across L1 and L2.

The Scroll Messenger contract also enables cross-chain contract interaction, which means that contracts on one network can interact with contracts of another network through the Scroll Messenger contract. This expands the possibilities for DAPPs(Decentralized Applications) and smart contracts to operate seamlessly across both networks.

L1 Gateway architecture

From scroll docs

If you want to send ETH or ERC20 tokens, you should use the GatewayRouter . If you want to send NFTs, you should use the L1ERC20Gateway or L1ERC115Gateway . If you want to send arbitrary data, you should use the L1ScrollMessenger . All Gateway transfers use the Scroll Messenger to send assets cross-chain, whose job is to append transactions to the Message Queue for L2 inclusion.

L2 Gateway architecture

The L2 Gateway architecture is very similar to the L1’s Gateway architecture. The difference is that when sending a message from L2, calling the appendMessage function will store the message in an append-only Merkle tree (withdraw tree) in the L2MessageQueue . When a new message is sent to the L2MessageQueue , the relayer will detect it and store it in the database. When the block is finalized, it will generate a proof of the new merkle path and pass it to the L1geth node to execute on L1ScrollMessenger . All finalized withdraw roots are then stored on the rollup contract so the proof can be verified against them.

ETH and ERC Token Bridge

Deposit ETH and ERC20 tokens from L1

The Gateway Router allows ETH and ERC20 token bridging from L1 to L2 using the depositETH and depositERC20 functions respectively. It is a permissionless bridge deployed on L1. ERC20 tokens will have a different address on L2, you can use the getL2ERC20Address function to query the new address.

NOTE: both depositETH and depositERC20 are payable functions, the amount of ETH sent to these functions will be used to pay L2 fees. 0.0001 ETH should be enough to process a token deposit, also if the fee amount is not enough, the transaction won’t be sent. All excess ETH will be sent back to the sender.

When bridging ERC20 tokens, you don’t have to worry about selecting the right Gateway. This is because the L1GatewayRouter will choose the correct underlying entry point to send the message:

• L1StandardERC20Gateway: This Gateway permits any ERC20 deposit and will be selected as the default by the L1GatewayRouter for an ERC20 token that doesn’t need custom logic on L2. On the very first token bridging, a new token will be created on L2 that implements the ScrollStandardERC20. To bridge a token, call the depositERC20 function on the L1GatewayRouter.
• L1CustomERC20Gateway: This Gateway will be selected by the L1GatewayRouter for tokens with custom logic. For an L1/L2 token pair to work on the Scroll Custom ERC20 Bridge, the L2 token contract has to implement IScrollStandardERC20. Additionally, the token should grant mint or burn capability to the L2CustomERC20Gateway.

All Gateway contracts will form the message and send it to the L1ScrollMessenger which can send arbitrary messages to L2. The L1ScrollMessenger passes the message to the L1MessageQueue. A user can send messages directly to the Messenger to execute arbitrary data on L2. This means they can execute any function on L2 from a transaction made on L1 via the bridge. Although an application could directly pass messages to existing token contracts, the Gateway abstracts the specifics and simplifies making transfers and calls.

When a new block gets created on L1, the Watcher will detect the message on the L1MessageQueue and will pass it to the Relayer service, which will submit the transaction to the L2 via the l2geth node. Finally, the l2geth node will pass the transaction to the L2ScrollMessenger contract for execution on L2.

Withdraw ETH and ERC20 tokens from L2

The L2 Gateway is similar to the L1 Gateway. You can withdraw ETH and ERC20 tokens back to L1 using the withdrawETH and withdrawERC20 functions. The contract address is deployed on L2. Use the getL1ERC20Address to retrieve the token address on L1.

NOTE: withdrawETH and withdrawERC20 are also payable functions. Fees will depend on L1 activity but 0.005 ETH should be enough to process a token withdrawal.

L1 Gateway API

Recommend visiting the npm library for the complete Scroll cotract API documentation.

depositETH

function depositETH(address _to, uint256 _amount, uint256 _gasLimit) public payable;

Sends ETH from L1 to L2

From: Scroll docs

depositERC20

function depositERC20(address _token, address _to, uint256 _amount, uint256 _gasLimit) payable;

Sends ERC20 tokens from L1 to L2

From: Scroll docs

getL2ERC20Address

function getL2ERC20Address(address _l1Token) external view returns (address);

Returns the corresponding L2 token address given L1 token address

updateTokenMapping

function updateTokenMapping(address _l1Token, address _l2Token) external;

Updates the mapping that connects an ERC20 token from L1 to L2.

L2 Gateway API

withdrawETH

function withdrawETH(address to, uint256 amount, uint256 gasLimit) external payable;

Sends ETH from L2 to L1

withdrawERC20

function withdrawERC20(address token, address to, uint256 amount, uint256 gasLimit) external payable;

Sends ERC20 tokens from L2 to L1

getL1ERC20Address

function getL1ERC20Address(address l2Token) external view returns (address);

Returns the corresponding L1 token address given an L2 token address

updateTokenMapping

function updateTokenMapping(address _l1Token, address _l2Token) external;

Updates the mapping that connects an ERC20 contract from L2 to L1

That’s the end of what I will be covering in this article. I believe Scroll’s close relationship with Ethereum will allow developers to easily build on Scroll and get to scale what can be done on both Ethereum and Scroll.

I believe this article has given you a head start on what zkTrie is and L1/L2 interoperability, I hope with this you can go out there and start exploring the possibilities of building with scroll. If you want to get more info on things like ERC721 NFT bridging, ERC1155 Token bridging and Sroll Messenger you should check this Scroll doc: https://docs.scroll.io/en/developers/l1-and-l2-bridging/

Thanks for reading.

Resources:

Scroll docs: zkTrie: https://docs.scroll.io/en/technology/sequencer/zktrie/ L1/L2 Interoperability and bridging: https://docs.scroll.io/en/developers/l1-and-l2-bridging/