# A fast-forwardable Witnet superblock chain

## Abstract

This describes a mechanism that allows "fast-forwarding" of superblocks in Witnet. That is, given a pre-validated chain state with its chain tip at superepoch `n`, any further superblocks for epochs `t > n` can be validated without the need to individually validate superblock signatures for all the superblocks in the epoch range `(n, t]` but rather a small subset of those.

The main change resides on how superblocks are chained with each other. Instead of _containing_ a field that points to the previous superblock, they _are_ a cryptographic commitment to multiple former superblocks, in the shape of a Verkle tree.

The other big change is the introduction of _endorsements_: votes for new superblocks coming from the identities in former signing committees.

## Constraints

This mechanism is designed based on the following constraints and general principles:

1. The superblock chaining and voting mechanism is kept as a meta-protocol that does not affect the regular chaining of blocks.
1. Clients should be able to fast-forward multiple days.
1. The impact on regular nodes that do not care about fast-forwarding should be minimal.

## Data structures and identifiers

### Superblock

A `Superblock` identifier is computed as the vector commitment to the following items:

| Index | Name | Description |
| ----- | ------------- | -------------------------------------------------- |
| 0 | `minus_1` | The superblock identifier for superblock `n-1` |
| 1 | `minus_2` | The superblock identifier for superblock `n-2` |
| 2 | `minus_4` | The superblock identifier for superblock `n-4` |
| 3 | `minus_8` | The superblock identifier for superblock `n-8` |
| 4 | `minus_16` | The superblock identifier for superblock `n-16` |
| 5 | `minus_32` | The superblock identifier for superblock `n-32` |
| 6 | `minus_64` | The superblock identifier for superblock `n-64` |
| 7 | `minus_128` | The superblock identifier for superblock `n-128` |
| 8 | `minus_256` | The superblock identifier for superblock `n-256` |
| 9 | `minus_512` | The superblock identifier for superblock `n-512` |
| 10 | `minus_1024` | The superblock identifier for superblock `n-1024` |
| 11 | `minus_2048` | The superblock identifier for superblock `n-2048` |
| 12 | `minus_4096` | The superblock identifier for superblock `n-4096` |
| 13 | `minus_8192` | The superblock identifier for superblock `n-8192` |
| 14 | `minus_16384` | The superblock identifier for superblock `n-16384` |
| 15 | `root` | A `SuperblockRoot` identifier |

As the `minus_X` identifiers are themselves `Superblock` identifiers, this can be treated as a Verkle tree with branching factor `16`.

### SuperblockRoot

The `SuperblockRoot` identifier is also a vector commitment to the following item:

| Index | Name | Description |
| ----- | ------------ | ---------------------------------------------------------- |
| 0 | `block_0` | The block identifier for lock `n*10` |
| 1 | `block_1` | The block identifier for lock `n*10+1` |
| 2 | `block_2` | The block identifier for lock `n*10+2` |
| 3 | `block_3` | The block identifier for lock `n*10+3` |
| 4 | `block_4` | The block identifier for lock `n*10+4` |
| 5 | `block_5` | The block identifier for lock `n*10+5` |
| 6 | `block_6` | The block identifier for lock `n*10+6` |
| 7 | `block_7` | The block identifier for lock `n*10+1` |
| 8 | `block_8` | The block identifier for lock `n*10+8` |
| 9 | `block_9` | The block identifier for lock `n*10+9` |
| 10 | `committee` | The identifier for the signing committee of superblock `n` |
| 11 | `unassigned` | Unassigned |
| 12 | `unassigned` | Unassigned |
| 13 | `unassigned` | Unassigned |
| 14 | `unassigned` | Unassigned |
| 15 | `unassigned` | Unassigned |

As `SuperblockRoot` is a vector commitment analogous to that used for `Superblock`, each item contained within can be treated as a leaf of the Verkle tree whose root is the `Superblock` identifier.

### Committee

The `Committee` identifier is a vector commitment to the `100` identities in the signing committee, and hence those public keys in the committee can be treated again as leaves of the Verkle tree whose root is the `Superblock` identifier.

## Superblock signing and superblock endorsing

In the context of this document, superblock endorsing describes the situation in which the eligibility for signing superblock `n` also grants rights to broadcast signatures for some subsequent superblocks.

May a node in the Witnet network be eligible for signing superblock `n`, it must produce and broadcast BLS signatures (endorsements) for the superblocks `n + 2 ^ ℕ` for `0 <= ℕ < 15`. That is, it will become eligible for endorsing at every subsequent superblock whose index is a power of two added to `n`.

Endorsing does not replace real-time signing. The liveness mechanism of Witnet still relies on real-time signing for deciding whether to continue building the chain or roll it back.

Endorsements are to be used by clients that need to perform fast-forwarding. That is the case of bridges to smart contract platforms, which need to keep their superblock chain tip synchronized with the one on the Witnet side at the lowest gas cost possible.

## Proving and validation procedure

Given a client synchronized up to superblock `n`, any further superblock `t > n` can be efficiently verified thanks to the properties of Verkle trees and BLS, provided that endorsements are regularly produced, broadcast, collected, aggregated and stored by the clients (e.g. a Witnet node trying to sync from scratch) or intermediaries (e.g. a piece software that brokers superblocks between a Witnet node and a `WitnetBlockRelay` Solidity contract).

### Proving procedure

1. Calculate how many superblocks we are fast-forwarding: `ff = t - n`
1. Iterate with `0 <= ℕ < 15` over every bit in `ff` in a big-endian fashion, performing the following operations if the bit at position `ℕ` is `1`:
2.1. Accumulate the block identifier of `n + 2 ^ ℕ` into a vector of intermediary superblock identifiers.
2.2. Aggregate endorsements for superblock `n + 2 ^ ℕ`.
2.3. Aggregate the BLS public keys of the non-endorsing identities for the same superblocks.
1. Generate PCS multiproof for all the paths leading to the target `Superblock` identifier of `t` from:
- Each `Committee` vector entry at `n`.
- The superblock identifier of `n`.
1. Present the following items to the validator (client):
- The target superblock index `t`.
- The vector of intermediary superblock identifiers.
- The aggregated endorsements (up to 15 BLS signatures).
- The aggregated BLS public key of the non-endorsing identities (up to 15 BLS keys).
- The PCS multiproof.

### Validation procedure

1. Calculate how many superblocks we are fast-forwarding: `ff = t - n`
1. Verify that `ff > 0`.
1. Verify that the presented PCS multiproof is a valid commitment from `n` and its signing committee to the superblock identifier of `t`. (Optionally: verify that the intermediary superblock identifiers also belong in the Verkle tree).
1. Iterate with `0 <= ℕ < 15` over every bit in `ff` in a big-endian fashion, performing the following operations if the bit at position `ℕ` is `1`:
- Verify that the next aggregated BLS signature is a valid BLS signature for the BLS complementary of the next aggregated BLS key and the next intermediary superblock identifier.
1. If all validations passed, we are good to update our superblock chain tip (`n = t`), as well as, optionally, all the intermediary superblocks.

## Bootstrapping

From a client perspective, a first superblock identifier, index and signing committee need to be presented to the client in a trusted manner. In the case of an EVM-based client, this shall be done through a permissioned method that can be only called once, or even better, in the contract constructor, which automatically fits in that category of methods.

From the point of view of the Witnet network, nodes must start producing, collecting and aggregating endorsements in advance of the bootstrapping process of any client.

## Limitations

- This algorithm allows fast-forwarding up to 85 days at once. In the event that a longer fast-forward is needed, it can be easily repeated in 85-days steps, provided that all the relevant signatures and elements of proof have been retained.
- As `ℕ` becomes closer to `15`, the likelyhood of a "lack of endorsements" situation grows, because as time pases, there is an increased chance for the identities in the committee `n` to quit the system. May a client need to fast-forward from `n` to a `t` for which there are not enough endorsements by the identities in the `n`th signing committee, it will first need to fast-forward to a lower `t' < t`, and then do a further fast-forward attempt from `t'` to `t`.
- Clients may implement a rescue mechanism to recover in a trusted manner in the event that no fast-forward is performed after the 85 days period (or whatever period is suitable for the client).

## Rollbacks

Superblock rollbacks have no impact on this scheme, because this operates solely on superblocks for which the network can obtain enough signatures.

## Impact on resources

### Network usage

- This protocol may increase number of `SUPERBLOCK_VOTE` messages or a similar message used for endorsements by a factor of up to `15`. This increase is expected to have a negligible impact because these messages would still make up for a small fraction of all the messages currently going through a Witnet P2P session.

### Computing and memory

- This protocol may increase CPU and RAM usage if the BLS endorsements are validated as they come before they are aggregated. However, aggregation is only needed for nodes that actively collect endorsements with a view to proving superblocks to other clients. Nodes should be fine to opt-out from these validations as long as they keep forwarding the unvalidated messages.

### Storage

- Nodes that actively collect endorsements with a view to proving superblocks to other clients should persist those elements of proof in their storage so that they can provide them at a later time even if they are restarted.
- Beyond the maximum fast-forwarding period of 85 days, it is up to those nodes to decide how often they wipe old endorsements. Some may keep them longer if they know they are serving a client that goes idle for longer periods.
- Nodes that do not participate in proving can forget the endorsements as soon as the next superepoch.

## Further development

### Transaction-to-chain commitments

If we get rid of contraint no. 1 above, we can turn blocks into vector commitments themselves, and actually prove the existence of individual transactions or all the transactions in all superblocks in between `n` and `t` with just a few more elements of proof when proving `n → t`.

## Some graphics