<h1>
Introducing <img src="https://hackmd.io/_uploads/r10L2GPUA.png" style="height:1.5em" alt="kona" />
</h1>

Today, [@andreaslbigger](https://x.com/andreaslbigger) and I are thrilled to announce the MVP of [`kona`][kona], a suite of portable, `no_std` Rust implementations of the [OP Stack][op-stack] rollup state transition.

Early in June, our team at [OP Labs][op-labs] released the [Stage 1 milestone](https://blog.oplabs.co/the-fault-proof-system-is-available-for-the-op-stack/) on OP mainnet. This week, the `kona` repository includes the first alternative [Fault Proof Program][fpp-specs] for the OP Stack, delivering a critical piece of redundancy in the proving system on the road to [Stage 2 Decentralization](https://l2beat.com/scaling/projects/optimism#stage) 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](https://specs.optimism.io/fault-proof/stage-one/fault-dispute-game.html), [deriving the inputs for the L2 chain](https://specs.optimism.io/protocol/derivation.html), [executing the derived inputs statelessly](https://specs.optimism.io/protocol/exec-engine.html), 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](https://specs.optimism.io/fault-proof/stage-one/fault-dispute-game.html) 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][g-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][g-output-root] at the above block height.

The starting [L2 output root][g-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](https://specs.optimism.io/protocol/derivation.html) available on L1. In this process, the [L1 origin](https://specs.optimism.io/glossary.html#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](https://specs.optimism.io/protocol/derivation.html) 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 `IndexedBlobHash`es 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][g-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`][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](https://optimistic.etherscan.io/block/121449098).

---

`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](https://github.com/ethereum-optimism/kona/tree/main/crates/derive/src/online) implementation of these traits, as well as the [offline, `PreimageOracle`-backed](https://github.com/ethereum-optimism/kona/tree/main/bin/client/src) 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](https://succinct.xyz) 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](https://succinct.xyz) team, alongside [@ZachObront](https://x.com/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](https://blog.oplabs.co/multiple-proofs/). 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`][asterisc] (developed by [@protolambda](https://x.com/protolambda) and [Sunnyside Labs](https://x.com/testinprod_io)), 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](https://www.paradigm.xyz/2024/04/reth-alphanet) with multi-proofs activated, serving as a long-lived testing environment.

## How can you contribute?

Beyond viewing [existing issues](https://github.com/ethereum-optimism/kona/issues), contribution guidelines for [`kona`][kona] can be found in the [book](https://static.optimism.io/kona/CONTRIBUTING.html).

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][op-labs] and other contributors' work on the [`op-program`][op-program]
- [Paradigm][paradigm]'s continued improvements to and support of our original `op-reth` diff
- [Dragan Rakita](https://x.com/rakitadragan)'s continued improvements to and support of our original `revm` diff
- [BadBoiLabs][bad-boi-labs]'s work on [Cannon-rs][badboi-cannon-rs]

### Shoutouts

A very big thank you to all of those who have contributed to `kona` directly thus far:
- [@merklefruit](https://x.com/merklefruit)
- [@ZachObront](https://x.com/zachobront)
- [@N0xMare_](https://x.com/N0xMare_)
- [@tyneslol](https://x.com/tyneslol)

[kona]: https://github.com/ethereum-optimism/kona
[op-stack]: https://github.com/ethereum-optimism/optimism
[op-program]: https://github.com/ethereum-optimism/optimism/tree/develop/op-program
[cannon]: https://github.com/ethereum-optimism/optimism/tree/develop/cannon
[paradigm]: https://github.com/paradigmxyz
[cannon-rs]: https://github.com/anton-rs/cannon-rs
[badboi-cannon-rs]: https://github.com/BadBoiLabs/cannon-rs
[asterisc]: https://github.com/etheruem-optimism/asterisc
[fpp-specs]: https://specs.optimism.io/experimental/fault-proof/index.html
[book]: https://ethereum-optimism.github.io/kona/
[op-labs]: https://github.com/ethereum-optimism
[bad-boi-labs]: https://github.com/BadBoiLabs
[g-output-root]: https://specs.optimism.io/glossary.html#l2-output-root
[g-derivation-pipeline]: https://specs.optimism.io/protocol/derivation.html#l2-chain-derivation-pipeline
[g-fault-proof-vm]: https://specs.optimism.io/experimental/fault-proof/index.html#fault-proof-vm
[g-preimage-oracle]: https://specs.optimism.io/experimental/fault-proof/index.html#pre-image-oracle