In the previous lecture, we saw that traditional consensus solution do not scale due to the nature of the consensus problem definition. As the consensus, is a central component of blockchains. A non-scalable consensus limits the performance of the block chain that uses it. In our last lecture, we redefined the byzantine consensus problem into the set byzantine consensus problem. Now we need to define a solution to this new problem. In this lecture, we will examine the democratic byzantine fault tolerant algorithm, or DBFT for short. It is a solution that can be used to scale. As we will learn today, the DBFT algorithm consists of the following state. It has an estimate est of the value to decide. It has a round number r that is initially zero. DBFT also has an array of binary values called bin-values, indexed by the round number and auxiliary binary value b and a set of auxiliary values. Finally, two types of messages are used by this algorithm. Est of r used at round, are to be rebroadcast, the estimate, as we will explain later. An AUX of r used at round r broadcast bin-values of r. DBFT uses two other algorithms; a binary consensus algorithm and a binary value broadcast algorithm. Let's discuss both of these. A binary consensus algorithm solves the classic byzantine consensus problem applied to binary values, where processes proposed and decide either zero or one. On the other hand, DBFT also uses the binary value broadcast algorithm denoted as BV broadcast. Note that in this lecture we will not look at the pseudocode, of the BV broadcast, it can be found elsewhere. When a process invokes BV broadcast, it sends the binary value to other processes that insert this value in the bin values set of this correct participating process. More precisely, it ensures the following properties. BV-obligation. If t plus one correct BV-broadcast V, then V is eventually added to the set bin values of all correct processes. BV-justification. If PI is correct and V is bin values, then V was BV broadcast by a correct process. BV-uniformity, If V is added to bin values of a correct process PI, then eventually V will be in the bin values for all correct processes, PJ. BV-termination, eventually bin values of correct process PI is not empty. Here's a pseudocode of the binary consensus that is used by DBFT. It consists of refining an estimate initially said to the input value V across several iterations or rounds of a loop until it decides. The loop starts by incrementing the round number or to one. Then it consist of BV broadcasting binary values. Once some values are BV delivered in bin values, these values are echoed in a normal broadcast and the delivered values are added to a set of favorite values. Then the algorithm waits until there exists a subset of these favorite values that contains the values delivered in messages of N minus D distinct processes and such that all these values are also among the bin values. Note here that the set bin values may keep being populated until such a set exists. Finally, if this set of values is actually a singleton V, then the estimate become this value V. If in addition V is also the parity of the round, then it is the decided value. If instead the set contains the two binary values, then the estimate is set to the parity of the round to help processes converge. For simplicity in this presentation, Note that this algorithm does not terminate because even after deciding, a process keeps executing additional rounds to help other processes decide, you can refer to the original paper for the terminating version. Let us have a look at why this algorithm ensures agreement of the binary byzantine consensus problem. First, if at the beginning of a round all correct processes have the same estimate, then there will never change their estimate thereafter. This is due to BV obligation and BV justification, leading to the fact that bin values is a singleton, said that the estimate becomes the singleton value. Second, if pi and pj are correct and their values are singleton, then these values are the same. The proof is by contradiction. Assuming that if they have distinct singletons, it means that they received these values from n minus d distinct processes, each among which t plus one are correct. This is impossible as two times n minus t is greater than n over three, which is greater than t. Which means that at least one correct process would have different values while it cannot. Finally, agreement is insured for two reasons, by Lemma two, if one correct process decides v, then another correct process cannot decide differently. In addition, if a correct process does not decide in a round where another decides, then its estimate in the next round becomes the value decided and the process will stick to it as proved by lemma one. The DBFT algorithm actually solves the set byzantine consensus by using the binary byzantine consensus, in a reduction algorithm. The reduction algorithm is very similar to the one that was proposed in 1994 in the conference principle of distributed computing. It also uses a classic reliable broadcast algorithm from the literature. In particular, this reduction algorithm invokes multiple instances of the binary consensus. The novelty here is that the decisions of the binary consensus serve to populate a bitmask that will be used to filter out some of the set of proposal reliably exchange using the reliable broadcast. Now to ensure the validity of the set byzantine consensus, this algorithm does the union of the valid proposal each received, to output a set of transaction that can be used as a block in the block chain.
