The relay chain in Polkadot is built with the underlying proof-of-stake (POS) block production mechanism by validators. The currently deployed mechanism is a hybrid of BABE and Aura. We plan to replace BABE+Aura with Sassafras in the future.
BABE: A PoS protocol provides a way to elect validators to produce a block in the corresponding time slot. BABE's election is based on verifiable random function (VRF) of validators invented by David et al. for Ouroboros Praos i.e., if a VRF output of a validator is less than a pre-defined threshold, then the validator is legitimate to produce a block. So, one validator or more than one validator or no validator can be elected. This election mechanism is completely private. In other words, no one can guess who is elected until the elected validator publishes a block. The privacy property is very critical for the blockchain security because it is indispensable for achieving security against an adaptive adversary who can corrupt any validator at any time. The drawback of this election mechanism is that no validator will be elected in a significant amount of time. So, validators waste these times by doing nothing which causes slightly worse (and uneven) throughput. Therefore, we fill the empty slots with blocks generated by validators who are deterministically selected by Aura. Aura's election mechanism is not private so it is not secure against an adaptive adversary. For example, the adversary can prepare a DDOS attack on the elected validator by Aura to prevent him to publish his block because the adversary knows who is elected beforehand. Therefore, filling the empty slots with Aura blocks is not a solution in the adaptive adversarial model to prevent empty slots. Nevertheless we note that BABE+Aura is secure (safe and live) in the adaptive adversarial model - the security reduces to the BABE's security. It just does not prevent theoretically to have empty slots that we need to have a better throughput in the adaptive adversarial model.
Sassafras: We construct Sassafras to obtain both security and non-empty slot property in the relay chain in the adaptive adversarial model. The election mechanism is based on the new primitive 'ring-VRF' that we define. Ring-VRF has the same properties as VRF e.g. randomness, verifiability of the output but also has verifiability property without knowing the public key of the validator who generated the output. In short, all validators generate a good amount of ring VRF outputs. Then, these outputs are sorted after verification by all validators to determine the order of the validators in the block production. Since a ring-VRF output does not reveal the identity of the validators for the verification, the privacy is preserved. Another good property of Sassafras is that there is only one validator is selected for a specified time interval. This property is useful to have fewer forks which is better for the parachain performance.
Authors: Handan Kilinc Alper
Authors: Jeff Burdges, Fatemeh Shirazi, Alistair Stewart, Sergey Vasilyev