====================================================================
Author: Handan Kilinc Alper
Last updated: 07.11.2019
Email: handan@web3.foundation
====================================================================
BABE¶
1. Overview¶
In Polkadot, we produce relay chain blocks using our Blind Assignment for Blockchain Extension protocol, abbreviated BABE. BABE assigns blocks production slots, according to stake, using roughly the randomness cycle from Ouroboros Praos [2].
In brief, all block producers have a verifiable random function (VRF) keys which they register with locked stake. These VRFs produce secret randomness which determines when they produce blocks. A priori, there is a risk that block producers could grind through VRF keys to bias results, so VRF inputs must include public randomness created only after the VRF key. We therefore have epochs in which we create fresh public onchain randomness by hashing together all the VRF outputs revealed in block creation during the epoch. In this way, we cycle between private but verifiable randomness and collaborative public randomness.
... TODO ...
In Ouroboros [1] and Ouroboros Praos [2], the best chain (valid chain) is the longest chain. In Ouroboros Genesis, the best chain can be the longest chain or the chain which is forked long enough and denser than the other chains in some interval. We have a different approach for the best chain selection based on GRANDPA and longest chain. In addition, we do not assume that all parties can access the current slot number which is more realistic assumption.
2. BABE¶
In BABE, we have sequential nonoverlaping epochs , each of which consists of a number of sequential block production slots () up to some bound . At the beginning of an epoch, we randomly assign each block production slot to a "slot leader", often one party or no party, but sometimes more than one party. These assignments are initially secrets known only to the assigned slot leader themselves, but eventually they publicly claim their slots when they produce a new block in one.
Each party has as session key containing at least two types of secret/public key pair:
 a verifiable random function (VRF) key , and
 a signing key for blocks , possibly the same as the VRF key.
We favor VRF keys being relatively long lived because new VRF keys cannot be used until well after creation and submission to the chain. Yet, parties should update their associated signing keys from time to time to provide forward security against attackers who might exploit from creating slashable equivocations. There are more details about session key available here.
Each party keeps a local set of blockchains . All these chains have some common blocks, at least the genesis block, up until some height.
We assume that each party has a local buffer that contains the transactions to be added to blocks. All transactions in a block is validated with a transaction validation function.
BABE with GRANDPA Validators Ouroboros Praos¶
BABE is almost the same as Ouroboros Praos [2] except chain selection rule and the slot time adjustment.
In BABE, all validators have same amount of stake so their probability of being selected as slot leaders is equal. Given that we have $n$ validators and relative stake of each party is $\theta = 1/n$ the probability of being selected is
where is a constant.
The threshold used in BABE for each validator is
where is the length of the VRF's first output (randomness value).
BABE consists of three phases:
1. Genesis Phase¶
In this phase, we manually produce the unique genesis block.
The genesis block contain a random number for use during the first epoch for slot leader assignments, the initial stake's of the stake holders () and their corresponding session public keys (), ).
We might reasonably set for the initial chain randomness, by assuming honesty of all validators listed in the genesis block. We could use public random number from the Tor network instead however.
TODO: In the delay variant, there is an implicit commit and reveal phase provided some suffix of our genesis epoch consists of every validator producing a block and all produced blocks being included onchain, which one could achieve by adjusting paramaters.
2. Normal Phase¶
We assume that each validator divided their timeline in slots after receiving the genesis block. They determine the current slot number according to their timeline. If a new validator joins to BABE after the genesis block, this validator divides his timeline into slots with the Median algorithm we give in Section 4.
In normal operation, each slot leader should produce and publish a block. All other nodes attempt to update their chain by extending with new valid blocks they observe.
We suppose each validator has a set of chains in the current slot in the epoch . We have a best chain selected in by our selection scheme, and the length of is .
Each validator produces a block if he is the slot leader of . If the first output () of the following VRF is less than the threshold then he is the slot leader.
If is the slot leader, generates a block to be added on in slot . The block should contain the slot number , the hash of the previous block , the VRF output , transactions , and the signature . updates with the new block and sends .
In any case (being a slot leader or not being a slot leader), when receives a block produced by a validator , it validates the block with . should check the followings in order to validate the block:

if (signature verification),

if the party is the slot leader: and (verification with the VRF's verification algorithm).

if did not produce another block for another chain in slot (no double signature),

if there exists a chain with the header ,

if the transactions in $B$ are valid.
If the validation process goes well, adds to . Otherwise, it ignores the block.
At the end of the slot, decides the best chain with the chain selection rule we give in Section 3.
3. Epoch Update¶
Before starting a new epoch $e_m$, there are certain things to be completed in the current epoch $e_{m1}$. * Validators update * (Session keys) * Epoch randomness
If there is a validator update in BABE, this update has to be done until the end of the last block of the current epoch $e_{m1}$ so that they are able to actively participate the block production in epoch $e_{m+2}$. So, any validator update will valid in the BABE after at least two epoch's later.
The new randomness for the new epoch is computed as in Ouroboros Praos [2]: Concatenate all the VRF outputs of blocks in the current epoch $e_{m1}$ (let us assume the concatenation is ). Then the randomness in epoch $e_{m+1}$:
This also can be combined with VDF output to prevent little bias by the adversaries for better security bounds. BABE is secure without VDF but if we combine VDF with the randomness produced by blocks, we have better parachain allocation.
3. Best Chain Selection¶
Given a chain set an the parties current local chain , the best chain algorithm eliminates all chains which do not include the finalized block by GRANDPA. Let's denote the remaining chains by the set . If we do not have a finalized block by GRANDPA, then we use the probabilistic finality in the best chain selection algorithm (the probabilistically finalized block is the block which is $k$ block before than the last block of $C_{loc}$).
We do not use the chain selection rule as in Ouroboros Genesis [3] because this rule is useful for parties who become online after a period of time and do not have any information related to current valid chain (for parties always online the Genesis rule and Praos is indistinguishable with a negligible probability). Thanks to Grandpa finality, the new comers have a reference point to build their chain so we do not need the Genesis rule.
4. Relative Time¶
It is important for parties to know the current slot for the security and completeness of BABE. Therefore, we show how a party realizes the notion of slots. Here, we assume partial synchronous channel meaning that any message sent by a party arrives at most slots later. is not an unknown parameter.
Each party has a local clock and this clock does not have to be synchronized with the network. When a party receives the genesis block, it stores the arrival time as as a reference point of the beginning of the first slot. We are aware of the beginning of the first slot is not same for everyone. We assume that the maximum difference between start of the first slot is at most $\delta$. Then each party divides their timeline in slots.
Median Algorithm: Parties who join BABE after the genesis block released or who lose notion of slot run the following protocol to obtain the current slot number with the Median Algorithm.
The median algorithm is run by all validators in the end of syncepochs (we note that epoch and syncepoch are not related). The first syncepoch starts just after the genesis block is released. The other syncepochs start when the slot number of the last (probabilistically) finalized block is $sl_{e} $ which is the smallest slot number such that $sl_{e}  sl_{e1} \geq s_{cd}$ where $sl_{e_1}$ is the slot number of the last finalized block in epoch $e1$. Here, $s_{cd}$ is the parameter of the chain density (CD) property which will be defined according the chain growth. If the previous epoch is the first epoch then $sl_{e1} = 0$. We define the last finalized block as follows: Retrieve the best blockchain according to the best chain selection rule, trim the last $k$ blocks of the best chain, the last block of the trimmed best chain is the last finalized block. Here, $k$ is defined according to the common prefix property.
Each validator stores the arrival time $t_i$ of valid blocks constantly. At the end of a syncepoch $e$, validators retrieve the arrival time $t_i$ of only finalized blocks that belong to the syncepoch $e$. At the end of a syncepoch, each validator retrieves the arrival times of valid and finalized blocks which has a slot number $sl_x$ where $sl_{e1} < sl_x \leq sl_{e}$. Let's assume that there are $n$ such blocks that belong to the current syncepoch. Then, a validator selects a slot number $ sl > sl_e $ and runs the median algorithm which works as follows:
Let us denote the stored arrival times of blocks in the current syncepoch by whose slot numbers are , respectively. Remark that these slot numbers do not have to be consecutive since some slots may be empty, with multiple slot leaders or the slot leader is offline, late or early. After storing $n$ arrival times, $P_j$ sorts the following list where $a_i = sl  sl_i$. Here, $sl$ is a slot number that $P_j$ wants to learn at what time it corresponds in his local time. At the end. $P_j$ outputs the median of the ordered list as ($t$) and $sl$.
for i = 0 to n: a_i = sl  sl_i store t_i + a_i * T to lst lst = sort (lst) return median(lst)
Lemma 1: Asuming that $\delta$ is the maximum network delay, the maximum difference between start time of a slot with the median algorithm where $sl'$ the correct slot number of time $t$ with the probability $p_{cp}$.
Proof Sketch: Since all validators run the median algorithm with the arrival time of the same blocks, the difference between the output of the median algorithm of each validator differs at most $\delta$.
Lemma 1: Assuming that the maximum total drift on clocks between syncepochs is at most $\Sigma$ and $2\delta + 2\Sigma \leq \theta$, the maximum difference between the new start time of a slot $sl$ and the old start time of $sl$ is at most $\theta$.
Proof Sketch: It comes from the fact the property that with $s_{sd}$ slot we can guarantee that majority of finalized blocks produced by honest parties. Becuase of this the selected block by the median algorithm should have been sent in a time compatiple with honest clocks.
Having $\theta$ small enough is important not to slow down the block production mechanism a while after a syncepoch. For example, (a very extreme example) we do not want to end up with a new clock that says that we are in the year 2001 even if we are in 2019. In this case, validators may wait 18 years to execute an action that is supposed to be done in 2019.
5. Security Analysis¶
(If you are interested in parameter selection based on the security analysis, you can directly go to the next section) BABE is the same as Ouroboros Praos except the chain selection rule and slot time extraction. Therefore, we need a new security analysis.
Definitions¶
We give the definitions of security properties before jumping to proofs.
Definition 1 (Chain Growth (CG)) [1,2]: Chain growth with parameters and ensures that if the best chain owned by an honest party at the onset of some slot is , and the best chain owned by a honest party at the onset of slot is , then the difference between the length of and is greater or equal than/to .
Definition 2 (Chain Quality (CQ)) [1,2]: Chain quality with parameters and ensures that the ratio of honest blocks in any length portion of an honest chain is .
Definition 3 (Common Prefix) Common prefix with parameters ensures that any chains possessed by two honest parties at the onset of the slots are such satisfies where denotes the chain obtained by removing the last blocks from , and denotes the prefix relation.
We define a new and stronger conmmon prefix property since we have a chance to finalize blocks earlier (smaller ) than the probabilistic finality that Ouroboros Praos [2] provides thanks to GRANDPA.
Definition 4: (Strong Common Prefix (SCP)) Assuming that the common prefix property is satisfied with parameter , strong common prefix with parameter ensures that there exists and a slot number such that for any two chain possessed by two honest parties at the onset of and where , .
In a nutshell, strong common prefix property ensures that there is a least one block which is finalized earlier than other blocks.
It has been shown [4] that the persistence and liveness is satisfied if the block production ensure chain growth, chain quality and common prefix proerties. Persistence ensures that, if a transaction is seen in a block deep enough in the chain, it will stay there and liveness ensures that if a transaction is given as input to all honest players, it will eventually be inserted in a block, deep enough in the chain, of an honest player.
Security Proof of BABE¶
We first prove that BABE satisfies chain growth, chain quality and strong common prefix properties in one epoch. Second, we prove that BABE's secure by showing that BABE satisfies persistence and liveness in multiple epochs.
Before starting the security analysis, we give probabilities of being selected as a slot leader [2] or noone selected. We use the notations if a slot is empty, if is given to only one late honest party ( behind the current slot) and if is given to only one synchronized honest party.
similarly,
where is the set of indexes of all parties, is the set of indexes of all late and honest parties, is the set of indexes of all honest and synchronized parties with using Proposition 1 in [2].
We can bound and as and where denotes the total relative stake of synchronized and honest parties and denotes the total relative stake of honest and late parties. For the rest, we denote where and is the relative stakes of honest parties.
In Lemma 1 and Lemma 2, we prove that a late party can be at most behind of the current slot. If a late party is a slot leader then his block is added to the best chain if there are at least consecutive empty slots because he sends his block times later and his block may be received times later by other honest parties becuase of the network delay. Having late parties in BABE influences chain growth.
Theorem 1 (CG): Let and let is the total relative stake of honest parties. Then, the probability that an adversary makes BABE violate the chain growth property (Definition 1) with parameters and throughout a period of slots, is no more than , where c denotes the constant .
Proof: We define two types of slot. We call a slot right isolated if the slot leader is one late party and the next slots are empty (no party is assigned). We call a slot right isolated if the slot leader is only one synchronized honest party (not late party) and the next consecutive slots are empty.
Now consider a chain owned by an honest party in and a chain owned by an honest party in . We need to show that honest parties' blocks are added most of times between and . Therefore, we need to find the expected number of right isolated slots between and given that the relative stake of late parties is and expected number of right isolated slots given that the relative stake of synchronized honest parties is . Remark that a slot can be either right isolated or right isolated or neither of them.
Consider the chains and in slots and owned by the honest parties, respectively where is the first slot of the epoch. We can guarantee that is one of the chains of everyone in and the chain is one of the chains of everyone if it is sent in slot . Therefore, we are interested in slots between and . Let us denote the set of these slots by . Remark that .
Now, we define a random variable where . if is or right isolated with respect to the probabilities . Then
With , ,
Remark that and are independent if . Therefore, we define where all indexed by are independent and .
We apply a Chernoff Bound to each with .
Recall that we want to bound the number of and right isolated slots. Let's call this number . If for all , , then . With union bound
since
We find that in the first slot of an epoch the chain grows block with the probability given in (2). Now consider the chain growth from slot to . We know that the chain grows at least blocks between to . So, the chain grows one block for sure if is or right isolated which with probability .
If we apply the same for each we obtain
given and if , ().
Theorem 2 (CQ): Let and . Let where is the relative stake of honest parties. Then, the probability of an adversary whose relative stake is at most violate the chain growth property (Definition 2) with parammeters and in slots with probability at most .
Proof (sketch): The proof is very similar to the proof in [2]. It is based on the fact that the number of and isolated slots are more than normal slots because of the assumption . Remark that probability of having right isolated slot is , having right isolated slot is and sum of them are greater than 1/2 because of the assumption.
Theorem 3 (SCP): Let and . Let where is the relative stake of honest parties. Assuming that the GRANDPA finality gadget finalizes a block at most slots later with the probability , then the probability of an adversary whose relative stake is at most violate the strong common prefix property with parammeter in slots with probability at most .
Proof Sketch: First of all, we need to show that common prefix prefix property is satisfied with the honest relativestake assumption. With a similar proof in [2] in Theorem 5, we can conclude that the common prefix property can be violated with the probability at most .
SCP property is violated if there is no two chain at any slot number such that and where is a chain of an honest party in slot . If slots later, the chain grows more than , then the probabilistic finality passes the GRANDPA finality gadget. So, if for all slots after a nonempty slot, the chains grows more than or the GRANDPA finality gadget finalize a block after slots then strong common prefix proerty is violated given that the GRANDPA finality gadget finalizes a block at most slots later with the probability . This happens with at least the probability in slots.
Remark than even if , we still have the common prefix property as in Ouroboros Praos [2].
Theorem 4 (Persistence and Liveness): Fix parameters , and . Let be the epoch length, is the total lifetime of the system and BABE satisfies persitence [2] with parameters and liveness with parameters with probability where is the resetting power of the adversary during the randomness generation.
Proof (Sketch): The proof is very similar to Theorem 9 in [2]. The idea is as follows: The randomness for the next epoch is resettable until the end of the epoch . Now let's check the chain growth in with where .
The stake distribution (for epoch $e_{j+3}$) which is updated until the end of epoch $e_j$ is finalized at latest in the last slot $12k/c(1+\epsilon)$ of epoch $e_{j+1}$. So it is finalized before the randomness of the epoch ($e_{j+3}$) generated. In addition to this, the chain growth property shows that there will be at least one honest block in the first $12k/c(1+\epsilon)$ slots. These two imply that the adversary cannot adapt validators' in or out according to the random number for the epoch and this random number provides good randomness for the epoch even though the adversary has capability of resetting times ( is the number of corrupted parties and is the maximum number of randomoracle queries for a party). So, the common prefix property still preserved with the dynamic update. Therefore, we can conclude that persistence is satisfied thanks to the common prefix property of dynamic stake with the probability (comes from Theorem 1) If we use the assumptions we can simplify this probability as . Liveness is the result of the chain growth and chain quality properties.
These results are valid assuming that the signature scheme with account key is EUFCMA (Existentially Unforgible Chosen Message Attack) secure, the signature scheme with the session key is forward secure, and VRF realizing is realizing the functionality defined in [2].
Analysis With VDF: TODO
If we use VDF in the randomness update for the next epoch, disappers in because we have completely random value which do not depend on hashing power of the adversary.
6. Practical Results¶
In this section, we find parameters of BABE in order to achieve the security in BABE. In addition to this, we show block time of BABE in worst cases (big network delays, many malicious parties) and in average case.
We fix the life time of the protocol as seconds. Then we find the life time of the protocol . We find the network delay in terms of slot number with $\lfloor \frac{D}{T}\rfloor$ where $D$ is the network delay in seconds. Assuming that parties send their block in the beginning of their slots, $\lfloor\rfloor$ operation is the enough to compute the delay in terms of slots.
The parameter $c$ is very critical because it specifies the number of empty slots because probability of having empty slot is $1c$. If $c$ is very small, we have a lot of empty slots and so we have longer block time. If $c$ is big, we may not satisfy the condition to apply the result of Theorem 4. So, we need to have a tradeoff between security and practicality.
We need to satisfy two conditions to apply the result of Theorem 4 and to apply the result of Lemma 1 . Remark that the second condition implies the first one so it it enough to satistfy the second condition. In order to find a $c$ value which provide resistance against maxumum network delays, we let $\alpha = 0.65$ and $\gamma = 0.8$. Given this if we want to be secure even if we have maximum delay $D$, we need following $c$ values.
 c = 0.278 if $\D = \lfloor \frac{D}{T}\rfloor = 1$,
 c = 0.034 if $\D = \lfloor \frac{D}{T}\rfloor = 2$
 c = 0.018 if $\D = \lfloor \frac{D}{T}\rfloor = 3$
 c = 0.0125 if $\D = \lfloor \frac{D}{T}\rfloor = 4$
 c = 0.0094 if $\D = \lfloor \frac{D}{T}\rfloor = 5$
 c = 0.0076 if $\D = \lfloor \frac{D}{T}\rfloor = 6$
We compute the average block time in the case that the network delay is in average 1 second and all validators behave honestly, $gamma = 0.8$. In order to find, the probability of an unsychronized party's block added to the best chain, we find the probability of having $2\D$right isolated slot meaning that the leaders are all honest and late and the next $2\D1$ slots are empty. Remark that the definitions of $2\D$ right isolated slot is more relaxed than the definition in the proof of Theorem 1 because we do not care the growth of other chains as we care in the security analysis. We compute the expected number of $2\D$isolated slot according to average delay (1 sec) even though we use the secure $c$ value to have maximum network resistance. So, $\D = $\lfloor\frac{1}{T}\rfloor$ in the below computations.
Given a nonempty slot, the probability that this slot is $2\D$right isolated slot is
The expected number of nonempty slot in $L$ is $Lc$. So, the expected number of $2\D$right isolated slot in $Lc$ slot is
$\mathbb{E} = Lcp_{H_S}.$ Then, the block time $T_{block} \leq \frac{LT}{\mathbb{E}} = \frac{T}{c p_{H_S}}$.
We give graphs for required slot time to have the block time in $(1,+1)$neighborhood of the time in the xaxis with different maximum network delay ($D = 1,2,3,4,5,6$ seconds) resistance. Slot time being 0 in the graphs means is that it is not possible to have the corresponding block time.
If we decide to be resistant 6 seconds delay, we can choose $T = 3.905$ and have around 14 seconds block time if the average network delay is 1 second. In this case, the epoch length has to be around 4.5 hours to make sure that we have a good randomness and $k = 96$. If GRANDPA works well the epoch length can be around half of 4.5 hours.
If we decide to be resistant 4 seconds delay, we can choose $T = 2.78 $ and have around 10 seconds block time if the average network delay is 1 second. In this case, the epoch length has to be around 3.2 hours to make sure that we have a good randomness and $k = 97$. If GRANDPA works well the epoch length can be around half of 3.2 hours.
References¶
[1] Kiayias, Aggelos, et al. "Ouroboros: A provably secure proofofstake blockchain protocol." Annual International Cryptology Conference. Springer, Cham, 2017.
[2] David, Bernardo, et al. "Ouroboros praos: An adaptivelysecure, semisynchronous proofofstake blockchain." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018.
[3] Badertscher, Christian, et al. "Ouroboros genesis: Composable proofofstake blockchains with dynamic availability." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2018.
[4] Aggelos Kiayias and Giorgos Panagiotakos. Speedsecurity tradeoffs in blockchain protocols. Cryptology ePrint Archive, Report 2015/1019, 2015. http://eprint.iacr.org/2015/1019