Mental Model: Rollups

The throughput-decentralization tradeoff of blockchains is that:

• targeting high throughput increases the operational cost of running a node, which increases the barrier of entry for running a node and thus, can lead to a more centralized network of fewer nodes.
• targeting low throughput means lower operational costs, which can lead to a more decentralized network of more nodes, but it also creates a worse platform for hosting high frequency apps.

Thus, we end up with a hard problem: a single blockchain cannot target high throughput without impacting operational cost per node.

A "rollup" system is one approach to solving this problem.

Separating execution from verification

Consider two blockchains. The first blockchain optimizes for decentralization -- it accepts low throughput in exchange for a large network of independent nodes, giving it strong properties of permissionlessness, trustlessness and immutability. Call this the "parent chain".

The second blockchain optimizes for throughput -- it processes a high volume of transactions per second, at the cost of fewer independent nodes, given high node operational costs. Call this the "rollup chain".

On its own, the rollup is a blockchain with weak guarantees. Few nodes means it is easier for a small group to selectively include, exclude, or roll back transactions. Users of the rollup would have to trust that its small set of nodes is operating honestly. These factors make a rollup chain, operated as just a regular blockchain in isolation, a bad host of critical data.

And so, a rollup chain works in tandem with a parent chain to create guarantees of permissionlessness, trustlessness and immutability for its high throughput execution environment.

How a rollup borrows security

The main infrastructural component of a rollup chain is a "sequencer". This is a single, central machine that houses the rollup chain's own blockchain key-value database, accepts user submitted transactions, creates a block from them, and performs this block of state updates onto its database.

Every given period of time, this sequencer posts the updated state of the rollup chain onto the parent chain. This involves posting the raw transaction data of the $k$ blocks since the last update posted onto the parent chain, and the state of the rollup after the state updates of those $k$ blocks were applied.

This data posted on the parent chain is essentially a complete, replayable, historical record of the rollup chain's state updates. What's accomplished here, is that a high-throughput but centralized execution system processes a large volume of transactions very fast, and it periodically makes its execution and results publicly auditable for honesty and correctness on a low-throughput but decentralized database.

Fundamentally, a rollup chain's sequencer is incentivised to process transactions honestly because acting dishonestly means users will not use it to store critical data and real monetary value. This incentive is hardened by posting the sequencer's transaction, execution and results data onto a parent chain, since now, any independent actor can permissionlessly replay the sequencer's actions to verify whether it behaved honestly.

What the rollup posts to the parent chain, and how verification works, comes in two forms:

Approach 1: Assume validity, allow challenges

The rollup posts its transaction data to the parent chain. Anyone can download this data, re-execute the transactions, and check whether the rollup's claimed state transitions are correct. If someone finds a discrepancy, they submit a "fraud proof" -- a demonstration, verifiable by a program on the parent chain, that a specific state transition was invalid. If the fraud proof is valid, the incorrect state transitions up to the fraudulent one, are rolled back on the rollup chain.

This rolling back of state transitions on the rollup chain is not up to the rollup chain or sequencer's discretion. Rather, it is forced.

In this rollup system, the sequencer posts data by making a transaction to an account with a program in its code. Upon receiving execution and results data from the sequencer, this program "optimistically" stores this data in its account storage. This simply means that it stores the sequencer's execution and results data without replaying the execution data and verifying the execution's correctness itself. This would cost a lot of gas, perhaps more than the parent chain's transaction or block gas limit.

However, on every data post transaction from a sequencer, the program is able to verify (based on its locally stored data up to that point, and the incoming data from the sequencer) that:

• The last update from the sequencer stated the rollup chain is in $\text{state}_{n}$.
• This latest incoming update from the sequencer includes state updates data starting at this $\text{state}_{n}$ going to whatever $\text{state}_{n+k}$ after $k$ blocks of the rollup chain.

So, when the program receives a fraud proof transaction for the sequencer's dishonesty in some $\text{block}_{n+m}$ where $m \lt k$, it is able to replay just enough execution data to verify the validity of the fraud proof. And in case of a genuine fraud proof, it rolls back its locally tracked rollup chain state before the fraudulent block.

The sequencer is forced to honor this rollback, since the next time it posts execution and results data onto the parent chain, the program will reject the update unless it successfully verifies the sequencer has posted data starting from $\text{block}_{n+m}$ and not more. This would essentially render the rollup valueless as infrastructure for storing critical data and real monetary value.

It is in this hard sense that the rollup chain "inherits the security" of the parent chain. This rollup system where the parent chain optimistically stores updates received from the rollup chain which are then subject to fraud proofs, is called an "optimistic rollup".

This approach works because the data needed to verify (and challenge) the rollup's execution is permanently available on the parent chain. Even if every rollup node is dishonest, a single honest external party with access to the parent chain's data can detect and prove fraud.

Approach 2: Prove validity upfront

Fundamentally, the executions performed by a rollup chain's sequencer are just computer operations that output a result -- the resultant state of the rollup chain.

$\text{execute}(\text{operations},\text{initial-state}) \rightarrow \text{result-state}$

One way to verify that a given set operations applied to an initial-state outputs the given result-state is to execute the operations yourself to derive a result state, and check whether you derived the expected result state. Replaying execution in this way is an expensive task. A parent chain only does this in the optimistic rollups setup on a small, scoped set of operations that are put under scrutiny by a fraud proof.

Another, significantly cheaper way to verify a rollup's execution is via "validity proofs".

A validity proof is the output of a cryptographic scheme. It is a small piece of data ("proof") that gives you a hard, mathematical guarantee that a given set of computations produces a given result, without the verifying party having to replay the executions to derive the result for themselves.

$\text{verify}(\text{proof}, \text{initial-state}, \text{result-state}) \rightarrow \text{bool}$

And so, instead of posting raw execution and resultant state transition data onto the parent chain, a sequencer can be architected to post the rollup chain's state transition, along with a validity proof of the correctness of its execution of transactions. Since this verification is significantly cheaper than replaying the rollup chain's executions, the recipient program on the parent chain can verify a validity proof right when it receives data from the sequencer, and only upon successful verification, accept the given, resultant state of the rollup chain as enshrined.

This approach does not require anyone to re-execute the rollup's transactions. This rollup system is referred to as "validity rollups".

Trade-offs: optimistic vs. validity rollups

A drawback of the optimistic rollup approach is that there is a delay between a sequencer's update post onto a parent chain, and that update being safely considered as finalized.

Since the parent chain stores the sequencer's execution data without verifying it, verification is left to third parties who may submit fraud proofs. This means there must be a waiting period after each update to allow reasonable time for independent verifiers to submit fraud proofs.

For example, if a user performs important transactions after a block that has been invalidated via a fraud proof, their transactions will generally be rolled back. This has adverse consequences since those user transactions may, for example, be time-sensitive. That said, this delay primarily affects the parent chain's acknowledgment of the rollup's state. For transactions within the rollup, users still get fast confirmation from the sequencer, since the sequencer processes transactions at rollup speed regardless of the parent chain's fraud proof period.

Validity rollups avoid this issue of delays from fraud proof periods entirely. However, compared to optimistic rollups, they are much more difficult to architect and build, and to generalize for the rollup chain's execution environment to support building any kind of app or program.

What the rollup achieves

In both approaches, the parent chain does not re-execute the rollup's transactions. It only stores data or verifies proofs -- work that is far smaller than the rollup's actual execution. This means the rollup can process a high volume of transactions without increasing the computational burden on parent chain nodes.

The result: the rollup achieves high throughput, while its state transitions are backed by the parent chain's properties of permissionlessness, trustlessness and immutability. The hard problem -- high throughput at strong guarantees -- is addressed not by improving a single blockchain, but by composing two blockchains with complementary strengths.