TLDR: This article explores the approaches of different L2s to cross-chain messaging from rollups’ perspective, focusing more on trustless cross-chain communication. We briefly explain the direct state reading approach, light client approach, and storage proofs. We also mention proof aggregating mechanism, trusted-third party cross-chain messaging, and core ZK-cross-chain solutions. In the end, we cover examples of how different L2s approach cross-chain messaging today.

Part I: Introduction to cross-chain messaging

• Two types of access: direct state reading and proof generation

• Approaches to "cross-chain messaging with a proof": cross-chain messaging with Light Client, storage proofs

• Trusted third parties

• "Common" proving system

• Some open unclear questions when it comes to ZK-cross-chain messaging

Part II: some ZK-cross-chain messaging solutions

Part III: different approaches to cross-chain messaging by different L2s

For cross-chain communication, all parties (L2s, L3s, etc.) must have direct access to the recent Ethereum state root.

All layers that provide deposits already have a "built-in" cross-chain mechanism that could be used to get the L1 state root. The state root will be passed to L2 as a deposit message in this case.

Type 1: direct state reading – could be done with an opcode or a precompile. However, it hasn’t been implemented yet so no proof is needed.

• One of the possible approaches to direct state reading was described in the research post by Brecht Devos: "…we can expose a precompile contract that can directly call a smart contract on the destination chain. This precompile injects and executes the smart contract code of the other chain directly in the source chain. This ensures that smart contracts always have access to the latest available state in an efficient and easily provable way."

• As well as in the Optimism RFP "Remote Static Call Proof of Concept."

Type 2: proof generation – that is, proving statements about one blockchain on another blockchain.

There are two approaches to "cross-chain messaging with proof":

• Trustless cross-chain communication – that is, with no trusted third party (ex., using a light client or a storage proof). Trustless approach can work both with third party generating proof or with cross-chain communication participants generating proofs on their own.

• Shared proofs between different rollups to guarantee the cross-chain actions. This category is out of scope for the current article as it is currently in the research and exploration stage and is not considered a presumably widely used solution. For more details, check the research proposal for shared fraud proofs (by Succinct Labs and Ellipsis Labs) and the research proposal for a shared proof aggregator mechanism (by Kalman Lajko).

Cross-chain messaging with Light Client

To prove chain B data on chain

• Get the Merkle proof data from a chain B full node (archive node if a storage proof is needed against some old state);

• Send the proof data and the header corresponding to the chain B block containing the state we want to verify as calldata to the prover contract on chain A;

• The prover contract computes the block hash from the header data, queries the Light Client smart contract on chain A (which keeps track of chain B block hashes), and checks whether the hash is valid;

• Proof data is verified against the bytes32 state root in the block header.

Storage proofs

There are two “workflow” options for storage proofs:

• generate storage proof → use it on-chain

• generate storage proof → generate zk proof → use it on-chain

There also might be an entity that collects multiple proofs into single proof (both in case of storage and zk proofs). That’s an optional optimization step that is currently out of scope.

Below we review three main stages of the storage proof “workflow”: storage proof generation, zk proof generation, on-chain usage.

1. Generate a storage proof

• Storage proofs allow us to prove that certain information exists on a blockchain and is true using cryptographic commitments;

• Storage proofs have been a part of the cryptographic landscape since the invention of Merkle trees in 1979. However, vanilla proof of storage is often quite large. The modern world innovation lies in combining storage proofs with provable computation to create succinct proofs that can be verified on-chain;

• An example is described in this article.

To generate a storage proof, one must provide a specific piece of data and its associated Merkle or Verkle path within the tree. The path consists of the sibling hashes required to reconstruct the root hash using the same hashing algorithm.

To verify a storage proof, a recipient can use the provided data and Merkle or Verkle path to recompute the root hash. If the recomputed root hash matches the known root hash, the recipient can be confident that the data is authentic and part of the committed dataset.

2. Generate ZKP

However, an Ethereum-style storage proof is ~4kb – pretty large to post the entire storage proof on the target chain, as the proof verification will be pretty expensive. So it is reasonable to use ZKP (ex., ZK-SNARK) to provide compression, making the proof smaller and cheaper to verify.

3. Unroll ZKP

After getting the ZKP, users on the destination chain can unroll the proof they got (ex., access the past states through headers or block hash).

Unrolling can be done through

1. On-chain accumulation: the entire procedure of recreating block headers from proof is performed directly on the blockchain.Cons: high gas cost and resource-intensive computations; Pros: no overhead in proving time, latency is low because the proof does not need to be generated outside the blockchain.

2. On-chain compression: removing redundant or unnecessary information from the data or using data structures that are optimized for space efficiency. The compressed data is sent to the blockchain and can be decompressed when needed. Cons: compressing and decompressing the data might imply additional computations, however this latency will be probably negligible. The compression algorithm used might negatively impact the data's security; Pros: reducing data costs.

3. Off-chain storage: stores the data off-chain and on-demand puts the specific pieces on-chain. This is relevant for solutions that for some reason need to store huge amounts of data (ex., Ethereum archive node starting from genesis block). Cons: the same as on-chain compression; Pros: reducing data costs further.

For cross-chain solutions completeness, one should also mention cross-messaging solutions with trusted third parties such as oracles, centralized bridges, etc.

Suppose rollups are settled to L1 using a shared proof aggregator mechanism. In that case, it is possible to make the messaging faster by accepting block hashes when they are settled inside this aggregator, and settlement here will also take care of messaging (but what if the proof aggregator fails). For detailed description: link.

• Is cross-chain messaging possible without a trusted third party (that can be both a single entity or multiple entities)? What are the efficient mechanisms for it? In general, for Ethereum L2s (that have direct access to L1’s blockhashes) and Ethereum itself, if one chain can run something like a light client on another chain, it can verify block headers from this external chain that is enough for trustless cross-chain messaging.

• Are ZK circuits for cross-chain proof generations of reasonable size? In some cases, especially when the Consensus Layer (needs to be verified for cross-chain operations) is huge, circuits for ZK cross-chain messaging might be orders of magnitude larger than rollups and on-chain storage, and computational overhead is huge as well. Presumably, it can be overcome with a more centralized approach. This question was explored in this paper.

• Succinct Labs use light clients to verify the consensus from the source chain to the consensus layer of the target chain. The idea is that a light client protocol exists that ensures nodes can synchronize block headers of a finalized blockchain state. ZKP is used to generate proof of consensus.

• Lagrange Labs builds non-interactive cross-chain state proofs. The Lagrange Attestation Network is responsible for creating state roots. Each Lagrange Node contains a portion of a sharded private key that it uses to attest to the state of a particular chain. Each State Root is a threshold signed Verkle Root that can be used to prove the state of a specific chain at a particular time. State Roots are fully generalized and can be used within State Proofs to prove the current state of any contract or wallet in a chain.

• Herodotus uses storage proofs with ZKP to provide smart contracts with synchronous access to on-chain data from other Ethereum layers. For verification, it uses the native L1<>L2 message passing to synchronize block hashes between ethereum rollups.

• =nil; Foundation (Mina, L1) allows smart contracts on Ethereum to verify the validity of the Mina state. Generate special-purpose state proofs, which would be cheap to verify on Ethereum (native Mina proofs are expensive to verify on Ethereum). It is supposed that (in some future) apps can directly use Mina’s proof-generation tool to check cross-chain tx validity. =nil; Foundation also has the Proof Market, where users/projects can buy/sell mostly SNARK proofs that allow trustless data accessibility.

• Axiom: if Axiom has ZKPs generated for the ledger up to now – it doesn’t need to generate ZKP for a specific piece of data – it can just deliver this ZKP to the chain (acting as a relayer) or maybe even provide access to this ZKP.

Disclaimer: For most L2s, cross-chain messaging is still a work in progress. All the analysis below is based on information from open sources. That is, mentioned solutions might be under exploration and test implementation, and rollups might end up using other approaches.

Taiko

• Taiko stores block hashes of each chain. For each pair of chains, it deploys two smart contracts which store the hashes of each other. In L2 ← → L1 example, every time an L2 block is created on Taiko, the hash of the enclosing block on L1 is stored in the TaikoL2 contract. It works in this way in both L1 ← → L2 directions.

• One can get the latest known Merkle root stored on the destination chain by calling getCrossChainBlockHash(0) on the TaikoL1/TaikoL2 contract and get the value/message to verify. One can get the sibling hashes for that latest known Merkle root by asking for it with the standard RPC call eth_getProof on the "source chain."

• Then, one just needs to send them to be verified against that latest known block hash that is stored in a list on the "destination chain." A verifier will take the value (a leaf in the Merkle tree) and the sibling hashes to re-calculate the Merkle root and check if it matches the one that is stored in the destination chain's list of block hashes.

Starknet

Starknet uses storage proofs for trustless cross-chain messaging.

L2→ L1 messaging protocol

• During the execution of a Starknet transaction, a contract on Starknet sends an L2→L1 message.

• The message parameters (which contain the recipient contract on L1 and the relevant data) are then attached to the relevant state update (main storage Tree).

• L2 message is stored on L1 in Smart Contract.

• An event (storing message parameters) is emitted on L1.

• The recipient address on L1 can access and consume the message as part of an L1 transaction by re-supplying the message parameters.

• Cross-chain messages are stored in the main tree.

L2 → L1

L1 → L2

Optimism

• Communication between L1 and L2 is enabled by two special smart contracts called the "messengers".

• For Optimism (L2) to Ethereum (L1) transactions, it is necessary to provide Merkle proof of the message on L1 after the state root is written. The fault challenge period starts after that proof transaction becomes part of the L1 chain. After this waiting period, any user can "finalize" the transaction by triggering a second transaction on Ethereum that sends the message to the target L1 contract.

• Cross-chain messages are stored in the main tree.

Arbitrum

• Retryable tickets are Arbitrum's canonical method for creating L1 to L2 messages, i.e., L1 transactions that initiate a message to be executed on L2. A retryable can be submitted for a fixed cost (dependent only on its calldata size) paid at L1. The main state tree is used for cross-chain communication with custom data format in their smart contracts. Submitting the retryable ticket on L1 is separable/asynchronous with its execution on L2. Retryables provide atomicity between the cross-chain operations. If the L1 transaction to request submission succeeds (i.e., does not revert), then the execution of the Retryable on L2 has a strong guarantee to ultimately succeed as well.

• Arbitrum has two trees: a Nitro chain is maintained in Ethereum's state tree format, organized as a Merkle tree. The Assertion tree stores the state of an Arbitrum chain that is confirmed back on Ethereum via "assertions." The rules of advancing an Arbitrum chain are deterministic. This means that given a chain state and some new inputs, there is only one valid output. Thus, if the Assertion Tree contains more than one leaf, then at most, only one leaf can represent the valid chain state.

• Arbitrum's Outbox system allows for arbitrary L2 to L1 contract calls, i.e., messages initiated from L2, which eventually resolve in execution on L1. L2-to-L1 messages (aka "outgoing" messages) bear many things in common with Arbitrum's L1-to-L2 messages (Retryables), "in reverse" though with a few differences. Part of the L2 state of an Arbitrum chain — and consequently, part of what's asserted in every RBlock — is a Merkle root of all L2-to-L1 messages in the chain's history. Upon an asserted RBlock being confirmed (typically ~1 week after it is asserted), this Merkle root is posted on L1 in the Outbox contract. The Outbox contract then lets users execute their messages — validating Merkle proofs of inclusion and tracking which L2 to L1 messages have already been spent.

Polygon zkEVM

• The zkEVM's Bridge SC utilizes a special Merkle Tree called Exit Tree for each network participating in the communication or asset exchange.

• It uses Merkle roots (in a separate state tree), a bridge architecture diagram can be found on github.

• The zkEVM Bridge SC's implementation is based on the Ethereum 2.0 Deposit Contract, except for a few alterations. For example, while it utilizes specially designed Merkle Trees that are append-only, it employs the same logic as the Ethereum 2.0 Deposit Contract. Other differences are related to the base hash and the leaf nodes.

• The Polygon zkEVM Bridge smart contract's main feature is using Exit Trees and the Global Exit Tree, with the Global Exit Tree Root serving as the primary source of state truth. So, two distinct Global Exit Root managers exist for L1 and L2 and a separate logic for the Bridge SC.

Scroll

• The Bridge contracts deployed on the Ethereum and Scroll allow users to pass arbitrary messages between L1 and L2. On top of this message-passing protocol, we have also built a trustless bridging protocol to allow users to bridge ERC-20 assets in both directions. To send a message or funds from Ethereum to Scroll, users call a sendMessage transaction on the Bridge contract. The Relayer will index this transaction on L1 and send it to the sequencer for inclusion in an L2 block. Sending messages from Scroll back to Ethereum uses a similar process on the L2 Bridge contract.

• Cross-chain messages are stored in a regular message queue. The sequencer picks them from this queue and adds them as regular transactions on the chain.

zksync Era

Disclaimer: this it related to zksync Era only, might differ from cross-chain messaging on ZK Stack, a modular framework for building sovereign ZK-powered Hyperchains.

• Each batch has a separate small tree of L2->L1 messages.

• It is impossible to send transactions directly from L2 to L1. Instead, you can send arbitrary-length messages from zkSync Era to Ethereum and then handle the received message on Ethereum with an L1 smart contract. zkSync Era has a request proof function that returns a boolean parameter indicating whether the message was sent successfully to L1. Merkle proof of the message inclusion is retrieved by observing Ethereum or using the zks_getL2ToL1LogProof method of the zksync-web3 API.

• For L1 → L2, the zkSync Era smart contracts allow the sender to request transactions on Ethereum L1 and pass data to zkSync Era L2.

• Bridge contract: https://github.com/matter-labs/era-contracts/blob/main/ethereum/contracts/bridge/L1ERC20Bridge.sol

Cross-chain communication is necessary for bunches of applications that are “must haves” for mass blockchain adoption (ex., cross-chain social recovery wallets described in Vitalik’s article). Most cross-chain solutions rollups use today are designed for L1 ← → L2 to cover the withdrawals feature. These solutions can be expanded to cover more blockchains. But at the same time, more advanced cross-chain communication solutions can be implemented, such as “direct state reading” that doesn’t require proof at all or trustless “storage proofs.”

Cross-chain communication is still work-in-progress for most L2s. If you have any suggestions and comments on this article or existing or potential approaches to cross-chain communication – you’re more than welcome to share and collaborate to work together and build the most robust, efficient, and flexible cross-chain communication solution.

Sources:

• The article "Bridging the Multichain Universe with Zero Knowledge Proofs" by Ingonyama.

• The article "What are Storage Proofs and how can they improve Oracles?" by Starkware.

• Vitalik’s article "Deeper dive on cross-L2 reading for wallets and other use cases".

• The paper "zkBridge: Trustless Cross-chain Bridges Made Practical" by Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, and Dawn Song.

• The research proposal "Research on fast cross-rollup messaging and settlement inside recursive proofs" by Kalman Lajko.

• The article "The ZK Cross-chain Message Protocol and How it Paves a New Way of Cross-chain Communication" by

Explore open positions on our job board.

To stay updated on the latest from Taiko:

• Website: https://taiko.xyz

• Discord: https://discord.gg/taikoxyz

• GitHub: https://github.com/taikoxyz

• Twitter: https://twitter.com/taikoxyz

Contribute to Taiko and earn a GitPOAP! You will also be featured as a contributor on our README. Get started with the contributing guide.