# Incremental Design of Eudico's Ordering Layer

> This document is outdated. Its relevant parts are being incorporated in the [Trantor design document](/P59lk4hnSBKN5ki5OblSFg).

This document describes the high-level design of the ordering layer of the Eudico Filecoin client.
We first present the general architecture in terms of abstract components and their interactions
and then describe multiple concrete instantiations of these abstractions.
We start by an instantiation with basic functionality and sub-optimal performance that is easy and quick to implement.
Further presented instantiations progressively improve in expected performance and functionality
for the price of their increasing complexity.
The architecture, however, is general enough to conveniently describe even the latest state-of-the-art protocols
without making any compromises on the efficiency of their implementation.

In this document we define the *logical* components (abstractions) of the ordering layer at the algorithm level,
rather than blocks of code implementing them.
In practice, multiple of the abstractions defined here may be implemented using a single object in the code
and a single abstraction may be implemented by multiple interacting blocks of code.
We describe the physical implementation in a [separate document](https://hackmd.io/P59lk4hnSBKN5ki5OblSFg).

## General Architecture of the Ordering Layer

The general architecture of the ordering layer is depicted in the figure below.
Each node runs one instance of its implementation.

It has the following (logical) components:

### Transaction mempool

The transaction mempool persistently stores incoming transactions, including their payloads.
Exposes an interface that allows for
- Notifications of new incoming transactions
- Retrieval of the transaction payload based on a small identifier (e.g. the transaction hash)
- Garbage collection of transactions applied to the state

### Availability layer

The availability layer assembles *batches of transaction identifiers* (e.g. hashes) and executes a protocol ensuring availability
of all transactions in these batches (including their payloads) throughout the system.
When a batch of transactions becomes provably available to all correct nodes,
the availability layer produces an *availability certificate*.
Protocol-specific metadata can be attached to created batches and their corresponding certificates,
representing, for example, relations (e.g. causal ones) between the batches/certificates
or additional protocol messages piggybacked on the batches (to be interpreted later).
Exposes an interface that allows for
- Consuming new incoming transaction identifiers
- Notifications of new batches and availability certificates

### Structured batch store

Stores the batches of transaction identifiers and their corresponding availability certificates produced by the availability layer.
Keeps track of the relations between the batches.
If, for example, the batches are causaly related, this component stores the resulting DAG.
Based on the state of the batch store, proposes certificates to the consensus layer.
Exposes an interface that allows for
- Storing batches of transaction identifiers, availability certificates, and the attached metadata
- Retrieving batches of transaction identifiers based on their availability certificates and potentially additional metadata
- Proposing batches/certificates to the consensus layer

### Consensus layer

Establishes a total order on available batch availability certificates.
The consensus layer only orders availability certificates, without ever accessing the associated transaction payloads.
It makes sure, however, that the certificates at its output are valid.
Note that, depending on the implementation, it might not be necessary for the consensus layer
to directly output a certificate for every single batch produced by the availability layer.
Some certificates might be skipped if, for example, they become outdated
or their position in the total order can implicitly be inferred from their relations to other ordered batches.
Exposes an interface that allows for
- Proposing availability certificates
- Outputting a totally ordered stream of availability certificates

### Block assembler

Consumes a stream of totally ordered batch availability certificates,
retrieves the corresponding batches of transaction identifiers from the structured batch store,
retrieves transaction payloads from the mempool, and delivers full blocks to Eudico.
If incoming batches contain duplicate references to the same transaction, the block assembler performs the necessary deduplication.
Note that
- On reception of a single availability certificate, the block assembler may retrieve multiple batches from the batch store,
based on the associated metadata.
- There need not be a 1:1 relationship between the batches produced by the availability layer and the blocks delivered to Eudico.

The block assembler exposes an interface that allows for:
- Consuming a stream of batch availability certificates
- Delivering blocks of transactions (including payloads) to Eudico

In the following, we present instantiations of this general architecture,
starting with a simple one and continuing incrementally towards more advanced ones.

## 1. Simple Ordering Layer

In the first iteration, we propose an instantiation of the ordering layer depicted below.

We use Eudico's mempool augmented by a mechanism for push-notifying about newly added transactions.

We implement the availability layer by a simple algorithm that periodically creates a batch of newly received transaction identifiers,
disseminates the batch to other nodes and gathers signed confirmations from those nodes
that they persistently store all transactions referenced by the batch in their respective mempools.

The transfer of the transaction payloads (at least in an initial implementation) is left to the mempool implementation
and a node receiving a batch simply waits until the referenced transactions all appear in its mempool before sending a confirmation.
Optionally, this simple algorithm can be augmented by a pull mechanism,
where a node actively fetches transaction payloads from the batch originator (e.g. after a timeout).

After gathering a quorum of signed confirmations for an assembled batch,
a node assembles these confirmations to a certificate and stores it in the batch store,
which is itself a simple key-value store for batches indexed by their availability certificates.

In this simple instantiation, the availability layer directly proposes each newly created certificate to the consensus layer,
bypassing the batch store (which contains no logic for deciding which batch to propose).
Alternatively, the batch store can be augmented by some trivial logic that simply proposes
certificates of all newly added batches.

We implement the consensus layer using "Redundant ISS", which is a simplified version of ISS without request deduplication.
We pick PBFT for the ISS ordering sub-protocol, because it is simple and already partially implemented.
Such a simple version of ISS boils down to a multi-leader multiplexer of PBFT instances.
An advantage of this choice compared to proper deduplicated ISS is resistance to a mobile adversary.

We also implement a simple block assembler that gathers the required data for each received block,
deduplicates transactions and delivers full blocks to Eudico.

## 2. Improving Throughput

In the second iteration, we augment the simple design by [Narwhal](https://arxiv.org/abs/2105.11827)
to improve throughput (especially during adverse network conditions).
The Narwhal-based design is shown below.

We replace the simple availability layer by a proper implementation of Narwhal, producing a DAG of batch availability certificates.
Since Narwhal is only an augmented version of
The batch store, if at all, only needs to be modified to store additional metadata encoding the causal relations.

This time, the block assembler uses all causal dependencies of the received batches for assembling the final blocks delivered to Eudico.

To address duplication among the proposed transactions,
a discussed [Narwhal deduplication mechanism](https://github.com/protocol/ConsensusLab/discussions/93) can be implemented.

## 3. Improving Latency

Treating the availability and ordering of transaction batches separately comes at a cost of latency,
since the messages exchanged by the availability layer
are not taken into account at all by the ordering protocol of the consensus layer.
To leverage the work done by the availability layer by the consensus layer,
we implement [Tusk](https://arxiv.org/abs/2105.11827) or [Bullshark](https://arxiv.org/abs/2201.05677)
both in the availability layer and in the consensus layer, as depicted below.

The Tusk and Bullshark algorithms can naturally be split into an availability component creating a DAG
and an ordering component interpreting the DAG produced by the availability component.
This makes them conveniently expressible in terms of the general architecture proposed in this document.

## Reconfiguration

In order to support dynamic reconfiguration of the system,
we need to create a unified notion of progress of the whole system (a version of the system state),
of which multiple components must be aware.
This is necessary for all the components to have enough information on when to switch to new configurations.
This notion of system progress can be expressed as block height, sequence number, epoch, etc... (to be established when implementing reconfiguration).

As is usual, configuration changes must be totally ordered with respect to state updates.
As depicted below, we thus introduce an abstraction keeping track of the configuration of the system
and deciding at which version of the system state which configuration applies.

All system components then need to attach an identifier of the used system configuration to the output they produce,
such that this output can be interpreted accordingly.
For example, an availability certificate of a batch that was produced by a configuration with an outdated membership must be considered invalid.

Note that this reconfiguration approach refers to the general architecture
and can thus be applied to any of the stages of the implementation discribed above.