====================================================================
Author: Handan Kilinc Alper
Last updated: 20.09.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 this difference is negligible comparing to since there will not be too many validators in the beginning. Then each party divides their timeline in slots.
Obtaining Slot Number: 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 and then updates with the consistency algorithm if it sees a inconsistency with the output of median algorithm after running the consistency algorithm.
If a party is a newly joining party, he downloads chains and receives blocks at the same time. After chains' download completed, he adds the valid blocks to the corresponding chains. Assuming that a slot number $sl$ is executed in a (local) time interval $[t_{start}, t_{end}]$ of party $P_j$, we have the following protocols for $P_j$ to output $sl$ and $t \in [t_{start}, t_{time}]$.
 Median Algorithm: Each validaor stores the arrival time $t_i$ of blocks that belongs to an epoch $e$. At the end of the epoch, validators retrieve the arrival time $t_i$ of only finalized blocks that belong to the epoch $e$. We note that if epoch length is too short than validators may consider the arrival time of blocks in more than one epoch. This should be decided according to epoch lenght and slot length later. In the next epoch, all validators updates their clock according to the result of the median algorithm given below. We note that it is very crtitical for validators to update their clocks at the same time with using the same blocks for the synchronization.
Let us denote the stored arrival times of blocks 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$.
Lemma 1: Asuming that $\D$ is the maximum network delay in terms of slot number and where is the honest stake and $\gamma\alpha$ is the honest and synchronized parties' stake and $\epsilon \in (0,1)$, with the median algorithm where $sl'$ the correct slot number of time $t$ with probability 1  \exp(\frac{\delta^2\mu}{2} where $0 < \delta \leq \frac{\epsilon}{1+\epsilon}$ and $\mu = n(1+\epsilon)/2$.
Proof: Let us first assume that more than half of the blocks among $n$ blocks are sent by the honest and synchronized parties and $t = t_i + a_iT$. Then, it means that more than half of the blocks sent on time. If the block of $sl_i$ is sent by an honest and synchronized party, we can conclude it is sent at earliest at $t_i' \leq t_i  \D T$. In this case, the correct slot number $sl'$ at time $t$ is $sl_i + \lceil\frac{tt_i'}{T}\rfloor = sl_i + \lceil\frac{t_i + a_iT  t_i'}{T}\rfloor$. If $\D T = 0$, sl' = sl, otherwise $sl' \geq sl_i + \lceil\frac{a_iT + \D T}{T}\rfloor = sl+\D$.
If the median does not corresponds to time derived from an honest and synchronized parties' block, we can say that there is at least one honest and synchronized time after the median because more than half of the times are honest and synchronized. Let's denote this time by $t_u + a_uT$. Let's assume that the latest honest one in the ordered list is delayed $\D' \leq \D$ slots. It means that if the median was this one, $sl_u'  sl \leq \D'$ as shown above where $sl_u'$ is the correct slot number of time $t_u + a_uT$. Clearly, $sl \leq sl_u'$. Then, we can conclude that $sl'  sl \leq sl_u'  sl \leq \D' \leq \D$.
Now, we show the probability of having more than half honest and synchronized blocks in $n$ blocks. If , then the blocks of honest and synchronized parties are added to the best chain even if there are $\D$ slots delay (it is discussed in the proof of Theorem 2) with the probability more than $(1+\epsilon)/2$. We define a random variable $X_v \in {0,1}$ which is 1 if $t_v$ is the arrival time of an honest and synchronized block. Then the expected number of honest and synchronized blocks among $n$ blocks is $\mu = n(1+\epsilon)/2$. We bound this with the Chernoff bound:
Given that $0 < \delta \leq \frac{\epsilon}{1+\epsilon}$, $\mu(1\delta) \geq n/2$, this probability should be negligibly small with a $\delta \approx 1$ in order to have more than half honest and synchronized blocks in $n$ slots.
If $\epsilon \geq 0.1$ and $\delta = 0.09$, the probability of having less than half is less than $0.06$ if $n \geq 1200$.
We give another algorithm called consistency algorithm below. This can be run after the median algorithm to verify or update $t$ later on.
 Consistency Algorithm: Let us first define lower consistent blocks. Given consecutive blocks if for each block pair and which belong to the slots and (), respectively are lower consistent for a party , if they arrive on and such that . We call upper consistent if for all blocks . Whenever receives at least either upper or lower consistent blocks, it outputs $t$ and where is the slot of one of the blocks in the block set.
Lemma 2: Assuming that the network delay is at most and the honest parties' stake satisfies the condion in Theorem 2, 's current slot is at most behind or $2\D$ behind of the correct slot $sl'$ at time $t$ (i.e., ).
Proof: According to Theorem 2, there is at least one block honestly generated by an honest party in slot with probability . Therefore, one of the blocks in the lower oe upper consistent blocks belong to an honest party. We do our proof with lower consistent block. The upper consistent one is similar. Let's denote $\hat{\D} = \D$ or $\hat{\D} = 2\D$
If blocks are lower consistent, then it means that all blocks are lower consistent with the honest block.
If chooses the arrival time and slot number of this honest block, then because the honest parties' block must arrive to at most slots later. Now, we need to show that if chooses the arrival time of a different block which does not have to be produced by an honest and synchronized party, then he is still at most behind.
Assume that picks to compute $sl$ for $t$. We show that this computation is equal to . We know because of the lower consistency .
So is going to obtain the same and $t$ with all blocks. Similarly, if picks , he obtains
There are two drawbacks of this protocol. One of drawbacks is that a party may never have consistent blocks if an adversary randomly delays some blocks. In this case, may never has consistent blocks. The other drawback is that if the honest block in $k$consistent block is not a synchronized party then consistency algorithm performs worse than the median. However, this protocol can be used after the median protocol to update or verify the slot number with the consistency algorithm. If this party sees $k$consistent blocks and the slot number $sl'$ obtained with the the consistency algorithm is less than slot number obtained from the median protocol, he updates it with $sl'$.
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