# General description of TORU

This document aims to give specification of the TORUs.

:::warning
This document is not complete. For the moment, mainly we focus on the `commitment`, `commitment_finalisation` and `rejection` operations.
:::

We try to give both an informal and formal semantics for operations. All the formal parts are hidden by default to not disturb the reading of this document.

:::spoiler Notations used throughout this document (mainly used for the formal part of this document)

In the following, we always assume that given an operation $o$, we denote:

- $o_s$ : the source of the operation
- $o_f$ : the fees associated to the operation
- $o_c$ : the counter associated to the operation

The context will be denoted by $\mathcal{C}$. We denote $\mathcal{C}_l$ the context at level $l$ (subscript $l$ is sometimes omitted). If a key $k$ is registered into the context it will be denoted $\mathcal{C}[k]$. The assignement of a value $v$ with $k$ in the context will be denote $\mathcal{C}[k] \leftarrow v$.
:::

[TOC]

## Glossary
- **Message**: An L2 operation (deposit, L2 batch, withdraw)
- **Deposit**: (Internal) L1 operation that transfers tickets from the `L1` to the rollup.
- **Withdrawal**: An L2 operation that allows to transfer tickets from an L2 address to an L1 address.
- **L2 batch**: A list of (L2) transactions.
- L2 transaction: a list of (L2) operations, plus a BLS aggregated signature
- L2 operation: a list of (L2) transfers from a single source, and a counter for the source to prevent replay attacks.
- L2 transfer: A ticket amount and an L2 destination.
- **Inbox**: conceptually, a once per block list of messages for the rollup.
- On L1: (possibly empty) list containing hashes of messages for an L2/Rollup. The corresponding messages are included in an L1 block as manager operations.
- On L2: reconstruction by the rollup operator of L1 inboxes, where hashes are replaced by their corresponding messages.
- **L2-context**: (A representation of) the context/legder of the rollup.
- For L2: It is updated by the application of each message of an L2-inbox.
- For L1: parts (merkle proofs) of L2-contexts are provided alongside rejections.
- **Commitment**: An L1 operation that allows to "notarize" the successive updates of the L2 context by the application of each message in an inbox. A commitment targets an inbox and contains, for each message in the inbox, a hash made from the L2-context hash and the associated withdrawals resulting from the message application.
- **Rejected commitment**: A commitment that has been shown to be invalid by an L1 (rejection) operation.
- **Orphan commitment**: Any commitment whose (not necessarily immediate) ancestor has been rejected. Such a commitment will not be slashed but it can never be finalized.
- **Finalised commitment**: A commitment for which the L2-context and the withdrawals^[maybe not accurate here, before finalisation is done in two steps] are finalised. Consequently the commitment^[what about inboxes ??] is removed from the L1's context. These commitments can no longer be rejected. Finalisation is done after an amount of time (~2 weeks).
- **Pending commitment**: Non-rejected, non-orphan commitment for which the associated inbox is not finalised
- **Message application**: Given a message and an L2-context, returns a new modified L2-context by taking the message's content into account. Messages application is both used by L2 to update its context, and by L1 in case of rejection.
- **Rollup origin block**: The block containing the rollup origination operation

## Extending L1 context/storage

New structures are added into the L1 context to store informations about the originated rollups. Among these:

- Rollup state: on L1, should not be confused with L2 context/state, stores generic information about the progression of the rollup
- Rollup storage: on L1, should not be confused with L2 storage, stores the structure of inboxes

## Rollup state

The rollup state associated to the rollup can be describe as an OCaml record:

:::warning
The state below is not complete. The invariants are also approximative. The reason is that the various levels expressed below are actually options, for handling corner cases.

This will be refined later on.
:::

type state = {
    uncommitted_inboxes : int;

    most_recent_inbox_level: level; 
    (* the L1 level of the most recent non-empty inbox for this rollup *)
    
    most_recent_pending_commitment_level: level; 
    (* the L1 level with the most recent pending commitment *)
    
    most_recent_finalised_inbox_level: level; 
    (* the L1 level with the most recent finalised inbox *)
    
    most_recent_finalised_commitment_level: level; 
    (* the L1 level with the most recent finalised commitment *)
    
    ...
}

The rollup state maintains the following invariants:
- `most_recent_inbox_level - most_recent_pending_commitment_level <=
MAXIMUM_INBOX_PROGRESSION` if no rejection happened. Otherwise,
`most_recent_inbox_level - most_recent_pending_commitment_level <=
REJECTION_PERIOD`
- `most_recent_finalised_inbox_level <= most_recent_pending_commitment_level <= most_recent_inbox_level`
- `most_recent_pending_commitment - most_recent_finalised_commitment_level <=
COMMITMENT_MAXIMUM_PROGRESSION [ = REJECTION_PERIOD ]`

At the origination of the rollup, all those fields are initialised with the level of the rollup origin block.

## Rollup storage

The storage of the L1 can be approximated as a key-value map where the keys are itself a list of strings and the values are bytes. To store an OCaml value, an encoding is provided alongside.

In this section, we make abstraction of those details and just assume that the storage is a `key-value` map and give below the various tables used by the rollup implementation.

### Inbox storage

#### Key

    type inbox_key = {
        rollup : rollup_hash; (* rollup associated with this inbox *)
        level : level; (* level of the inbox *)
    }

#### Value

type inbox = {
    messages_hashes : message_hash list; (* list of messages hashes in the inbox *)
    previous_inbox : level option; (* last non-empty inbox level *)
    successor_inbox : level option (* next non-empty inbox level *)
}

The protocol ensures that the maximum number of inboxes in the storage is `finalisation period + maximum commitment progression` (without any rejection it is ``maximum commitment progression + maximum inbox progression``).

### Commitment storage

#### Key

    type commitment_key = {
        rollup = rollup_hash;
        inbox_level : level (* level of the inbox the commitment is associated with *)
    }

#### Value

In the rest of this document, we will call "Context&Withdrawals hash" `cw_hash` (c for context and w for withdrawals) a hash made of the root of an L2-context and the hash of given withdrawals. Informally speaking, `cw_hash = h(h(context) # h(withdraws))`
:::info
TODO: refine the definition if needed.
:::

type commitment = {
    states : cw_hash list; 
    (* The list of L2-context hashes associated with the messages of the inbox *)
    
    previous_commitment : level option; 
    (* the last inbox level with a commitment *)
    
    committer : public_key_hash; 
    (* Public key of the committer *)
    
    submitted_at : level; 
    (* the level of the block containing the commitment *)
}

# Operations description

We describe below the following L1 operations associated with the TORU proposal.

## Deposit operation

A deposit is not associated to an L1 operation. It is done via the Michelson instruction `Deposit` whose semantics is extended: the destination of a deposit can be a TORU address. The deposit contains an amount associated to the ticket.

## Batch submission

A batch of messages for a given rollup can be posted on-chain. The batches are (possibly) included in blocks and the messages's hashes stored in inboxes. For a given rollup, `L1` maintains at most one inbox per level. The inbox of the rollup operator is reconstructed by tracking the inboxes of the `L1` for the corresponding rollup.

## Commitments

A commitment associates to an inbox a list of (context&withdrawal) hashes (of the same size as the list of message hashes contained in the inbox). A commitment can be rejected if at least one of the cw-hashes is not valid (see the rejection operation). To discourage submission of such an invalid commitment, a committer needs to have a bond associated to this rollup. This also incentivizes people to send a rejection if an invalid commitment is posted (as they get rewarded with half the bond).

A rejection operation may create orphan commitments (recall that this means a commitment which is the successor of a rejected commitment). The commitment operation also allows to override an orphan commitments.

The rollup storage maintains for each inbox at most one pending commitment. If an inbox does not have a corresponding commitment it means either that:

1. It never received a commitment so far, and neither do all the successor inboxes;
2. It already received a commitment which was rejected, hence the successor inboxes may contain orphan commitments.

### Syntax
A commitment is an operation that commits on an inbox. A commitment operation $o^c$ is a $5$-tuple $(r,l,i_h, c_p, sl_h)$.

- $r$ is the rollup address;
- $l$ is the level of the inbox;
- $i_h$ is the hash of the inbox;
- $c_p$ is the predecessor commitment (if any);
- $sl_h$ is the list of cw-hashes of the `L2` after applying the various messages of the inbox at level $i_h$.

### Semantics

:::spoiler semantics

Let $l_c$ be the current level.

#### Solvability
A commitment $(r,l,i_h, c_p, sl_h)$ is solvable iff:
- The manager operation is solvable (parsable, is well-signed, TTL didn't expire, manager can pay fee, ...)
- $l_c - l \geq 1$

#### Validity
A commitment $o^c=(r, l,i_h, c_p, sl_h)$ is valid iff, it is solvable, and:

Let tru1 = r

- Ensure $C_l[\mathrm{tru1}][\mathrm{inbox}] \neq \bot$
- ~~Ensure $C_l[\mathrm{tru1}][\mathrm{commitment}] = \bot$~~
> ### Warning
>- The item above is probably not correct, depending on the way we deal with orphan commitments.
> - One solution in the implementation would be to mark the successor of a rejected/orphan block as orphan every time it is encountered.
> - Anyway, from a spec point of view, it's replaced by the item below.
- Ensure $C_l[\mathrm{tru1}][\mathrm{commitment}] = \bot$ or is orphan
- Let $i = C_l[\mathrm{inbox}])$
- Ensure $i.hash = i_h$
- Ensure $len(i.message\_hashes) = len(sl_h)$
- Let $\{\mathrm{most\_recent\_inbox\_level} = l'; \_\} = C_l[\mathrm{tru1}][\mathrm{state}]$
- if $l' \neq \bot$:
- Let $c' = C[\mathrm{tru1}][(l',\mathrm{commitment})]$
- Ensure $\mathsf{hash}(c') = c_p$
- Ensure if $l' = \bot$ then $c_p = \bot$
- Ensure if $\mathcal{C}[o_m^c][\mathrm{tru1}][\mathrm{bond}] = \bot$ then
- Ensure $C[o_m][\mathrm{balance}] >= \mathrm{commitment\_bond}$
- Ensure if $\mathcal{C}[o_m^c][\mathrm{tru1}][\mathrm{bond}] = k$ then
- Ensure $k = \mathrm{commitment\_bond}$

#### Effects

- If $\mathcal{C}[o_m^c][\mathrm{tru1}][\mathrm{bond}] = \bot$ then
- $\mathcal{C}[o_m^c][\mathrm{tru1}][\mathrm{bond}] \leftarrow \mathrm{commitment\_bond}$
- $\mathcal{C}[o_m^c][\mathrm{balance}] \leftarrow C[o_m^c][\mathrm{balance}] - \mathrm{commitment\_bond}$
- $\mathcal{C}[\mathrm{tru1}][(l,\mathrm{commitment})] \leftarrow \\ \qquad \{~ \mathrm{states} = sh_h;\\ \qquad~~~ \mathrm{previous\_commitment} = \mathrm{Some}(l'); \\ \qquad~~~ \mathrm{committer} = o_m; \\ \qquad~~~ \mathrm{submitted\_at} = l_c~\}$
- $\mathcal{C}[o_m][\mathrm{tru1}][\mathrm{pending\_commitment}] \leftarrow 1 + \mathcal{C}[o_m][\mathrm{tru1}][\mathrm{pending\_commitment}]$
- Let $state = \mathcal{C}[\mathrm{tru1}][\mathrm{state}]$
- if $state.next\_commitment =\bot$ then
- $\mathcal{C}[\mathrm{tru1}][\mathrm{state}] \leftarrow \{\mathrm{state}\text{ with } \mathrm{next\_commitment} = l\}$

> ### Warning
>- `most_recent_pending_commitment_level` is never updated (should be here)
>- `next_commitment` not defined in state. Is it the same as `most_recent_pending_commitment_level` ?
>- Introduce why we remember the number of pending commitments per manager (probably for bonds withdrawal)

:::
## Inbox/Commitment finalisation

A finalisation operation can decide to finalise either the state associated to a commitment or to finalise the withdrawals associated to a commitment. For a given commitment, finalising the withdrawals requires the state of this commitment to be finalised. Finalising the state means that the inbox can be removed from the context storage. Finalising the withdrawals means the commitment can be removed from the context storage. This operation succeeds only if the commitment is old enough to be finalised. We also allow the finalisation of commitment for which there is no bond (see [A discussion on the rejection and invalid commitments](https://hackmd.io/Fkh70no4TcK4X3E0qQBrBQ?both#A-discussion-on-the-rejection-and-invalid-commitments).

Withdrawal actually happens only for finalised states. This is why we have this `2` staged process to fully finalise a commitment.

> ### Warning
> - By finalizing the state, we probably mean: finalizing the L2-context whose hash is used to compute the last element `cw_hash` of the `sl_h` field of the commitment ? Maybe add it as a definition in the glossary, or introduce it above.
> - By `state` in the paragraph above, we mean L2-context ? We may want to replace to avoid confusion
> - `requires the state of this commitment to be finalised`: What is the state of a commitment ?
> - Is it possible to batch two L1 operations that successively finalize the state and the withdrawals (I'd say yes)
> - How do we finalize the withdrawals, as only hashes are stored in the inbox and in the commitments ?
> - Once a commitment is finalized, it is said that the commitment can be removed. We guess that we need to keep the latest `cw_hash` to chain it with the next inbox ? This probably needs a clarification in the test above.

### Syntax

A commitment finalisation operation $o^f$ is a $2$-uple $(r, kind\_finalisation)$.

- $r$ is the rollup address
- $kind\_finalisation$ is either `State | Commitment` and says which operation needs to be finalised.

### Semantics

:::spoiler semantics

#### Solvability

- The manager operation is solvable

#### Validity

- if $\mathcal{C}[tru1][state] = \{\mathrm{next\_commitment\_to\_finalise} = l; ~\_\}$
- if $\mathcal{C}[tru1][(l,\mathrm{commitments})] = c_p$ then
- Ensure $l_c - c_p.\mathrm{submitted\_level} > \mathrm{REJECTION\_PERIOD}$

> ### Warning
> - If $kind\_finalisation$ is `Commitment`, we should also check that the state is finalized ? Check if this condition should be added to validity or to solvability.
> - `next_commitment_to_finalize` is not defined in `state`. It should probably be expressed in term of `most_recent_finalised_inbox_level` or`most_recent_finalised_inbox_level`.
> - check that the commit is not orphan (?? could it happen ??)

#### Effects

- Let $c = \mathcal{C}[tru1][(l,\mathrm{commitment})]$
- Let $inbox = \mathcal{C}[tru1][(c.\mathrm{inbox\_level},\mathrm{inbox})]$
- Let $successor\_inbox\_level = inbox.successor\_inbox$
- Let $state = \mathcal{C}[tru1][\mathrm{state}]$
- $\mathcal{C}[tru1][\mathrm{state}] = \{\mathrm{state}\text{ with }\mathrm{next\_commitment\_to\_finalise = sucessor\_inbox\_level}\}$
- $\mathcal{C}[tru1][\mathrm{inbox.predecessor\_level},\mathrm{inbox}] = \bot$
- $\mathcal{C}[tru1][\mathrm{inbox.predecessor\_level},\mathrm{commitment}] = \bot$

> ### Warning
> - Is there a difference between the context keys `commitments` and `commitment` in the validity and effects above, or is it a typo ?
> - In the first line of effects, is the retrieved $c$ equal to the retrieved `c_p` in validity section. If yes, use the same name for both.
> - Ok, it seems that `c_p` is a commitment and `c` is a commitment key from what follows (access to field $inbox\_level$).
> - In `Let inbox = ...`, what happens if we are finalizing the withdrawals ? In which case the state has already been finalized and the inbox removed.
> - The effects doesn't make any distinction between state and withdrawals finalization.
:::

## Rejection

The rejection operation allows to refute any pending commitment which is invalid. If the refutation succeeds, the invalid commitment is removed. The `most_recent_pending_commitment_level` is set to the predecessor of the commitment declared as invalid (**or None, if the precesssor is already finalized ??**). All the descendants of this commitment are orphaned and will be overridden later on by valid commitments. Rejecting a commitment may induce that some commitments (those from the manager whose commitment is rejected) have no associated bonds.

> ### Warning
> - Can we reject an orphan invalid commitment ??
> - Should we explicitely mark the direct successor of the rejected commit as `orphan`, to easily detect its status when overriding it or to avoid finalizing it.
> - Actually, the two cases could be detected without flag, just by checking that the predecessor commit of a direct orphan commitment is not reachable (either rejected or an orphan which has been garbage-collected).

### Syntax

The rejection operation $o^r$ is a $n$-tuple $(l, m, i, c_h, p)$ where:

- $l$ is the inbox level being rejected;
- $m$ is the specific $L2$ message of the inbox which is being disputed;
- $i$ is the index of $\mathrm{hash}(m)$ in the inbox;
- $c_h$ is the commitment hash being rejected (**?? is this the commitment hash or the `cw_hash` before or after (to be checked) application of message $m$ ??**);
- $p$ is a proof that the commitment $c_h$ computed the wrong state.

> ### Warning
> - clarify items in bold between parentheses
> - the last item ($p$ is a proof that) is too vague.

### Semantics

:::spoiler semantics

#### Solvability

- The manager operation is solvable

#### Validity

- Let $st = \mathcal{C}[tru1][\mathrm{state}]$
- Ensure $l \geq \mathrm{st.next\_commitment\_to\_finalise}$
- Let $\mathrm{commitment} = \mathcal{C}[tru1][l,\mathrm{commitment}]$
- Ensure $0 \leq i < len(\mathrm{commitment.state\_hashes})$
- Let $inbox = \mathcal{C}[tru1][l, \mathrm{inbox}]$
- Ensure $inbox.message\_hashes[i] = \mathsf{hash}(m)$
- Let $s = apply(p,m)$
- Ensure $s \neq \mathrm{commitment}.states[i]$

> ### Warning
> - `next_commitment_to_finalize` is not defined in `state`
> - Even if `l >= next_commitment_to_finalize`, we should probably check that we didn't finalize the state.
> - In the semantics below the `Ensure s <> commitment.states[i]` is not accurate. We should take withdrawals into account. In fact `commitment.states[i]` is a `cw_hash = h (h(l2-context) + h(withdrawals))`
> - $c_h$ is not used in the semantics above
> - It's not clear from the validity section, but $p$ should probably include a proof for both a part of the previous context and of the withdrawals (for the message before $m$)
> - An item that links $p$ to the $cw_hash$ before applying $m$ (to prove that $p$ is legit) is probably missing in the validity steps.

#### Effects
TODO

:::

<a id="example_rejection" />

#### Example

We have the following inbox and commitment at level $l$:

inboxL1[l] =        mh0     |       mh1      | mh2
-------------------------------------------------------------------------
inboxL2[l] =        m0      |       m1      | m2
-------------------------------------------------------------------------
C-L2[l]    = {c,{}} m0  {c0,w0}     m1   {c1,w1}    m2    {c2,w2}
-------------------------------------------------------------------------
com[l]     =  -  ,  h0 =            h1 =            h2 =
           =  -  ,  h(h(c0)+h(w0)), h(h(c1)+h(w1)), h(h(c2)+h(w2))

The message application being recused is for $m_1$.

On L1, we don't have access to the (context,withdrawals) before applying the faulty message $m_i$ (in our example $m_1$). However we have access to $h_i = h(h(c_i)+h(w_i))$. The proof $p$ is a compressed Merkle tree (or maybe a pair of compressed Merkle trees) which has the same Merkle root(s) as $(c_{i-1},w_{i-1})$ and in which all leaves not pertinent for applying $m_i$ have been stripped. Using $p$, the L1 layer can both:

- evaluate $m_i$ to check that the next cw_hash is indeed incorrect
- Relate p to $(c_{i-1},w_{i-1})$ in a tamper-proof way

## Bond withdraw

This operation is posted when a manager whish to withdraw its rollup bond. To do so, its number of pending commitment should be empty.

TODO

## Ticket withdraw

This operation is posted when an implicit contract wishes to withdraw the tickets he holds on the rollup. To do so, the inbox containing the withdrawl needs to be finalised.

TODO

## Default limits

- maximum inbox size: $1000$ message
- maximum message size: $5000$ bytes
- commitment bond: $10,000$ xtz
- rejection period: $60,000$ \blocks (about $2$ weeks)
- inbox maximum progression: $150$ inboxes
- commitment maximum progression: rejection period

*[L1]: The Tezos main chain
*[L2]: The rollup state seen as a chain
*[TORU]: Transactional rollups

## Technical Glossary
:::spoiler technical glossary

**operation solvable**: The operation can be included in a block
operation valid]: The operation can be included in a block and the execution succeeds (ie. produces its effects). Note that, when we talk about **validity semantics** or **validity effects**, we assume that **solvability effects** have been applied (eg. taking fees, incrementing the manager's counter, etc)
:::

# A discussion on the rejection and invalid commitments

There is an unclear technical choice on the following invariant:

:::info
Any pending commitment should be associated with a committer having a valid bond
:::

It seems that this invariant is not directly related to the safety of the rollup.

The scenario is the following:

digraph {
    rankdir="LR"
    c1 [label = "c1/A"];
    c2 [label = "c2/B"];
    c3 [label = "c3/C"];

    c1 -> c2;
    c2 -> c3;
}

There are three commits posted by committers `A`,`B` and `C`. Assume that `c1` and `c2` are invalid. It means that from the state of `c1` which is invalid, `B` was able to post another invalid commit `c2`. The most reasonable way that such scenario happens, is that `B` was able to compute the same invalid state than `A`.

This means that an honest play will always try to reject `c1` instead of `c2`. Let us specialize the example above:

digraph {
    rankdir="LR"
    c1 [label = "c1/A"];
    c2 [label = "c2/A"];
    c3 [label = "c3/A"];

    c1 -> c2;
    c2 -> c3;
}

and assume that `c1` and `c2` are invalid. The only way for an honest operator to not get rewarded by the rejection of `c1` is that `A` (or anyone aware of the invalid state committed by `c1`) happens before `c2`.

If we look at the incentive economics:

- `A` lost half of its bond (currently `2500` xtz)
- The honest operator paid the fees associated to the rejection operation without any reward

Any honest operator of TORU already pays fees to maintain the state of the rollup. Likely, he will pay fees also to reject the commit of `A`. Especially considering the current fee market on the L1.

From the point of view of `A` it seems to be a very bad idea to lose `2500` xtz to make a rollup operator to pay more fees.

It seems therefore reasonable to consider that the commit `c1` is valid. In that case. Hence, it can be finalised even though there is no bond attached to it.

Hence, with the current design, there are cases where an honest player will not get rewarded by a rejection operation. However, it also means the attacker lost `2500` xtz.

This design choice can be evolved if we still want to prevent such scenario to happen.