# Linear++: congestion control for Linear VMs

Linear++ is a congestion control mechanism available for linear VMs. Linear++ can be activated on any linear VM with no modifications to the VM internals. It is sufficient to wrap the target VM with a wrapper VM called `proposerVM` and to specify an activation time for the congestion-control mechanism. In this document we describe the high level features of Linear++ and the implementation details of the `proposerVM`.

## Congestion control mechanism description

Linear++ introduces a **_soft proposer mechanism_** which attempts to select a single proposer with the power to issue a block, but opens up block production to every validator if sufficient time has passed without blocks being generated.

At a high level, Linear++ works as follows: for each block a small list of validators is randomly sampled, which will act as "proposers" for the next block. Each proposer is assigned a submission window: a proposer cannot submit its block before its submission window starts (the block would be deemed invalid), but it can submit its block after its submission window expires, competing with next proposers. If no block is produced by the proposers in their submission windows, any validator will be free to propose a block, as happens for ordinary linear VMs.

In the following we detail the block extensions, the proposers selection, and the validations introduced for Linear++.

### Linear++ block extension

Linear++ does not modify the blocks produced by the VM it is applied to. It extends these blocks with a header carrying the information needed to control block congestion.

A standard block header contains the following fields:

- `ParentID`, the ID of the parent's enriched block (Note: this is different from the inner block ID).
- `Timestamp`, the local time at block production.
- `PChainHeight` the height of the last accepted block on the P-chain at the time the block is produced.
- `Certificate` the TLS certificate of the block producer, to verify the block signature.
- `Signature` the signature attesting this block was proposed by the correct block producer.

An Option block header contains the field:

- `ParentID` the ID of the Oracle block to which the Option block is associated.

Option blocks are not signed, as they are deterministically generated from their Oracle block.

### Linear++ proposers selection mechanism

For a given block, Linear++ randomly selects a list of proposers. Block proposers are selected from the net's validators. Linear++ extracts the list of a given net's validators from the P-Chain. Let a block have a height `H` and P-Chain height `P` recorded in its header. The proposers list for next block is generated independently but reproducibly by each node as follows:

- Net validators active at block `P` are retrieved from P-chain.
- Validators are canonically sorted by their `nodeID`.
- A seed `S` is generated by xoring `H` and the chainID. The chainID inclusion makes sure that different seeds sequences are generated for different chains.
- Validators are pseudo-randomly sampled without replacement by weight, seeded by `S`.
- `maxWindows` number of net validators are retrieved in order from the sampled set. `maxWindows` is currently set to `6`.
- The `maxWindows` validators are the next block's proposer list.

Each proposer gets assigned a submission window of length `WindowDuration`. currently set at `5 seconds`.
A proposer in position `i` in the proposers list has its submission windows starting `i × WindowDuration` after the parent block's timestamp. Any node can issue a block `maxWindows × WindowDuration` after the parent block's timestamp.

### Linear++ validations

The following validation rules are enforced:

- Given a `proposervm.Block` **C** and its parent block **P**, **P**'s inner block must be **C**'s inner block's parent.
- A block must have a `PChainHeight` that is larger or equal to its parent's `PChainHeight` (`PChainHeight` is monotonic).
- A block must have a `PChainHeight` that is less or equal to current P-Chain height.
- A block must have a `Timestamp` larger or equal to its parent's `Timestamp` (`Timestamp` is monotonic)
- A block received by a node at time `t_local` must have a `Timestamp` such that `Timestamp < t_local + maxSkew` (a block too far in the future is invalid). `maxSkew` is currently set to `10 seconds`.
- A block issued by a proposer `p` which has a position `i` in the current proposer list must have its timestamp at least `i × WindowDuration` seconds after its parent block's `Timestamp`. A block issued by a validator not contained in the first `maxWindows` positions in the proposal list must have its timestamp at least `maxWindows × WindowDuration` seconds after its parent block's `Timestamp`.
- A block issued within a time window must have a valid `Signature`, i.e. the signature must be verified to have been by the proposer `Certificate` included in block header.
- A `proposervm.Block`'s inner block must be valid.

A `proposervm.Block` violating any of these rules will be marked as invalid. Note, however, that a `proposervm.Block` invalidity does not imply its inner block invalidity. Notably the validation rules above enforce the following invariants:

- Only one verification attempt will be issued to a _valid_ inner block. On the contrary multiple verification calls can be issued to invalid inner blocks.
- Rejection of a `proposervm.Block` does not entail rejection of inner block it wraps. This is necessary since different `proposervm.Blocks` can wrap the same inner block. Without proper handling this could result in an inner block being accepted after being rejected. Therefore, an inner block is only rejected when a sibling block is being accepted.

## ProposerVM Implementation Details

Linear++ must have an activation time, following which the congestion control mechanism will be enforced.

### Block Structure

Generally speaking the `proposerVM` wraps an inner block generated by the inner VM into a `proposervm.Block`. Once the activation time has past, the `proposervm.Block` will attach a header to inner block, carrying all the fields necessary to implement the congestion mechanism. No changes are performed on the inner block, but the inclusion of the header does change the block ID and the serialized version of the block.

There are three kinds of `proposervm.Blocks`:

- `preForkBlock` is a simple wrapper of an inner block. A `preForkBlock` does not change the ID or serialization of an inner block; it's simply an in-memory object allowing correct verification of `preForkBlocks` (see [Execution modes](#execution-modes) section below for further details of why this is required).
- `postForkBlock` adds congestion-control related fields to an inner block, resulting in a different ID and serialization than the inner block. Note that for such blocks, serialization is a two-step process: the header is serialized at the `proposerVM` level, while the inner block serialization is deferred to the inner VM.
- `postForkOption` wraps inner blocks that are associated with an Oracle Block. This enables oracle blocks to be issued without enforcing the congestion control mechanism. Similarly to `postForkBlocks`, this changes the block's ID and serialization.

### Execution modes

When creating a `proposerVM`, one must specify an activation time following which the congestion control mechanism will be enforced. Therefore, the `proposerVM` must be able to execute before the mechanism is enforced, after the mechanism is enforced, and during the enabling of the mechanism.

#### Pre-fork Execution

Before the congestion control mechanism is enforced, it must hold that the chain's rules are unchanged.

- `preForkBlocks` are the only blocks that are able to be verified successfully.

#### Post-fork Execution

After the congestion control mechanism is enforced, it must hold that the inner VM's rules are still enforced, and that blocks will only be verified if they are signed by the correct validator.

- If an inner block's `Verify` is called, then it is enforced that the `proposervm.Blocks` additional verification must have already passed. This maintains the invariant that when `Verify` passes, either `Accept` or `Reject` will eventually be called on the block.
- Given a parent block, there must be one deterministic proposer window for every child block. This ensures that modifying the child block doesn't allow conflicting proposal windows.
- The proposal windows should rotate after each block, to avoid a single proposer from dominating the block production.
- `postForkBlocks` are issued only when the local node's ID is currently in their proposal window.
- `postForkOptions` are only allowed after a `postForkBlock` that implements `Options` and do not require signatures.

#### Fork Transition Execution

- Each `proposervm.Block` whose timestamp follows the activation time, must have its children made up of `postForkBlocks` or `postForkOptions`.
