# BABE Epoch Changes

> BABE execution happens in sequential non-overlapping phases known as **epoch**

*https://spec.polkadot.network/sect-block-production*

Epochs are sequentially indexed period of time where a set of authorities are selected to produce blocks. The length of an epoch is pre-defined in the runtime genesis configuration and cannot be changed after the chain has started.

Each epoch has a fixed amount of slots which are equal-length periods (e.g seconds) within an epoch, they are also sequentially indexed and its index is called **slot number**. Each slot within an epoch is assigned to an authority throughout a [lottery proccess](https://spec.polkadot.network/sect-block-production#algo-block-production-lottery) that runs in the very start of an epoch.

It is important to mention that slots relate to real-world clock time, and that's why they can be skipped and by extension why epochs can be skipped as well.


## How an authority is assigned to a slot?

There is no a central point who decides which slot belongs to each authority, what does happen is the authority itself runs a verifiable random function that produces a **pseudorandom output** as well as a proof of authenticity, that can be verified by anyone, then it compares this **pseudorandom output** with a **threshold**, if it is less than the **treshold** then the authority is required to produce a block.

You might ask: *Ok, but, how is the epoch related to how an authority claim slots?*

Good question! The short awnser is randomness and primary probability, those are the necessary informations needed to correctly produce and validate blocks in any epoch.

#### Everything starts at Genesis Chain Spec

The genesis chain spec file contains all the informations needed to build the Genesis block. It also contains the runtime wasm blob which exports the `BabeApi_configuration` function that returns the necessary informations, defined in the [BabeConfiguration](https://github.com/paritytech/substrate/blob/426c26b8bddfcdbaf8d29f45b128e0864b57de1c/core/consensus/babe/primitives/src/lib.rs#L132) struct, to setup the verifiable random function and the threshold, as the initial authorities, the randomness and the primary probability which is a tuple of integers (C1, C2).

- The verifiable random function needs the provided randomness, [Primary Block Production Lottery](https://spec.polkadot.network/sect-block-production#id-primary-block-production-lottery)
- To calculate the threshold we need the primary probability tuple integers and the size of the authorities list, [Winning threshold](https://spec.polkadot.network/sect-block-production#defn-winning-threshold)

With these informations you have everything that you need to either claim a slot to produce a block or validate a block while syncing from genesis on epoch 0 and will keep valid until the epoch 1 starts.

#### After chain started

> The Runtime is required to provide the BABE authority list and randomness to the host via a consensus message in the header of the first block of each epoch.

[Polkadot Spec - 11. Consensus](https://spec.polkadot.network/id-consensus)

Now, once the chain has started the informations that was retrieved from the genesis spec are now provided by the runtime through blocks, but is not every block that contains such information, only the first blocks in an epoch.

The first non-genesis block (a.k.a block number #1) is the first block of epoch 0, and as the spec describes it contains in its header the BABE authority list and randomness for the next epoch (in this case for epoch 1), and this bahavior should happen for every first block inside an epoch.

Then a host client should be awere of those blocks as it needs these informations beforehand to correctly claim slots before an epoch begins also to validate correclty blocks within an epoch.


These messages are encoded in the header digest and they are called **Consensus Messages** ([Definition of Consensus Messages](https://spec.polkadot.network/sect-block-production#defn-consensus-message-babe)), and currently there are 3 types of BABE Consensus Messages:
- Next Epoch Descriptor ([FRAME definition](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/primitives/consensus/babe/src/digests.rs#L131))
- Next Config Descriptor ([FRAME definition](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/primitives/consensus/babe/src/digests.rs#L144))
- On Disabled ([FRAME definition](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/primitives/consensus/babe/src/lib.rs#L129))

You might have the following question: *How the runtime knows when an new epoch should start?*

#### Jump into FRAME internals

For answering the previous question we need to understand what is a Session and how is it related to an epoch.

In the Session substrate frame pallet, the Session is described as:

> A session is a period of time that has a constant set of validators. Validators can only join or exit the validator set at a session change. It is measured in block numbers. The block where a session is ended is determined by the ShouldEndSession trait. When the session is ending, a new validator set can be chosen by OnSessionEnding implementations.

[ref - paritytech/polkadot-sdk](https://github.com/paritytech/polkadot-sdk/tree/master/substrate/frame/session)

That is pretty close from what an epoch is defined by the Polkadot specification, however there is a slightly difference, Sessions are sequentially indexed while epochs might not be sequential, also the Session gives away the responsability of calculates when a session should end and when a new one should start, that is pretty much BABE's responsability

The BABE FRAME Pallet implements two traits defined in the Session FRAME Pallet called [`SessionHandler`](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/frame/session/src/lib.rs#L270) and [`ShouldEndSession`](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/frame/session/src/lib.rs#L145) that are responsible to calculate if a given block slot number is ahead of the end slot of the current epoch, as the runtime keeps track of the start slot for a given epoch, the following comparision is made:

> `epoch_start_slot + epoch_duration < current_block_slot_number`

[ref: Polkadot BABE FRAME Pallet - should_epoch_change](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/frame/babe/src/lib.rs#L538)

The runtime checks if the session should end in block initialization, if the current epoch (session) should end then the session pallet calls the method `rotate_session` which basically updates the authority set and define the next authorities that will compose the Consensus Message for the upcoming next epoch which is handled by BABE's pallet

#### Skipped epochs

As we saw previously the runtime provides the host beforehand with necessary information for the next epoch, but what happen if in a certain epoch there is no first block or even worse there were no blocks at all for _N_ epochs!

Epoch numbers (indexes) might not be contiguous, is possible that the block production mechanism does not work properly and all slots for one epoch or more became all empty, in this case both runtime and host should be aware of this event.

Let's follow the example: we have an epoch duration of 1 minute divided into 10 slots of 6 seconds each. This means that every 6 seconds a block should be produced, now lets say that on epoch X, the last block was produced on slot with index #5, and then no more blocks were produced until slot #2 from epoch X + 4.

So here is the first problem: how the host should behave in this case? What informations should it use to validate the block that appear 4 epochs later? Or once the block production mechanism is fixed what informations should the validator use to claim slots and check if it can produce blocks?

Following what is said in the Polkadot spec:

> In case the epochs **E + 1** to **E + k** are skipped (i.e., BABE does not produce blocks), then the epoch data is used by the epoch **E + k + 1**.

[ref - Consensus Messages, Polkadot Spec](https://spec.polkadot.network/sect-block-production#defn-consensus-message-babe)

What the host client should do in this case is: once it notice that more than one epoch was skipped it should immediatelly use the next epoch data that was already setup, this is pretty similar to how Epoch Configs are handled, _The supplied configuration data are intended to be used from the next epoch onwards_, if no epoch data appears you must use the latest available one!

Regards with the runtime, since it stores the latest epoch index it can easily find if one or more epochs were skipped, to calculate the current epoch index the runtime needs three informations: `current slot`, `genesis slot` (the slot number for the very first non-genesis block, this information is stored by the runtime) and `epoch duration`, with these three arguments we can have the epoch for a block:

> (current_slot - genesis_slot) / epoch_duration

[ref: Substrate Primitives - epoch_index](https://github.com/paritytech/polkadot-sdk/blob/0c6c837f689a287583508506e342ba07687e8d26/substrate/frame/babe/src/lib.rs#L538)

Given the result of the previous formula, the runtime compares with the previous stored epoch index, if it does not grow by 1 then epochs were skipped. Also the runtime should have a mechanism to tie together sessions and epoch indices as they cannot match if an epoch skip happens, for that the runtime holds `BoundVec(epoch, session)` which is basically a vector of tuples and it stores the latest 100 skipped epochs, so it enables the runtime to validate equivocations proofs by knowing what session index was active during some epoch.

Ok, now that we know the runtime stores skipped epochs there is a missing part, what informations the runtime should use to create and issue a BABE Consensus Message? From where it should get the next randomness and authorities?

The Session pallet defines the set of authorities that are going to be active in the current session/epoch and define the set of authorities that gonna be used in the next epoch, so the runtime just have the information already to use. Regards the randomness, BABE pallet is responsible for accumalate randomness during the current epoch X to use for epoch **X + 1** and as 3 epochs were skipped then the runtime will just get the already accumulated randomness to use for epoch **X + 4**.

> The runtime generates randomness by concatenating all the VRF outputs from the previous period.

[ref - paritytech/polkadot-sdk](https://github.com/paritytech/polkadot-sdk/blob/7241a8db7b3496816503c6058dae67f66c666b00/substrate/frame/babe/src/lib.rs#L1001)