# Optimistic Rollups in Tezos
## Introduction
Optimistic rollups are some of the most promissing `layer 2` approaches to scaling in blockchains. This note intends to be a birdeye view of [Marigold](https://marigold.dev)'s implementation on the [Tezos](https://tezos.com/) blockchain.
Verifying nodes on chain is expensive and hard to scale. Optimistic Rollups(ORU) post transaction to chain (as tickets) but the chain does not execute or verify these until the ORU settles or there are dissagreements about their results. Note that the settlement does not mean that the block is correct just that nobody challenged it in the time allocated. This is the meaning of the word `optimistic` in the title, verifying a rollup node is rather cheap and the punishment for false commits/reward for rejections are quite significant.
The first step is to create an ORU. At this point, a new rolup_id is created, a small fee (100Tz) is paid, Genesis [pre_block](#Pre-block) and [committed-blocks](#Commited-blocks) are initialised on the chain and a new `ticket_next_index` table is initialised. A very simple [Rollup_result](#Rollup_result) is created.
Various operations are possible on the ORU (see [example](#Operations-and-their-effects-an-example) or [details](#Operations-and-their-types)). An important such operation is [`Commit_block of Rollup_block_commitment.t`](#Commitment). In this case the commiter posts a (10_000Tz) bond to the chain and adds the block to "commited blocks". After that any user can verify the correctness of the commited blocks that are written on the chain. If the block turns out to be incorrect then the "verifier" can submit a [`Reject_committed_block Block_rejection.t`](#Rejection) to the chain. This is checked before being written to the chain. If the rejection holds, then the bond is forfeit and the rejector gets half that (see below).
Most rollup operations will invoke [`process_backlog`](#Process_backlog) which checks if enough time (at this time the limit is 30 Tezos levels ans seen in `rejection_delay_limit`) has passed and if so, it takes the oldest rollup_block on the chain and settles its effects (taht is gas costs, refunding the bond and, possibly withdrawal of funds to the main chain, there will in time be more effects).
If the oldest such block turns out to be a rejection of an incorrect commitment then the author of the incorrect commitment forfeits the bond. Half of the forfeited bond is transfered to the author of the rejection and the other half is burned. This incentivises the creators to make correct commitments and others to verify them.
Since the various operations are not verified on chain, various optimisations can be done. For example only certain pieces of the actual state of the ORU (the root and a [Merkle proof](https://hackmd.io/@corneliuhoffman/Merkle-proofs)) are posted on the chain. Also one can aggregate the signatures of several operations using [BLS signature aggregation](https://hackmd.io/@corneliuhoffman/BLS-signatures).
The ORU maintains table of assets and can interact with it through [`Rollup_operations`](#Operations-and-their-types). Of course in order to be functional, the ORU will interact with the main chain. An address from the main chain can deposit some tez to the ORU and create a linked asset on the ORU. This happens through a `Tezos_operation`. Reversely one can burn some assets on the ORU and transfer the corresponding linked chain assets to an address on the main chain. In the next session we will briefly survey some of these interactions. We then work through an [example](#Operations-and-their-effects-an-example) and then [describe](h#Operations-and-their-types) the operations in more detail
### The ORU offchain.
The offchain ORU is mainly developed in the library `lib_rollup`.
The encompassing type is `Validator.t`. It is a record containing a `node` and a `committed_blocks_map`.
#### Commited blocks maps
The `committed_blocks_map` is a representation of the tree of commitments. in practice it is a (rotating) array of `Block_map`s. A `Block_map` is an integer labeled map of blocks.
:::spoiler Each block contains a status (Valid, Invalid or Invalid_ancestor), a predecesor is and a list of succesor ids.
```ocaml=
{
status : block_status ;
successors : R.Committed_blocks.Single.Id.t list ;
predecessor : R.Committed_blocks.Single.Id.t ;
}
```
:::
Here is an example of a `committed_blocks_map` containing 4 blocks:
| id | Status | predecesor | succesors |
| -------- | -------- | -------- | --
| 0 | Valid | -1 | [1,2]
| id | Status | predecesor | succesors |
| --- | ------- | --- | --- |
| 1 | Invalid | 0 | [3] |
| 2 | Valid | 0 | [] |
| id | Status | predecesor | succesors |
| --- | ---------------- | --- | --- |
| 3 | Invalid_ancestor | 1 | [] |
```graphviz
digraph hierarchy{
rankdir="LR";
0->1[dir="back"]
1->3[dir="back"]
0 -> 2[dir="back"]}
```
#### Nodes
:::spoiler A `node` is the most complicated object of the ORU. It contains a Processor (containing the state of the rollup), gas and effect gas rates, a list of operations in the current block, an array of processed blocks as well as a list "valid commitments".
`Node`
```ocaml=
{
processor : Processor.t ;
current_run_gas_rate : Tez_repr.t ;
current_effect_gas_rate : Tez_repr.t ;
current_block_processed_operations_rev : Processed.operation list ;
processed_blocks : Processed.block_map ;(* Processed.operation list RotatingArray_Z.t *)
valid_commitment_chain : Valid_commitment_chain.t ;(* int RotatingArray_Z.t *)
}
```
:::
:::spoiler A `Processor` contains a level and an a rollup_id as well as the state of the rollup as a Patricia tree.
`Processor.t`
```ocaml=
{
level : Z.t ;
state : NS.t ; (* a Patricia tree *)
rollup_id : Z.t ;
}
```
:::
:::spoiler A `Processed_operation` contains `before_root` and `after_root` as well as a `trace` (a Merkle proof), `content` and `effect`.
`Processed_operation`
```ocaml=
{
before_root : Rollup_patricia.Root.t ;(* Root of bytes *)
after_root : Rollup_patricia.Root.t ;
effect : R.Rollup_effect.t ;(* | Withdraw of {ticket : Rollup_ticket.t ; tezos_destination : Contract_repr.t;} | Event of string*)
content : R.Pre_block.operation ; (* | Rollup_operation of Rollup_operation.t | Tezos_operation of Tezos_operation.t *)
trace : R.State_trace.t ;(* bytes list *)
}
```
:::
The `Node` module contains functions that allow one to produce `Rollup_operation_commitment` or `Block_rejection` from a commited block and to sync the operations from the program of a `Rollup.result` with the node.
Note that a processed operation can be either a `Tezos_operation` (at this point this can only be a Deposit) or a `Rollup_operation` (which is essentially a content of bytes).
It is very important to notice that, for example, in the case of `Block_rejection.t` it is not the entire state that is saved on the chain but just the `state_trace` which is (via Merkle proofs) enough.
### The ORU on Chain
Of course the ORU will interact with the main chain. This happens in `lib_protocol.ml`. As usual `alpha_context` provides a high level interface and `apply.ml` (which uses `rollup_apply.ml`) that provides the behaviours of the various operations.
#### Ticket_on_chain.
::: spoiler A `Ticket_onchain_content` contains an optional beneficiary and a Ticket_like.
```ocaml=
type t = {
ticket : Ticket_like.t ;
beneficiary : Contract_repr.t option ;
}
```
:::
::: spoiler In turn a `Ticket_like` is similar to a standard ticket, it contains an `ticketer` a `content` and an `amount`.
```ocaml=
type t = {
ticketer : Address.t ;
content : content ;(* {data ;type_} *)
amount : Z.t ;
}
```
:::
A Ticket_on_chain can be added to the context with `append_to_table` or removed with `withdraw_from_table` from the context.
The operation ` Deposit { ticket ; rollup_destination ; rollup_id }` will append_to_table the `Ticket_onchain_content.Ticket_like.t` called `ticket`.
TODO: expend this section, explain how the `apply` work in general.
#### Rollup_on_chain
::: spoiler a `Rollup_onchain_content` contains the kind of rollup and an interval of "pending operations"
``` ocaml type t = {
kind : Rollup_kind.t ;
pending_operation_queue : Pending_operation_queue.t ;
}
```
:::
::: spoiler in turn a `Pending_operation_queue` is an interval described by the `oldest_pending_block`, the `newest_pending_block` and some gas info.
``` ocaml
{
oldest_pending_block : Rollup_level.t ;
newest_pending_block : Rollup_level.t ;
current_run_gas_rate : Tez_repr.t ;
current_effect_gas_rate : Tez_repr.t ;
}
```
:::
`Alpha_context` contains two functions, `get_rollup` and `set_rollup` that allow getting respectively writing a `Rollup_on_chain`.
#### Pre-block
::: spoiler A `pre_block` contains a tezos_level al list of operations and some gas info.
```ocaml
{
rev_content : operation list ;
tezos_level : Level_repr.t ;
cumulated_run_gas : Z.t ;
cumulated_effect_gas : Z.t ;
cumulated_size : Z.t ;
}
```
:::
There are functions that allow one to get, create, set or remove a pre-block.
#### Commited-blocks
::: spoiler A `commited_block` is very similar to a `Processed_operation` on a node, it contains a before and after roots, a rollup_level a pedecesor and a list of succesors, an author and a content.
```ocaml
{
before_root : Root.t ;
after_root : Root.t ;
rollup_level : Rollup_level.t ;
content : Rollup_operation_commitment.t list ;
predecessor : Id.t ;
successors : Id.t list ;
author : Contract_repr.t ;
}
```
:::
There are functions that allow one to get, create, verify membership or remove commited-blocks.
#### Rollup_result
::: spoiler A `Rollup_result` contains info about the result of a [Rollup_opreation](#Operations-and-their_types). It contains data for the gas it consumed, the allocated storage, the contracts that it originated, the various balance updates and a list of `result_instruction_content`.
```ocaml
type result = {
consumed_gas : Gas.Arith.fp;
allocated_storage : Z.t;
originated_contracts : Contract.t list;
balance_updates : Receipt.balance_updates;
program : result_program;
}
```
:::
#### Result instruction_content
::: spoiler A `result_instruction_content` is a chain instruction that refers to rollup blocks.
```ocaml
type result_instruction_content =
| Create_rollup
| Add_committed_block of {
id : Committed_blocks.Single.Id.t;
commitment : Rollup_block_commitment.t;
}
| Remove_committed_block of (Rollup_level.t * Committed_blocks.Single.Id.t)
| Process_committed_block of (Rollup_level.t * Committed_blocks.Single.Id.t)
| Add_pre_block_operation of Pre_block.operation
| Flush_pre_block
| Update_run_gas_rate of Tez.t
| Update_effect_gas_rate of Tez.t
```
:::
## [Process_backlog](https://gitlab.com/marigold/tezos/-/blob/ulrikstrid@rollup-rewrite-history/src/proto_alpha/lib_protocol/rollup_apply.ml#L287)
`process_backlog` is a function that takes a `context` and a `rollup_id` and produces an updated context and a list of `result_instruction`s. A result instruction contains a rollup_id and
:::spoiler a `result_instruction_content`
```ocaml
type result_instruction_content =
| Create_rollup
| Add_committed_block of {
id : Committed_blocks.Single.Id.t ;
commitment : Rollup_block_commitment.t ;
}
| Remove_committed_block of (Rollup_level.t * Committed_blocks.Single.Id.t)
| Process_committed_block of (Rollup_level.t * Committed_blocks.Single.Id.t)
| Add_pre_block_operation of Pre_block.operation
| Flush_pre_block
| Update_run_gas_rate of Tez.t
| Update_effect_gas_rate of Tez.t
```
:::
* The first step is `flush_newest_preblock:`
We first pick the `Rollup_on_chain` for the given `rollup_id` and check if the level is smaller of the existing context level. If so, new `pre_block` and `commited_bloks` are created on the context and the gas rates are updated. Finally the `operation_queue` is updated and the context is returned together to the list of instructions:
```
[Flush_pre_block ;
Update_run_gas_rate new_run_gas_rate ;
Update_effect_gas_rate new_effect_gas_rate ]
```
* Next the oldest block is executed:
First check the oldest pre_block is final (that is if enough blocks have been baked - controlled by `rejection_delay_limit=30`) then pick the pre-block and commited_block of the corresponding level and rollup_id.
1. If there are no commited blocks then update the pre-block rollup_level to the current level, set it on the context and return the context with an empty list of instructions.
2. Otherwise, recursively traverse the (reversed) rev-content of the pre_block and the first commited_block applying the effects on the context.
## Commitment
When contract `source` applies `Commit_block commitement` where `commitment` is a [Rollup_block_commitment](#Commit_block-of-Rollup_block_commitmentt) then:
* the backlog is processed.
* `source` pays 10_000Tz commitment stake
* the [ Rollup_onchain_content](#Rollup_on_chain) corresponding to the rollup is obtained.
* We check that the `rollup_level` of the commitment is smaller than the `newest_pending_block` in the Rollup_onchain_content.
* The [`Committed_blocks`](#Commited-blocks) in the context are updated with a new block so that the `before_root` is the `after_root` of its predecesor, the `after_root` is described in the commitment and the author is `source`. This block is also added to the `succesors` of its predecesor.
* Finally a result is returned that contains the `balance_update` describing the payment of the commintment state and with an new program thatcontains a `Add_committed_block` instruction.
## Rejection
When contract `source` submits `Reject_committed_block block_rejection` where `block_rejection` is a [Block_rejection](#Reject_committed_block-of-Block_rejectiont) then:
* the backlog is NOT processed. This would be expensive and it is avoided.
* The [pre-block](#Pre-block) corresponding to the rollup_id and rollup_level is computed.
* The [commited_block](#Commited-blocks) corresponding to the rollup_id and rollup_level and the commited_block_id is computed.
* First one checks if the rejection level is not too old (that is the block is already accepted - this saves on computations).
* Obtain the before_root, after_root and effect of the element in the `commited_block` corresponding to the `operation_index` of the `block_rejection` above.
* [replay](https://hackmd.io/@corneliuhoffman/Merkle-proofs) the `state_trace` from the `block_rejection` above with the `before_root` above and obtain a new`after_hash'` and `effect'`.
* Check that the new `after_hash'` or `effect'` do not equal the expected ones.
* Finally remove the block and all its descendants from the context and from the succesors of its predecesors.
NOTE: at this point the reward for a succesful rejection is not implemented.
## Operations and their effects (an example).
TODO discuss rejection
We will now briefly discuss some the operations introduced by the ORU proposal. For this we will use a very small example based on test_tx_only_rollup and walk through what happens. Here is the plan:
1. `tz_a` creates a rollup on chain.
2. A Rollup is created with 2 entities `bls_a , bls_b`
3. `tz_a` deposits 1000Tz to `bls_a`
4. inside the ORU some operations happen:
* `bls_a` sends 1Tz to `bls_b`
* `bls_a` sends 2Tz to `bls_b`
* `bls_b` sends .5Tz to `bls_a`
* `bls_b` tries to burn 1.8Tz and send them to `tz_b` (this will not be possible).
5. The 4 operations are batched in one single signature.
6. The batched operations are submitted and commited to the block.
7. `bls_a` "sends" 50Tz to `kt_c`
We start with the creation of the rollup on Chain. We will assume that the chain contains two contracts `tz_a`, `tz_b`.
1. `tz_a` creates a rollup on chain: The commend is `Create_rollup { kind }`. This spends 100Tz from `tz_a`, increments rollup_id creates a packed operation returns the conetxt and an incremented rollup_id. Note that at this point no new tickets have been created.
2. An "empty" rollup `validator.t` is created with an empty node with id `rollup_id` that contains a "genesis block" in its commited_block map. Asume we also create a contract called `kt_c`.
3. `tz_a` deposits 1000Tz to destination `bls_a`. `tz_a` creates a ticket with unit content None as beneficary and value 1_000_000. This ticket is added to the table of tickets on the chain. A `Rollup.result` is produced that has zero consumed gas, zero allocated storage and empty originated contracts and balance_updates. The Tezos_operation `Deposit {ticket_id, beneficiary:bl_a, 10000000}` is added to the existing "program". Finally the Roll_up Validator is sincronised with the above result. At this point on the main chain there will be a ticket:
```ocaml=
{ticket_id=0;
beneficiary= None;
ammmount= 1_000_000;
ticketer= tz_a}
```
and on the ORU there will be a corresponding [ticket](#Operations-and-their-types) whose beneficiary is `bl_a`.
5. The 4 operations are created as `{signer; content; signature}` records. The creation uses the Batcher `sign_transfer_int` resoectively the `sign_burn_int` function. Note also that the fourth operation will be invalid.
6. The signatures are agregated into a `{content; agregated_signature}` record. Here content is the list of the `{signature, content}` from each of the 4 operations. The agregation happens via a [BLS signature aggregation](https://hackmd.io/@corneliuhoffman/BLS-signatures).
7. [Submit of rollup](https://gitlab.com/marigold/tezos/-/blob/ulrikstrid@rollup-rewrite-history/src/proto_alpha/lib_protocol/rollup_apply.ml#L328) The backlog is processed, gas is ran and fees are paid. Then the `Rollup_operation` is added to the pre_block. A `Rollup_result` is produced that has zero consumed gas, zero allocated storage and empty originated contracts and balance_updates and a `Rollup_operation` added to the program. Finally the Roll_up Validator is syncronised by the above result. Note that, in particular, this operation builds a forest of [commits](#Commit_block-of-Rollup_block_commitmentt). The parent commits will be in a previous block but there could be sevar commits per block. This will be used in the process of rejection as there are two reasons to reject a commitment:
* The commitment itself is invalid.
* one of its ancestors is invalid.
At this point nothing changed on the main chain but 3 new tickets have been created on the ORU, one two with beneficiary `bls_a` (of 500), and two with beneficiary `bl_b` (on of 2_000 and one of 500). The initial ticket will also be amended to only contain 997_000.
7. The `sign_burn_int` is used to burn 50 Tz from bls_a. The corresponding linked Tz from tz_a are transfered to kt_c. As before the backlog is processed, gas is ran, and fees are paid and the respective tickets are updated.
After enough time(blocks baked) passes, the window for rejection delays closes and the rollup becomes final. At this point the chain will contain two tickets: with `tz_a` as ticketeer
```ocaml
{ticket_id=0;
beneficiary= None;
ammmount= 950_000;
ticketer= tz_a}
{ticket_id= 1;
beneficiary= kt_c;
ammmount= 50_000;
ticketer= tz_a}
```
The beneficiary `None` in the first ticket represents the fact that the `950_000` are still linked to assets that reside in the ORU and so they could in principle be transfered to other tickets or burned back to the chain.
On the ORU there will still be 4 tickets, two with beneficiary `bls_a` (on of 947_000and one of 500), and two with beneficiary `bl_b` (on of 2_000 and one of 500)
---
# Some more formal details
TODO Explain how each of these work in the `apply.ml`
## Operations and their types
#### Create_rollup of Rollup_creation.t
This operation creates a rollup. The type
:::spoiler `Rollup_creation.t`
```
{kind : Counter | Tx_only}
```
:::
#### Commit_block of Rollup_block_commitment.t
This operation commits a rollup to the chain. Here are the involved types:
:::spoiler `Rollup_block_commitment.t`
```ocaml
{
rollup_id : Z.t ;
rollup_level : Z.t;
content : Rollup_operation_commitment.t list;
predecessor int ;
}
```
:::
:::spoiler `Rollup_operation_commitment.t`
```ocaml
{
before_root : Root of bytes ;
after_root : Root of bytes ;
effect : Rollup_effect.Single.t list ;
}
```
:::
:::spoiler `Rollup_effect.Single.t`
```ocaml
| Withdraw of {
ticket : Rollup_ticket.t ;
tezos_destination : Contract_repr.t ;
}
| Event of string
```
:::
:::spoiler `Rollup_ticket.t`
```ocaml
{
beneficiary : public_key ;
amount : Z.t ;
content : Content.t ;
}
```
:::
:::spoiler `Content.t`
```ocaml
| Tezos_ticket_handle of Z.t
| Rollup_ticket of {
ticketer : public_key ;
value : bytes ;
}
```
:::
#### Reject_committed_block of Block_rejection.t
This rejects the block. The involved types are:
:::spoiler `Block_rejection.t`
```ocaml
{
rollup_id : Z.t ;
rollup_level : Z.t ;
committed_block_id : int ;
content : Rollup_operation_rejection.t ;
}
```
:::
:::spoiler `Rollup_operation_rejection.t`
```ocaml
{
operation_index : int ;
state_trace : Patricia_tree ;
}
```
:::
#### Deposit of Deposit.t
:::spoiler `Deposit.t`
```ocaml
{
ticket : Ticket_onchain_content.Ticket_like.t ;
rollup_id : int ;
rollup_destination : public_key ;
}
```
:::
:::spoiler `Ticket_onchain_content.Ticket_like.t`
```ocaml
{
ticketer : Address.t ;
content : content ;
amount : Z.t ;
}
```
:::
:::spoiler `Address.t`
```ocaml
| Tezos_address of Contract_repr.t
| Rollup of Z.t
| Rollup_address of {
rollup_id : Z.t ;
address : public_key ;
}
```
:::
#### Withdraw of Withdrawal.t
:::spoiler `Withdrawal.t`
```ocaml
{
ticket_id : Z.t ;
tezos_destination : Contract_repr.t ;
entrypoint : string ;
rollup_id : Z.t ;
}
```
:::
#### Submit_rollup_operation of Operation_submission.t
:::spoiler `Operation_submission.t`
```ocaml
{
fee : Tez_repr.t ;
content : Rollup_operation.t ;
rollup_id : Rollup_id.t ;
}
```
:::
:::spoiler `Rollup_operation.t`
```ocaml
{
content : bytes ;
run_gas_limit : Z.t ;
effect_gas_limit : Z.t ;
}
```
:::
#### Touch of { rollup_id : Rollup_id.t }
Sign in with Wallet
Connect another wallet