# Proving Superchain Interoperability

_Special thanks to Mark Tyneway, Meredith Baxter, and Mofi Taiwo for feedback and review._

The [OP Stack](https://specs.optimism.io) is introducing [native L2<->L2 interoperability][interop-spec] in an upcoming hardfork, enabling Superchain members to communicate efficiently and securely with *intra-block* latency. Recently, OP Stack protocol engineers gathered to work on a design for the Superchain's new bridge proof, a key component to the secure release of this feature. During this time, we put together a working version of the proof in two implementations: [`op-program`][op-program] and [`kona`][kona].

## Interop

The OP Stack's [Interop feature][interop-spec], from the application developer's perspective, has a pretty thin overview. Within the Superchain, [smart contracts can emit logs](https://ethereum.org/en/developers/docs/smart-contracts/anatomy/#events-and-logs) ([Initiating Messages](https://specs.optimism.io/interop/messaging.html#initiating-messages)), and smart contracts on other L2 chains can optimistically relay that log via the [`CrossL2Inbox`](https://specs.optimism.io/interop/predeploys.html?highlight=crossl2#crossl2inbox) predeploy ([Executing Messages](https://specs.optimism.io/interop/messaging.html#executing-messages)). Logs that are relayed are guaranteed to be present in the remote chain if the block is included. Notably, intra-block cross-chain messaging is supported, meaning usecases such as cross-chain flashloans are possible with security guaranteed _by the protocol_.

<center>
<img src="https://hackmd.io/_uploads/BkrUDIjw1e.png"/>
</center>

<br/>

On the protocol's end, the OP Stack's flavor of interop makes use of optimistic message relay to prioritize a snappy user experience, with the sequencer instating [a _policy_](https://specs.optimism.io/interop/sequencer.html?highlight=policy#sequencer-policy) to check for message validity before signing and sending out an unsafe payload to its peers. To save you a click:

> Sequencer Policy is the process of optimistically enacting rules outside of consensus (the state-transition function in this context), and the choices can then be asynchronously validated by verifiers and the fault-proof.
>
> In the context of Superchain interoperability, sequencer policy is utilized to enable cross-chain message relay without adding additional state-transition complexity or cross-chain synchronicity to the protocol.

With some further details, this means that:
1. When an [unsafe block](https://specs.optimism.io/glossary.html#unsafe-l2-block) (read: a block preconfirmed by the sequencer) is built by the sequencer for an individual L2 chain, the sequencer will reach out to its own sources in order to determine if their block has any [invalid executing messages](https://specs.optimism.io/interop/messaging.html#invalid-messages) before signing the execution payload and sending it off to the validator nodes.
- If any executing messages are found to be invalid, the block is thrown away and re-executed with only its deposit transactions before signing. This block is guaranteed to be valid, since executing messages may not be invoked from a deposit transaction, and deposit transactions must always be included by consensus rule.
- When validator nodes receive this block via gossip, it is now marked as "cross unsafe." It has not yet been derived from L1, and its cross-chain dependencies have been checked for validity by the sequencer (an *untrusted* party.)
- When validator nodes derive this block from L1, it is marked as "local safe." It has been derived from L1, but its cross-chain dependencies have not been checked for validity.
- When validator nodes consult their own sources and determine the messages in a "local safe" block to be correct, the block is promoted to "cross safe."
2. There is now *more room for the sequencer to misbehave*. The sequencer is not prohibited from breaking this policy, just as they are not prohibited from censoring and/or adjusting the order of L2-originating transactions.
- Note that, while extra potential for the sequencer to misbehave while producing the unsafe chain is introduced, a block with invalid messages is deemed to be invalid by the derivation function. If a block with invalid messages is batched and posted to L1, it will be reduced to deposits only when it is derived, disallowing the invalid block to reach a finalized state. This is analogous to a sequencer censoring deposit transactions from L1; In that case, the derivation function will also invalidate their block and force a L2 reorg.
4. The bridge proof (and off-chain verifier nodes) must implement additional logic to check that the sequencer's trusted sources told the truth about remote logs' inclusion. The bridge, if the sequencer misbehaves, must follow the canonical version of the superchain where, by consensus rule, no invalid executing messages were included.

When it comes to off-chain verifier nodes, they can establish their own source of truth by operating the `op-supervisor` (TL;DR - It's a service that performs [message validity checks](https://specs.optimism.io/interop/messaging.html#invalid-messages), tracks cross-safety of L2 blocks across the superchain, and offers an RPC to consult) and nodes for all L2 chains within the Superchain's [dependency set](https://specs.optimism.io/interop/dependency-set.html). The proof, in essence, is a verifier node, but a bit more complex in design to allow for both trustless assumptions on data integrity and economically rational verification on L1 Ethereum.

## Proving Interop

> For more details on (or an introduction to) the OP Stack's existing, single-chain bridge proof, [head over to the docs](https://docs.optimism.io/stack/fault-proofs/explainer).

When it comes to proving OP Stack interop, it builds on the existing concept of the bridge proof:
- Given a trusted commitment to L1 state (sourced from within the EVM during proof verification, via [BLOCKHASH](https://www.evm.codes/?fork=cancun#40)), have a program that traverses L1 history / blobs for L2 batch data and produces the L2 chain at a given block height. Once the chain has been produced, compare the result with the claim, and signal validity. All data pulled from the unrolled L1 commitment is content-addressable by hash, which is constrained either optimistically via an on-chain oracle contract that a stateless Fault Proof Virtual machine talks to, or via explicit, inline constraints in a validity proof.
- Bisect over the instruction trace of this program in an interactive dispute or verify a validity proof on-chain in order to validate the state transition described above.

However, we move from caring about the state of a single L2 to the collective state of all L2s within the superchain. This has several neat implications, but namely it means all bridges in the superchain can share proposals (and eventually, share a single bridge!) It also gives us a good mental model for how to think about _what_ we're actually proving.

### Superchain State Transition

When thinking about the Superchain with interoperability, no single chains' state exists on its own anymore. Therefore, the state of any chain in the superchain is a subset of a broader state.

State transitions on the Superchain happen once per second. Each individual chain within that time can produce a block, several blocks, or no block. At any second following interop activation, a superchain snapshot can be taken, including the highest block number at or before the given timestamp for each L2 chain in the dependency set. The commitment to this collective state at any given time is called a `SuperRoot`.

<center>
<img src="https://hackmd.io/_uploads/HJsksDoDJl.png"/>
</center>

### Sub-problems

Now that we've got a definition for the Superchain state transition, we can break it up into distinct parts. The new goal of the proof is to produce "local safe" blocks for all L2 chains in the Superchain's dependency set at a given timestamp, derived from the trusted Ethereum L1 state commitment - we'll call this "sub-problem #1." Then, it must aggregate the local-safe blocks to check message validity, resolve invalid dependencies, and finally construct the `SuperRoot` from the "cross safe" blocks to validate the L2 state proposal - we'll call this portion "sub-problem #2."

Sub-problem #1 is performed `n` times, where `n` is the number of chains within the Superchain. As the dependency set grows, the computational cost of the proof grows. However, there are no dependencies between runs of the first "sub-problem," which lends well towards parallelization for the sake of non-interactive provers or additional interaction to reduce computational costs in an interactive prover.

Sub-problem #2 aggregates the results of the `n` sub-problem #1 runs, and is only performed once.

<center>
<img src="https://hackmd.io/_uploads/H1HL6X17xe.png"/>
</center>

<br/>

For the sake of an interactive fault proof, where bisection over sequential execution is required, we can flatten out the state transition and accumulate state along the way like so:

<center>
<img src="https://hackmd.io/_uploads/rJDND_owke.png"/>
</center>

<br/>

The dispute game on-chain then has the opportunity to add an additional layer of bisection, where a certain segment of the broader state transition can be ran. This prevents the fault proof from having to sequentially execute the entirety of the Superchain's state transition on the fault prover at any point.

For the sake of a non-interactive validity proof, each instance of sub-problem #1 (verifiable local safe block generation) can be proven in parallel, before finally folding each result into the second sub-problem.

## Summary

The method for proving the full Superchain's STF isn't much different than proving a single OP Stack chain's STF, barring additional hardware requirements and a final consolidation step. However, in aggregate, the cost of these proofs will be amortized over time, since each individual OP Stack chain will not need to operate its own independent bridge proof as they do today. Instead of deriving and executing a single chain from verifiable data sources, we derive and execute `n` L2 chains, before finally checking that cross-chain dependencies are met via history lookups.

Most importantly, in-protocol interop embeds the idea of cross-L2 message validity into the state transition function, allowing cross-chain messages to enjoy the same security properties as within-L2 transactions.

If you'd like to contribute towards the development of this effort, come reach out to us over in the issues of [`kona`][kona] / [`op-program`][op-program], contribute to the [OP Stack specs][interop-spec], or ping [@vex_0x](https://x.com/vex_0x) on X.

[interop-spec]: (https://specs.optimism.io/interop/overview.html)
[op-program]: https://github.com/ethereum-optimism/optimism/tree/develop/op-program
[kona]: https://github.com/op-rs/kona