Polkadot Consensus Part 1: BABE Algorithm Analysis
Tags: polkadot, consensus, algorithms, blockchain
Published: 2022-07-08 02:19:06

## Why do we need consensus?

Every blockchain system has its own consensus algorithm. It is the way that the nodes in a decentralized network are able to stay synced with each other. It is the process by which these nodes communicate and come to agreement, and are able to produce new blocks. To secure the blockchain network, it is crucial to consistently produce the blocks. _It should never stop._ Today, let's closely look at consensus algorithm of Polkadot, which is *BABE*.

## Polkadot's Consensus


> Babe Overview

One of the consensus protocol _**Polkadot/Kusama**_ use is _BABE_(Blind Assignment for Blockchain Extension). It is a _slot-based_ block production mechanism which uses a VRF function to randomly perform the slot allocation for _validators(authorities)_.

_Polkadot's block time can be split into epoch and slot. Epochs can be broken into slots and every slot is six seconds long._

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qtrpka1fkjrbio3za9cf.png)

On every slot, all validators(authorities) generate a random number from VRF and if it is lower than threshold value which is proportional to _weight/amount of stake_(Currently, amount of stake has nothing to do with threshold value) they have right to produce new block. Since it is fully randomized and probabilistic way, which Polkadot called _Primary Slots_, there are some chances that no validators(authorities) are chosen for specific slot. To prevent not to be delayed for producing blocks, Polkadot has made _Secondary slots_, which is also using VRF but deterministic way. Moreover, there could be multiple authorities for single slot, which could lead to **temporal fork**. BABE's fork-choice rule is _weight-based_, which mean chains that has more primary slots are chosen for the system. 


> Code Overview

So let's look at how slot-based BABE is implemented.

**claim_slot**

_Explanation_
- Tries to claim the given slot.

_Params_

- slot: pub struct Slot(u64)
- epoch: pub struct Epoch { some fields }
- keystore: Pointer to keystore. Arc<dyn SyncCryptoStore>

_Returns_
- Option<(PreDigest, AuthorityId)>
- PreDigest: Enum type that contains all data required to validate a block such as _Primary_, _Secondary_, _SecondaryVRF_
- AuthorityId: Public address of authority
```

// Get authorities for specific epoch
// authorities = Vec[(authorityId, index), ...]
// pub struct Slot(u64);
// epoch.authorities = [(authority's public address, weight)]

pub fn claim_slot(
	slot: Slot,
	epoch: &Epoch,
	keystore: &SyncCryptoStorePtr,
) -> Option<(PreDigest, AuthorityId)> {
        
	let authorities = epoch
		.authorities
		.iter()
		.enumerate()
		.map(|(index, a)| (a.0.clone(), index))
		.collect::<Vec<_>>();

	claim_slot_using_keys(slot, epoch, keystore, &authorities)
}
```

**claim_slot_using_keys**

_Explanation_
- Claim Primary and claim Secondary

_Params_
- _slot,epoch,keystore_ are mentioned above
- keys: [(author's public address, index for epoch)]

_Returns_
- Option<(PreDigest, AuthorityId)>

_Comment_
- In *claim_primary_slot*, there is _epoch.config.c_. This is pre-defined constant when we build our node. That is, _pub const PRIMARY_PROBABILITY: (u64, u64) = (1, 4)_ 

```
// claim primary. If fail, claim secondary
pub fn claim_slot_using_keys(
	slot: Slot,
	epoch: &Epoch,
	keystore: &SyncCryptoStorePtr,
	keys: &[(AuthorityId, usize)],
) -> Option<(PreDigest, AuthorityId)> {

	claim_primary_slot(slot, epoch, epoch.config.c, keystore, keys).or_else(|| {
		if epoch.config.allowed_slots.is_secondary_plain_slots_allowed() ||
			epoch.config.allowed_slots.is_secondary_vrf_slots_allowed()
		{
			claim_secondary_slot(
				slot,
				epoch,
				keys,
				keystore,
				epoch.config.allowed_slots.is_secondary_vrf_slots_allowed(),
			)
		} else {
			None
		}
	})
}
```

**claim_primary_slot**

_Explanation_
- If the result of VRF, here, it is _inout_, is less than threshold returns _Some((pre_digest, authority_id.clone()_ else returns _None_. 

```
fn claim_primary_slot(
	slot: Slot,
	epoch: &Epoch,
	c: (u64, u64),
	keystore: &SyncCryptoStorePtr,
	keys: &[(AuthorityId, usize)],
) -> Option<(PreDigest, AuthorityId)> {
    
    ---snippet---

    let threshold = calculate_primary_threshold(c, authorities, *authority_index);
    if check_primary_threshold(&inout, threshold) {
    let pre_digest =
PreDigest::Primary(PrimaryPreDigest {
        slot,
        vrf_output: VRFOutput(signature.output),
        vrf_proof: VRFProof(signature.proof),
        authority_index: *authority_index as u32,
    });
    return Some((pre_digest,
authority_id.clone()))}

    None
}
```

**Secondary Slot**

_Explanation_
- If there is no _primary authorities_, set up to back-up plan.
- **sencondary_author** should return authority if there is no primary slot authority.

_Params_
- _slot,epoch,keys,keystore_ are same with above.
- author_secondary_vrf: _bool type_ for whether VRF secondary slots are allowed.

_Returns_
- Option<(PreDigest, AuthorityId)>

```
fn claim_secondary_slot(
	slot: Slot,
	epoch: &Epoch,
	keys: &[(AuthorityId, usize)],
	keystore: &SyncCryptoStorePtr,
	author_secondary_vrf: bool,
) -> Option<(PreDigest, AuthorityId)> {
    
    if authorities.is_empty() {
    // It means there is authorities for primary slot. Return Immediately
    return None
    }

    let expected_author = secondary_slot_author(slot, authorities, *randomness)?;

    --snippet--
}

pub(super) fn secondary_slot_author(
	slot: Slot,
	authorities: &[(AuthorityId, BabeAuthorityWeight)],
	randomness: [u8; 32],
) -> Option<&AuthorityId> {
	if authorities.is_empty() {
		return None
	}

	let rand = U256::from((randomness, slot).using_encoded(blake2_256));

	let authorities_len = U256::from(authorities.len());
	let idx = rand % authorities_len;

	let expected_author = authorities.get(idx.as_u32() as usize).expect(
		"authorities not empty; index constrained to list length; \
				this is a valid index; qed",
	);

	Some(&expected_author.0)
}
```

**BabeApi**

_Explanation_ 
- After claim _primary/secondary_ slot, it is used in BabeAPi for give epochs.
- Result would be used for _fork-choice_ rule.

_Variables_
- claims: Hashmap<AuthorityId, EpochAuthorship> 
- EpochAuthorship: Struct{
    primary: Vec<u64>,
    Secondary: Vec<u64>,
    SecondaryVRF: Vec<u64>
}

```
async fn epoch_authorship(&self) -> RpcResult<HashMap<AuthorityId, EpochAuthorship>> {
    
    --snippet--

    for slot in *epoch_start..*epoch_end {
			if let Some((claim, key)) =
				authorship::claim_slot_using_keys(slot.into(), &epoch, &self.keystore, &keys)
			{
				match claim {
					PreDigest::Primary { .. } => {
						claims.entry(key).or_default().primary.push(slot);
					},
					PreDigest::SecondaryPlain { .. } => {
						claims.entry(key).or_default().secondary.push(slot);
					},
					PreDigest::SecondaryVRF { .. } => {
						claims.entry(key).or_default().secondary_vrf.push(slot.into());
					},
				};
			}

    Ok(claims)
}
```
 
## Further Thought

When BABE calculates threshold value in *calculate_primary_threshold_ , they have used the sum of all authorities' weight which is equal to 1 as denominator. It doesn't seem like threshold value is proportional to (weight/stake) as they said. Since validators' weight in Polkadot/Kusama is same, amount of stake is not important for current BABE system.



## Reference
{% embed https://medium.com/polkadot-network/polkadot-consensus-part-3-babe-dcc2e0dd8878 %}
{% embed https://wiki.polkadot.network/docs/learn-consensus %}