# Polkadot protocol

TODO:
- go through [this](https://forum.polkadot.network/t/some-old-slide-decks-on-approval-checking-and-disputes/2168) and add if necessary
- write doc in own language
- add cumulus info ([ref](https://github.com/paritytech/cumulus/blob/master/docs/overview.md))

Providing a high-level summary of the most prominent components of the protocol with some diving-into-detail where I found necessary while figuring this all out. I will start by explaining how a parachain block will be added into a relay chain block. Moreover, I will briefly mention BABE and GRANDPA and explain some details which helped me to create a clear highlevel understanding of the protocol.

First, a high high level overview: Only X of the total amount of validators are actively participating in the consensus, the **active validator set**. This set changes every Y amount of hours. Validators from the active validator set can extend the relay chain with new blocks, **BABE**. In addition, they are voting on the head of the chain they believe to be the best, the **finalization** a.k.a. **GRANDPA**. Within this active validator set, a small amount of validators will be assigned to a parachain. The **assigned validators** are the link between the full active validator set and the **collators** on the parachain side. Now, let's dive in!

## Parachain consensus

The base unit of parachain consensus isn't actually a parachain, but something that we call an **availability core** or **core** for short. These are something like CPU cores: they operate in parallel, and have work scheduled onto them in discrete time-slots. Each **parachain** has its own dedicated core, which means that it's always scheduled onto a particular core. However, we can also multiplex multiple chains onto a single core, called **parathreads**. The only difference is the scheduling algorithm.

It's helpful to divide parachain consensus up into 5 distinct protocols that are intertwined in relay-chain consensus.
### 1. Collation

During the **Collation**, collators collect transactions, create a parachain block and a corresponding **candidate**, then submit it to the assigned validators. The candidate consists of the **receipt** and the **PoV**.

The PoV or **proof of validity** contains the final header and all the data needed to check the transition from the previous parachain state to the current state. As for the latter, this includes the list of extrinsics the block is applying and all the merkle nodes that are required to execute the extrinsic (e.g. an extrinsic requires iterating over a StorageMap, then all the map entries will be included in the pov).

The receipt consists of the **CandidateDescriptor** and the hashed **CandidateCommitment**.

- The CandidateDescriptor {
para_id,
relay_parent,
collator,
persisted_validation_data_hash,
pov_hash,
erasure_root,
signature,
para_head,
validation_code_hash,
}

- The CandidateCommitment {
upward_messages,
horizontal_messages,
new_validate_code,
**head_data**,
processed_downward_message,
hrmp_watermark,
}

### 2. Backing

When a validator observes that an availability core is empty and the parachain scheduled on that core is one that the node is assigned to , it'll attempt to gather a collation from a collator and participate in the **backing** process. Here's a flowchart loosely describing the logic that validators perform for the backing process.


Once created, a candidate is sent to a validator in the appropriate backing group (the assigned validators). The validator runs the PVF with the given PoV and the current state found on the relay chain. If the candidate turns out to be valid, the validator circulates the candidate to other validators in the backing group. Once validators check the candidate, they issue a backing statement. Those backing statements are gossiped to all the validators in the active set.

When it’s time to create the next relay chain block, the block author would include the candidates that have received enough backing statements into the new block. It’s worth noting that only the **head_data** from the receipt of the candidate is included on the relay chain. At this point, only the backing group possesses the full PoV.

### 3. Availability

We use **erasure coding** to ensure that PoVs are **available**: in other words, the data (PoV) is split into pieces called chunks, one for each validator. Any large enough subset of chunks can recover the full data. This provides protection against nodes that go offline or lie about having their piece of the data.

Once a parachain block is backed on chain (i.e. its head-data has appeared in a relay-chain block *along with attestations by selected validators*) it begins occupying the availability core. When a validator observes that an availability core is occupied, it attempts to fetch its chunk of the **erasure-coded PoV** if it was not part of the group of validators that initially attested to the block. Otherwise, the validator is responsible for distributing chunks to the corresponding validators.

Every validator signs statements about which parachain blocks it has its chunks for and gossips those statements. The relay-chain block author includes such statements in the relay chain. Once 2/3+ of validators have indicated they have their chunk for the parachain block occupying a core, the parachain block is considered **available** and is officially **included** as part of the parachain and the core is made free again. If availability isn't achieved within some set amount of blocks, then the core is made free, having been considered as **timed out** and the parachain block occupying the core is abandoned.

### 4. Approval Checking

**Approval checking** is a mechanism by which validators randomly self-select (VRF) to check parachain blocks that are available and communicate the intention and results of their checks to the rest of the network. The goal of validators here is to decide if the assigned/backing validators were involved in any misbehaviour. This takes 3 steps:
1. Download the PoV data to check the block. This is done by getting 1/3 of the chunks and combining them to form the full data.
2. Ensure that the PoV data corresponds to a valid parachain state transition.
3. Ensure that all the outputs committed to by the parachain block header actually match the outputs of parachain block execution.

There are two kinds of messages validators send in approval-checking: **assignments** and **approvals**. Assignments are used to communicate intent and eligibility to check a parachain block. An assignment is in one of 3 states:
1. **Pending**: The assignment has no corresponding approval, but it was issued recently.
2. **Fulfilled**: The assignment has a corresponding approval.
3. **No-show**: The assignment has no corresponding approval and it was not issued recently.

When a validator begins checking a parachain block, the first thing it does is gossip its assignment to other validators. This informs the other validators to wait for a corresponding approval message. Once the validator has finished checking, it issues an approval message. If the approval message doesn't come within NO_SHOW_DURATION, then the other nodes consider the initial validator to be a **no-show**. This is the logic each validator runs until parachain blocks are approved:


One of the key insights to understand from the approval checking system is that every validator is assigned to check every parachain block, but it's a matter of when they check. If a validator sees a parachain block as approved before it's their time to check, then they simply don't check and they move on.

### 5. Disputes

Polkadot's Consensus Court of Law. A dispute occurs when 2 or more validators disagree on the validity of a parachain block. The dispute process is relatively straightforward. It was designed to meet the following goals:
1. Determine whether the parachain block is good or bad by putting it to a vote of all validators.
2. If the parachain block is bad, make sure not to finalise or build upon any relay-chain block making it available.
3. Ensure that the losers of the dispute are punished accordingly.

Validators participating in a dispute cast votes in either a 'for' or 'against' category. Participation is either automatic or explicit. Participation is automatic through backing and approval checking. When a validator has issued a backing attestation or an approval message for a parachain block, they automatically count as having participated in the 'for' category. In fact, honest validators keep a record of all recent backing and approval checking messages they've received in order to present evidence against their peers later on. The vast majority of validators are not automatic participants. These validators participate explicitly, which means that they sign a vote for the 'for' or 'against' category after validating the transition from one to the next state (approval checking).

Participation is not mandatory, but a dispute cannot resolve until at least 2/3 of validators have cast a vote in one side. Validators are rewarded for participation and are rewarded for being on the majority side. There are slashing penalties for the losers of a dispute. Disputing a parachain block that is actually valid is just a waste of time and bandwidth so there's a small penalty for that. Submitting an invalid parachain block is an attack against Polkadot, so the slashing penalty is 100%.

This flow-chart captures the logic that each validator runs to determine if a parachain block is approved:
The key takeaways from this procedure are that assignments for later tranches don't get counted at all if there are enough early assignments and that nodes that disappear under mysterious circumstances get replaced.

Disputes are primarily an off-chain process. That is, they occur at the level of 'the chains' and not at the level of 'the chain'. However, the fork of the relay chain that eventually gets finalised should contain a record of the dispute. This is because slashing is an on-chain process.

A **remote** dispute, with respect to a fork of the relay chain, is one which references a parachain block that was not included in this fork of the relay chain. Found in the **finalised chain**.

A **local** dispute, with respect to a fork of the relay chain, is one which references a parachain block that was included in this fork of the relay chain. Eventually erased from history by honest validators.

## BABE

**BABE** is a slot-based algorithm, it is forkful and it has *probabilistic finality*. It breaks time into epochs, with each epoch being broken into slots. In Polkadot, each slot is six seconds long, our target block time. Each slot can have a primary and secondary author (or “slot leader”).

*Primary* slot leaders are assigned randomly, using **VRF**. VRF takes an epoch random seed (agreed upon in advance by all nodes), a slot number and the author’s private key. Each author evaluates its VRF for each slot in an epoch. For each slot whose output is below some agreed-upon threshold, the validator has the right to author a block in that slot. Because the function is random, however, sometimes there are slots without a leader. In order to ensure a consistent block time, BABE uses a round-robin system to assign *secondary* slot leaders.

**Disputes affecting BABE**: when a block is disputed, BABE will create a fork before that block. Disputes will be included into the new fork. What that looks like:
- In block 1a, a parachain block P is included.
- By the time block 3a is built, the parachain block P has been disputed and found to be invalid.
- Honest validators start ignoring block 1a and any children of 1a. Instead, they build a new chain starting with an alternate block 1b which doesn't include the invalid parachain block P.
- These honest validators post the dispute messages relating to parachain block P to the new fork of the relay chain, which ensures that the backers of P are slashed. Once 4b is built, it surpasses the original chain and 1b is finalized.

## GRANDPA

**GRANDPA**'s purpose is to deterministically select the canonical chain. In other words, GRANDPA decides which set of changes is final. It doesn’t produce blocks on its own; instead, BABE does. GRANDPA stands apart from other Byzantine fault-tolerant (BFT) blockchain algorithms in that validators vote on chains, not blocks.

A GRANDPA round:
1. A node that is designated as the **primary** broadcasts the highest block that it thinks could be final from the previous round.
2. After waiting for a network delay, each validator broadcasts a **pre-vote** for the highest block that it thinks should be finalised. If the supermajority of validators are honest, this block should extend the chain of the primary broadcast. This new chain could be several blocks longer than the last finalised chain.
3. Each validator computes the highest block that can be finalised based on the set of pre-votes. If the set of pre-votes extends the last finalised chain, then each validator will cast a **pre-commit** to that chain.
4. Each validator waits to receive enough pre-commits to form a **commit message** on the newly finalised chain.

This commit message is what is included in the block as part of a GRANDPA justification, but additionally it may contain extra block headers that might be needed to verify the commit (since voters might have voted for forks that eventually get orphaned and those blocks might no longer be available on the network).

**Disputes affecting GRANDPA**: We never want a situation where we finalize an invalid block or finalize a block that collators cannot reconstruct. Therefore, GRANDPA voting rule for approval-checking says that each validator should find the highest block B in the chain such that every block between the current finalised block and up to B only triggers inclusion for parachain blocks that the validator has observed to have been approved by enough validators.

GRANDPA also has a feature called **accountable safety** to hold validators accountable for safety violations. A safety violation occurs when two blocks that are in different chains are finalised. BFT systems are always built on the requirement that the maximum number of faulty validators is some fraction — in our case one-third — of the total validators. In order to finalise two conflicting chains, the validator set has failed to meet this requirement; at least one-third of the validators voted on these two chains.

For example, there are 10 validators, meaning 3 is the maximum number of faulty validators the system can withstand (f = (10 - 1) / 3). With 4 faulty validators (red) and a network partition, each group of honest validators (blue) can think a different block is final.

So how do we find out who are adversary? First, we start asking nodes why they didn’t consider one block final when they voted to finalise the second block. Any honest validator should answer this with a set of pre-votes or pre-commits for the second round that have a supermajority for the second block. If that’s the case, then we ask a second question: Which pre-votes for the first round have you seen? We are essentially asking them to rat on other validators and reveal all the votes they received from peers. Somewhere in the union of both sets you will discover the validators who voted for the two conflicting chains.

## END

Alright this was it! Well done for finishing it till the end!

I will keep this document updated with new upgrades to the protocol, mistakes that are made by me or things I think need to be explained less/more thoroughly.

Thanks and have a nice day!

Daan