Introducing

Today, @andreaslbigger and I are thrilled to announce the MVP of kona, a suite of portable, no_std Rust implementations of the OP Stack rollup state transition.

Early in June, our team at OP Labs released the Stage 1 milestone on OP mainnet. This week, the kona repository includes the first alternative Fault Proof Program for the OP Stack, delivering a critical piece of redundancy in the proving system on the road to Stage 2 Decentralization of the OP Stack as a whole.

How does it work?

At a high-level, verifying the correctness of a claim about the state of an OP Stack L2 on the DA layer consists of bootstrapping trusted inputs, deriving the inputs for the L2 chain, executing the derived inputs statelessly, and finally asserting the correctness of the L2 claim against the produced L2 chain.

The process is modeled in three separate phases, outlined below.

Prologue

We start off by pulling in a few inputs declared by the dispute contracts on L1:

1. [TRUSTED] An L1 block hash at a height that contains the batch data posted to L1 to reproduce the chain at the height of the L2 state claim.
2. [TRUSTED] An L2 output root to determine the starting L2 safe head during the derivation process.
3. [PROPOSER-SUBMITTED] The L2 block number of the following output root claim.
4. [PROPOSER-SUBMITTED] A claimed L2 output root at the above block height.

The starting L2 output root may be bisected to in an on-chain dispute, to reduce the derivation + execution requirements in the program. This extra phase of bisection, already present in the live system, allows us to reduce the range of blocks that we must execute from (previous_finalized_proposal_block, disputed_proposal_block] to (disputed_proposal_block - 1, disputed_proposal_block].

Execution

The execution phase of the program is split among two synchronously executed sub-routines: Derivation (viewing trusted L1 state) & stateless L2 block execution (viewing + extending trusted L2 state).

Derivation

The beginning of the execution phase involves deriving the L2 chain inputs from batch data available on L1. In this process, the L1 origin block of the L2 output root claim is found through providing preimage witnesses for the L1 block hashes in reverse-order, starting from the trusted L1 block hash retrieved in the Prologue phase.

Once the L1 origin block of the L2 output root claim has been reached, derivation steps forwards until the disputed L2 Execution Payload is produced, verifiably fetching transaction and receipt data from the transactions root and receipts root within the L1 headers, as well as blobs from the IndexedBlobHashes in EIP-4844 transactions submitted by the batcher, along the way.

L2 Execution

Once the derivation pipeline has produced the disputed L2 execution payload from verified L1 data, the disputed L2 block is then statelessly executed, starting from the prestate header (committed to in the trusted starting output root). For those unfamiliar, this process is nearly identical to regular block execution in a standard EL, though rather than having access to the state touched during execution in a fast database with knowledge of previously validated data, it is verifiably fetched by providing MPT proofs for all accessed accounts / storage slots in the global Ethereum state trie + account storage tries. In addition, the preimages of any hashed sibling nodes that must be revealed during trie node deletion are included inside of this witness, to allow for successful state root computation on block boundaries.

The result of this sub-routine is the canonical block header for the disputed L2 block, constructed from data committed to in the two trusted commitments retrieved within the Prologue phase.

Epilogue

Once the block header for the disputed L2 block has been produced in the Execution phase, the final step is to compute the L2 Output Root from the produced header + the account storage root of the L2ToL1MessagePasser contract after the disputed block's execution.

Finally, the output root claim and specified L2 block height retrieved during the prologue phase are validated against the produced output, where the proposer-submitted claim may be definitively validated or invalidated.

kona Fault Proof Program Benchmarks

Several optimizations to kona were made against the original op-program, namely eth_getProof support to reduce RPC hits as well as reducing the range of the initial walkback performed during the derivation sub-routine of the Execution phase. Today, the fault proof program is able to successfully validate L2 output root claims, running both natively and on the asterisc Fault Proof VM.

All benchmarks below are performed on an M1 Max Macbook pro 2021, with 64GB unified memory, running kona-client and kona-host natively in racing threads. The client program and host program were compiled with performance-oriented release profiles. The block being derived + executed is block #121449098 on OP Mainnet.

---

kona-client benchmarks, running natively:

No cache (local nodes consulted for data, low latency. Using in-memory k/v store):

With cache (dry run performed before, persisting all preimages. The disk is hit instead of RPC):

---

op-program benchmarks, on the same machine, also running natively:

No cache (local nodes consulted for data, low latency. Using in-memory k/v store. Datadir flag omitted to force memory k/v store.):

With cache (dry run performed before, persisting all preimages. The disk is hit instead of RPC - RPC flags omitted to force FetchingEnabled):

The future is ZK?

kona's components were built with alternative backend support in mind, starting from building them from the ground up as no_std w/ alloc enabled libraries to promote portability between bare-metal LLVM targets. When boiled down to the high-level concerns of a verifiable program, the most fundamental differences between a program running on a zkVM versus a Fault Proof VM are:

1. Host <-> {Client/Guest} communication may occur on-the-fly for programs executing on Fault Proof VMs, whereas zkVMs require the executor of the program to have the full witness upfront.
2. For programs executing on Fault Proof VMs, data retrieved from the host may be assumed to be trusted, since the on-chain implementation of the host (PreimageOracle.sol) validates all data within it upon entry. In contrast, programs executing on zkVMs must validate the witness data's correctness in the context of the verifiable execution environment in order to fully constrain the proof.

With this in mind, all components within kona have been abstracted over their data sources, allowing them to adapt to executing in various contexts. For example, kona-derive ships with trait-abstracted data sources, allowing for downstream consumers to simply maintain an alternative implementation of these traits without the need to fork. A clear example of this can be found in the online implementation of these traits, as well as the offline, PreimageOracle-backed implementations for the fault proof program.

This strategy has worked well so far, enabling a great deal of code re-use. We've worked closely alongside Succinct Labs to lay a solid foundation for forwards compatibility with ZK programs built on top of kona's libraries, and we cannot thank them enough for helping ideate what this looks like!

Currently, the Succinct Labs team, alongside @ZachObront, are also working on the first zkVM backend for kona. So far, they've shipped the MVP of this backend, using kona-host to generate all witness data as well as run kona inside SP-1 with the generated witness in order to generate a full proof for the block.

OP Stack Multi Proofs

kona is only a component within a broader multi-proof system that we're looking to develop for the OP Stack, as noted in an old multi-proof blog post from OP Labs. Having multiple proofs aggregated within the withdrawal path enables a critical portion of L2 beat's definition of "Stage 2 decentralization," which is that the security council's actions must be confined to "on-chain, provable bugs." Multiple proofs disagreeing on the validity of an output proposal may fulfill this requirement.

By taking advantage of the OP Stack's existing client diversity, kona brings in an alternative implementation of both the state transition function (based on op-reth, revm, & kona-mpt) and derivation (kona-derive), adding redundancy to the op-program, based off of op-geth + op-node.

In the future, with kona and a secondary FPVM, asterisc (developed by @protolambda and Sunnyside Labs), we seek to move the security model of the OP Stack's withdrawal path from this:

To this:

… and maybe an eventual expansion to include a ZK proof as well 😉

What's next?

1. Continue iteration on kona, squashing bugs and productionizing the existing MVP.
2. Develop a consensus test suite for the OP Stack, allowing for a common set of test vectors to be executed against various implementations of the consensus-critical codepaths.
3. More FPVM + zkVM backends for kona!
   • Document the process for building an alternative backend.

Nice-to-haves

1. Develop an alternative Rollup Node implementation using kona-derive as a reth Execution Extension.
2. Reth AlphaNet with multi-proofs activated, serving as a long-lived testing environment.

How can you contribute?

Beyond viewing existing issues, contribution guidelines for kona can be found in the book.

We look forwards to getting more of the community involved in the development process!

Credits

kona is inspired and enabled by the work of several teams:

• OP Labs and other contributors' work on the op-program
• Paradigm's continued improvements to and support of our original op-reth diff
• Dragan Rakita's continued improvements to and support of our original revm diff
• BadBoiLabs's work on Cannon-rs

Shoutouts

A very big thank you to all of those who have contributed to kona directly thus far:

• @merklefruit
• @ZachObront
• @N0xMare_
• @tyneslol