Byzantine Agreement, Made Trivial
CSAIL, MIT Cambridge, MA 02139, USA
March 19, 2018
We present a very simple, cryptographic, Byzantine-agreement protocol that, with n = 3t + 1 players, t of which are malicious, halts in expected 9 rounds.
Copyright By PowCoder代写 加微信 powcoder
1 Introduction
Byzantine agreement is hugely important, and has attracted an enormous amount of attention over the course of multiple decades. Yet, somehow, the simple, digital-signature-based, solution contributed in these few pages appears to have eluded detection. (A possible explanation may lie in the fact that, although digital signatures have been used in Byzantine agreement for a long time, they could have, for the most part, been replaced by an abstract form of authentication by fiat. By contrast, the protocol presented here exploits their very numerical values.)
Our protocol is not only simple and theoretically attractive, but also extremely practical, despite the fact that the envisaged adversarial model is very strong.
Historical Note The notion of Byzantine agreement was introduced by and Lamport [1] for the case of binary values. However, it was quickly extended to allow for arbitrary initial values. (See the surveys of Fischer [2] and Chor and Dwork [3].) Initially, BA protocols were deterministic. Probabilistic BA protocols were pioneered by Ben-Or in asynchronous settings [6].
2 Preliminaries
Cryptography We shall rely on two well known cryptographic tools, digital signatures and a hash function H. Both are idealized, for simplicity sake. Digital signatures are not existentially forgeable under adapting chosen message attacks and enjoy the following uniqueness property: for each public key and each message m, there is only one string that is accepted as the signature of m relative to that public key. The hash function H is modeled as a random oracle.
Note. We wish to stress that the result holds also via verifiable random functions, which can be constructed under concrete complexity assumptions [12]. (However, this introduces conceptual complexities that are quite orthogonal to the real contributions of this paper.)
• Communication. The players communicate, in rounds, over a synchronous and complete point- to-point network. Messages are sent at the start of a round and received by the end of the round.
• PKI. Each player i has a public key, and a sufficiently long (e.g., 256-bit long) string R is selected randomly and independently of the players’ public keys. The players, their public keys, and R are common knowledge.
• The Adversary. A player is honest and follows all his prescribed protocol instructions, until he becomes malicious, that is corrupted by the Adversary, a polynomial-time algorithm (unable to forge digital signatures), who initially knows all players, all public keys and R. The Adversary perfectly coordinates all malicious players. He takes all actions on their behalf, including receiving and sending all their messages, and can choose to have them deviate from their prescribed instructions in arbitrary ways. At the start of every round, the Adversary first chooses which additional players to corrupt, then learns all the messages sent by the currently honest players, and finally chooses the messages sent by the currently malicious players. The
Adversary cannot, however, tamper or interfere in any way with the messages sent by (currently) honest players. (Thus, the Adversary does not have the power of, after seeing the message sent by an honest player i in a given round, corrupt i, and modify any of i’s messages in the round.)
The Adversary is a t-adversary if he corrupts exactly t players.
In this paper we show how to defeat adversaries who can corrupt a third (minus one) of the players,
and thus, for simplicity, we solely define Byzantine agreement protocols for such adversaries.
Byzantine agreement Protocols Let n and t be positive integers, such that n = 3t + 1. A protocol P is an arbitrary-value (respectively, binary) (n,t)-Byzantine agreement (BA) protocol with soundness σ ∈ (0,1], if, for every set of values V (respectively, for V = {0,1}), and any t-adversary A, in an execution e of P with A with n players, in which every player i starts with an initial value vi ∈ V , every honest player j halts with probability 1, outputting a value outj ∈ V , so as to satisfy, with probability σ, the following two properties:
1. Agreement: outi = outj for all honest players i and j.
2. Consistency: if, for some v, vi = v for all honest players i, then outj = v for all honest players j.
(P halts when each honest player halts, and its output is v if, for some honest player i, outi = v.)
Remark We stress that, in the antecedent of the Consistency property, a player i is honest if he is honest throughout the execution e. Thus our notion of consistency is more robust than the traditional one, which requires that the output of every honest player j is v only when v is the initial input of all initially honest (or even all) players i. Our BA protocols have soundness 1.
• Throughout this paper, the set of all players is N, the cardinality of N is n, the number of malicious players is t, and n = 3t + 1.
• We identify each player i with his public key. We denote i’s digital signature of a string x by sigi(x). To ensure signers and messages are retrievable from digital signatures, we define
SIGi(x) (i, x, sigi(x)).
• For all rounds r and players i and j, in a BA protocol i receives a single message from j, denoted
by mri (j), either an element of V or the symbol ⊥ ∈/ V .1
• For each possible value v we denote by #ri (v) (or just #i(v) when r is clear) the number of
players from which i has received the value v.
1That is, we assume that a player sends exactly one message to another player in a round. Indeed, if i sent two different messages to j in a round r, then —say— mri (j) is assumed to be the lexicographically first element of V that j has received from i.
3 The Binary BA Protocol BBA⋆
Historical Note and Quick Announcement The binary BA protocol of this paper, BBA⋆, is a novel adaptations to our public-key setting of the probabilistic binary BA protocol of Feldman and Micali [9]. Their protocol was the first to work in an expected constant number of steps. It worked by having the players themselves implement a common coin, a notion proposed by Rabin, who implemented it via an external trusted party [7].
The protocol of [9] was not cryptographic and required a 2/3 honest majority. To the best of our knowledge, BA protocols with digital signatures were pioneered by Dolev and Strong [4]. To the best of our knowledge, Dolev and Strong [4] were the first to prove the existence of (n, t) BA protocol,, with n ≥ 2t + 1, assuming digital signatures. A probabilistic, cryptographic version of the Feldman-Micali protocol, halting in expected constant number of rounds and tolerating any t < n/2 malicious players was discovered by Katz and Koo [10]. Their protocol is beautiful, but quite complex and not too practical.
A practical modification of BBA⋆ tolerating a t-adversary for any t < n/2, has been recently discovered by and the author. Stay tuned!
All the above protocols have soundness 1.
3.1 The Intuition behind BBA⋆
Before our new binary (n,t)-BA protocol BBA⋆, we wish to build some intuition.
Consider executing, for γ = 1, 2, . . ., the following 3-step protocol P(γ). Throughout these executions, each player i updates a retained binary variable bi, representing his current opinion about what his final binary value outi should be. (Initially, bi is the initial binary value of player i.)
The Idealized Protocol P(γ)
1. Every i sends bi to all players, including himself.
2. A new randomly and independently selected bit c(γ) magically appears in the sky, visible to all. 3. Every player i updates bi as follows.
3.1 If #1i(0)≥2t+1, then i (re)sets bi to 0.
3.2 Else, if #1i(1)≥2t+1, then i (re)sets bi to 1. 3.3 Else i (re)sets bi to c(γ).
We refer to each such bit c(γ) as a magic coin.
Quick Analysis. Since we assume that at least 2t + 1 players are honest, it is clear that
(A) If, at the start of each protocol P(γ), the honest players are in agreement on a bit b (i.e., if bi = b for all honest player i), then they remain in agreement on b by its end.
It is not not hard to see (and will be shown in our proof of Theorem 3.1 anyway) that
(B) If the honest players are not in agreement (on any bit) at the start of P(γ), then, with
probability 1/2, they will be in agreement (on some bit) by its end.
Finally, it is also clear that
(C) If all honest verifiers started with the same initial binary value b (i.e, if the honest players were
originally in agreement on a bit b), then they will continue to agree on b.
Properties A, B, and C guarantee that each P(γ) is a binary BA protocol with soundness 1/2.
Replacing Magic Coins with Frequently Magic Coins
Notice that, to bring the players into agreement with probability significant probability, it is not necessary that a magic coin is generated in the second step of P(γ). Trivially, if the bit c(γ) were always visible to all players, but only with probability 2/3 random and independent, then the players not already in agreement would be brought into agreement with probability 1/3.
Slightly less trivially, P(γ) would bring the players into agreement with probability 1/3 with
an even less magic coin. Namely, it suffices that, in the second step of P(γ), each player i sees his
own bit c(γ), provided that, with probability > 2/3, i
E: for all players i and j, c(γ) = c(γ), where c(γ) is a random bit. iji
With complementary probability, the bits c(γ) can be adversarially chosen. i
We call such a bit-vector {c(γ) : i ∈ N} a frequently magic coin. i
(Note that, when event E occurs, the players happen to see a “common and random coin”, but they may not be aware that this is the case. By contrast, with a magic coin, it is common knowledge that the bit c(γ) is “random and common”.)
The reason why a frequently magic coin suffices to bring the players into agreement with probability 1/3 is that, once the coin happens to be random and common, which happens with probability 2/3, it brings the palyers into agreement with probability 1/2. Also notice that, once the players are in agreement, no matter what the future frequently magic coins might be, the honest players remain in agreement, due to rules 3.1 and 3.2.
Replacing Frequently Magic Coins with Concrete Coins
Frequently magic coins are less magic, but magic nonetheless. Let us thus show that the players themselves, without any help from the “sky”, can, by themselves (with digital signatures, random oracle H, and random string R), implement a frequently magic coin c(γ) in a single step.
Single-Step Protocol ConcreteCoin(γ)
Each player i
• Sends the value vi SIGi(R, γ).
• Computes the first player, m, such that H(vm) ≤ H(vj) for all players j. • Sets c(γ) to be the least significant bit of H(vm).
Note that all the 256-bit strings H(vi) are random (because H is a random oracle) and independent (because, due to the retrievability property of digital signatures, SIGi(R,γ) ̸= SIGi′(R,γ′) whenever (i, γ) ̸= (i′, γ′)).
Also note that the value vm is not totally random. For instance, since it is the minimum of n, random, 256-bit values, the first bit of vm is very likely to be 0 when n is sufficiently large.
However, for each γ, the least significant bit of H(vm), lsb(H(vm)), is, ignoring negligible biases, a random and independent bit, no matter whether n is large or small.
We refer to the so generated bit lsb(H(vm)) as a concrete coin. One Last Problem
Since each P(γ), executed with concrete coins, reaches Byzantine agreement with probability 1/3, one may consider executing P(1), P(2),…, until agreement is reached. The problem with this idea is that one would have to keep executing the protocols P(γ) for ever. In fact, when Byzantine agreement is reached, the honest players are not aware that this is the case, and thus cannot terminate.
Two Possible Solutions
A simple solution consists of executing P k times, where k is fixed and sufficiently high. For instance, k = 300. By doing so, however, one may waste rounds unnecessarily, since most of the time agreement will be reached early on.
A second solution, followed in protocol BBA⋆, consists of executing, for γ = 1, 2, . . . a protocol P′(γ) consisting of three correlated executions of P(γ).
More precisely, each P′(γ) consists of
1. A first execution of P(γ) with c(γ) = 0 (I.e., with “the concrete coin is forced to be 0”.)
2. A second execution of P(γ) with c(γ) = 1. (I.e., with “the concrete coin is forced to be 1”.) 3. A third execution of P(γ) with c(γ) being a “genuinely flipped” concrete coin.
As already mentioned, the third execution of P(γ) —and thus an execution of P′(γ)— enables reaching agreement with probability 1/3. The first two executions of P(γ), as we shall see, ensure that, once agreement has already been reached on some bit b, an honest player i can learn that this is the case, and terminate the iteration with the binary output b.
3.1.1 Description and Analysis of BBA⋆
Protocol BBA⋆ is a 3-step loop, where the players repeatedly exchange Boolean values, and different players may exit this loop at different times. A player i exits this loop by propagating (i.e., by sending to all players, including himself), at some step, either a special value 0∗ or a special value 1∗, thereby instructing all players to “pretend” they respectively receive 0 and 1 from i in all future steps. (Alternatively said: assume that the last message received by a player j from another player i was a bit b. Then, in any step in which he does not receive any message from i, j acts as if i sent him the bit b.)
The protocol uses a counter γ, representing how many times its 3-step loop has been executed. At the start of BBA⋆, γ = 0. (One may think of γ as a global counter, but it is actually increased by each individual player every time that the loop is executed.)
Protocol BBA⋆
(Communication) Step 1. [Coin-Fixed-To-0 Step] Each player i propagates bi.
1.1 If #1i(0)≥2t+1, then i sets bi =0, sends 0∗, outputs outi =0, and HALTS. 1.2 If #1i(1)≥2t+1, then, then i sets bi =1.
1.3 Else, i sets bi = 0.
(Communication) Step 2. [Coin-Fixed-To-1 Step] Each player i propagates bi.
2.1 If #2i(1)≥2t+1, then i sets bi =1, sends 1∗, outputs outi =1, and HALTS. 2.2 If #2i(0)≥2t+1, then i set bi =0.
2.3 Else, i sets bi = 1.
(Communication) Step 3. [Coin-Genuinely-Flipped Step] Each player i propagates bi and SIGi(R, γ).
3.1 If #3i(0)≥2t+1, then i sets bi =0.
3.2 Else, if #3i(1)≥2t+1, then i sets bi =1.
3.3 Else, letting Si = {j ∈ N : m3i (j) = SIGj(R,γ)},
i sets bi = c(γ) lsb(minj∈S H(SIGi(R, γ))); increases γi by 1; and returns to Step 1. ii
Theorem 3.1. BBA⋆ is a binary (n,t)-BA protocol with soundness 1. Proof Sketch. We start by proving the following claims.
Claim A: If, at the start of an execution of Step 3, no player has yet halted and agreement has not yet been reached, then, with probability at least 1/3, the players will be in agreement at the end of the step.
Proof of Claim A. Let γ be the current value of the counter. By the uniqueness property of the underlying digital signature scheme, the n values H(SIG1(R,γ)),…H(SIGn(R,γ)) are well defined, 256-bit long, random strings. Ignoring the remote possibility of ties, let H(SIGm(R,γ)) be the minimum of these value. Then, with probability at least 2/3, m is a honest player. In this case, at the start of the Step 3 in question, player m sends SIGm(R,γ), and his signature is received by all players. Thus, when m is honest, whether or not the malicious players send their signatures, for all honest players i
H(SIGm(R, γ)) = min H(SIGi(R, γ)). j ∈Si
Define the bit c(γ) as follows:
Then, ignoring negligible biases, when m is honest, c(γ) is a random bit and c(γ) = c(γ) for all honest
c(γ) lsb(H(SIGm(R, γ))).
players i. Continuing to assume that m is honest, there are five exhaustive cases to consider: namely,
(i) All honest players i update their binary variables bi according to 3.1. In this case, Agreement holds on 0.
(ii) All honest players i update their binary variables bi according to 3.2. In this case, Agreement holds on 1.
(iii) All honest i update their binary variables bi according to 3.3. In this case, at the end of Step 3, Agreement holds on c.
(iv) Some honest i update their binary variables bi according to 3.1, and all others according to 3.3.
Let H0 (respectively, H(1)) be the set of honest players updating their bits according to 3.1 (respectively, 3.2). If c(γ) = 0, then all players i in H(0) reset their binary variables bi to 0, while all those in H(1) reset theirs to c(γ), which is 0. Since c(γ) = 0 with probability 1/2, then in case (iii) Agreement on 0 is reached with probability 1/2.
(v) Some honest i update their binary variables bi according to 3.2, and all others according to 3.3. In this case, a symmetric argument shows that Agreement is reached on 1 with probability 1/2.
In sum, when m is honest, at the end of an execution of Step 3, no matter what malicious players might do, agreement is reached with probability at least 1/2. Thus, since the probability that m is honest is > 2/3, the probability that agreement is reached at the end of Step 3 is
> 32 · 12 = 1/3.
Claim B: If, at some step, agreement holds on some bit b, then it continues to hold on the same
Proof of Claim B. Assume that the players are in agreement on a bit b at the start of some step. Then in that step all honest players send b, so that, for every honest i, #i(b) ≥ 2t + 1 and thus i sets bi = b at the end of the step. Thus, agreement holds ob b at the start of the next step. And so on.
Claim C: If, at some step, a honest player i halts, then agreement will hold at the end of the step.
Proof of Claim C. Assume first that a honest player i halts in Coin-Fixed-To-0 Step. Then, in that step, #i(0) ≥ 2t+1 and i sets bi = 0. Since #i(0) ≥ 2t+1, at least t+1 honest players send 0 at the start of the step. Thus, #j(0) ≥ t + 1 for all other honest player j.
For each such player j two mutually exclusive cases may occur : (1) #j (0) ≥ 2t + 1 and (2) t + 1 ≤ #j(0) < 2t + 1. Accordingly, j sets bj = 0 in substep 1.1 in the first case, and in substep 1.3 in the second. Thus Agreement holds on 0 at the end the Coin-Fixed-To-0 Step.
A symmetric argument shows that Agreement holds on 1 at the end of a Coin-Forced-To-1 Step
there are n ≥ 3t + 1 players and t malicious players, the following 3 properties hold. 0. All honest players halt with probability 1.
Before proving Property 0, let us note that in BBA⋆ agreement is reached with probability 1. (This trivially follows from the fact that, as already proven, if the players were not in agreement at the start of the main loop of BBA⋆, then they will be in agreement by the end of the loop with probability at least 1/3.)
in which a honest player halts.
Let us now prove our theorem. That is, let us prove that, in every execution of BBA⋆, in which
To prove Property 0, assume first that agreement is reached on 0. Consider the first Coin-Fixed- To-0 Step at the start of which the players are in agreement on 0. Such a step must exists, because of property B. Then, at the start of the step, all honest players send 0, including those who have already halted, because when they did halt they sendd 0∗, thereby virtually propagating 0 at every subsequent step. Accordingly, for all honest players j who have not yet halted, in substep 1.1 #j (0) ≥ 2t + 1 and j halts.
1. outi = outj for all honest players i and j.
Property 1 holds because, by Property 0, all honest players halt, and whenever they do, by
To prove Property 2, assume first that the initial bit of all honest players is 0. Then, in Substep 1.1 of the very first Coin-Fixed-To-0 step, #i(0) ≥ 2t + 1 for each honest player
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com