Introduction
Byzantine Agreement is a fundamental problem in distributed computing, where a set of parties must agree on a single value even in the presence of some malicious parties. In its simplest form, we are given n n n parties, of which at most t t t can be byzantine. Without any kind of setup, this problem can only be solved if t < n / 3 t < n/3 t < n /3 [25 ] . However, if we assume the presence of a public key infrastructure (PKI), and more specifically that parties can sign messages, then we can solve the problem with t < n / 2 t < n/2 t < n /2 .
Another important aspect of the problem is the complexity of the protocol. In 1982, Dolev and Reischuk [14 ] gave a quadratic lower bound for communication complexity. In the authenticated setting, this lower bound was only somewhat recently matched by Momose and Ren [24 ] . However, when considering optimal resiliency t < n / 2 t < n/2 t < n /2 , their protocol relies on threshold signatures [5 ] , which are a stronger cryptographic primitive, allowing parties, in certain cases, to compress n n n signatures into one. Even though threshold signatures are used in practice, they have multiple drawbacks:
Threshold signatures require their keys to be correlated. A consequence is that a trusted dealer setup is needed. This is a strong assumption and requiring a trusted third party, even if only for the setup, for a decentralized protocol is not ideal. Another possible approach is to use a distributed key generation (DKG) protocol, but this is a complex protocol in itself.
Looking in the future, most common signature and threshold signature primitives are not quantum-safe. While regular signatures quantum-safe alternatives exist and have already been thoroughly studied [3 , 15 ] , quantum-safe threshold signatures [11 , 19 ] are less mature and have been less studied.
In general, it is interesting to known the best we can do with the least amount of cryptographic assumptions.
For these reasons, we consider the problem of solving Byzantine Agreement with optimal resiliency t < n / 2 t < n/2 t < n /2 with only regular signatures. To the best of our knowledge, all existing protocols for this setting have cubic complexity. In this work, we show that this is not a requirement and give the following result:
Theorem 1. There exists a deterministic byzantine agreement protocol with round complexity R B A ( n ) = O ( n ) R_{\mathrm{BA}}(n) = O(n) R BA ( n ) = O ( n ) and bit complexity B B A ( n ) = O ( κ ( 13 − 1 ) / 2 n ( 13 + 1 ) / 2 ) ≈ O ( κ 1.303 n 2.303 ) B_{\mathrm{BA}}(n) = O(\kappa^{(\sqrt{13}-1)/2}n^{(\sqrt{13}+1)/2}) \approx O(\kappa^{1.303}n^{2.303}) B BA ( n ) = O ( κ ( 13 − 1 ) /2 n ( 13 + 1 ) /2 ) ≈ O ( κ 1.303 n 2.303 ) .
Our work builds on the framework laid by Momose and Ren [24 ] , and make use of numerous new techniques, including more refined recursive protocols, improved uses of dispersers and fault-tolerant expander graphs, as well as fair cake cutting theory to achieve a subcubic complexity.
AI Disclosure: ChatGPT-6 Astra was used to improve and refine ideas in § 9 and § 11.1 . ChatGPT-6 Astra was also used to provide an initial draft, which the authors based their proof of Theorems 9 and 10. Apart of the uses mentioned above, LLMs were only used for grammar and spelling checks.
Related work
Deterministic synchronous protocols In the deterministic synchronous setting, the Dolev-Reischuk [14 ] lower bound shows that a quadratic amount of communication is necessary to solve byzantine agreement. Dolev and Strong [13 ] also show that t + 1 t+1 t + 1 rounds are necessary to solve deterministic byzantine agreement. In the unauthenticated setting, Berman, Garay and Perry [2 ] were the first to give a protocol with optimal resiliency t < n / 3 t < n/3 t < n /3 and optimal bit complexity O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) . It took until 2020 for Momose and Ren [24 ] to match this result in the unauthenticated setting. More precisely, they give a protocol with optimal resiliency t < n / 2 t < n/2 t < n /2 and quadratic bit complexity O ( κ n 2 ) \mathcal{O}(\kappa n^2) O ( κ n 2 ) using threshold signatures. When considering only regular signatures, they provide a protocol with resiliency t < n / ( 2 + ε ) t < n/(2 + \varepsilon) t < n / ( 2 + ε ) and bit complexity O ( κ ε − 1 n 2 ) \mathcal{O}(\kappa\varepsilon^{-1}n^2) O ( κ ε − 1 n 2 ) , which results in a cubic complexity for t < n / 2 t < n/2 t < n /2 .
Randomized protocols We note that all the previous lower bounds only apply to deterministic algorithms. In the randomized settings, more efficient protocols exist, concerning both round and bit complexity [18 ] . In particular, even in the much weaker asynchronous setting, when properties are only required to hold with high probability, byzantine agreement can be solved with expected near-linear complexity [4 , 9 ] .
Bypassing the lower bound There have been multiple attempts to bypass the deterministic lower bounds by using additional assumptions. Some of them rely on using adaptive algorithms which depend on the actual number of byzantine parties [6 , 10 ] . Others rely on amortizing the cost of byzantine agreement over multiple instances [7 , 16 ] . However, all approaches with resiliency t ≥ n / 3 t \ge n/3 t ≥ n /3 rely on threshold signatures. A notable exception is [16 ] which can be used to solve Θ ( n ) \Theta(n) Θ ( n ) concurrent instances of byzantine agreement with an amortized near-linear cost per instance while only using regular signatures. However, this is only achieved with resiliency t < n / ( 2 + ε ) t < n/(2 + \varepsilon) t < n / ( 2 + ε ) .
Overview
Our main contribution is a new weak agreement protocol using plain PKI with subcubic message complexity. This protocol consists of 2 main parts:
Proof Gathering: In the first part, parties exchange signed messages between themselves to get a proof that either 0 or 1 can be voted. We note that because of the lack of threshold signatures, a proof must contains at least t + 1 t + 1 t + 1 signatures so that byzantine parties cannot forge it. In our protocol it is the case: a proof is made of exactly t + 1 t + 1 t + 1 threshold signatures and thus has size Θ ( κ n ) \Theta(\kappa n) Θ ( κn ) . At the end of this part, we require that at least n / 10 n/10 n /10 honest parties have a proof for either 0 or 1. Additionally, if every honest party has the same input, then every honest party will get a proof for this input by the end of the proof gathering.
Validated Dispersion: From the first part, at least n / 10 n/10 n /10 honest parties have a proof. Our goal in this part is to make every honest party hold the same proof, i.e that there is a specific p r o o f v proof_v p r oo f v with v ∈ { 0 , 1 } v \in\{0,1\} v ∈ { 0 , 1 } such that every honest party has received p r o o f v proof_v p r oo f v by the end of this part.
After running consecutively these two parts, if a party has a proof for both 0 and 1, it will decide ⊥ \bot ⊥ . Otherwise, it will decide the value matching the proof it received (validated dispersion ensures at least one proof will be received). Although these two sections sound simple to explain, obtaining a subcubic protocol for both of them is the main difficulty of this paper and requires multiple complex ideas. An overview is given below:
Proof construction
The goal of proof gathering is that, by the end of it, at least n / 10 n/10 n /10 honest parties have a proof showing that either 0 or 1 can be decided. We first give an initial idea for the proof. A proof for v ∈ { 0 , 1 } v \in\{0,1\} v ∈ { 0 , 1 } allows a party to confirm it can decide v v v without any additional communication. In particular, if all honest parties have input v v v , a proof for 1 − v 1-v 1 − v cannot exist. A common construction for such a proof is to have every party sign and send its input. If a party gets t + 1 t+1 t + 1 distinct signatures for v ∈ { 0 , 1 } v \in\{0,1\} v ∈ { 0 , 1 } , it shows that at least one honest party had input v v v and thus that this value can be decided.
Using threshold signatures, such a proof can be encoded using O ( κ ) \mathcal{O}(\kappa) O ( κ ) bits. Here, because only plain signatures are available, such a proof will require ( t + 1 ) κ = O ( κ n ) (t+1)\kappa= \mathcal{O}(\kappa n) ( t + 1 ) κ = O ( κn ) bits. As such, a protocol should be careful when sending this proof to avoid having a cubic complexity. We present the different ideas used to achieve proof gathering with O ~ ( κ n 2 ) \widetilde{\mathcal{O}}(\kappa n^2) O ( κ n 2 ) bit complexity and O ( log n ) \mathcal{O}(\log n) O ( log n ) rounds complexity:
I know that I can’t know: As said before, we consider a first round where every party votes for its input and sends its (signed) vote to every other party. Given a party v v v , this can results in two outcomes for v v v :
v v v gets enough votes for 0 or 1 to get a proof for either 0 or 1
v v v is not able to get a proof for either 0 or 1. However, in this case, we make the observation that v v v still gained information from this step: it learned that all honest parties don’t hold the same value (otherwise it would have received n − t ≥ t + 1 n-t \ge t+1 n − t ≥ t + 1 votes for this value), and therefore both 0 and 1 are ”fine” to decide. To symbolize this, it sets its input to ⊥ \perp ⊥ . A downside of this approach is that v v v has no way to prove this observation to other parties. But we show that this simple remark is powerful enough to always get a proof afterward. We note that this approach was already used to obtain optimal adaptive byzantine agreement protocol using threshold signatures [10 , 17 ] .
Let n b ⊥ nb_{\perp} n b ⊥ be the number of honest parties which set their input to ⊥ \perp ⊥ (they know that both values are fine). We remark that if n b ⊥ ≤ 4 n / 10 nb_{\perp} \le4n/10 n b ⊥ ≤ 4 n /10 , then at least n − t − n b ⊥ ≥ n / 10 n-t-nb_{\perp} \ge n/10 n − t − n b ⊥ ≥ n /10 honest parties have a proof and therefore this step is already done.
In the case where n b ⊥ > 4 n / 10 nb_{\perp} > 4n/10 n b ⊥ > 4 n /10 , we perform a second round of input (which can now be 0, 1 or ⊥ \perp ⊥ ) signing and sending. We now observe that byzantine parties can only behave in two different ways.
If byzantine parties behave as honest: We consider the first case, where multiple byzantine will send their vote to an honest party, as a way to appear as honest from this party’s point of view. More specifically, we consider the case when any honest party receives at least 7 n / 10 7n/10 7 n /10 votes. In this case, we use a disperser to disperse the votes received. Every vote is forwarded to a constant (different for each vote) number of parties. This ensures that any set of 4 n / 10 4n/10 4 n /10 honest parties holds enough information together to produce a proof. Afterwards, we give and use the following fault-tolerant expander, which we believe to be of independent interest:
Theorem 2. For any α ∈ ] 0 , 1 [ \alpha\in]0,1[ α ∈ ] 0 , 1 [ , β > 1 \beta> 1 β > 1 , there exists D > 0 D > 0 D > 0 such that for any n > 0 n > 0 n > 0 , there exists an explicit graph G = ( V , E ) G = (V,E) G = ( V , E ) on n n n vertices of bounded degree D D D . Additionally, for any C ⊂ V C \subset V C ⊂ V such that ∣ C ∣ ≤ α ⋅ n |C| \le\alpha\cdot n ∣ C ∣ ≤ α ⋅ n , there exists S ⊆ V S \subseteq V S ⊆ V such that S ∩ C = ∅ S \cap C = \emptyset S ∩ C = ∅ , ∣ S ∣ ≥ n − β ⋅ ∣ C ∣ |S| \ge n - \beta\cdot|C| ∣ S ∣ ≥ n − β ⋅ ∣ C ∣ , and the induced subgraph G [ S ] G[S] G [ S ] is connected and has diameter O ( log n ) \mathcal{O}(\log n) O ( log n ) .
We note that this is a generalization and stronger version of [26 ] ’s result, which had fixed α = 1 / 72 \alpha= 1/72 α = 1/72 and β = 6 \beta= 6 β = 6 . Using this graph, we ensure that a subset of 4 n / 10 4n/10 4 n /10 honest parties will be able to communicate and all get a proof in O ( log n ) O(\log n) O ( log n ) rounds.
If byzantine parties behave as malicious: If the previous case is not reached, it implies that all honest parties received less than 7 n / 10 7n/10 7 n /10 votes and thus each honest party can identify at least 3 n / 10 3n/10 3 n /10 byzantine parties. We note that in this case, votes only may not be enough to get a proof. Therefore, we combine votes with our next ”trick”: accusations. An honest party can only accuse another party if it is byzantine. Thus, given a signed accusation from p i p_i p i to p j p_j p j , we know that either p i p_i p i or p j p_j p j is byzantine. This approach is inspired by the work done for repeated agreement [7 ] and relies on the insight formalized by [21 ] : instead of trying to determine whether p i p_i p i or p j p_j p j is byzantine, we can just discard the two parties.
This is implemented by adding accusations into a proof. For example, with n = 5 n = 5 n = 5 and t = 2 t = 2 t = 2 , assume the proof consists of: { vote p 1 ( 0 ) , vote p 2 ( ⊥ ) , accuse ( p 3 , p 4 ) } \{\operatorname{vote}_{p_1}(0), \operatorname{vote}_{p_2}(\perp), \operatorname{accuse}(p_3,p_4)\} { vote p 1 ( 0 ) , vote p 2 ( ⊥ ) , accuse ( p 3 , p 4 )} , we know that either p 3 p_3 p 3 or p 4 p_4 p 4 is byzantine, so at most one party among p 1 p_1 p 1 and p 2 p_2 p 2 is byzantine and thus 0 is a valid value. We note that for this to work, votes and accusations must be disjoint, and in particular, accusations must form a matching.
From accusations to fair cake-cutting: In this setting, each honest party wants to get ”rid of” up to 3 n / 10 3n/10 3 n /10 non-⊥ \perp ⊥ votes, and each honest party can accuse at least 3 n / 10 3n/10 3 n /10 byzantine parties. We view this in another way: consider the set of n n n parties to be a cake. Each party knows at least 3 n / 10 3n/10 3 n /10 byzantine parties which we identify as delicious slices. The goal becomes for a party to split the cake such that each relevant party is given a range which contains what it considers to be a delicious slice: this is fair cake-cutting theory. We adapt an existing algorithm to our setting and show that such an assignment can always be obtained by asking each party to cut a range of the cake into 2 equal parts ⌈ log n ⌉ \lceil\log n\rceil ⌈ log n ⌉ times. This approach has bit complexity O ( n 2 log 2 n ) O(n^2\log^2 n) O ( n 2 log 2 n ) and round complexity O ( log n ) O(\log n) O ( log n ) .
Validated dispersal
Using proof construction, we can guarantee that at least n / 10 n/10 n /10 honest parties hold a proof (possibly not for the same value). Each party running the proof dispersal algorithm will get a set of proofs in return. The main property of proof dispersal is that there exists a proof which is in every set returned by an honest party. This implies that every party will either get a proof for 0 or every party will get a proof for 1. Because a proof for v v v can only exist if v v v satisfies weak validity (i.e if all honest party don’t have input 1 − v 1-v 1 − v ), we show that deciding v v v if a party only receives proofs for v v v or otherwise deciding ⊥ \perp ⊥ satisfies weak agreement.
Validated dispersal in its definition does not consider proofs, it consider any L L L -bit input which satisfies some external validity predicate (where in our case, the validity predicate is that the value is a valid proof). We note that a really simple implementation of validated dispersal can be to have every party send its input (if it has one) to every other party, then return the set of inputs received. This works and can be done in one round, however, it has cubic complexity.
Divide-And-Conquer: The approach we took to improve the complexity in this paper is based on a divide-and-conquer approach (and later recursive calls). We divide the n n n parties into m : = m ( n ) m := m(n) m := m ( n ) groups of similar size (where m m m is decided later) and make two key remarks. The first remark is that by sending messages using a disperser pattern, we can make it so at most n / ( 10 m ) n/(10m) n / ( 10 m ) honest parties do not have an input, with a bit cost of O ( n 2 m ) O(n^2m) O ( n 2 m ) . The second insight is that if one of the groups has a byzantine minority (which we are guaranteed at least one has), and all honest parties in this group agree on the same value, then, using standard erasure coding techniques, all parties can learn this value using only O ( n 2 ) O(n^2) O ( n 2 ) communication. Summing this over all m m m groups, we get the same O ( n 2 m ) O(n^2m) O ( n 2 m ) bit cost.
Validated Agreement: Using the previous idea, we can effectively reduce Validated dispersal to m m m parallel calls to agreement on a valid value within a group of smaller size n / m n/m n / m . We note that this problem is not exactly regular Validated Byzantine Agreement, as some honest parties may not have an input. We call this problem Partial Validated Agreement. Nevertheless, we show that Partial Validated Agreement can be implemented using O ( log n ) O(\log n) O ( log n ) calls to regular Validated Agreement.
Our setting is now Validated Byzantine Agreement with a byzantine minority. An easy way to solve this would be to have every party send its input using Byzantine Broadcast (for example the Dolev-Strong protocol). Although this simple approach would be enough to achieve a subcubic complexity for the overall protocol, there exists better approaches.
A first improvement would be to implement Byzantine Broadcast using our own Byzantine Agreement protocol, effectively making our protocol recursive. This is more efficient, but requires n n n recursive calls in total and also has a high bit-complexity due to multiple inputs sharings.
Dynamic Programming approach When considering the previous Validated Agreement running with n n n parties and input size L L L , it requires O ( κ n ) O(\kappa n) O ( κn ) recursive binary agreement calls and its dependency on L L L is O ( n 2 L ) O(n^2L) O ( n 2 L ) . To reduce the dependency on L L L to O ( n L ) O(nL) O ( n L ) , we take a dynamic programming approach: for a set S S S of parties, we keep track of a tuple ( d , H ) (d, H) ( d , H ) where d d d is the Merkel root of a valid value and H H H is a set of parties that know the value associated with H H H . One key invariant we keep is that S ∖ H S \setminus H S ∖ H has a byzantine majority (i.e at least half of its parties are byzantine). We show how to merge two disjoint sets S S S and S ′ S' S ′ where we have a tuple satisfying these properties to obtain a new tuple for S ∪ S ′ S \cup S' S ∪ S ′ using only ∣ S ′ ∣ |S'| ∣ S ′ ∣ byzantine agreement calls with an additional O ( L ∣ S ′ ∣ ) O(L|S'|) O ( L ∣ S ′ ∣ ) bit complexity. When merging sets in the correct order, this allows the protocol to only have an O ( n L ) O(nL) O ( n L ) dependency on L L L .
Batching Our dynamic programming approach relies on running multiple independent byzantine broadcast procedures. Each broadcast requires one recursive call to our byzantine agreement protocol, which is expensive. To work around this issue, we show how to use batching to improve the overall bit complexity. Let b : = b ( n ) b := b(n) b := b ( n ) , we consider b b b independent instances of byzantine broadcast from a set of broadcasters S S S . We rely on a committee-based broadcast protocol, based on the Dolev-Strong protocol, which is more efficient, but only guarantees agreement if at least one party in the committee is honest. Using S S S as the committee, each party tries to broadcast its value using the committee-based protocol. Afterwards, a single multi-valued byzantine protocol (implemented on top of our binary BA protocol) is run to check the consistency of all b b b instances at once. This decreases the number of recursive calls needed from O ( κ n ) O(\kappa n) O ( κn ) to O ( κ n / b ) O(\kappa n/b) O ( κn / b ) .
Parallel execution A point we did not mention up to now is round complexity. Byzantine Agreement requires Ω ( n ) \Omega(n) Ω ( n ) rounds and our goal is for our algorithm to be optimal in this regard. When implementing the ideas presented above naively while optimizing m m m and b b b to minimize the bit complexity, the resulting algorithm would end up with a super-linear round complexity. To solve this, we make a more efficient use of the batching approach above, in particular by batching byzantine broadcasts from multiple independent merges together. This, together with running independent subprotocols in parallel whenever possible, allows the final round complexity to be linear.
Overall Complexity As said before, our algorithm is recursive: it recursively calls itself on smaller groups. When computing the bit complexity, we show that the per-party bit complexity B B A ( n ) B_{BA}(n) B B A ( n ) , while optimizing the parameters m m m and n n n is:
B B A ( n ) = 2 B B A ( n / 2 ) + O ~ ( κ n ) + min 1 ≤ b ≤ n / m < n O ~ ( n m + κ n b 2 m + κ n b 2 m + κ n m b B B A ( n / m ) ) B_{BA}(n) = 2B_{BA}(n/2) + \widetilde{O}(\kappa n) + \min_{1 \le b \le n/m < n} \widetilde{O}\left(nm + \frac{\kappa n b^2}{m} + \frac{\kappa n}{b^2m} + \frac{\kappa n}{mb}B_{BA}(n/m)\right) B B A ( n ) = 2 B B A ( n /2 ) + O ( κn ) + 1 ≤ b ≤ n / m < n min O ( nm + m κn b 2 + b 2 m κn + mb κn B B A ( n / m ) )
We get the optimal value by choosing b = m = Θ ~ ( ( κ n ) ( 13 − 3 ) / 2 ) b=m=\widetilde{\Theta}\left((\kappa n)^{(\sqrt{13}-3)/2}\right) b = m = Θ ( ( κn ) ( 13 − 3 ) /2 ) which leads to the algorithm per-party bit complexity B B A ( n ) = O ~ ( n ( 13 − 1 ) / 2 ) B_{BA}(n)=\widetilde{O}\left(n^{(\sqrt{13}-1)/2}\right) B B A ( n ) = O ( n ( 13 − 1 ) /2 ) .
Regarding round complexity, the recurrence relation is:
R B A ( n ) = 2 R B A ( n / 2 ) + O ( log n ) + m 1 / 3 R B A ( n / m ) R_{BA}(n) = 2R_{BA}(n/2) + O(\log n) + m^{1/3}R_{BA}(n/m) R B A ( n ) = 2 R B A ( n /2 ) + O ( log n ) + m 1/3 R B A ( n / m )
For our optimal choice of m m m , the resulting round complexity is the expected optimal R B A ( n ) = O ( n ) R_{BA}(n)=O(n) R B A ( n ) = O ( n ) .
Preliminaries
We consider a set P \mathcal{P} P of n n n parties, out of which up to t t t can be byzantine. We focus on fully deterministic protocols. The network is fully connected and channels are authenticated: any party can send a message to any other party, and the receiver will know who the sender is.
Model: We consider a synchronous model, where parties communicate in rounds. In each round, parties can send messages to other parties, and all messages will be received by the beginning of the next round.
Hashes: We assume the existence of a cryptographic hash function that is collision-resistant: it is computationally infeasible to find two distinct inputs that hash to the same output. We assume that the output of the hash function is κ \kappa κ bits long. Because byzantine parties should not be able to brute force a hash, we assume that κ = Ω ( log n ) \kappa=\Omega(\log n) κ = Ω ( log n ) . Another assumption made in this work is that κ = polylog ( n ) \kappa=\operatorname{polylog}(n) κ = polylog ( n ) .
Signatures: Each party has a public-private key pair, where the public key is known to all parties, and can sign messages with its private key. We assume that signatures are unforgeable: it is computationally infeasible for a party to forge a signature of another party. The signature size is κ \kappa κ bits.
Erasure Coding: Erasure coding allows a message to be split into multiple shares, such that a subset of the shares can be used to reconstruct the original message. We use classical Reed-Solomon codes [27 ] :
Definition 1. An L L L -bit value can be split into m m m shares, such that any subset of m / 2 m/2 m /2 shares can be used to reconstruct the original value. Each share has size O ( L / m + log m ) O(L/m+\log m) O ( L / m + log m ) bits.
Cryptographic Accumulator/Merkel Tree: Our work relies on the use of cryptographic accumulators. Given a set S S S of m m m elements, a cryptographic accumulator returns an accumulator value h h h for S S S as well as a witness w s w_s w s for each element s ∈ S s \in S s ∈ S such that given the accumulator h h h , an element s s s and its witness w s w_s w s , a party can verify that s ∈ S s \in S s ∈ S without knowledge of S S S . When implemented using a Merkel Hash Tree [23 ] , the accumulator has size κ \kappa κ while each witness has size κ ⌈ log n ⌉ \kappa\lceil\log n \rceil κ ⌈ log n ⌉ .
We note that more efficient cryptographic accumulator implementations exist [12 ] , however they rely on stronger cryptographic primitives, and a more complex setup, which our work aims to avoid.
We always use erasure coding paired with cryptographic accumulators: When generating shares of a value, each share, along with its index, is considered as an element of a set, and the accumulator is computed on this set. This way, a party can verify that a share is valid using its witness.
Definitions
All the following protocols are assumed to be run on n n n parties, out of which at most t < n / 2 t < n/2 t < n /2 are byzantine.
Definition 2. A protocol where each party is given an input v i n v_{\mathrm{in}} v in and decides an output v o u t v_{\mathrm{out}} v out satisfies byzantine agreement if:
Termination: All honest parties decide
Validity: If all honest parties have the same input v v v , then only v v v can be decided
Agreement: If two honest parties decide respectively v v v and v ′ v' v ′ , then v = v ′ v = v' v = v ′ .
Even though we give (and use) protocols for byzantine agreement where the input is an L L L -bit value, the target of this paper is binary agreement, where v i n ∈ { 0 , 1 } v_{\mathrm{in}} \in\{0,1\} v in ∈ { 0 , 1 } .
Definition 3. A protocol where each party is given an input v i n ∈ { 0 , 1 } v_{\mathrm{in}} \in\{0,1\} v in ∈ { 0 , 1 } and decides an output v o u t ∈ { 0 , 1 , ⊥ } v_{\mathrm{out}} \in\{0,1,\bot\} v out ∈ { 0 , 1 , ⊥ } satisfies weak byzantine agreement if:
Termination: All honest parties decide
Validity: If all honest parties have the same input v v v , then only v v v can be decided
Weak Agreement: If two honest parties decide respectively v ≠ ⊥ v \ne\bot v = ⊥ and v ′ v' v ′ , then v ′ = v v' = v v ′ = v or v ′ = ⊥ v' = \bot v ′ = ⊥ .
Definition 4. We consider an external validity function V A L \mathrm{VAL} VAL and a protocol where parties decide an output v o u t v_{\mathrm{out}} v out with the following properties:
Termination: All honest parties decide
Validity: If an honest party decides v v v , then v v v satisfies the validity function
Agreement: If two honest parties decide respectively v v v and v ′ v' v ′ , then v = v ′ v = v' v = v ′ .
If every honest party is given an input v i n v_{\mathrm{in}} v in satisfying the validity function, we say that the protocol satisfies validated agreement.
If at least n / 10 n/10 n /10 honest parties are given an input v i n v_{\mathrm{in}} v in satisfying the validity function, we say that the protocol satisfies partial validated agreement.
Byzantine minority/majority: When considering a set of Q Q Q parties, out of which k k k are byzantine, we say that Q Q Q has a byzantine minority if k < ∣ Q ∣ / 2 k < |Q|/2 k < ∣ Q ∣/2 , and a byzantine majority otherwise (i.e when k ≥ ∣ Q ∣ / 2 k \ge|Q|/2 k ≥ ∣ Q ∣/2 ).
Proofs: Our protocols rely on the creation and dissemination of ”proofs ”, which allows parties to verify whether or not they can decide a given value.
Definition 5. Assuming all honest parties have an input in { 0 , 1 } \{0,1\} { 0 , 1 } , it is computationally infeasible for an adversary to compute a proof for v ∈ { 0 , 1 } v \in\{0,1\} v ∈ { 0 , 1 } if all honest parties have input 1 − v 1-v 1 − v .
Byzantine-robust protocols: Our protocols are designed to be able to solve byzantine agreement with resiliency t < n / 2 t < n/2 t < n /2 , which is optimal in regard to this problem, even with a trusted setup (if all honest parties have input 0 and all byzantine parties act as honest with input 1, BA cannot be solved if t ≥ n / 2 t \ge n/2 t ≥ n /2 ). However, one of the key points of our protocol is that we partition the n n n parties into smaller groups then run recursively our algorithm on them. This approach guarantees that at least one of the groups has an honest majority, but this may not be the case of the remaining ones. Although we do not expect anything from the output of protocols run in a byzantine majority, messages sent in this context by honest parties still count toward to the total bit complexity. To prevent any issue in this regard, we define the term of byzantine-robust protocols:
Definition 6. Given an upper bound on the bit complexity per party, a protocol is byzantine-robust if this upper bound is satisfied regardless of the messages received. In particular, this applies even if all other parties are byzantine.
A byzantine-robust protocol must be balanced, as such it makes more sense to look at the per-party bit complexity (i.e the number of bits sent by a party) rather than the total bit complexity. Given a protocol Π \Pi Π , we denote by B Π ( n ) B_{\Pi}(n) B Π ( n ) the per-party bit complexity of Π \Pi Π when run on n n n parties. We also denote by R Π ( n ) R_{\Pi}(n) R Π ( n ) the round complexity of Π \Pi Π when run on n n n parties.
Because all of our primitives and approaches have a bit cost increasing with the number of parties, we make simplifying assumptions that all our protocols complexities are non-decreasing with the number of parties. This allows us to simplify the analysis of our protocols.
Graphs: Given a (possibly directed) graph G = ( V , E ) G = (V,E) G = ( V , E ) , the neighborhood of a vertex u ∈ V u \in V u ∈ V is N G ( u ) = { v ∈ V , u → v ∈ E } N_G(u) = \{v \in V, u \to v \in E\} N G ( u ) = { v ∈ V , u → v ∈ E } . Given a set S ⊆ V S \subseteq V S ⊆ V , we denote N G ( S ) = ⋃ u ∈ S N G ( u ) N_G(S) = \bigcup_{u \in S} N_G(u) N G ( S ) = ⋃ u ∈ S N G ( u ) . Our work makes multiple uses of dispersers, which are defined below:
Definition 7. A graph G = ( V , E ) G = (V,E) G = ( V , E ) is a ( a , b ) (a,b) ( a , b ) -disperser if for any subset S ⊆ V S \subseteq V S ⊆ V of size ∣ S ∣ ≥ a |S| \ge a ∣ S ∣ ≥ a , we have ∣ N G ( S ) ∣ ≥ b |N_G(S)| \ge b ∣ N G ( S ) ∣ ≥ b .
A bipartite graph G = ( L ∪ R , E ) G = (L \cup R,E) G = ( L ∪ R , E ) is a bipartite ( a , b ) (a,b) ( a , b ) -disperser if for any subset S ⊆ L S \subseteq L S ⊆ L of size ∣ S ∣ ≥ a |S| \ge a ∣ S ∣ ≥ a , we have ∣ N G ( S ) ∣ ≥ b |N_G(S)| \ge b ∣ N G ( S ) ∣ ≥ b .
A last point to remark is that many of our protocols are designed to run in parallel, but there is not enough information in the messages to know which instance to target. Moreover, our protocols, as they are written, are weak to replay attacks. We keep them this way for simplicity, but we show in Section 13 how to add tags to messages and signatures to fix these issues, while keeping the same complexity.
Weak byzantine Agreement
Our Byzantine Agreement protocol uses the framework introduced by Momose and Ren [24 ] , who show how to implement Byzantine Agreement on top of Weak Agreement. Therefore, our focus and main contribution is implementing a weak agreement protocol using plain PKI. For completeness, protocols showing the reduction from byzantine agreement to weak agreement are provided in Sections B.1 and B.2. Our protocol relies on two subprotocols: proof creation which makes sure at least n / 10 n/10 n /10 honest parties are able to get ahold of a proof and Validated dispersion which makes sure there exists one proof received by every party. We provide formal definitions of these two subprotocols:
Definition 8. In a proof creation protocol , each party has an input v i n ∈ { 0 , 1 } v_{in} \in\{0,1\} v in ∈ { 0 , 1 } and outputs a message m m m such that the following properties are satisfied:
Termination: All honest parties output.
Certifiability: If an honest party outputs a message m ≠ ⊥ m \ne\perp m = ⊥ , then m m m is a proof for either 0 or 1, relevant to the inputs.
Partial decision: At least n / 10 n/10 n /10 honest parties do not output ⊥ \perp ⊥ .
Definition 9. In a validated dispersal protocol , given some external validity function, each party is given an input which is either ⊥ \perp ⊥ or an L L L -bit message satisfying the validity function. Additionally, at least n / 10 n/10 n /10 honest parties do not have ⊥ \perp ⊥ as input. Each party outputs a set S S S of messages such that:
Termination: All honest parties output.
Validity: All messages output by an honest party satisfy the validity function.
Coverage: The exists a valid L L L -bit message m m m such that m m m is contained in the set of every honest party’s output.
Assuming access to these two subprotocols, we provide a simple implementation of weak agreement. The validity function used for validated dispersal is to check whether the message is a valid proof for 0 or 1. We properly define what a valid proof is in TODO:
WeakBA
Weak Byzantine Agreement protocol for a party p with input v_in
proof ← ProofCreation(v_in)
proofs ← ValidatedDispersal(proof)
if proofs only contains proofs for a single value v ∈ {0, 1} then
Decide v
else
Decide ⊥
end if
Theorem 3. WeakBA is a weak agreement protocol .
Proof. We note that ProofCreation ensures that at least n / 10 n/10 n /10 honest parties get a valid proof, and the remaining ones output a ⊥ \perp ⊥ . Therefore, at least n / 10 n/10 n /10 parties start the validated dispersal
protocol with a valid input while the remaining ones have input ⊥ \bot ⊥ , so the input conditions for the validated dispersal algorithm are respected.
Termination follows from ProofCreation’s and ValidatedDispersal’s termination.
If all honest parties have the same input b b b , then according to the definition of a proof (Definition 5), a proof for 1 − b 1-b 1 − b cannot exist, so any proof obtained can only be for b b b . Because validated dispersal’s coverage and validity ensure every party gets at least a proof, it must be for b b b . Hence the protocol will decide b b b for every honest party, so validity is satisfied.
Using validated dispersal’s coverage, there exists a proof for a value b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } that every honest party receives. We note this implies that parties can only decide b b b or ⊥ \bot ⊥ , so weak agreement is satisfied.
When considering complexity, we abbreviate WeakBA to WBA, ProofCreation to PC and ValidatedDispersal to VD. Additionally, B V D ( n , L ) B_{\mathrm{VD}}(n,L) B VD ( n , L ) is the per-party bit complexity to disperse an L L L -bit message among n n n parties using validated dispersal.
Observation 1. Assuming the underlying protocols are byzantine-robust, WeakBA is byzantine-robust. Additionally, B W B A ( n ) = B P C ( n ) + B V D ( n , κ n ) B_{\mathrm{WBA}}(n) = B_{\mathrm{PC}}(n) + B_{\mathrm{VD}}(n,\kappa n) B WBA ( n ) = B PC ( n ) + B VD ( n , κn ) and R W B A ( n ) = R P C ( n ) + R V D ( n ) R_{\mathrm{WBA}}(n) = R_{\mathrm{PC}}(n) + R_{\mathrm{VD}}(n) R WBA ( n ) = R PC ( n ) + R VD ( n ) .
Proof Creation
We now explain the proof creation protocol. The protocol starts, like many weak byzantine protocols, with each party sending its (signed) input to every other party. It differs greatly afterwards:
If a party does not get t + 1 t+1 t + 1 votes for 0 or t + 1 t+1 t + 1 votes for 1, it knows that not all honest parties have the same input. Thus, it can then support votes for both 0 and 1. We symbolize this by setting its input to ⊥ \bot ⊥ . As stated in the overview, this idea was already used by [10 ] for adaptive algorithms. But their protocol is leader-based and uses threshold signatures, allowing it to be simpler compared to the approach used here.
Another key idea is to always be able to extract information from byzantine parties: if byzantine parties send votes, honest parties will be able to use them and make signatures. Otherwise, honest parties will be able to identify many byzantine parties, accuse them and use these accusations to form a proof.
Proofs
Our construction relies on proof, which allows a party to know that a value satisfies validity without any additional communication. Usually, a proof is a single ( t + 1 ) (t+1) ( t + 1 ) -threshold signature. Because we do not have access to threshold signatures, our proofs require more insight. More specifically, we rely on votes, where a party p i p_i p i signs a message Vote( p , v ) (p,v) ( p , v ) for a value v ∈ { 0 , 1 , ⊥ } v \in\{0,1,\bot\} v ∈ { 0 , 1 , ⊥ } , and accusations, where a party p i p_i p i signs a message Accuse( p i , p j ) (p_i,p_j) ( p i , p j ) to accuse a party p j p_j p j . We consider the following properties:
Voting accuracy: An honest party can only vote for v ∈ { 0 , 1 } v \in\{0,1\} v ∈ { 0 , 1 } if its input is v v v . Moreover, it can only vote for ⊥ \bot ⊥ if it knows both 0 and 1 are valid (i.e not all honest parties have the same input).
Accusation accuracy: If an honest party p i p_i p i accuses p j p_j p j , then p j p_j p j is byzantine.
Using votes and accusation, we can define what is a proof in the context of our algorithm:
Definition 10. A message m m m is a proof for b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } if it is made of k k k votes and q q q accusations such that:
All votes are for b b b or ⊥ \perp ⊥
All parties voting and parties contained in each accusation (both the accuser and accused) are entirely disjoint
k ≥ 1 k \ge1 k ≥ 1 and k + q = t + 1 k + q = t + 1 k + q = t + 1 , i.e there is at least one vote and in total t + 1 t + 1 t + 1 votes or accusations.
We note that using this definition, a proof has size Θ ( κ ( t + 1 ) ) = Θ ( κ n ) \Theta(\kappa(t + 1)) = \Theta(\kappa n) Θ ( κ ( t + 1 )) = Θ ( κn ) .
Lemma 1. Assuming votes and accusations are accurate, a proof, as defined above in Definition 10, satisfies the definition given in Definition 5.
Proof. Consider a proof for b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } . We want to show that b b b satisfies validity. Using voting accuracy, it is enough to show that an honest party voted for b b b or ⊥ \perp ⊥ . The proof is made from k k k votes for b b b or ⊥ \perp ⊥ and q q q accusations. Using accusation accuracy, each pair of accuser/accused contains at least one byzantine party. Because they are all disjoint, they are at least q q q byzantine parties among the 2 q 2q 2 q parties that are part of accusations. Therefore, there are at most t − q = k − 1 t-q = k-1 t − q = k − 1 byzantine parties remaining. Using disjointness again and the fact that k ≥ 1 k \ge1 k ≥ 1 , this means that there is at least one honest party among the k k k votes, which shows that b b b satisfies validity.
Overall protocol
Our protocol starts with two rounds of signing and sending your own vote to every party, then sharing votes received in the second round in a different way, as well as obtaining accusations if many byzantine parties were silent.
After the first round of sending votes, if an honest party does not receive t + 1 t+1 t + 1 votes for the same value, it sets its input to ⊥ \perp ⊥ , which is used for the second round of sending votes.
After the second round of voting, all votes received are preserved. Additionally, each party keeps track of other parties which did not send a vote in the previous round. It knows these are byzantine (as they did not follow the protocol) and thus can accuse them later on.
PROOFCREATION
Proof creation protocol for a party p with input v_in
Send signed VOTE(p, v_in) to everyone
if did not receive t + 1 votes for 0 or t + 1 votes for 1 then
v_in ← ⊥
end if
Send signed VOTE(p, v_in) to everyone
Let VOTES be the set of votes received in the second round
Let ACCUSERS be the set of parties which sent a vote for 0 or 1 to p in the second round
Let ACCUSED be the set of parties which did not send a vote to p in the second round
ACCUSATIONS ← GETACCUSATIONS(ACCUSERS, ACCUSED)
VOTES ← SPREADVOTES(VOTES)
if COMPUTEPROOF(0, VOTES, ACCUSATIONS) or COMPUTEPROOF(1, VOTES, ACCUSATIONS) returns a proof p then
Return p
else
Return ⊥
end if
In this whole section, let n b ⊥ nb_{\perp} n b ⊥ be the number of honest parties which changed their input to ⊥ \perp ⊥ , and therefore sent a signed input for ⊥ \perp ⊥ in the second round. We remark that if a party did not change its input to ⊥ \perp ⊥ , it implies it has already enough votes for a proof. Thus n − t − n b ⊥ ≥ n / 2 − n b ⊥ n-t-nb_{\perp} \ge n/2-nb_{\perp} n − t − n b ⊥ ≥ n /2 − n b ⊥ parties already have enough votes for a proof, hence the following observation:
Observation 2. If n b ⊥ ≤ 4 n / 10 nb_{\perp} \le4n/10 n b ⊥ ≤ 4 n /10 , then at least n / 10 n/10 n /10 honest parties will be able to get a proof.
As a consequence, the following protocols (getting accusations and vote spreading) only need to focus on the case where n b ⊥ > 4 n / 10 nb_{\perp} > 4n/10 n b ⊥ > 4 n /10 . We now have two different cases, depending on the behavior of byzantine parties:
If at least one honest parties receives many votes from byzantine parties (more specifically, if one honest party receives at least 7 n / 10 7n/10 7 n /10 votes), then the vote spreading procedure will ensure that 4 n / 10 4n/10 4 n /10 parties will be able to receive enough votes to form a proof.
Otherwise, it means every honest party is able to identify at least 3 n / 10 3n/10 3 n /10 byzantine parties. In this case, we remark that if an honest party manages to make n / 10 n/10 n /10 honest parties with non-⊥ \perp ⊥ votes accuse disjoint byzantine parties, then these accusations along with the ⊥ \perp ⊥ votes will be enough to form a proof. This is what the accusation procedure does.
Computing accusations
As stated above, computing accusations is only needed when n b ⊥ > 4 n / 10 nb_{\perp} > 4n/10 n b ⊥ > 4 n /10 and each honest party is able to identify at least 3 n / 10 3n/10 3 n /10 byzantine parties. As a consequence, we ignore parties claiming to know less than 3 n / 10 3n/10 3 n /10 byzantine parties or when a party needs too many accusations (to be more specific, more than 3 n / 10 3n/10 3 n /10 ). The protocol consists of a leader, asking queries to other parties acting as helpers. It has O ( n log 2 n ) O(n\log^{2} n) O ( n log 2 n ) bit complexity, O ( log n ) O(\log n) O ( log n ) round complexity and allows the leader to get its desired matching. We run it in parallel n n n times, with each party acting as the leader of its own instance.
Because we have a set of at most 3 n / 10 3n/10 3 n /10 entities, each interested in at least 3 n / 10 3n/10 3 n /10 parts of a common set of size n n n (the parties), we can represent this as a fair cake cutting problem: the cake is the set of parties and each accuser wants a piece of the cake which contains a party to accuse. We adapt the divide and conquer approach described by Even and Paz [20 ] to the distributed and online setting. By repeatedly asking helpers (accusers) to split a range of the cake (parties) into two equal parts, we can obtain a fair cake cutting with significantly less communication.
GetAccusations(Accusers, Accused)
Return a set of accusations for a party p
Send |Accused| to everyone
Let A be the parties in Accusers which accuse at least 3n/10 parties
M ← ∅
in parallel for i = 1, …, n do
if p = p_i and |A| ≤ 3n/10 then
M ← CakeLeader(A, 1, n), in parallel
end if
Call CakeHelper(p_i, Accused), in parallel
Return M
We now describe the behavior of a helper party. Given the set of byzantine parties B B B it knows, it can only answer two kinds of queries:
At most ⌈ log n ⌉ \lceil\log n\rceil ⌈ log n ⌉ split queries: given an interval of parties { p l , p l + 1 , … , p r } \{p_l,p_{l+1},\ldots,p_r\} { p l , p l + 1 , … , p r } , and a position i i i , it returns the index of the i i i -th party in B ∩ { p l , p l + 1 , … , p r } B \cap\{p_l,p_{l+1},\ldots,p_r\} B ∩ { p l , p l + 1 , … , p r } .
CakeHelper(p i p_i p i , B B B )
Help a party p i p_i p i get accusations by answering queries, for a party p p p
Upon Receiving ( A c c u s e , l , r ) (\mathit{Accuse}, l, r) ( Accuse , l , r ) from p i p_i p i
if there exists p j ∈ B ∩ { p l , p l + 1 , … , p r } p_j \in B \cap\{p_l,p_{l+1},\ldots,p_r\} p j ∈ B ∩ { p l , p l + 1 , … , p r } then
Send signed A c c u s a t i o n ( p , p j ) \mathit{Accusation}(p,p_j) Accusation ( p , p j ) to p i p_i p i
end if
Stay silent for the rest of the subprotocol
for 2 ⌈ log n ⌉ 2\lceil\log n\rceil 2 ⌈ log n ⌉ rounds do
Upon Receiving ( S p l i t , l , r , i ) (\mathit{Split}, l, r, i) ( Split , l , r , i ) from p i p_i p i
Q ← { p l , p l + 1 , … , p r } ∩ B Q \leftarrow\{p_l,p_{l+1},\ldots,p_r\} \cap B Q ← { p l , p l + 1 , … , p r } ∩ B
Let p j p_j p j be the i i i -th party in Q Q Q if it exists, otherwise j = 0 j=0 j = 0
Send j j j to p i p_i p i
Wait 2 rounds
end for
We can finally describe the protocol used by the leader. This protocol has input a set A A A of accusers and a range parametrized by two integers $1 \le l \le r \le n$. Let I = [ l , l + 1 , … , r ] I=[l,l+1,\ldots,r] I = [ l , l + 1 , … , r ] and h h h the number of honest parties in A A A . We show that this protocol returns a disjoint matching of size at least h h h between parties in A A A and parties in { p l , p l + 1 , … , p r } \{p_l,p_{l+1},\ldots,p_r\} { p l , p l + 1 , … , p r } . To do so, this algorithm divides I I I into two halves of the same size, then using helper queries, is able to partition A A A into these two segments and recurse on them.
CakeLeader(A A A , l, r$)
Return a set of accusations from A A A to { p l , … , p r } \{p_l,\ldots,p_r\} { p l , … , p r }
if ∣ A ∣ = 1 |A|=1 ∣ A ∣ = 1 then
Send ( A c c u s e , l , r ) (\mathit{Accuse},l,r) ( Accuse , l , r ) to the party in A A A
Wait two rounds and return the set of accusations received
else
Send ( S p l i t , l , m , ⌈ ∣ A ∣ / 2 ⌉ ) (\mathit{Split},l,m,\lceil|A|/2\rceil) ( Split , l , m , ⌈ ∣ A ∣/2 ⌉) to every party in A A A
Wait two rounds for answers ( a p ) p ∈ A (a_p)_{p\in A} ( a p ) p ∈ A (a p = 0 a_p=0 a p = 0 if p p p didn’t answer a positive number)
Let A l A_l A l be the ⌈ ∣ A ∣ / 2 ⌉ \lceil|A|/2\rceil ⌈ ∣ A ∣/2 ⌉ parties in A A A with lowest value ( a q ) (a_q) ( a q ) (breaking ties arbitrarily)
Let m = max p ∈ A l a p m=\max_{p\in A_l}a_p m = max p ∈ A l a p
in parallel do
M l ← C a k e L e a d e r ( A l , l , m ) M_l \leftarrow\mathit{CakeLeader}(A_l,l,m) M l ← CakeLeader ( A l , l , m )
M r ← C a k e L e a d e r ( A ∖ A l , m + 1 , r ) M_r \leftarrow\mathit{CakeLeader}(A\setminus A_l,m+1,r) M r ← CakeLeader ( A ∖ A l , m + 1 , r )
Return M l ∪ M r M_l\cup M_r M l ∪ M r
end if
The main reason this protocol achieves its goal is because it is able to preserve the following invariant:
Lemma 2. For a party p i p_i p i , let B i B_i B i be the set of parties it can accuse. Then, for any call to
CakeLeader with an honest leader and input A , l , r A,l,r A , l , r :
∀ p i ∈ A , p i is honest ⇒ ∣ B i ∩ { p l , p l + 1 , … , p r } ∣ ≥ ∣ A ∣ \forall p_i \in A,\ p_i\text{ is honest} \Rightarrow|B_i \cap\{p_l,p_{l+1},\ldots,p_r\}| \ge|A| ∀ p i ∈ A , p i is honest ⇒ ∣ B i ∩ { p l , p l + 1 , … , p r } ∣ ≥ ∣ A ∣
Proof. We first consider the first instance where GetAccusations calls CakeLeader. We remark that it is only called if the leader has at most 3 n / 10 3n/10 3 n /10 accusers who can accuse at least 3 n / 10 3n/10 3 n /10 parties. Additionally, it is called with l = 1 l=1 l = 1 and r = n r=n r = n which is the entire set of parties, so in this case:
∣ B i ∩ { p l , p l + 1 , … , p r } ∣ = ∣ B i ∣ ≥ 3 n / 10 ≥ ∣ A ∣ |B_i \cap\{p_l,p_{l+1},\ldots,p_r\}|=|B_i| \ge3n/10 \ge|A| ∣ B i ∩ { p l , p l + 1 , … , p r } ∣ = ∣ B i ∣ ≥ 3 n /10 ≥ ∣ A ∣
So the invariant holds.
Consider now a call to CakeLeader with input A , l , r A,l,r A , l , r , where the invariant already holds. We want to show that it is still the case in the recursive calls. Consider a party p i ∈ A p_i \in A p i ∈ A , which is honest. Using the invariant, ∣ B i ∩ { p l , p l + 1 , … , p r } ∣ ≥ ∣ A ∣ |B_i \cap\{p_l,p_{l+1},\ldots,p_r\}| \ge|A| ∣ B i ∩ { p l , p l + 1 , … , p r } ∣ ≥ ∣ A ∣ . The leader sends a query for the ⌈ ∣ A ∣ / 2 ⌉ \lceil|A|/2 \rceil ⌈ ∣ A ∣/2 ⌉ -th party in the previous set. Because ⌈ ∣ A ∣ / 2 ⌉ ≤ ∣ A ∣ \lceil|A|/2 \rceil\le|A| ⌈ ∣ A ∣/2 ⌉ ≤ ∣ A ∣ , p i p_i p i will answer with such a party. Let k k k be the index of this party. We therefore have:
∣ B i ∩ { p l , p l + 1 , … , p k } ∣ = ⌈ ∣ A ∣ / 2 ⌉ |B_i \cap\{p_l,p_{l+1},\ldots,p_k\}|=\lceil|A|/2 \rceil ∣ B i ∩ { p l , p l + 1 , … , p k } ∣ = ⌈ ∣ A ∣/2 ⌉
and
∣ B i ∩ { p k + 1 , p k + 2 , … , p r } ∣ ≥ ∣ A ∣ − ⌈ ∣ A ∣ / 2 ⌉ |B_i \cap\{p_{k+1},p_{k+2},\ldots,p_r\}| \ge|A|-\lceil|A|/2 \rceil ∣ B i ∩ { p k + 1 , p k + 2 , … , p r } ∣ ≥ ∣ A ∣ − ⌈ ∣ A ∣/2 ⌉
We now have two cases:
p i ∈ A l p_i \in A_l p i ∈ A l , then in this case m = max p ∈ A l a p ≥ a i = k m=\max_{p\in A_l}a_p \ge a_i=k m = max p ∈ A l a p ≥ a i = k , so the recursive call on p i p_i p i will be made on a set of size ⌈ ∣ A ∣ / 2 ⌉ \lceil|A|/2 \rceil ⌈ ∣ A ∣/2 ⌉ and range [ l , m ] [l,m] [ l , m ] , which contains [ l , k ] [l,k] [ l , k ] , for which p i p_i p i can accuse at least ⌈ ∣ A ∣ / 2 ⌉ \lceil|A|/2 \rceil ⌈ ∣ A ∣/2 ⌉ parties.
p i ∉ A l p_i \notin A_l p i ∈ / A l , then by minimality, m ≤ k m \le k m ≤ k , so the recursive call on p i p_i p i will be made on a set of size ∣ A ∣ − ⌈ ∣ A ∣ / 2 ⌉ |A|-\lceil|A|/2 \rceil ∣ A ∣ − ⌈ ∣ A ∣/2 ⌉ and range [ m + 1 , r ] [m+1,r] [ m + 1 , r ] , which contains [ k + 1 , r ] [k+1,r] [ k + 1 , r ] , for which p i p_i p i can accuse at least ∣ A ∣ − ⌈ ∣ A ∣ / 2 ⌉ |A|-\lceil|A|/2 \rceil ∣ A ∣ − ⌈ ∣ A ∣/2 ⌉ parties.
In both cases, p i p_i p i can accuse at least as many parties in the given range as the size of the new set A A A . As a consequence, by induction, the invariant is always satisfied.
Another key point is that accusations are accurate:
Lemma 3. Accuracy: All accusations returned by CakeLeader are accurate: an honest party will only accuse byzantine parties.
Proof. Accusations returned by MatchingLeader come from CakeHelper, which themselves come from the set A c c u s e d Accused A cc u se d of parties which did not send a vote in the second round of the ProofCreation protocol. Because any party following the protocol will send a vote in the second round, it implies that these parties are byzantine.
We also remark that accusations are signed by the accuser, as such a byzantine party cannot generate an accusation made from an honest party if it does not already have it.
Using this invariant and accusation accuracy, we can prove the main property of our matching protocols, which is that the accusations produced by honest parties form a disjoint matching.
Lemma 4. Consider an honest party, where GetAccusations calls CakeLeader with a set of accusers A c c Acc A cc . Let A c c h Acc_h A c c h be the honest parties in A c c Acc A cc , then the set of accusations returned by GetAccusations contains a disjoint matching of size ∣ A c c h ∣ |Acc_h| ∣ A c c h ∣ , where each edge is made from an accuser in A c c h Acc_h A c c h and an accused party being byzantine.
Proof. We first note that CakeLeader partitions accusers into two sets and recursively calls itself on these two sets. No accuser gets ”lost” between recursive calls and therefore every accuser will end up in exactly one case where ∣ A ∣ = 1 |A| = 1 ∣ A ∣ = 1 .
Let q ∈ A c c h q \in Acc_h q ∈ A c c h . Consider the call to CakeLeader with set A A A such that A = { q } A = \{q\} A = { q } . Let l l l , r r r be the range parameters of the protocol at that point. We remark that using the invariant, ∣ B ∩ { p l , … p r } ∣ ≥ ∣ A ∣ = 1 |B \cap\{p_l, \ldots p_r\}| \ge|A| = 1 ∣ B ∩ { p l , … p r } ∣ ≥ ∣ A ∣ = 1 . As such, q q q will be able to find a party to accuse in { p l , … p r } \{p_l, \ldots p_r\} { p l , … p r } , which won’t ask any other party for an accusation in this range. As a consequence, every honest party in A c c Acc A cc will send an accusation to the leader, they will all be distinct, and using accusation accuracy, they will all target byzantine parties. Finally, looking at these accusations, because the accusers are the parties in A h A_h A h and thus honest while all accused parties are all byzantine and distinct, all these accusations are fully disjoint.
Lemma 5. GetAccusations has per-party bit complexity O ( n 2 ( log 2 n + κ ) ) O(n^2(\log^2 n+\kappa)) O ( n 2 ( log 2 n + κ )) and round complexity O ( log n ) O(\log n) O ( log n ) . Moreover, it is byzantine-robust .
Proof. MatchingLeader cuts into half the number of accusers at each recursion level, starting with at most 3 n / 10 3n/10 3 n /10 parties, thus its recursion depth is ⌈ log ( 3 n / 10 ) ⌉ \lceil\log(3n/10)\rceil ⌈ log ( 3 n /10 )⌉ because of the check in GetAccusations. In each recursion level, the leader sends a query to each party in its original accuser set, which has size at most 3 n / 10 3n/10 3 n /10 . The query being a tag and a range made of two integers between 1 1 1 and n n n , the overall bit complexity for the leader will be O ( n log 2 n ) O(n\log^2 n) O ( n log 2 n ) . And the leader only spending two rounds before the parallel recursive calls means the round complexity is 2 ⌈ log n ⌉ 2\lceil\log n\rceil 2 ⌈ log n ⌉ . Looking at an helper party, for a specific leader, it will respond to at most ⌈ log n ⌉ \lceil\log n\rceil ⌈ log n ⌉ queries and send at most one accusation. Because there are n n n helper for a given leader, this amounts in total to O ( log 2 n + κ ) O(\log^2 n+\kappa) O ( log 2 n + κ ) bits with the same round complexity.
GetAccusations makes at most n n n parallel matching leader calls, one for each party. So, the total per-party bit complexity is O ( n ( log 2 n + κ ) ) O(n(\log^2 n+\kappa)) O ( n ( log 2 n + κ )) and round complexity O ( log n ) O(\log n) O ( log n ) .
Finally, we remark that we did not use the resiliency t < n / 2 t < n/2 t < n /2 at any point for proofs related to this protocol. As a matter of fact, it supports an arbitrary number of byzantine parties. Thus it is byzantine-robust.
Spreading votes
The last case to handle happens when at least one honest party is not able to identify many byzantine parties. More specifically, if at least one honest party p p p is unable to identify at least 3 n / 10 3n/10 3 n /10 byzantine parties. For this to happen, most byzantine parties must appear as following the protocol for p p p and therefore send a vote (for 0 0 0 , 1 1 1 or ⊥ \perp ⊥ ) to it. As a consequence, in this case, p p p will receive at least 7 n / 10 7n/10 7 n /10 votes. As a reminder, we can also assume that n b ⊥ n_{b_\perp} n b ⊥ (the number of ⊥ \perp ⊥ votes by honest parties) is at least 4 n / 10 4n/10 4 n /10 . We remark that this is enough for p p p to get a proof: in addition to 4 n / 10 4n/10 4 n /10 ⊥ \perp ⊥ votes, either 0 0 0 or 1 1 1 will get at least ( 7 n / 10 − 4 n / 10 ) / 2 (7n/10-4n/10)/2 ( 7 n /10 − 4 n /10 ) /2 votes supporting it, which in total is strictly more than 0.55 n > n / 2 > t 0.55n > n/2 > t 0.55 n > n /2 > t votes.
However, getting a single party to get a proof is not enough, we want at least n / 10 n/10 n /10 honest parties to get one. To do so, we remark that p p p has a ”surplus” of 0.05 0.05 0.05 votes. So, by forwarding votes to other parties using a disperser pattern, which only requires parties to forward each vote to a constant number of parties, we can make it so that any subset of 4 n / 10 4n/10 4 n /10 parties has enough votes together to get a proof. A key insight is that we forward each vote to a different set of parties, so even if a single vote may only be forwarded to byzantine parties, only an arbitrary small fraction of the votes will. Finally, using a fault-proof expander graph, we can find a subset of 4 n / 10 4n/10 4 n /10 honest parties which are all at logarithmic distance of each other and such that the graph degree is constant.
SpreadVotes($Votes$)
Spread votes among all parties for a party $p$
Let $G_1$ be a $(n/20, 7n/10)$-disperser // Using {xref}`Theorem 11` with $\alpha = 1/20$ and $m = 115$
for each vote $v$ from party $q$ in $Votes$, in parallel do
Send $v$ to $N_{G_1}(q)$
end for
Let $G_2$ be a fault-tolerant expander // Using {xref}`Theorem 2`
Send $Votes$ to $N_{G_2}(p)$
for $O(\log n)$ rounds do
Upon Receiving a vote $v$ not in $Votes$
Forward $v$ to parties in $N_{G_2}(p)$
$Votes \gets Votes \cup \{v\}$
end for
Return $Votes$
Lemma 6. SpreadVotes has per-party bit complexity O ( n κ ) O(n\kappa) O ( nκ ) and round complexity O ( log n ) O(\log n) O ( log n ) . Additionally, it is byzantine-robust.
Proof. The graphs (G 1 G_1 G 1 and G 2 G_2 G 2 ) used in the protocol using Theorems 2 and 11 have constant degree. We note that there can only exist 3 n 3n 3 n votes in total: n n n parties and 3 votes (0, 1 or ⊥ \perp ⊥ ) per party, and each vote is O ( κ ) O(\kappa) O ( κ ) bits. Because each party sends each unique vote to at most O ( 1 ) O(1) O ( 1 ) parties using G 1 G_1 G 1 and G 2 G_2 G 2 , the total per-party bit complexity is O ( n κ ) O(n\kappa) O ( nκ ) . Regarding round complexity, the first step takes 1 round while the second step takes O ( log n ) O(\log n) O ( log n ) rounds. So the overall round complexity is O ( log n ) O(\log n) O ( log n ) round. Finally, we remark that the resiliency t < n / 2 t < n/2 t < n /2 was not used when computing the complexity, as such this protocol is byzantine-robust.
Lemma 7. Consider a party p p p and a subset S S S of its votes, where each vote is from a distinct party. For any party q q q , let E q ⊆ S E_q \subseteq S E q ⊆ S be the votes from S S S it received after the first round. Then for any subset H ⊆ P H \subseteq\mathcal{P} H ⊆ P of parties such that ∣ H ∣ ≥ 4 n / 10 |H| \ge4n/10 ∣ H ∣ ≥ 4 n /10 , ∣ ⋃ q ∈ H E q ∣ ≥ ∣ S ∣ − n / 20 |\bigcup_{q\in H} E_q| \ge|S| - n/20 ∣ ⋃ q ∈ H E q ∣ ≥ ∣ S ∣ − n /20 .
Proof. Consider a party p p p and sets S S S and H H H as defined in the lemma. Let R R R be the set of votes from S S S that were received by no parties in H H H , i.e R = S ∖ ⋃ q ∈ H E q R = S \setminus\bigcup_{q\in H} E_q R = S ∖ ⋃ q ∈ H E q . We want to prove that ∣ R ∣ ≤ n / 20 |R| \le n/20 ∣ R ∣ ≤ n /20 . Because each vote in S S S comes from a different party, we can identify votes with the party that emitted it. Because votes were transmitted using the graph G 1 G_1 G 1 , this implies that there is no edge between R R R and H H H , so N G 1 ( R ) ⊆ P ∖ H N_{G_1}(R) \subseteq\mathcal{P} \setminus H N G 1 ( R ) ⊆ P ∖ H , so ∣ N G 1 ( R ) ∣ ≤ n − ∣ H ∣ ≤ n − 4 n / 10 ≤ 6 n / 10 |N_{G_1}(R)| \le n - |H| \le n - 4n/10 \le6n/10 ∣ N G 1 ( R ) ∣ ≤ n − ∣ H ∣ ≤ n − 4 n /10 ≤ 6 n /10 . G 1 G_1 G 1 is a disperser, any set of size n / 20 n/20 n /20 has neighborhood of size at least 7 n / 10 7n/10 7 n /10 . By contrapositive, ∣ R ∣ < n / 20 |R| < n/20 ∣ R ∣ < n /20 .
Lemma 8. If n b ⊥ ≥ 4 n / 10 nb_{\perp} \ge4n/10 n b ⊥ ≥ 4 n /10 and an honest party has votes from at least 7 n / 10 7n/10 7 n /10 parties, then at least 4 n / 10 4n/10 4 n /10 parties will receive enough votes to form a proof.
Proof. Assume n b ⊥ ≥ 4 n / 10 nb_{\perp} \ge4n/10 n b ⊥ ≥ 4 n /10 and an honest party p p p has votes from more than 7 n / 10 7n/10 7 n /10 honest party. Let R R R be the set of votes p p p has, keeping only one per party. We have ∣ R ∣ ≥ 7 n / 10 |R| \ge7n/10 ∣ R ∣ ≥ 7 n /10 . Because we only consider one vote per party, we can identify a vote with the party that emitted it. Let B z B_z B z be the set of byzantine parties, we have ∣ B z ∣ ≤ t ≤ n / 2 |B_z| \le t \le n/2 ∣ B z ∣ ≤ t ≤ n /2 . Using the property on G 2 G_2 G 2 (Theorem 2), there exists a set of parties S S S such that S S S and B z B_z B z are disjoint, i.e S S S is honest, ∣ S ∣ ≥ 4 n / 10 |S| \ge4n/10 ∣ S ∣ ≥ 4 n /10 , and G 2 [ S ] G_2[S] G 2 [ S ] is connected and has diameter O ( log n ) O(\log n) O ( log n ) . We can now use Lemma 7 on S S S and R R R : there exists R ′ ⊆ R R' \subseteq R R ′ ⊆ R such that ∣ R ′ ∣ ≥ ∣ R ∣ − n / 20 ≥ 7 n / 10 − n / 20 = 6.5 n / 10 |R'| \ge|R| - n/20 \ge7n/10 - n/20 = 6.5n/10 ∣ R ′ ∣ ≥ ∣ R ∣ − n /20 ≥ 7 n /10 − n /20 = 6.5 n /10 and parties in
S S S together receive all votes of R ′ R' R ′ from p p p in the first round of SpreadVotes. Therefore, after all O ( log n ) O(\log n) O ( log n ) rounds, all parties of S S S will have all votes of R ′ R' R ′ .
We now show that votes in R ′ R' R ′ are enough to form a proof. Because n b ⊥ ≥ 4 n / 10 nb_{\perp} \ge4n/10 n b ⊥ ≥ 4 n /10 , there are at least 4 n / 10 4n/10 4 n /10 votes for ⊥ \perp ⊥ in R R R . Since R ′ ⊆ R R' \subseteq R R ′ ⊆ R and ∣ R ′ ∣ ≥ ∣ R ∣ − n / 20 |R'| \ge|R| - n/20 ∣ R ′ ∣ ≥ ∣ R ∣ − n /20 , R ′ R' R ′ has at least 4 n / 10 − n / 20 = 3.5 n / 10 4n/10 - n/20 = 3.5n/10 4 n /10 − n /20 = 3.5 n /10 votes for ⊥ \perp ⊥ . Let x x x be the number of votes for ⊥ \perp ⊥ in R ′ R' R ′ and let y y y be the number of votes for 0 or 1. We have x + y = ∣ R ′ ∣ ≥ 6.5 n / 10 x+y=|R'| \ge6.5n/10 x + y = ∣ R ′ ∣ ≥ 6.5 n /10 . One of 0 and 1 has at least y / 2 y/2 y /2 votes in R ′ R' R ′ . Hence, the votes for ⊥ \perp ⊥ together with the votes for this value are at least:
x + y 2 = x + ( x + y ) 2 = x + ∣ R ′ ∣ 2 ≥ 3.5 n + 6.5 n 2 = n / 2 \begin{aligned}
x+\frac{y}{2} &= \frac{x+(x+y)}{2}\\
&= \frac{x+|R'|}{2}\\
&\ge\frac{3.5n+6.5n}{2}\\
&= n/2
\end{aligned} x + 2 y = 2 x + ( x + y ) = 2 x + ∣ R ′ ∣ ≥ 2 3.5 n + 6.5 n = n /2
Since t < n / 2 t<n/2 t < n /2 , there are at least t + 1 t+1 t + 1 such votes, all from distinct parties, so a proof can be formed. Thus, all parties in S S S will be able to get form a proof and ∣ S ∣ ≥ 4 n / 10 |S| \ge4n/10 ∣ S ∣ ≥ 4 n /10 , which concludes the proof. □
Computing a Proof
We finally describe the last step of the protocol, which is to compute a proof from votes and accusations. This is done by computing a maximum matching on accusations where neither accuser nor accused can be used as votes.
ComputeProof (b b b , Votes , Accusations )
Compute a proof for b b b if one can be found
Let Q Q Q be the votes in Votes for v v v or ⊥ \perp ⊥
Let E E E be the Accusations disjoint from Q Q Q , seen as edges
Compute a maximum matching M M M of E E E
if ∣ Q ∣ ≥ 1 |Q| \ge1 ∣ Q ∣ ≥ 1 and ∣ Q ∣ + ∣ M ∣ ≥ t + 1 |Q|+|M| \ge t+1 ∣ Q ∣ + ∣ M ∣ ≥ t + 1 then
Return a set of t + 1 t+1 t + 1 votes/accusations from Q Q Q and M M M with at least one vote
else
Return ⊥ \perp ⊥
end if
The maximum matching can be computed in polynomial time using the Blossom Algorithm. As a side note, looking at how we got accusations, we remark that the undirected graph the matching is computed on comes from a directed graph where each vertex has in-degree and out-degree at most 1. Hence, it is a collection of disjoint paths and cycles, which allows a maximum matching to be computed in linear time.
Lemma 9. If there exists a proof for b b b using Votes and Accusations, then a call to ComputeProof will return a proof for $b.
Proof. Consider a proof for b b b , let Q Q Q be its set of votes and T T T its set of accusations. We note that, without loss of generality, we can assume that no party present in T T T (as an accuser or accused) has a vote for b b b or ⊥ \perp ⊥ in Votes . The reason for it is that if this were the case, we could remove the accusation from T T T and add the vote to Q Q Q , which would result in a valid proof. Let V b V_b V b be the set of votes in Votes for b b b or ⊥ \perp ⊥ and let E b E_b E b be the set of accusations in Accusations disjoint from V b V_b V b . We have Q ⊆ V b Q \subseteq V_b Q ⊆ V b and, because no accuser or accused in T T T has a vote for b b b or ⊥ \perp ⊥ , T ⊆ E b T \subseteq E_b T ⊆ E b . As a consequence, ∣ V b ∣ ≥ ∣ Q ∣ ≥ 1 \lvert V_b\rvert\ge\lvert Q\rvert\ge1 ∣ V b ∣ ≥ ∣ Q ∣ ≥ 1 . Moreover, T T T is a matching of E b E_b E b , so there exists a matching of size ∣ T ∣ \lvert T\rvert ∣ T ∣ . By maximality of M M M , we will have ∣ M ∣ ≥ ∣ T ∣ \lvert M\rvert\ge\lvert T\rvert ∣ M ∣ ≥ ∣ T ∣ . Therefore, ∣ V b ∣ + ∣ M ∣ ≥ ∣ Q ∣ + ∣ T ∣ = t + 1 \lvert V_b\rvert+ \lvert M\rvert\ge\lvert Q\rvert+ \lvert T\rvert= t+1 ∣ V b ∣ + ∣ M ∣ ≥ ∣ Q ∣ + ∣ T ∣ = t + 1 , which shows that ComputeProof( b , V o t e s , A c c u s a t i o n s ) (b, Votes, Accusations) ( b , V o t es , A cc u s a t i o n s ) will return a proof for b b b .
Putting it together
Theorem 4. After running ProofCreation, at least n / 10 n/10 n /10 honest parties will have a proof for 0 or 1.
Proof. We remind the reader that n b ⊥ nb_{\perp} n b ⊥ is the number of honest parties which changed their input to ⊥ \perp ⊥ . After the first round of sending votes. We now have 3 different cases to consider:
n b ⊥ ≤ 4 n / 10 nb_{\perp} \le4n/10 n b ⊥ ≤ 4 n /10 : If a party does not change its input to ⊥ \perp ⊥ , it means it either received t + 1 t+1 t + 1 votes for 0 or t + 1 t+1 t + 1 votes for 1. So, it has already enough votes to form a proof. Because t < n / 2 t < n/2 t < n /2 , at least n − t − n b ⊥ ≥ n / 2 − 4 n / 10 = n / 10 n-t-nb_{\perp} \ge n/2-4n/10 = n/10 n − t − n b ⊥ ≥ n /2 − 4 n /10 = n /10 honest parties will have enough votes to form a proof.
n b ⊥ > 4 n / 10 nb_{\perp} > 4n/10 n b ⊥ > 4 n /10 and at least one honest party received votes from at least 7 n / 10 7n/10 7 n /10 parties: Using Lemma 8, at least 4 n / 10 4n/10 4 n /10 parties will receive enough votes to form a proof.
n b ⊥ > 4 n / 10 nb_{\perp} > 4n/10 n b ⊥ > 4 n /10 and every honest party received less than 7 n / 10 7n/10 7 n /10 votes: In this case, every honest party is able to identify at least 3 n / 10 3n/10 3 n /10 byzantine parties. Moreover, given an honest party p p p , its set of accusers A c c Acc A cc is made of parties which sent a vote to p p p different than ⊥ \perp ⊥ . So ∣ A c c ∣ ≤ n − 3 n / 10 − n b ⊥ ≤ 3 n / 10 \lvert Acc\rvert\le n-3n/10-nb_{\perp} \le3n/10 ∣ A cc ∣ ≤ n − 3 n /10 − n b ⊥ ≤ 3 n /10 . As a consequence, GetAccusations will call MatchingLeader for every honest party. Consider an honest party p p p , either p p p is counted towards n b ⊥ nb_{\perp} n b ⊥ and sent a ⊥ \perp ⊥ -vote to everyone, or it sent a vote for 0 or 1 to everyone, which implies it is in the set of accusers of every other honest party. Using Lemma 4, the set of accusations returned by GetAccusations contains a disjoint matching between all such honest parties as accusers and byzantine parties as accused. Thus, these accusations are disjoint from ⊥ \perp ⊥ -votes of the n b ⊥ nb_{\perp} n b ⊥ honest parties. Because each honest party appears exactly once with a ⊥ \perp ⊥ -vote or as an accuser, we have a set of votes and accusations of size n − t ≥ t + 1 n-t \ge t+1 n − t ≥ t + 1 with at least one vote (n b ⊥ > 0 nb_{\perp}>0 n b ⊥ > 0 ), which is enough to form a proof. So all honest parties will be able to form a proof.
Finally, using Lemma 9, the n / 10 n/10 n /10 honest parties that have enough votes and accusations will return a proof for 0 or 1.
Theorem 5. ProofCreation has bit complexity B P C ( n ) = O ( n 2 ( log 2 n + κ ) ) B_{\mathrm{PC}}(n) = O(n^2(\log^2 n+\kappa)) B PC ( n ) = O ( n 2 ( log 2 n + κ )) and round complexity R P C ( n ) = O ( log n ) R_{\mathrm{PC}}(n) = O(\log n) R PC ( n ) = O ( log n ) . Additionally, it is byzantine-robust.
Proof. The first two rounds of ProofCreation have bit complexity O ( n 2 κ ) O(n^2\kappa) O ( n 2 κ ) , as each party sends a vote to every other party. Combining it with Lemmas 5 and 6, we get the expected complexities.
Validated dispersion
We now consider the second part of our protocol, which is validated dispersion. After the first part, n / 10 n/10 n /10 honest parties are guaranteed to hold a proof of size O ( n κ ) O(n\kappa) O ( nκ ) . The goal of validated dispersion is to ensure that there is one proof which ends up known by all honest parties. We note that a very simple implementation of validated dispersion is to have each party send its proof to all other parties if it has one. Although it is quite simple, the total bit complexity would be O ( n 3 κ ) O(n^3\kappa) O ( n 3 κ ) .
Our protocol instead relies on partitioning all n n n parties into m m m groups of size ⌊ n / m ⌋ \lfloor n/m\rfloor ⌊ n / m ⌋ or ⌈ n / m ⌉ \lceil n/m\rceil ⌈ n / m ⌉ , where m : = m ( n ) m := m(n) m := m ( n ) is a parameter to be determined later. We first remark that, by sending proofs following a disperser graph, we can ensure that all but at most n / ( 10 m ) n/(10m) n / ( 10 m ) honest parties will have a proof. This has bit complexity O ( n 2 m κ ) O(n^2m\kappa) O ( n 2 mκ ) . Afterwards, we can agree on a proof in each group and broadcast it efficiently using erasure codes. Because one of the groups is guaranteed to have a byzantine minority, this ensures that the proof from this group will reach every party. In the end, the protocol returns the set of proofs received from each group.
The group broadcast protocol is described in Section B.4. An assumption we make is that m = O ( n α ) m = O(n^\alpha) m = O ( n α ) for some 0 < α < 1 0 < \alpha< 1 0 < α < 1 as a way to simplify the complexity analysis. We show that this assumption is satisfied in § 12 .
ValidatedDispersion(proof)
Disperse a proof for a party p p p
p r o o f s ← ∅ proofs \gets\varnothing p r oo f s ← ∅
Let G G G be a ( n / 10 , n − n / ( 10 m ) ) (n/10,n-n/(10m)) ( n /10 , n − n / ( 10 m )) -disperser // Using Theorem 11 with α = 1 / 10 \alpha= 1/10 α = 1/10 and degree 4 ∗ 10 ∗ 10 ∗ m 4 \ast10 \ast10 \ast m 4 ∗ 10 ∗ 10 ∗ m
Send p r o o f proof p r oo f to N G ( p ) N_G(p) N G ( p )
if p r o o f = ⊥ proof = \bot p r oo f = ⊥ and received a valid proof q q q then
p r o o f ← q proof \gets q p r oo f ← q
end if
Partition P \mathcal{P} P into m m m groups of size ⌊ n / m ⌋ \lfloor n/m\rfloor ⌊ n / m ⌋ or ⌈ n / m ⌉ \lceil n/m\rceil ⌈ n / m ⌉ .
for each group G G G in parallel do
if p ∈ G p \in G p ∈ G then
q \gets\textsc{PartialValidatedAgreement}(G)
end if
q \gets\textsc{GroupBroadcast}(G,q)
if q q q is valid then
p r o o f s ← p r o o f s ∪ { q } proofs \gets proofs \cup\{q\} p r oo f s ← p r oo f s ∪ { q }
end if
end for
Return $proofs
Theorem 6. The protocol satisfies validated dispersion.
Proof. Termination comes from PartialValidatedAgreement and GroupBroadcast’s termination. Because a value only gets added to p r o o f s proofs p r oo f s if it is valid, validity follows.
We assume that at least n / 10 n/10 n /10 honest parties have a non-⊥ \bot ⊥ valid input. Because we send values using a ( n / 10 , n − n / ( 10 m ) ) (n/10,n-n/(10m)) ( n /10 , n − n / ( 10 m )) -disperser, at most n / ( 10 m ) ≤ ⌊ n / m ⌋ / 10 n/(10m) \le\lfloor n/m\rfloor/10 n / ( 10 m ) ≤ ⌊ n / m ⌋ /10 honest parties will not receive a valid input. Parties are partitioned into groups of size at least ⌊ n / m ⌋ / 10 \lfloor n/m\rfloor/10 ⌊ n / m ⌋ /10 . Because the initial set of parties has a byzantine minority, it implies that at least one of the groups has a byzantine minority too. Consider this group G G G , of size k k k . It has a byzantine minority, and among the honest parties, at most k / 10 k/10 k /10 do not have a valid input, so at least k − k / 10 − k / 2 ≥ k / 3 k-k/10-k/2 \ge k/3 k − k /10 − k /2 ≥ k /3 honest parties have a valid input.
Therefore, using partial validated agreement, all honest parties in G G G will agree on a valid proof q q q . Again, because G G G has an honest majority and all honest parties call it with the same input q q q , all honest parties in P \mathcal{P} P will receive q q q . So coverage is also satisfied.
Theorem 7. Assuming the partial validated agreement protocol is byzantine-robust, ValidatedDispersion has per-party bit complexity B V D ( n , L ) = O ( m L ) + B P V A ( ⌈ n / m ⌉ , L ) B_{\mathrm{VD}}(n,L)=O(mL)+B_{\mathrm{PVA}}(\lceil n/m\rceil,L) B VD ( n , L ) = O ( m L ) + B PVA (⌈ n / m ⌉ , L ) , round complexity R V D ( n ) = O ( 1 ) + R P V A ( ⌈ n / m ⌉ , L ) R_{\mathrm{VD}}(n)=O(1)+R_{\mathrm{PVA}}(\lceil n/m\rceil,L) R VD ( n ) = O ( 1 ) + R PVA (⌈ n / m ⌉ , L ) and is byzantine-robust.
Proof. The disperser G G G is obtained from Theorem 11 using degree 4 ∗ 10 ∗ 10 ∗ m = O ( m ) 4 * 10 * 10 * m=O(m) 4 ∗ 10 ∗ 10 ∗ m = O ( m ) , so each party sends its proof of size L L L to O ( m ) O(m) O ( m ) parties, which gives a per-party bit complexity of O ( m L ) O(mL) O ( m L ) . Afterwards, each party calls PartialValidatedAgreement on a group of size at most ⌈ n / m ⌉ \lceil n/m\rceil ⌈ n / m ⌉ , which gives a per-party bit complexity of B P V A ( ⌈ n / m ⌉ , L ) B_{\mathrm{PVA}}(\lceil n/m\rceil,L) B PVA (⌈ n / m ⌉ , L ) . Finally, the group broadcast has cost O ( L n / ⌈ n / m ⌉ + κ n log n ) = O ( m L ) O(Ln/\lceil n/m\rceil+\kappa n\log n)=O(mL) O ( L n / ⌈ n / m ⌉ + κn log n ) = O ( m L ) as we assume m = O ( n α ) m=O(n^\alpha) m = O ( n α ) for α > 0 \alpha>0 α > 0 . Regarding the round complexity, every part of this protocol except the partial validated agreement takes O ( 1 ) O(1) O ( 1 ) rounds.
Parallel agreement
Using validated dispersion, we go from solving a problem on n n n parties to solving it on m < < n m << n m << n parties. A consequence, is that we can recursively run our own byzantine agreement protocol on this smaller set of parties. However, this agreement protocol is still expensive. We remark that we mostly use parallel reliable broadcast in our partial validated agreement protocol, and as such, optimizing this use case would improve the overall complexity of our protocol. To do so, we rely on batching, where given a batch size b b b , we only need to run recursively our byzantine agreement κ \kappa κ times for b b b parallel invocations.
Committee Broadcast
We first describe our committee broadcast protocol. This is a variant of the Dolev-Strong protocol, where only a smaller committee of size b b b is responsible for forwarding signatures, instead of all parties. The advantage of such approach is that it has lower complexity than the original Dolev-Strong protocol. The disadvantage is that agreement is only guaranteed if at least one honest party in the committee is honest.
Our broadcast protocol is used to send a small value. More specifically, we assume the input v i n v_{\mathrm{in}} v in satisfies ∣ v i n ∣ = O ( κ ) |v_{\mathrm{in}}|=O(\kappa) ∣ v in ∣ = O ( κ ) .
Figure 1.
CommitteeBroadcast(v i n , p i n , C v_{\mathrm{in}},p_{\mathrm{in}},C v in , p in , C )
Code for a party p i n ∈ C p_{\mathrm{in}}\in C p in ∈ C to broadcast a value v i n v_{\mathrm{in}} v in , executed by a party p p p
if p = p i n p=p_{\mathrm{in}} p = p in then Sign v i n v_{\mathrm{in}} v in and send it to all parties end if
for i = 2 i=2 i = 2 to ∣ C ∣ + 1 |C|+1 ∣ C ∣ + 1 do // An iteration lasts 2 rounds Upon receiving a message signed by p i n p_{\mathrm{in}} p in and i − 1 i-1 i − 1 parties from C C C Forward it to all parties in C C C // Only applied for two distinct messages received if p ∈ C p\in C p ∈ C then Upon receiving a message signed by p i n p_{\mathrm{in}} p in and i − 1 i-1 i − 1 parties from C C C Add your signature and forward it to all parties // Only applied for two distinct messages received end if end for
if received a single message m m m then Return m m m else
Return $\bot$
end if
Lemma 10. If at least one party in C C C is honest, then the protocol satisfies byzantine broadcast.
Proof. Assume there exists a party q ∈ C q \in C q ∈ C that is honest.
We first show that agreement is satisfied. We remark that if an honest party in C C C forwards 2 distinct signed messages from the sender, every party will receive these messages and decide ⊥ \bot ⊥ , in which case agreement is satisfied. Otherwise, consider the case where honest parties in C C C only forward at most one signed message. Consider any honest party p ∈ P p \in\mathcal{P} p ∈ P that accepts a signed message m m m , we want to show that every other honest party will receive m m m . We have two cases:
Or the message was not signed by q q q . We remark in this case that we are not in iteration ∣ C ∣ + 1 |C| + 1 ∣ C ∣ + 1 , as otherwise the message would have to be signed by all parties in C C C , including q q q . In this case, p p p will forward m m m to all parties in C C C including q q q . Because there is at least one iteration remaining, q q q will add its signature and forward it to all parties, so every honest party will receive and accept it.
As a consequence, the set of messages accepted by all honest parties is the same, so the decided value will be the same: agreement is satisfied. Given that the protocol runs for O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) rounds and then returns a value, termination is satisfied. Finally, assume the sender p i n p_{\mathrm{in}} p in is honest. Then, it will sign and send the same input v i n v_{\mathrm{in}} v in to all parties, which will receive and accept it. Moreover, p i n p_{\mathrm{in}} p in being honest will not sign any other message, so no other message will be accepted. As a consequence, all honest parties will decide v i n v_{\mathrm{in}} v in , so validity is satisfied.
:::
Lemma 11. The protocol has round complexity O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) . Regardless of messages received, parties in C C C send O ( κ n ∣ C ∣ ) O(\kappa n|C|) O ( κn ∣ C ∣ ) bits while other parties send O ( κ ∣ C ∣ 2 ) O(\kappa|C|^2) O ( κ ∣ C ∣ 2 ) bits.
Proof. We note that the protocol runs for exactly 2 ∣ C ∣ + 1 2|C| + 1 2∣ C ∣ + 1 rounds. All messages contain an input, which is O ( κ ) O(\kappa) O ( κ ) bits and at most ∣ C ∣ |C| ∣ C ∣ signatures, which are each κ \kappa κ bits. Parties in C C C send at most 2 such messages to each party, while other parties send at most 2 messages to parties in C C C , hence the result.
Batch Broadcast
Our previous committee broadcast is reliable as long as at least one party in the committee is honest. We use it to implement batch broadcast, where a group of C C C parties want to broadcast their L L L -bit input at the same time. We remind the reader that we assume L = O ( κ ) L = O(\kappa) L = O ( κ ) . We remark that if we use the previous committee broadcast with C C C being the committee, then either at least one party in C C C is honest, in which case we are done, or all parties in C C C are byzantine. In the latter case, we only care about agreement, so we can run a single byzantine agreement on the concatenated output of all broadcast result. This approach allows us to reduce the number of byzantine agreement calls from ∣ C ∣ |C| ∣ C ∣ to 1, which is a significant improvement. The MVBA protocol is described in Section B.3.
BatchBroadcast($v_{in}$, $C$)
Code for all parties in $C$ to broadcast an input $v_{in}$, executed by a party $p$
in parallel For each party $q \in C$ do
Call CommitteeBroadcast($v_{in}$, $q$, $C$)
Let $m$ be the concatenation of all outputs from the previous calls
Return MVBA($m$)
Lemma 12. The protocol satisfies byzantine broadcast for each party in C C C .
Proof. Termination follows from CommitteeBroadcast and MVBA’s termination. We consider validity. We remark that validity is only relevant if at least one party in C C C is honest. But in this case, using Lemma 10, the output of each committee broadcast satisfies validity and agreement. As a consequence, each honest party will receive the same output for each broadcast, which is the parties’ input if it is honest. Thus, the concatenated output will be the same for all honest parties, and MVBA’s validity will ensure that the final output is the same as the common input. So every honest party will output the parties’ input if it is honest, and validity is satisfied. Finally, agreement is a consequence of MVBA’s agreement.
Lemma 13. The protocol has round complexity O ( ∣ C ∣ ) + R M V B A ( n ) O(|C|) + R_{\mathrm{MVBA}}(n) O ( ∣ C ∣ ) + R MVBA ( n ) . Regardless of messages received, parties in C C C send O ( κ n ∣ C ∣ 2 ) + B M V B A ( n , ∣ C ∣ L ) O(\kappa n|C|^2) + B_{\mathrm{MVBA}}(n, |C|L) O ( κn ∣ C ∣ 2 ) + B MVBA ( n , ∣ C ∣ L ) bits while other parties send O ( κ ∣ C ∣ 3 ) + B M V B A ( n , ∣ C ∣ L ) O(\kappa|C|^3) + B_{\mathrm{MVBA}}(n, |C|L) O ( κ ∣ C ∣ 3 ) + B MVBA ( n , ∣ C ∣ L ) bits.
Proof. This is a direct application of Lemma 11 and the fact that the concatenation of all outputs is of size ∣ C ∣ L |C|L ∣ C ∣ L .
Parallel broadcast
We now describe our final protocol for parallel byzantine agreement. The idea is to partition the set of parties into groups of size b : = b ( n ) b := b(n) b := b ( n ) , and run BatchBroadcast on each group in parallel. This allows us to reduce the number of byzantine agreement calls from n n n to ⌈ n / b ⌉ \lceil n/b \rceil ⌈ n / b ⌉ . We note that there is a trade-off on b b b : the larger b b b is, the less amount of recursive byzantine agreement calls we need to make, but at the same time the more expensive the CommitteeBroadcast becomes. The exact choice is left for later, as it is chosen to minimize the bit complexity of the overall byzantine agreement protocol.
ParallelBroadcast($v_{in}$, $C$)
Code for all parties in $C$ to broadcast an input $v_{in}$, executed by a party $p$
Partition $C$ into groups of size $b$ (except possibly the last group)
for each group $C_i$ in parallel do
Call BatchBroadcast($v_{in}$, $C_i$)
end for
Return the output of all previous calls
Lemma 14. The protocol satisfies byzantine broadcast for each party in C C C .
Proof. This is a direct consequence of Lemma 12.
Lemma 15. The protocol has round complexity O ( ∣ C ∣ ) + R M V B A ( n ) O(|C|) + R_{\mathrm{MVBA}}(n) O ( ∣ C ∣ ) + R MVBA ( n ) . Regardless of messages received, parties send ( ∣ C ∣ / b + 1 ) ( O ( κ b 3 ) + B M V B A ( n , b L ) ) (|C|/b + 1) (O(\kappa b^3) + B_{\mathrm{MVBA}}(n, bL)) ( ∣ C ∣/ b + 1 ) ( O ( κ b 3 ) + B MVBA ( n , b L )) bits. Parties in C C C send an additional O ( κ n b 2 ) O(\kappa n b^2) O ( κn b 2 ) bits.
Proof. The round complexity follows from the fact that we only run parallel executions of BatchBroadcast and Lemma 13. Regarding the bit complexity, we make exactly ⌈ ∣ C ∣ / b ⌉ ≤ ∣ C ∣ / b + 1 \lceil|C|/b \rceil\leq|C|/b + 1 ⌈ ∣ C ∣/ b ⌉ ≤ ∣ C ∣/ b + 1 calls to BatchBroadcast, and each of these calls is run with a group size ∣ C ∣ ≤ b |C| \leq b ∣ C ∣ ≤ b . Using Lemma 13, this results in the expected bit complexity. Finally, if a party is in C C C , exactly one of the batch broadcasts will be on the party’s group, which using Lemma 13 results in the additional O ( κ n 2 b ) O(\kappa n^2 b) O ( κ n 2 b ) bits sent.
Partial Validated Agreement
We now describe a protocol to reduce partial validated agreement to validated agreement. In partial validated agreement, only n / 3 n/3 n /3 honest parties are guaranteed to have a valid input. The main insight is to have each party broadcast reliably whether it has a valid input or not. Then, we run the validated agreement protocol only on parties that claim to have a valid input. Afterwards, we use a group broadcast protocol to ensure that all parties receive the same decision value. If it is not valid, this implies that the validated agreement protocol was run on a byzantine majority, so the remaining parties form a byzantine minority. Thus, we can first use a disperser graph to ensure that a third of the remaining honest parties have a valid input, then iterate back onto them.
One point to note is that we want our protocol to be byzantine-friendly, so we must not iterate too many times if this should not be possible. In particular, if less than a third of the parties claim to have a valid input, this cannot happen with a byzantine minority, so we can just stay silent for the rest of the protocol.
The ReliableGroupBroadcast protocol is described in Section B.5.
PartialValidatedAgreement(v_in)
Agree on a valid input for a party p
Q ← P
for ⌈log_{3/2} n⌉ iterations do
Let G be a (n/3, 5|Q|/6) bipartite disperser // Using Theorem 12
Send v_in to N_G(p)
if v_in = ⊥ and received a valid input v from a neighbor then
v_in ← v
end if
(b_q)_{q∈Q} ← ParallelBroadcast(Q, v_in ≠ ⊥)
Q_1 ← {q ∈ Q : b_q = 1}
if |Q_1| < |Q|/3 then
Stay silent for the rest of the protocol // Can only happen with a byzantine majority
end if
if p ∈ Q_1 then
v ← ValidatedAgreement_{Q_1}(v_in)
end if
v ← ReliableGroupBroadcast_Q(Q_1, v)
if v is valid then
Return v
end if
Q ← Q \ Q_1
end for
Theorem 8. PartialValidatedAgreement satisfies partial validated agreement.
Proof. We first show by induction that, at the i i i -th iteration of the protocol, the set Q Q Q has a byzantine minority and ∣ Q ∣ ≤ n ⋅ ( 2 / 3 ) i − 1 |Q| \le n \cdot(2/3)^{i-1} ∣ Q ∣ ≤ n ⋅ ( 2/3 ) i − 1 . At first, Q = P Q = P Q = P which has a byzantine minority and size n n n , so initialization holds.
We now consider iteration i i i and assume Q Q Q has a byzantine minority and ∣ Q ∣ ≤ n ⋅ ( 2 / 3 ) i − 1 |Q| \le n \cdot(2/3)^{i-1} ∣ Q ∣ ≤ n ⋅ ( 2/3 ) i − 1 . G G G is a disperser used to send parties’ input. Because it is a ( n / 3 , 5 ∣ Q ∣ / 6 ) (n/3,5|Q|/6) ( n /3 , 5∣ Q ∣/6 ) -disperser and at least n / 3 n/3 n /3 honest parties send their valid input through it, at least 5 ∣ Q ∣ / 6 5|Q|/6 5∣ Q ∣/6 parties receive a valid input. So at least 5 ∣ Q ∣ / 6 − ∣ Q ∣ / 2 = ∣ Q ∣ / 3 5|Q|/6 - |Q|/2 = |Q|/3 5∣ Q ∣/6 − ∣ Q ∣/2 = ∣ Q ∣/3 parties will have a valid input. Because Q Q Q has a byzantine minority, the ParallelBroadcast call will succeed, and thus ∣ Q 1 ∣ ≥ ∣ Q ∣ / 3 |Q_1| \ge|Q|/3 ∣ Q 1 ∣ ≥ ∣ Q ∣/3 . If Q 1 Q_1 Q 1 has a byzantine minority, then all the conditions for validated agreement are satisfied, so all honest parties in Q 1 Q_1 Q 1 will agree on a valid input and ReliableGroupBroadcast will ensure that all honest parties receive this input and return.
If this does not happen, then it implies that Q 1 Q_1 Q 1 has a byzantine majority, so Q ∖ Q 1 Q \setminus Q_1 Q ∖ Q 1 has a byzantine minority. Moreover, because ∣ Q 1 ∣ ≥ ∣ Q ∣ / 3 |Q_1| \ge|Q|/3 ∣ Q 1 ∣ ≥ ∣ Q ∣/3 , we have ∣ Q ∖ Q 1 ∣ ≤ 2 ∣ Q ∣ / 3 ≤ n ⋅ ( 2 / 3 ) i |Q \setminus Q_1| \le2|Q|/3 \le n \cdot(2/3)^i ∣ Q ∖ Q 1 ∣ ≤ 2∣ Q ∣/3 ≤ n ⋅ ( 2/3 ) i using the induction hypothesis. Thus, the induction step holds.
Finally, after ⌈ log 3 / 2 n ⌉ \lceil\log_{3/2} n \rceil ⌈ log 3/2 n ⌉ iterations, if no output has been returned yet, we have ∣ Q ∣ ≤ n ⋅ ( 2 / 3 ) ⌈ log 3 / 2 n ⌉ ≤ 1 |Q| \le n \cdot(2/3)^{\lceil\log_{3/2} n \rceil} \le1 ∣ Q ∣ ≤ n ⋅ ( 2/3 ) ⌈ l o g 3/2 n ⌉ ≤ 1 . Because there is a byzantine majority, it implies that there is exactly one honest party left in Q Q Q . It will thus receive a valid input, share it with other parties and they will return it this iteration. Thus, all parties will return the same valid input: the protocol satisfies partial validated agreement.
Lemma 16. Assuming the underlying protocols are byzantine-robust, then the protocol is byzantine-robust and:
B P V A ( n , L ) = O ( L log n + κ n b 2 + κ b 3 log n ) + n / b ⋅ B M V B A ( n , b ) + O ( log n ) ⋅ B M V B A ( n , L ) + ∑ i = 0 ⌈ log 3 / 2 n ⌉ B V A ( n ⋅ ( 2 / 3 ) i , L ) B_{\mathrm{PVA}}(n,L) = O(L\log n + \kappa n b^2 + \kappa b^3 \log n) + n/b \cdot B_{\mathrm{MVBA}}(n,b) + O(\log n) \cdot B_{\mathrm{MVBA}}(n,L)
+ \sum_{i=0}^{\lceil\log_{3/2} n \rceil} B_{\mathrm{VA}}(n \cdot(2/3)^i,L) B PVA ( n , L ) = O ( L log n + κn b 2 + κ b 3 log n ) + n / b ⋅ B MVBA ( n , b ) + O ( log n ) ⋅ B MVBA ( n , L ) + i = 0 ∑ ⌈ l o g 3/2 n ⌉ B VA ( n ⋅ ( 2/3 ) i , L ) Additionally,
R P V A ( n ) = O ( log n ) ( b + R M V B A ( n ) ) + ∑ i = 0 ⌈ log 3 / 2 n ⌉ R V A ( n ⋅ ( 2 / 3 ) i ) R_{\mathrm{PVA}}(n) = O(\log n)(b + R_{\mathrm{MVBA}}(n)) + \sum_{i=0}^{\lceil\log_{3/2} n \rceil} R_{\mathrm{VA}}(n \cdot(2/3)^i) R PVA ( n ) = O ( log n ) ( b + R MVBA ( n )) + i = 0 ∑ ⌈ l o g 3/2 n ⌉ R VA ( n ⋅ ( 2/3 ) i ) Proof. We consider the round complexity. We note that in the i i i -th iteration, an honest party will only consider that at most ( 2 / 3 ) i − 1 n (2/3)^{i-1}n ( 2/3 ) i − 1 n parties are participating. However, because we want our protocol to be byzantine robust, this does not mean that at most ( 2 / 3 ) i − 1 n (2/3)^{i-1}n ( 2/3 ) i − 1 n honest parties are participating: if there is a byzantine majority, then honest parties may disagree on who is participating and all of them may believe they are participating. We consider the complexity of the i i i -th iteration, while remarking that a party p p p will consider itself to be part of at most one set Q 1 Q_1 Q 1 in the whole protocol:
Parallel broadcast: on at most n ⋅ ( 2 / 3 ) i − 1 n \cdot(2/3)^{i-1} n ⋅ ( 2/3 ) i − 1 parties. Parties broadcast a single bit. Using Lemma 15 , this takes b + R M V B A ( n ⋅ ( 2 / 3 ) i − 1 ) b + R_{\mathrm{MVBA}}(n \cdot(2/3)^{i-1}) b + R MVBA ( n ⋅ ( 2/3 ) i − 1 ) rounds and O ( κ n b 2 ) + ( ( n ⋅ ( 2 / 3 ) i − 1 ) / b + 1 ) ⋅ ( O ( κ b 3 ) + B M V B A ( n , b ) ) O(\kappa n b^2) + ((n \cdot(2/3)^{i-1})/b + 1) \cdot(O(\kappa b^3) + B_{\mathrm{MVBA}}(n,b)) O ( κn b 2 ) + (( n ⋅ ( 2/3 ) i − 1 ) / b + 1 ) ⋅ ( O ( κ b 3 ) + B MVBA ( n , b )) bits per party.
Validated agreement: has per-party bit complexity B V A ( n ⋅ ( 2 / 3 ) i − 1 , L ) B_{\mathrm{VA}}(n \cdot(2/3)^{i-1}, L) B VA ( n ⋅ ( 2/3 ) i − 1 , L ) and round complexity R V A ( n ⋅ ( 2 / 3 ) i − 1 ) R_{\mathrm{VA}}(n \cdot(2/3)^{i-1}) R VA ( n ⋅ ( 2/3 ) i − 1 ) .
Reliable group broadcast: Using Lemma 28, this takes O ( κ n log n ) + B M V B A ( n ⋅ ( 2 / 3 ) i − 1 , L ) \mathcal{O}(\kappa n \log n) + B_{\mathrm{MVBA}}(n \cdot(2/3)^{i-1}, L) O ( κn log n ) + B MVBA ( n ⋅ ( 2/3 ) i − 1 , L ) bits and O ( 1 ) + R M V B A ( n ⋅ ( 2 / 3 ) i − 1 ) \mathcal{O}(1) + R_{\mathrm{MVBA}}(n \cdot(2/3)^{i-1}) O ( 1 ) + R MVBA ( n ⋅ ( 2/3 ) i − 1 ) rounds.
Summing these over all iterations, and using the fact that ∑ i = 0 ⌈ log 3 / 2 n ⌉ ( n ⋅ ( 2 / 3 ) i − 1 ) = O ( n ) \sum_{i=0}^{\lceil\log_{3/2} n\rceil}(n \cdot(2/3)^{i-1}) = \mathcal{O}(n) ∑ i = 0 ⌈ l o g 3/2 n ⌉ ( n ⋅ ( 2/3 ) i − 1 ) = O ( n ) , we obtain the expected results.
Validated Agreement
We now present our protocol to solve validated byzantine agreement. To do so, we first present initial ideas to perform Validated Agreement and what their limitations are.
Dolev-Strong: An initial idea would be to have each party send their input using reliable broadcast and more specifically the Dolev-Strong broadcast protocol. Parties could just then pick up the first valid value they receive. This would have O ( n 3 ( n κ + L ) ) \mathcal{O}(n^3(n\kappa+ L)) O ( n 3 ( nκ + L )) bit complexity. If used within our framework, this would lead to a protocol solving byzantine agreement with bit complexity O ~ ( n 8 / 3 ) \widetilde{\mathcal{O}}(n^{8/3}) O ( n 8/3 ) . Although this is subcubic, the cubic cost of Dolev-Strong is the bottleneck in this case.
Recursive Application: We remark that we can assume a byzantine minority and that byzantine broadcast can be implemented with a single call to byzantine agreement. This leads to a new idea: instead of using Dolev-Strong to implement Byzantine Broadcast, we can use our own byzantine agreement protocol recursively. Doing so, along with common erasure coding techniques, would lead to validated agreement having a bit complexity of O ~ ( n 2 L + n 3.5 ) \widetilde{\mathcal{O}}(n^2L+n^{3.5}) O ( n 2 L + n 3.5 ) . This would cause the overall bit complexity of our byzantine agreement protocol to be O ~ ( n 2.5 ) \widetilde{\mathcal{O}}(n^{2.5}) O ( n 2.5 ) .
Byzantine-Robust protocol: The bottleneck of our protocol is now the O ( n 2 L ) \mathcal{O}(n^2L) O ( n 2 L ) in the bit complexity. If we ignore round complexity for a moment, a simple idea would be to perform the broadcast calls consecutively and stop as soon as one succeeds. Indeed, only the broadcaster has a O ( n L ) \mathcal{O}(nL) O ( n L ) cost and if the broadcaster is honest, the broadcast will succeed. This idea works and decreases the L L L -dependency to O ( n L ) \mathcal{O}(nL) O ( n L ) . However, this approach does not work with our requirements: it is not byzantine-robust. If there is a byzantine majority, they can prevent our broadcast protocol from succeeding, even if the broadcaster is honest and cause the overall bit complexity to go back to quadratic in L L L .
Our solution for these problems is to use a dynamic programming approach: we track for a given group a valid input as well as a set of parties that know this input and we show how to update this information when merging two groups. What remains is to decide how to merge groups to minimize both the round and bit complexity.
Group Merging
We now provide the proper invariant we maintain on each group. Given a group G ⊆ P G \subseteq\mathcal{P} G ⊆ P , every party keeps track of the tuple:
Such that h h h is the accumulator of a valid input, all honest parties in H H H know the value associated with h h h and G ∖ H G \setminus H G ∖ H has a byzantine majority (more specifically, at least ( ∣ G ∣ − ∣ H ∣ ) / 2 (|G|-|H|)/2 ( ∣ G ∣ − ∣ H ∣ ) /2 parties in G ∖ H G \setminus H G ∖ H are byzantine).
We note that initialization of this tuple is easy: as each honest party p p p is assumed to have a valid input, it can reliable broadcast the accumulator h h h associated with that input and all parties in P P P can set G = { p } G = \{p\} G = { p } , with tuple ( h , H ) = ( h , { p } ) (h, H) = (h, \{p\}) ( h , H ) = ( h , { p }) .
We now present how to merge two groups G 1 G_1 G 1 and G 2 G_2 G 2 with their respective tuples ( h 1 , H 1 ) (h_1, H_1) ( h 1 , H 1 ) and ( h 2 , H 2 ) (h_2, H_2) ( h 2 , H 2 ) . We note that parts of the procedure, namely sending the value and broadcasting the decision are implementation details, which will be explained in the next section. The only assumption we make about the implementation is that if a group A A A sends a value to another group B B B , then as long as at least one honest party in A A A is honest, then every party in B B B will receive the value.
MergeGroups
Merge two disjoint groups G 1 G_1 G 1 and G 2 G_2 G 2
Input: Two groups G 1 G_1 G 1 and G 2 G_2 G 2 with their respective tuples ( h 1 , H 1 ) (h_1, H_1) ( h 1 , H 1 ) and ( h 2 , H 2 ) (h_2, H_2) ( h 2 , H 2 ) Output: A valid tuple for G 1 ∪ G 2 G_1 \cup G_2 G 1 ∪ G 2
if H 1 = ∅ H_1 = \emptyset H 1 = ∅ then Return ( h 2 , H 2 ) (h_2, H_2) ( h 2 , H 2 ) end if
Parties in H 1 H_1 H 1 send the value associated with h 1 h_1 h 1 to parties in H 2 H_2 H 2 Parties in H 2 H_2 H 2 reliable broadcast 1 if they received the value associated with h 1 h_1 h 1 , 0 otherwise Let K K K be the subset of H 2 H_2 H 2 that broadcasted 0
if ∣ K ∣ ≥ ∣ H 1 ∣ |K| \ge|H_1| ∣ K ∣ ≥ ∣ H 1 ∣ then Let K ′ K' K ′ be a subset of K K K of size ∣ H 1 ∣ |H_1| ∣ H 1 ∣ Return ( h 2 , H 2 ∖ K ′ ) (h_2, H_2 \setminus K') ( h 2 , H 2 ∖ K ′ ) else Let H 1 ′ H'_1 H 1 ′ be a subset of H 1 H_1 H 1 of size ∣ K ∣ |K| ∣ K ∣ Return ( h 1 , ( H 1 ∖ H 1 ′ ) ∪ ( H 2 ∖ K ) ) (h_1, (H_1 \setminus H'_1) \cup(H_2 \setminus K)) ( h 1 , ( H 1 ∖ H 1 ′ ) ∪ ( H 2 ∖ K )) end if
Lemma 17. When called on two disjoint groups G 1 G_1 G 1 and G 2 G_2 G 2 with their respective tuples ( h 1 , H 1 ) (h_1, H_1) ( h 1 , H 1 ) and ( h 2 , H 2 ) (h_2, H_2) ( h 2 , H 2 ) that satisfy the invariant, MergeGroups returns a tuple ( h , H ) (h, H) ( h , H ) that satisfies the invariant for G 1 ∪ G 2 G_1 \cup G_2 G 1 ∪ G 2 .
Proof. Let M 1 = G 1 ∖ H 1 M_1 = G_1 \setminus H_1 M 1 = G 1 ∖ H 1 and M 2 = G 2 ∖ H 2 M_2 = G_2 \setminus H_2 M 2 = G 2 ∖ H 2 . Under the invariant, both M 1 M_1 M 1 and M 2 M_2 M 2 have a byzantine majority. Because they are disjoint, M 1 ∪ M 2 M_1 \cup M_2 M 1 ∪ M 2 also has a byzantine majority.
We consider the first case in the merge procedure: if H 1 = ∅ H_1 = \emptyset H 1 = ∅ , then the tuple ( h 2 , H 2 ) (h_2, H_2) ( h 2 , H 2 ) is returned. Using the invariant, we already know that honest parties in H 2 H_2 H 2 know the value associated with h 2 h_2 h 2 , and the set of remaining parties is exactly M 1 ∪ M 2 M_1 \cup M_2 M 1 ∪ M 2 , which has a byzantine majority. So the invariant is preserved.
Otherwise, we remark that either H 1 H_1 H 1 or K K K is composed only of byzantine parties. Indeed, if H 1 H_1 H 1 is only made of byzantine properties, this remark is true. Otherwise, H 1 H_1 H 1 has at least one honest party, which knows the value to send according to the invariant. Thus, the send will succeed and all honest parties in H 2 H_2 H 2 will receive the value. Hence, K K K , which is made of parties that claimed to not receive the value, is composed only of byzantine parties.
We remark that in both cases, ( G 1 ∪ G 2 ) ∖ H = M 1 ∪ M 2 ∪ H 1 ′ ∪ K ′ (G_1 \cup G_2) \setminus H = M_1 \cup M_2 \cup H'_1 \cup K' ( G 1 ∪ G 2 ) ∖ H = M 1 ∪ M 2 ∪ H 1 ′ ∪ K ′ , where all these sets are disjoint, H 1 ′ ⊆ H 1 H'_1 \subseteq H_1 H 1 ′ ⊆ H 1 and K ′ ⊆ K K' \subseteq K K ′ ⊆ K such that ∣ H 1 ′ ∣ = ∣ K ′ ∣ |H'_1| = |K'| ∣ H 1 ′ ∣ = ∣ K ′ ∣ . Because M 1 ∪ M 2 M_1 \cup M_2 M 1 ∪ M 2 already has a byzantine majority, and one of H 1 ′ H'_1 H 1 ′ or K ′ K' K ′ is fully composed of byzantine parties, the resulting set will also have a byzantine majority.
Finally, if ∣ K ∣ ≥ ∣ H 1 ∣ |K| \ge|H_1| ∣ K ∣ ≥ ∣ H 1 ∣ , then the tuple ( h 2 , H 2 ∖ K ′ ) (h_2, H_2 \setminus K') ( h 2 , H 2 ∖ K ′ ) is returned. Because all parties in H 2 H_2 H 2 already claim to know the value with accumulator h 2 h_2 h 2 using the invariant, it is preserved. Otherwise, the tuple ( h 1 , ( H 1 ∖ H 1 ′ ) ∪ ( H 2 ∖ K ) ) (h_1, (H_1 \setminus H'_1) \cup(H_2 \setminus K)) ( h 1 , ( H 1 ∖ H 1 ′ ) ∪ ( H 2 ∖ K )) is returned. Using the invariant, all parties in H 1 H_1 H 1 know the value with accumulator h 1 h_1 h 1 , additionally, all parties in H 2 ∖ K H_2 \setminus K H 2 ∖ K broadcasted that they received the value, so they also know it. Thus, the invariant is preserved in both cases.
Implementation
Sending value We first explain how to implement the send operation. We note that each party in H 1 H_1 H 1 can send the value to all parties in H 2 H_2 H 2 . However, if ∣ H 1 ∣ = ∣ H 2 ∣ = n / 2 |H_1| = |H_2| = n/2 ∣ H 1 ∣ = ∣ H 2 ∣ = n /2 , then this would lead to a O ( n 2 L ) O(n^2L) O ( n 2 L ) bit complexity. Instead, we use erasure codes and have each party encode their input into n n n shares and share it with all parties along with an accumulator witness. This way, when a party in H 2 H_2 H 2 wants to receive the value, every party can send its share to it and it can reconstruct it. A key point is that if an honest party p p p is able to reconstruct a valid value, it will immediately re-encode it and share it again with other parties. This is so that, even if p p p was only able to get enough shares with the help of byzantine parties, subsequent reconstruction will always succeed, even without their help. We give the implementation of Deconstruct and Reconstruct:
Deconstruct( p , h ) (p,h) ( p , h ) : Should only be called if p p p has the value v v v with accumulator h h h . p p p encodes v v v into n n n shares along with their witness, then sends each share to the corresponding party. When receiving a share, the party checks that the witness corresponds to the accumulator h h h and stores it. p p p sends O ( κ n log n + L ) O(\kappa n \log n + L) O ( κn log n + L ) bits, while other parties do not send any bits.
Reconstruct( p , h ) (p,h) ( p , h ) : For every party q q q , if q q q has a share with witness corresponding to h h h , it sends it to p p p . If p p p receives enough shares (at least n / 2 n/2 n /2 ), it reconstructs the value, checks that its accumulator is h h h , that it is valid and returns it. Otherwise, it returns ⊥ \perp ⊥ . Each party sends a share, of size O ( κ log n + L / n ) O(\kappa\log n + L/n) O ( κ log n + L / n ) .
Parallel broadcast We remark that all broadcast operations can be done in parallel. Additionally, if two merges for disjoint groups are done at the same time, their broadcasts can also be done in parallel. We leverage this idea and use our parallel broadcast protocol to perform as many of these broadcasts in parallel. This is needed to make sure the overall round complexity ends up staying linear. Regarding how we merge groups, a first idea would be to merge all groups one by one to a single group. However, this approach cannot be easily parallelized. Another approach is to use a balanced binary tree structure to merge groups, where leafs are the original groups and each internal node represents a merge operation. Although it is more efficient, it would lead to a logarithmic blowup in the bit complexity, as each party would be actively involved in O ( log n ) O(\log n) O ( log n ) merges. Instead, we take an approach which is in between these last two: we merge following a tree of height 3, where each internal node has at most ⌈ n 1 / 3 ⌉ \lceil n^{1/3} \rceil ⌈ n 1/3 ⌉ children.
Validated Agreement( v i n ) (v_{in}) ( v in )
Validated Agreement protocol for a party p p p
Let h i n h_{in} h in be the accumulator of v i n v_{in} v in
(h_p) \leftarrow\textsc{ParallelBA}(\mathcal{P}, h_{in})
for p ∈ P p \in\mathcal{P} p ∈ P , in parallel do
Deconstruct ( p , h p ) (p,h_p) ( p , h p )
end for
G ← { ( { p } , h p , { p } ) , p ∈ P } G \leftarrow\{(\{p\}, h_p, \{p\}), p \in\mathcal{P}\} G ← {({ p } , h p , { p }) , p ∈ P }
for 3 iterations do
Partition G G G into sets of size ⌈ n 1 / 3 ⌉ \lceil n^{1/3} \rceil ⌈ n 1/3 ⌉
G ′ ← ∅ G' \leftarrow\emptyset G ′ ← ∅
for each set $S = H_1,\ldots,H_k$, in parallel do
$(h,H) \gets H_1$
for $i = 2,\ldots,k$ do
in parallel for each $p \in H_i$ do
$v \gets \operatorname{Reconstruct}(p,h)$
if $v$ is valid and has accumulator $h$ then
$\operatorname{Deconstruct}(p,h)$
end if
$b_p \gets 1$ if $v$ is valid and has accumulator $h$, $0$ otherwise
Call $\operatorname{ParallelBA}$ on $(b_p)_{p\in H_i}$
$(h,H) \gets \operatorname{MergeGroups}((h,H),(h_i,H_i))$ using the result of $\operatorname{ParallelBA}$
end for
$G' \gets G' \cup \{(h,H)\}$
end for
$G \gets G'$
Let $h$ be the accumulator of the remaining group in $G$
in parallel for each $p \in \mathcal{P}$ do
$v \gets \operatorname{Reconstruct}(p,h)$
Return $v$
Lemma 18. The protocol satisfies Validated Agreement.
Proof. The protocol starts with n n n groups. In each iteration, it forms sets of size ⌈ n 1 / 3 ⌉ \lceil n^{1/3}\rceil ⌈ n 1/3 ⌉ (except the last one) and merges them. As a consequence, after 3 iterations, there is only n / n 1 / 3 3 = 1 n/n^{1/3^3}=1 n / n 1/ 3 3 = 1 group left. Consider the last group G G G with tuple ( h , H ) (h,H) ( h , H ) . By the invariant, P ∖ H \mathcal{P}\setminus H P ∖ H has a byzantine majority. Because P \mathcal{P} P has a byzantine minority, this implies that H H H has a byzantine minority and thus has at least one honest party p p p . Using the invariant again, this implies that h h h is the accumulator of a valid input that p p p has. We note that every time a party p p p receives a valid value, it calls Deconstruct on it, which ensures that every honest party will be able to reconstruct the value associated with h h h at the end of the protocol. Thus, all honest parties will output the same valid value associated with h h h , which satisfies Validated Agreement.
Lemma 19. ValidatedAgreement has per-party bit complexity:
B V A ( n , L ) = O ( L + κ n b 2 + κ n 1 / 3 b 3 ) + O ( n / b + n 1 / 3 ) ⋅ B M V B A ( n , b ) + O ( n / b ) ⋅ B M V B A ( n , b κ ) B_{\mathrm{VA}}(n,L) = O(L + \kappa n b^2 + \kappa n^{1/3}b^3) + O(n/b + n^{1/3}) \cdot B_{\mathrm{MVBA}}(n,b) + O(n/b) \cdot B_{\mathrm{MVBA}}(n,b\kappa) B VA ( n , L ) = O ( L + κn b 2 + κ n 1/3 b 3 ) + O ( n / b + n 1/3 ) ⋅ B MVBA ( n , b ) + O ( n / b ) ⋅ B MVBA ( n , bκ ) And round complexity:
R V A ( n ) = O ( n 1 / 3 ) ⋅ ( b + R M V B A ( n ) ) R_{\mathrm{VA}}(n) = O(n^{1/3}) \cdot(b + R_{\mathrm{MVBA}}(n)) R VA ( n ) = O ( n 1/3 ) ⋅ ( b + R MVBA ( n ))
Proof. We remark that a call to Deconstruct has a bit complexity of O ( κ n log n + L ) O(\kappa n \log n+L) O ( κn log n + L ) (the sender sends a share and a witness to every other party) to the sender while a call to Reconstruct has a bit complexity of O ( κ n log n + L / n ) O(\kappa n \log n+L/n) O ( κn log n + L / n ) for every party. In each iteration, which there are 3, a party is a member of a unique set H i H_i H i . As a consequence, in each iteration, it will only call Reconstruct at most once and be the sender of at most one ParallelBA operation. Additionally, because we batch all parallel broadcasts calls together for independant merges, each iteration will call at most k ≤ ⌈ n 1 / 3 ⌉ k \leq\lceil n^{1/3}\rceil k ≤ ⌈ n 1/3 ⌉ times the ParallelBA procedure. So in total, we have for a given party p p p :
Initial ParallelBA call: each party broadcasts its accumulator, of size κ \kappa κ . Hence, using Lemma 15, we have a total of ( n / b + 1 ) ( O ( κ b 3 ) + B M V B A ( n , κ b ) ) + O ( κ n b 2 ) (n/b+1)(O(\kappa b^3)+B_{\mathrm{MVBA}}(n,\kappa b))+O(\kappa n b^2) ( n / b + 1 ) ( O ( κ b 3 ) + B MVBA ( n , κb )) + O ( κn b 2 ) bits per party.
ParallelBA calls, ignoring when p p p is a sender: at most 3 n 1 / 3 3n^{1/3} 3 n 1/3 calls, all parties are a sender at most once in each iteration. So using Lemma 15, we have a total of 3 ( n / b + n 1 / 3 ) ( O ( κ b 3 ) + B M V B A ( n ) ) 3(n/b + n^{1/3})(O(\kappa b^3) + B_{\mathrm{MVBA}}(n)) 3 ( n / b + n 1/3 ) ( O ( κ b 3 ) + B MVBA ( n )) bits per party.
Summing all of these together, we get the expected bit complexity. As for round complexity, the Deconstruct and Reconstruct calls at the beginning and the end take 2 rounds. Otherwise, in each iteration, we have up to ⌈ n 1 / 3 ⌉ \lceil n^{1/3}\rceil ⌈ n 1/3 ⌉ ParallelBA calls which are dependent on each other, so the round complexity becomes:
R V A ( n ) = 2 + 3 ⌈ n 1 / 3 ⌉ R P a r a l l e l B A ( n ) = O ( n 1 / 3 ) ⋅ ( b + R M V B A ( n ) ) R_{\mathrm{VA}}(n) = 2 + 3\lceil n^{1/3}\rceil R_{\mathrm{ParallelBA}}(n)
= O(n^{1/3}) \cdot(b + R_{\mathrm{MVBA}}(n)) R VA ( n ) = 2 + 3 ⌈ n 1/3 ⌉ R ParallelBA ( n ) = O ( n 1/3 ) ⋅ ( b + R MVBA ( n ))
Using Lemma 15
Putting it all together
Per-party bit complexity
We can now combine all the previous protocols together to get a subcubic byzantine agreement protocol. We first start by simplifying the complexity of the partial validated agreement protocol. Using Lemma 16, we have:
B P V A ( n , L ) = O ( L log n + κ n b 2 + κ b 3 log n ) + n / b ⋅ B M V B A ( n , b ) + O ( log n ) ⋅ B M V B A ( n , L ) + ∑ i = 0 ⌈ log 3 / 2 n ⌉ B V A ( n ⋅ ( 2 / 3 ) i , L ) B_{\mathrm{PVA}}(n, L) = O(L \log n + \kappa n b^2 + \kappa b^3 \log n) + n/b \cdot B_{\mathrm{MVBA}}(n, b) + O(\log n) \cdot B_{\mathrm{MVBA}}(n, L) + \sum_{i=0}^{\lceil\log_{3/2} n\rceil} B_{\mathrm{VA}}(n \cdot(2/3)^i, L) B PVA ( n , L ) = O ( L log n + κn b 2 + κ b 3 log n ) + n / b ⋅ B MVBA ( n , b ) + O ( log n ) ⋅ B MVBA ( n , L ) + i = 0 ∑ ⌈ l o g 3/2 n ⌉ B VA ( n ⋅ ( 2/3 ) i , L )
Using Lemma 19, we have:
B V A ( n , L ) = O ( L + κ n b 2 + κ n 1 / 3 b 3 ) + O ( n / b + n 1 / 3 ) ⋅ B M V B A ( n , b ) + O ( n / b ) ⋅ B M V B A ( n , b κ ) B_{\mathrm{VA}}(n, L) = O(L + \kappa n b^2 + \kappa n^{1/3}b^3) + O(n/b + n^{1/3}) \cdot B_{\mathrm{MVBA}}(n, b) + O(n/b) \cdot B_{\mathrm{MVBA}}(n, b\kappa) B VA ( n , L ) = O ( L + κn b 2 + κ n 1/3 b 3 ) + O ( n / b + n 1/3 ) ⋅ B MVBA ( n , b ) + O ( n / b ) ⋅ B MVBA ( n , bκ )
Using the fact that ∑ i = 0 ⌈ log 3 / 2 n ⌉ ( n ⋅ ( α ) i ) = O ( n ) \sum_{i=0}^{\lceil\log_{3/2} n\rceil}(n \cdot(\alpha)^i) = O(n) ∑ i = 0 ⌈ l o g 3/2 n ⌉ ( n ⋅ ( α ) i ) = O ( n ) for any 0 < α < 1 0 < \alpha< 1 0 < α < 1 , we have:
∑ i = 0 ⌈ log 3 / 2 n ⌉ B V A ( n ⋅ ( 2 / 3 ) i , L ) = O ( L log n + κ n b 2 + κ n 1 / 3 b 3 ) + O ( n / b + n 1 / 3 ) ⋅ B M V B A ( n , b ) + O ( n / b ) ⋅ B M V B A ( n , b κ ) \sum_{i=0}^{\lceil\log_{3/2} n\rceil} B_{\mathrm{VA}}(n \cdot(2/3)^i, L) = O(L \log n + \kappa n b^2 + \kappa n^{1/3}b^3)
+ O(n/b + n^{1/3}) \cdot B_{\mathrm{MVBA}}(n, b) + O(n/b) \cdot B_{\mathrm{MVBA}}(n, b\kappa) i = 0 ∑ ⌈ l o g 3/2 n ⌉ B VA ( n ⋅ ( 2/3 ) i , L ) = O ( L log n + κn b 2 + κ n 1/3 b 3 ) + O ( n / b + n 1/3 ) ⋅ B MVBA ( n , b ) + O ( n / b ) ⋅ B MVBA ( n , bκ )
Using these two equations together, we get:
B P V A ( n , L ) = O ( L log n + κ n b 2 + κ n 1 / 3 b 3 ) + O ( n / b + n 1 / 3 ) ⋅ B M V B A ( n , b ) + O ( n / b ) ⋅ B M V B A ( n , κ b ) + O ( log n ) ⋅ B M V B A ( n , L ) = O ( L log n + κ n b 2 + κ n 1 / 3 b 3 + κ n 2 log n / b + κ n 4 / 3 log n ) + O ( n / b + n 1 / 3 ) ⋅ κ ⋅ B B A ( n ) \begin{aligned}
B_{\mathrm{PVA}}(n,L)=O(L\log n+\kappa nb^{2}+\kappa n^{1/3}b^{3})+O(n/b+n^{1/3})\cdot B_{\mathrm{MVBA}}(n,b)
+O(n/b)\cdot B_{\mathrm{MVBA}}(n,\kappa b)+O(\log n)\cdot B_{\mathrm{MVBA}}(n,L) \\
&=O(L\log n+\kappa nb^{2}+\kappa n^{1/3}b^{3}+\kappa n^{2}\log n/b+\kappa n^{4/3}\log n)
+O(n/b+n^{1/3})\cdot\kappa\cdot B_{\mathrm{BA}}(n)
\end{aligned} B PVA ( n , L ) = O ( L log n + κn b 2 + κ n 1/3 b 3 ) + O ( n / b + n 1/3 ) ⋅ B MVBA ( n , b ) + O ( n / b ) ⋅ B MVBA ( n , κb ) + O ( log n ) ⋅ B MVBA ( n , L ) = O ( L log n + κn b 2 + κ n 1/3 b 3 + κ n 2 log n / b + κ n 4/3 log n ) + O ( n / b + n 1/3 ) ⋅ κ ⋅ B BA ( n )
Using Lemma 24
We now look at the complexity of our weak agreement protocol:
B W B A ( n ) = B P C ( n ) + B V D ( n , κ n ) B_{\mathrm{WBA}}(n)=B_{\mathrm{PC}}(n)+B_{\mathrm{VD}}(n,\kappa n) B WBA ( n ) = B PC ( n ) + B VD ( n , κn )
Using Observation 1
= O ( n ( log 2 n + κ ) ) + B V D ( n , κ n ) =O(n(\log^{2}n+\kappa))+B_{\mathrm{VD}}(n,\kappa n) = O ( n ( log 2 n + κ )) + B VD ( n , κn )
Using Theorem 5
= O ( n ( log 2 n + κ ) ) + O ( n m κ ) + B P V A ( ⌈ n / m ⌉ , κ n ) =O(n(\log^{2}n+\kappa))+O(nm\kappa)+B_{\mathrm{PVA}}(\lceil n/m\rceil,\kappa n) = O ( n ( log 2 n + κ )) + O ( nmκ ) + B PVA (⌈ n / m ⌉ , κn )
Using Theorem 7
= O ( n m κ + κ n b 2 / m + κ n 1 / 3 b 3 / m 1 / 3 + κ n 2 log n / ( b m 2 ) + κ n 4 / 3 log n / m 4 / 3 ) + O ( n / ( m b ) + ( n / m ) 1 / 3 ) ⋅ κ ⋅ B B A ( ⌈ n / m ⌉ ) =O(nm\kappa+\kappa nb^{2}/m+\kappa n^{1/3}b^{3}/m^{1/3}+\kappa n^{2}\log n/(bm^{2})+\kappa n^{4/3}\log n/m^{4/3})
+O(n/(mb)+(n/m)^{1/3})\cdot\kappa\cdot B_{\mathrm{BA}}(\lceil n/m\rceil) = O ( nmκ + κn b 2 / m + κ n 1/3 b 3 / m 1/3 + κ n 2 log n / ( b m 2 ) + κ n 4/3 log n / m 4/3 ) + O ( n / ( mb ) + ( n / m ) 1/3 ) ⋅ κ ⋅ B BA (⌈ n / m ⌉)
Finally, we can consider the complexity of the binary agreement protocol, for n n n big enough, we have using Lemmas 21 and 22:
B B A ( n ) ≤ 2 B B A ( ⌈ n / 2 ⌉ ) + 4 B W B A ( n ) B_{\mathrm{BA}}(n)\le2B_{\mathrm{BA}}(\lceil n/2\rceil)+4B_{\mathrm{WBA}}(n) B BA ( n ) ≤ 2 B BA (⌈ n /2 ⌉) + 4 B WBA ( n )
So in total, we have:
B B A ( n ) ≤ 2 B B A ( ⌈ n / 2 ⌉ ) + O ( n m κ + κ n b 2 / m + κ n 1 / 3 b 3 / m 1 / 3 + κ n 2 log n / ( b m 2 ) + κ n 4 / 3 log n / m 4 / 3 ) + O ( n / ( m b ) + ( n / m ) 1 / 3 ) ⋅ κ ⋅ B B A ( ⌈ n / m ⌉ ) B_{\mathrm{BA}}(n)\le2B_{\mathrm{BA}}(\lceil n/2\rceil)+O(nm\kappa+\kappa nb^{2}/m+\kappa n^{1/3}b^{3}/m^{1/3}+\kappa n^{2}\log n/(bm^{2})+\kappa n^{4/3}\log n/m^{4/3})
+O(n/(mb)+(n/m)^{1/3})\cdot\kappa\cdot B_{\mathrm{BA}}(\lceil n/m\rceil) B BA ( n ) ≤ 2 B BA (⌈ n /2 ⌉) + O ( nmκ + κn b 2 / m + κ n 1/3 b 3 / m 1/3 + κ n 2 log n / ( b m 2 ) + κ n 4/3 log n / m 4/3 ) + O ( n / ( mb ) + ( n / m ) 1/3 ) ⋅ κ ⋅ B BA (⌈ n / m ⌉)
Theorem 9. For n n n large enough, by choosing m = b = Θ ( ( κ n ) ( 13 − 3 ) / 2 ) ≈ Θ ( ( κ n ) 0.3077 ) m=b=\Theta((\kappa n)^{(\sqrt{13}-3)/2})\approx\Theta((\kappa n)^{0.3077}) m = b = Θ (( κn ) ( 13 − 3 ) /2 ) ≈ Θ (( κn ) 0.3077 ) , we obtain
B B A ( n ) = O ( ( κ n ) ( 13 − 1 ) / 2 ) B_{\mathrm{BA}}(n)=O((\kappa n)^{(\sqrt{13}-1)/2}) B BA ( n ) = O (( κn ) ( 13 − 1 ) /2 )
Proof. We note that the dependency on κ \kappa κ , which cannot be considered as O ( 1 ) O(1) O ( 1 ) in B B A ( n ) B_{\mathrm{BA}}(n) B BA ( n ) ’s relation prevents us from using the Akra-Bazzi method. Our proof relies on the fact that κ = polylog n \kappa=\operatorname{polylog} n κ = polylog n . This implies that there are some constants C , K > 0 C,K>0 C , K > 0 such that κ ≤ K log C n \kappa\le K\log^{C}n κ ≤ K log C n . One thing to note is that although this inequality should be true for the initial number of parties n n n , it may not hold in the number of parties n ′ n' n ′ considered in recursive calls, as that would imply that κ = O ( 1 ) \kappa=O(1) κ = O ( 1 ) . Let us define p = ( κ n ) ( 13 − 1 ) / 2 ≈ 1.3077 p=(\kappa n)^{(\sqrt{13}-1)/2}\approx1.3077 p = ( κn ) ( 13 − 1 ) /2 ≈ 1.3077 . To give some informal insight regarding the parameters used, we will use m ( n ) = b ( n ) ≈ ( κ n ) p − 1 ≈ ( κ n ) 0.3077 m(n)=b(n)\approx(\kappa n)^{p-1}\approx(\kappa n)^{0.3077} m ( n ) = b ( n ) ≈ ( κn ) p − 1 ≈ ( κn ) 0.3077 .
Let N > 1 N>1 N > 1 large enough such that κ ≤ K log C N \kappa\le K\log^{C}N κ ≤ K log C N . We want to show that there exists constant A A A depending only on K K K and C C C such that B B A ( n ) ≤ A ( κ n ) p B_{\mathrm{BA}}(n)\le A(\kappa n)^{p} B BA ( n ) ≤ A ( κn ) p .
To do so, we prove by induction that for all 1 < n ≤ N 1<n\le N 1 < n ≤ N , we have:
B B A ( n ) ≤ A ( κ n ) p ( log ( N ) log ( n ) ) D B_{\mathrm{BA}}(n)\le A(\kappa n)^{p}\left(\frac{\log(N)}{\log(n)}\right)^{D} B BA ( n ) ≤ A ( κn ) p ( log ( n ) log ( N ) ) D
With D D D a constant to be determined later. We note that if this property holds for n = N n=N n = N , then we have the expected result.
We now give the explicit values of m m m and n n n used to obtain this bound:
( m , b ) = { ( n , 1 ) If n ≤ B κ 4 ( c ( κ n ) p − 1 , c ( κ n ) p − 1 ) Otherwise (m,b)=\begin{cases}
(n,1) & \text{If } n \le B\kappa^{4}\\
(c(\kappa n)^{p-1},c(\kappa n)^{p-1}) & \text{Otherwise}
\end{cases} ( m , b ) = { ( n , 1 ) ( c ( κn ) p − 1 , c ( κn ) p − 1 ) If n ≤ B κ 4 Otherwise
Where B B B and c c c are large enough constants to be determined later.
Let us define f ( n ) = A ( κ n ) p ( log ( N ) log ( n ) ) D f(n)=A(\kappa n)^{p}\left(\frac{\log(N)}{\log(n)}\right)^{D} f ( n ) = A ( κn ) p ( l o g ( n ) l o g ( N ) ) D . We consider the first case, where 1 < n ≤ B κ 4 1<n\le B\kappa^{4} 1 < n ≤ B κ 4 . In this case, we use m = n m=n m = n and b = 1 b=1 b = 1 . We note when looking at the validated dispersal protocol that this effectively amounts to parties sending their proof to all other parties if they have one. In fact, looking at the recurrence we have on B B A ( n ) B_{\mathrm{BA}}(n) B BA ( n ) , we obtain:
B B A ( n ) ≤ 2 B B A ( ⌈ n / 2 ⌉ ) + O ( κ n 2 + n ⋅ κ ⋅ B B A ( 1 ) ) B_{\mathrm{BA}}(n)\le2B_{\mathrm{BA}}(\lceil n/2\rceil)+O(\kappa n^{2}+n\cdot\kappa\cdot B_{\mathrm{BA}}(1)) B BA ( n ) ≤ 2 B BA (⌈ n /2 ⌉) + O ( κ n 2 + n ⋅ κ ⋅ B BA ( 1 ))
≤ 2 B B A ( ⌈ n / 2 ⌉ ) + O ( κ n 2 ) \le2B_{\mathrm{BA}}(\lceil n/2\rceil)+O(\kappa n^{2}) ≤ 2 B BA (⌈ n /2 ⌉) + O ( κ n 2 )
Because byzantine agreement on a single party needs no communication (B B A ( 1 ) = 0 B_{\mathrm{BA}}(1)=0 B BA ( 1 ) = 0 ). A simple induction argument shows that B B A ( n ) = ∑ i = 0 log n O ( κ ) ⋅ 2 i ( n / 2 i ) 2 = O ( κ n 2 ) B_{\mathrm{BA}}(n)=\sum_{i=0}^{\log n}O(\kappa)\cdot2^{i}(n/2^{i})^{2}=O(\kappa n^{2}) B BA ( n ) = ∑ i = 0 l o g n O ( κ ) ⋅ 2 i ( n / 2 i ) 2 = O ( κ n 2 ) . Hence, we can find α > 0 \alpha>0 α > 0 such that:
B B A ( n ) ≤ α ⋅ κ n 2 ≤ α ⋅ ( κ n ) p n Because p ≥ 1 ≤ α ⋅ ( κ n ) p B κ 4 Because n ≤ B κ 4 ≤ α ⋅ B ⋅ ( κ n ) p κ 4 log 4 C N \begin{aligned}
B_{\mathrm{BA}}(n)\le\alpha\cdot\kappa n^{2} \\
&\le\alpha\cdot(\kappa n)^{p}n \qquad\text{Because } p\ge1 \\
&\le\alpha\cdot(\kappa n)^{p}B\kappa^{4} \qquad\text{Because } n\le B\kappa^{4} \\
&\le\alpha\cdot B\cdot(\kappa n)^{p}\kappa^{4}\log^{4C}N
\end{aligned} B BA ( n ) ≤ α ⋅ κ n 2 ≤ α ⋅ ( κn ) p n Because p ≥ 1 ≤ α ⋅ ( κn ) p B κ 4 Because n ≤ B κ 4 ≤ α ⋅ B ⋅ ( κn ) p κ 4 log 4 C N
We remark that we assume κ ≤ K log C N \kappa\le K\log^{C}N κ ≤ K log C N and n ≤ B κ 4 n\le B\kappa^{4} n ≤ B κ 4 so log n = o N ( log β N ) \log n=o_{N}(\log^{\beta}N) log n = o N ( log β N ) for any β > 0 \beta>0 β > 0 . Therefore, for N N N large enough, if D > 4 C D>4C D > 4 C , we can find B B B large enough such that:
B B A ( n ) ≤ A ( κ n ) p ( log ( N ) log ( n ) ) D = f ( n ) B_{\mathrm{BA}}(n)\le A(\kappa n)^{p}\left(\frac{\log(N)}{\log(n)}\right)^{D}=f(n) B BA ( n ) ≤ A ( κn ) p ( log ( n ) log ( N ) ) D = f ( n )
We can now consider the second case, where n > B κ 4 n>B\kappa^{4} n > B κ 4 . Fix B κ 4 < n ≤ N B\kappa^{4}<n\le N B κ 4 < n ≤ N and assume the invariant already holds for all 1 < n ′ < n 1<n'<n 1 < n ′ < n . We have m = b = c ( κ n ) p − 1 ≈ Θ ( κ n ) 0.3077 m=b=c(\kappa n)^{p-1}\approx\Theta(\kappa n)^{0.3077} m = b = c ( κn ) p − 1 ≈ Θ ( κn ) 0.3077 . As a consequence, we can remove out lower-order terms in the recurrence of B B A ( n ) B_{\mathrm{BA}}(n) B BA ( n ) and simplify it:
B B A ( n ) ≤ 2 B B A ( ⌈ n / 2 ⌉ ) + O ( c ( κ n ) p + c − 2 ( κ n ) 3 − 2 p ⋅ B B A ( ⌈ n / m ⌉ ) ) = 2 B B A ( ⌈ n / 2 ⌉ ) + C 1 ⋅ c ( κ n ) p + C 2 ⋅ c − 2 ( κ n ) 3 − 2 p ⋅ B B A ( ⌈ n / m ⌉ ) \begin{aligned}
B_{\mathrm{BA}}(n)\le2B_{\mathrm{BA}}(\lceil n/2\rceil)+O\left(c(\kappa n)^{p}+c^{-2}(\kappa n)^{3-2p}\cdot B_{\mathrm{BA}}(\lceil n/m\rceil)\right) \\
&=2B_{\mathrm{BA}}(\lceil n/2\rceil)+C_{1}\cdot c(\kappa n)^{p}+C_{2}\cdot c^{-2}(\kappa n)^{3-2p}\cdot B_{\mathrm{BA}}(\lceil n/m\rceil)
\end{aligned} B BA ( n ) ≤ 2 B BA (⌈ n /2 ⌉) + O ( c ( κn ) p + c − 2 ( κn ) 3 − 2 p ⋅ B BA (⌈ n / m ⌉) ) = 2 B BA (⌈ n /2 ⌉) + C 1 ⋅ c ( κn ) p + C 2 ⋅ c − 2 ( κn ) 3 − 2 p ⋅ B BA (⌈ n / m ⌉)
For some constant C 1 C_{1} C 1 and C 2 C_{2} C 2 . First, using the induction hypothesis:
2 B B A ( ⌈ n / 2 ⌉ ) ≤ 2 A ( κ n / 2 ) p ( log ( N ) log ( ⌈ n / 2 ⌉ ) ) D 2B_{\mathrm{BA}}(\lceil n/2\rceil)\le2A(\kappa n/2)^{p}\left(\frac{\log(N)}{\log(\lceil n/2\rceil)}\right)^{D} 2 B BA (⌈ n /2 ⌉) ≤ 2 A ( κn /2 ) p ( log (⌈ n /2 ⌉) log ( N ) ) D
≤ 2 1 − p ⋅ ( log ( ⌈ n / 2 ⌉ ) log ( n ) ) D f ( n ) \le2^{1-p}\cdot\left(\frac{\log(\lceil n/2\rceil)}{\log(n)}\right)^{D}f(n) ≤ 2 1 − p ⋅ ( log ( n ) log (⌈ n /2 ⌉) ) D f ( n )
We note that lim n → ∞ 2 1 − p ⋅ ( log ( ⌈ n / 2 ⌉ ) log ( n ) ) D = 2 1 − p < 1 \lim_{n\to\infty}2^{1-p}\cdot\left(\frac{\log(\lceil n/2\rceil)}{\log(n)}\right)^{D}=2^{1-p}<1 lim n → ∞ 2 1 − p ⋅ ( l o g ( n ) l o g (⌈ n /2 ⌉) ) D = 2 1 − p < 1 . Let h = ( 2 1 − p + 1 ) / 2 < 1 h=(2^{1-p}+1)/2<1 h = ( 2 1 − p + 1 ) /2 < 1 . For n n n large enough (which we can ensure by taking B B B large enough), we therefore have 2 B B A ( ⌈ n / 2 ⌉ ) ≤ h f ( n ) 2B_{\mathrm{BA}}(\lceil n/2\rceil)\le hf(n) 2 B BA (⌈ n /2 ⌉) ≤ h f ( n ) . We consider the second recursive term, using the induction hypothesis again and the fact that ⌈ n / m ⌉ ≤ 2 n / m \lceil n/m\rceil\le2n/m ⌈ n / m ⌉ ≤ 2 n / m :
C 2 ⋅ c − 2 ( κ n ) 3 − 2 p ⋅ B B A ( ⌈ n / m ⌉ ) ≤ C 2 ( κ n ) 3 − 2 p ⋅ A ( κ ⌈ n / m ⌉ ) p ( log ( N ) log ( ⌈ n / m ⌉ ) ) D ≤ C 2 ⋅ c − 2 ( κ n ) 3 − 2 p ( 2 / m ) p ( log n log ( ⌈ n / m ⌉ ) ) D f ( n ) ≤ C 2 ⋅ c − 2 − p ( κ n ) 3 − p − p 2 2 2 p ( log n log c + ( 2 − p ) log ( n ) ) D f ( n ) \begin{aligned}
C_2 \cdot c^{-2}(\kappa n)^{3-2p} \cdot B_{\mathrm{BA}}(\lceil n/m\rceil)
&\le C_2(\kappa n)^{3-2p} \cdot A(\kappa\lceil n/m\rceil)^p \left(\frac{\log(N)}{\log(\lceil n/m\rceil)}\right)^D \\
&\le C_2 \cdot c^{-2}(\kappa n)^{3-2p}(2/m)^p \left(\frac{\log n}{\log(\lceil n/m\rceil)}\right)^D f(n) \\
&\le C_2 \cdot c^{-2-p}(\kappa n)^{3-p-p^2}2^{2p}\left(\frac{\log n}{\log c+(2-p)\log(n)}\right)^D f(n)
\end{aligned} C 2 ⋅ c − 2 ( κn ) 3 − 2 p ⋅ B BA (⌈ n / m ⌉) ≤ C 2 ( κn ) 3 − 2 p ⋅ A ( κ ⌈ n / m ⌉ ) p ( log (⌈ n / m ⌉) log ( N ) ) D ≤ C 2 ⋅ c − 2 ( κn ) 3 − 2 p ( 2/ m ) p ( log (⌈ n / m ⌉) log n ) D f ( n ) ≤ C 2 ⋅ c − 2 − p ( κn ) 3 − p − p 2 2 2 p ( log c + ( 2 − p ) log ( n ) log n ) D f ( n )
We remark that p = ( 13 − 1 ) / 2 p=(\sqrt{13}-1)/2 p = ( 13 − 1 ) /2 is a solution of 3 − x − x 2 = 0 3-x-x^2=0 3 − x − x 2 = 0 . Because lim n → ∞ log n log c + ( 2 − p ) log ( n ) = 1 2 − p ≈ 1.43 \lim_{n\to\infty}\frac{\log n}{\log c+(2-p)\log(n)}=\frac{1}{2-p}\approx1.43 lim n → ∞ l o g c + ( 2 − p ) l o g ( n ) l o g n = 2 − p 1 ≈ 1.43 , for n n n large enough (which we can ensure again by taking B B B large enough), we have:
C 2 ⋅ c − 2 ( κ n ) 3 − 2 p ⋅ B B A ( ⌈ n / m ⌉ ) ≤ C 2 ⋅ c − 2 − p κ n 3 − p − p 2 2 p 1.5 D ⋅ f ( n ) ≤ ( 1 − h ) / 2 f ( n ) By taking c large enough \begin{aligned}
C_2 \cdot c^{-2}(\kappa n)^{3-2p} \cdot B_{\mathrm{BA}}(\lceil n/m\rceil)
&\le C_2 \cdot c^{-2-p} \kappa n^{3-p-p^2} 2^{p}1.5^D \cdot f(n) \\
&\le(1-h)/2 f(n)
\end{aligned}
\qquad\text{By taking }c\text{ large enough} C 2 ⋅ c − 2 ( κn ) 3 − 2 p ⋅ B BA (⌈ n / m ⌉) ≤ C 2 ⋅ c − 2 − p κ n 3 − p − p 2 2 p 1. 5 D ⋅ f ( n ) ≤ ( 1 − h ) /2 f ( n ) By taking c large enough
Finally, by taking A A A large enough such that C 1 ⋅ c ≤ A ⋅ ( 1 − h ) / 2 C_1\cdot c\le A\cdot(1-h)/2 C 1 ⋅ c ≤ A ⋅ ( 1 − h ) /2 , we have:
B B A ( n ) ≤ h f ( n ) + ( 1 − h ) / 2 f ( n ) + ( 1 − h ) / 2 f ( n ) = f ( n ) B_{\mathrm{BA}}(n)\le h f(n)+(1-h)/2 f(n)+(1-h)/2 f(n)=f(n) B BA ( n ) ≤ h f ( n ) + ( 1 − h ) /2 f ( n ) + ( 1 − h ) /2 f ( n ) = f ( n )
So the invariant is preserved. This concludes the proof.
Round complexity
In the previous section, we described how to choose the parameters m m m and b b b to obtain the desired complexity. We now show that given these parameters, our protocol has an optimal linear round complexity.
Using Lemma 16, we have:
R P V A ( n ) = O ( log n ) ( b + R M V B A ( n ) ) + ∑ i = 0 ⌈ log 3 / 2 n ⌉ R V A ( n ⋅ ( 2 / 3 ) i ) R_{\mathrm{PVA}}(n)=\mathcal{O}(\log n)(b+R_{\mathrm{MVBA}}(n))+\sum_{i=0}^{\lceil\log_{3/2}n\rceil}R_{\mathrm{VA}}(n\cdot(2/3)^i) R PVA ( n ) = O ( log n ) ( b + R MVBA ( n )) + i = 0 ∑ ⌈ l o g 3/2 n ⌉ R VA ( n ⋅ ( 2/3 ) i )
Using Lemma 19, we have:
R V A ( n ) = O ( n 1 / 3 ) ⋅ ( b + R M V B A ( n ) ) R_{\mathrm{VA}}(n)=\mathcal{O}(n^{1/3})\cdot(b+R_{\mathrm{MVBA}}(n)) R VA ( n ) = O ( n 1/3 ) ⋅ ( b + R MVBA ( n ))
Using the fact that ∑ i = 0 ⌈ log 3 / 2 n ⌉ ( n ⋅ ( ( 2 / 3 ) 1 / 3 ) i ) = O ( n ) \sum_{i=0}^{\lceil\log_{3/2}n\rceil}(n\cdot((2/3)^{1/3})^i)=\mathcal{O}(n) ∑ i = 0 ⌈ l o g 3/2 n ⌉ ( n ⋅ (( 2/3 ) 1/3 ) i ) = O ( n ) , we have:
∑ i = 0 ⌈ log 3 / 2 n ⌉ R V A ( n ⋅ ( 2 / 3 ) i ) = O ( n 1 / 3 ) ⋅ ( b + R M V B A ( n ) ) \sum_{i=0}^{\lceil\log_{3/2}n\rceil}R_{\mathrm{VA}}(n\cdot(2/3)^i)=\mathcal{O}(n^{1/3})\cdot(b+R_{\mathrm{MVBA}}(n)) i = 0 ∑ ⌈ l o g 3/2 n ⌉ R VA ( n ⋅ ( 2/3 ) i ) = O ( n 1/3 ) ⋅ ( b + R MVBA ( n ))
Using these two equations together, we get:
B P V A ( n , L ) = O ( n 1 / 3 ) ⋅ ( b + R M V B A ( n ) ) B_{\mathrm{PVA}}(n,L)=\mathcal{O}(n^{1/3})\cdot(b+R_{\mathrm{MVBA}}(n)) B PVA ( n , L ) = O ( n 1/3 ) ⋅ ( b + R MVBA ( n ))
We now look at the complexity of our weak agreement protocol:
R W B A ( n ) = R P C ( n ) + R V D ( n , κ n ) = O ( log n ) + R V D ( n ) = O ( log n ) + O ( 1 ) + R P V A ( ⌈ n / m ⌉ ) = O ( ( n / m ) 1 / 3 ) ( b + R M V B A ( ⌈ n / m ⌉ ) ) = O ( ( n / m ) 1 / 3 ) ( b + R B A ( ⌈ n / m ⌉ ) ) \begin{aligned}
R_{\mathrm{WBA}}(n)=R_{\mathrm{PC}}(n)+R_{\mathrm{VD}}(n,\kappa n) \\
&=O(\log n)+R_{\mathrm{VD}}(n) \\
&=O(\log n)+O(1)+R_{\mathrm{PVA}}(\lceil n/m\rceil) \\
&=O((n/m)^{1/3})(b+R_{\mathrm{MVBA}}(\lceil n/m\rceil)) \\
&=O((n/m)^{1/3})(b+R_{\mathrm{BA}}(\lceil n/m\rceil))
\end{aligned} R WBA ( n ) = R PC ( n ) + R VD ( n , κn ) = O ( log n ) + R VD ( n ) = O ( log n ) + O ( 1 ) + R PVA (⌈ n / m ⌉) = O (( n / m ) 1/3 ) ( b + R MVBA (⌈ n / m ⌉)) = O (( n / m ) 1/3 ) ( b + R BA (⌈ n / m ⌉))
Finally, we can consider the complexity of the binary agreement protocol, for n n n big enough, we have using Lemmas 21 and 22:
R B A ( n ) ≤ 2 R B A ( ⌈ n / 2 ⌉ ) + 4 R W B A ( n ) R_{\mathrm{BA}}(n)\leq2R_{\mathrm{BA}}(\lceil n/2\rceil)+4R_{\mathrm{WBA}}(n) R BA ( n ) ≤ 2 R BA (⌈ n /2 ⌉) + 4 R WBA ( n )
So in total, we have:
R B A ( n ) ≤ 2 R B A ( ⌈ n / 2 ⌉ ) + O ( ( n / m ) 1 / 3 ) ( b + R B A ( ⌈ n / m ⌉ ) ) R_{\mathrm{BA}}(n)\leq2R_{\mathrm{BA}}(\lceil n/2\rceil)+O((n/m)^{1/3})(b+R_{\mathrm{BA}}(\lceil n/m\rceil)) R BA ( n ) ≤ 2 R BA (⌈ n /2 ⌉) + O (( n / m ) 1/3 ) ( b + R BA (⌈ n / m ⌉))
Theorem 10. Using the same parameters for b b b and m m m as in Theorem 9, R B A ( n ) = O ( n ) R_{\mathrm{BA}}(n)=O(n) R BA ( n ) = O ( n ) .
Proof. As a reminder, in Theorem 9, we use
( m , b ) = { ( n , 1 ) If n ≤ B κ 4 ( c ( κ n ) p − 1 , c ( κ n ) p − 1 ) Otherwise (m,b)=
\begin{cases}
(n,1) & \text{If } n\leq B\kappa^4 \\
(c(\kappa n)^{p-1},c(\kappa n)^{p-1}) & \text{Otherwise}
\end{cases} ( m , b ) = { ( n , 1 ) ( c ( κn ) p − 1 , c ( κn ) p − 1 ) If n ≤ B κ 4 Otherwise For some constants B B B and c c c large enough and p = ( 13 − 1 ) / 2 p=(\sqrt{13}-1)/2 p = ( 13 − 1 ) /2 . We show by induction that for all n ≥ 1 n\geq1 n ≥ 1 :
R B A ( n ) ≤ A ( n − n 0.95 / 2 ) R_{\mathrm{BA}}(n)\leq A(n-n^{0.95}/2) R BA ( n ) ≤ A ( n − n 0.95 /2 ) For some constant A A A large enough. When n = 1 n=1 n = 1 , the protocol returns immediately its input, so R B A ( 1 ) ≤ 1 R_{\mathrm{BA}}(1)\leq1 R BA ( 1 ) ≤ 1 . Assume 1 < n ≤ B κ 4 1<n\leq B\kappa^4 1 < n ≤ B κ 4 . In this case, we have m = n m=n m = n and b = 1 b=1 b = 1 , so:
R B A ( n ) ≤ 2 R B A ( ⌈ n / 2 ⌉ ) + O ( 1 ) ⋅ ( 1 + R B A ( 1 ) ) = 2 R B A ( ⌈ n / 2 ⌉ ) + O ( 1 ) R_{\mathrm{BA}}(n)\leq2R_{\mathrm{BA}}(\lceil n/2\rceil)+O(1)\cdot(1+R_{\mathrm{BA}}(1))=2R_{\mathrm{BA}}(\lceil n/2\rceil)+O(1) R BA ( n ) ≤ 2 R BA (⌈ n /2 ⌉) + O ( 1 ) ⋅ ( 1 + R BA ( 1 )) = 2 R BA (⌈ n /2 ⌉) + O ( 1 ) A simple induction argument shows that R B A ( n ) ≤ ∑ i = 0 log n O ( 1 ) ⋅ 2 i = O ( n ) R_{\mathrm{BA}}(n)\leq\sum_{i=0}^{\log n}O(1)\cdot2^i=O(n) R BA ( n ) ≤ ∑ i = 0 l o g n O ( 1 ) ⋅ 2 i = O ( n ) , so with A A A large enough, we have R B A ( n ) ≤ A n / 2 ≤ A ( n − n 0.95 / 2 ) R_{\mathrm{BA}}(n)\leq An/2\leq A(n-n^{0.95}/2) R BA ( n ) ≤ A n /2 ≤ A ( n − n 0.95 /2 ) . We now consider n > B κ 4 n>B\kappa^4 n > B κ 4 . In this case, we have m = b = c ( κ n ) p − 1 m=b=c(\kappa n)^{p-1} m = b = c ( κn ) p − 1 . Because κ 4 < n \kappa^4<n κ 4 < n , we have κ = O ( n 1 / 4 ) \kappa=O(n^{1/4}) κ = O ( n 1/4 ) . Additionally, b = m = Θ ( ( κ n ) p − 1 ) = Ω ( n 0.3 ) b=m=\Theta((\kappa n)^{p-1})=\Omega(n^{0.3}) b = m = Θ (( κn ) p − 1 ) = Ω ( n 0.3 ) and m = b = O ( n 0.31 ) m=b=O(n^{0.31}) m = b = O ( n 0.31 ) . Therefore:
O ( ( n / m ) 1 / 3 ) ( b + R B A ( ⌈ n / m ⌉ ) ) = O ( ( n 0.7 ) 1 / 3 ) ( ( κ n ) 0.31 + R B A ( ⌈ n / m ⌉ ) ) ≤ O ( n 0.24 ) ( ( n 1.25 ) 0.31 + A ( 2 n 0.7 − n 0.7 ∗ 0.95 / 2 ) ) = O ( n 0.94 ) \begin{aligned}
O((n/m)^{1/3})(b+R_{\mathrm{BA}}(\lceil n/m\rceil))&=O((n^{0.7})^{1/3})((\kappa n)^{0.31}+R_{\mathrm{BA}}(\lceil n/m\rceil))\\
&\leq O(n^{0.24})((n^{1.25})^{0.31}+A(2n^{0.7}-n^{0.7*0.95}/2))\\
&=O(n^{0.94})
\end{aligned} O (( n / m ) 1/3 ) ( b + R BA (⌈ n / m ⌉)) = O (( n 0.7 ) 1/3 ) (( κn ) 0.31 + R BA (⌈ n / m ⌉)) ≤ O ( n 0.24 ) (( n 1.25 ) 0.31 + A ( 2 n 0.7 − n 0.7 ∗ 0.95 /2 )) = O ( n 0.94 ) For n n n large enough, which can be ensured by taking B B B large enough. Moreover, using the induction
hypothesis, we have:
2 R B A ( ⌈ n / 2 ⌉ ) ≤ 2 A ( ⌈ n / 2 ⌉ − ⌈ n / 2 ⌉ 0.95 / 2 ) ≤ A ( n − n 0.95 / 2 ) + 2 A − ( ⌈ n / 2 ⌉ 0.95 − n 0.95 / 2 ) ≤ A ( n − n 0.95 / 2 ) − Ω ( n 0.95 ) 2R_{\mathrm{BA}}(\lceil n/2\rceil) \le2A(\lceil n/2\rceil- \lceil n/2\rceil^{0.95}/2)
\le A(n - n^{0.95}/2) + 2A - (\lceil n/2\rceil^{0.95} - n^{0.95}/2)
\le A(n - n^{0.95}/2) - \Omega(n^{0.95}) 2 R BA (⌈ n /2 ⌉) ≤ 2 A (⌈ n /2 ⌉ − ⌈ n /2 ⌉ 0.95 /2 ) ≤ A ( n − n 0.95 /2 ) + 2 A − (⌈ n /2 ⌉ 0.95 − n 0.95 /2 ) ≤ A ( n − n 0.95 /2 ) − Ω ( n 0.95 )
Therefore, putting it together, we have:
R B A ( n ) ≤ A ( n − n 0.95 / 2 ) − Ω ( n 0.95 ) + O ( n 0.94 ) ≤ A ( n − n 0.95 / 2 ) R_{\mathrm{BA}}(n) \le A(n - n^{0.95}/2) - \Omega(n^{0.95}) + O(n^{0.94})
\le A(n - n^{0.95}/2) R BA ( n ) ≤ A ( n − n 0.95 /2 ) − Ω ( n 0.95 ) + O ( n 0.94 ) ≤ A ( n − n 0.95 /2 )
For n n n large enough, which can be ensured by taking B B B large enough. The induction is preserved, so this concludes the proof: we have R B A ( n ) = O ( n ) R_{\mathrm{BA}}(n) = O(n) R BA ( n ) = O ( n ) . So the protocol is linear.
Final Result
Theorem 1. There exists a deterministic byzantine agreement protocol with round complexity R B A ( n ) = O ( n ) R_{\mathrm{BA}}(n) = O(n) R BA ( n ) = O ( n ) and bit complexity B B A ( n ) = O ( κ ( 13 − 1 ) / 2 n ( 13 + 1 ) / 2 ) ≈ O ( κ 1.303 n 2.303 ) B_{\mathrm{BA}}(n) = O(\kappa^{(\sqrt{13}-1)/2}n^{(\sqrt{13}+1)/2}) \approx O(\kappa^{1.303}n^{2.303}) B BA ( n ) = O ( κ ( 13 − 1 ) /2 n ( 13 + 1 ) /2 ) ≈ O ( κ 1.303 n 2.303 ) .
Proof. Using Theorem 10, the round complexity of the protocol is linear and with Theorem 9, the per-party bit complexity is O ( κ ( 13 − 1 ) / 2 n ( 13 + 1 ) / 2 ) O(\kappa^{(\sqrt{13}-1)/2}n^{(\sqrt{13}+1)/2}) O ( κ ( 13 − 1 ) /2 n ( 13 + 1 ) /2 ) . Multiplying this by n n n , we get the expected upper bound on the total bit complexity.
Message and signature tags
We note that the protocols we have described so far have a main weakness: we expect some of them to run in parallel, but messages do not get sufficient information to know which instance of the recipient party it targets. Additionally, our protocols as they are written are weak to replay attacks: a byzantine could take a vote from an earlier or parallel vote and use it in a later vote for a different value. To fix this, we explain how to add tags and prefixes to messages and signatures to ensure that they are unique to a given instance of a protocol.
First, we remark that given an instance of byzantine agreement of size n n n , we never have instances of size n / 2 n/2 n /2 running concurrently. Only instances of size n / m n/m n / m will. Moreover, in each step, we only run at most a linear number of instances in parallel, and there is a bonded number of steps in a given recursion depth. As a consequence, a given instance executing at a given time and recursion depth with n n n parties can be uniquely identified with a O ( log n ) O(\log n) O ( log n ) -bit tag. As a consequence, the total tag size T ( n ) T(n) T ( n ) needed for any instance at a given time satisfies:
T ( n ) = O ( log n ) + T ( n / m ) T(n) = O(\log n) + T(n/m) T ( n ) = O ( log n ) + T ( n / m )
Because, as seen in Theorem 9, we use m = Ω ( n α ) m = \Omega(n^\alpha) m = Ω ( n α ) for some α > 0 \alpha> 0 α > 0 , an immediate induction shows that T ( n ) = O ( log n ) T(n) = O(\log n) T ( n ) = O ( log n ) . Therefore, a O ( log n ) O(\log n) O ( log n ) -bit tag added as a prefix to each message is sufficient to ensure that a party can identify which instance of the protocol a message targets. We remark that all messages exchanged in our protocols already have size Ω ( log n ) \Omega(\log n) Ω ( log n ) , so this does not change the bit complexity of our protocols.
We now consider signatures and replay attacks. Adding the previous tag as a prefix to signatures is enough to prevent replay attacks across concurrent instances. However, they are not enough for attacks executed using a signature from an earlier instance in a later instance. A simple workaround is to add the current round number as an additional prefix to each signature, and send it along the signature. Because the protocol has a linear number of rounds, this only adds an additional O ( log n ) = O ( κ ) O(\log n) = O(\kappa) O ( log n ) = O ( κ ) bit to each signature. If the round number of a signature does no match what is expected of the current instance, the whole message is discarded.
Conclusion
In this paper, we present the first subcubic deterministic byzantine agreement protocol in the synchronous setting with optimal resiliency t < n / 2 t < n/2 t < n /2 . To do so, we introduce multiple new approaches, including better recursive techniques, use of fault-tolerant expanders and dispersers as well as fair cake-cutting techniques. We remark that our protocol has an unusual irrational exponent, being ( 13 + 1 ) / 2 (\sqrt{13} + 1)/2 ( 13 + 1 ) /2 .
There are still open questions regarding this problem. The first one would be to close the gap, which is still of a factor n 0.303 n^{0.303} n 0.303 between the quadratic lower bound of Dolev and Reischuk [14 ] and our upper bound. We remark that our proof gathering protocol is already near-optimal. As such, any improvement to validated dispersal, which we believe could be simplified would yield a more efficient algorithm.
Expander and Disperser Graphs
A graph is said to be explicit if it can be constructed deterministically in polynomial time.
Theorem 11. For any constant 0 < α < 1 0 < \alpha< 1 0 < α < 1 , 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n , there exists an explicit directed graph G = ( V , E ) G = (V, E) G = ( V , E ) on n n n vertices where each vertex has out-degree m m m and such that G G G is a ( α n , n − 4 α − 1 n / m ) (\alpha n, n - 4\alpha^{-1}n/m) ( α n , n − 4 α − 1 n / m ) -disperser.
Proof. Let 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n , we explain how to build explicitly such a graph and how to get G G G from it.
We consider a regular Ramanujan bipartite graph H = L ∪ R H = L \cup R H = L ∪ R on 2 n 2n 2 n nodes (n n n on each side) with degree d = m d = m d = m . Cohen [8 ] explains how to build such a graph in polynomial time. We want to show that this graph is a ( α n , n − 4 α − 1 n / m ) (\alpha n, n - 4\alpha^{-1}n/m) ( α n , n − 4 α − 1 n / m ) bipartite disperser. To do so, consider a set S S S of α n \alpha n α n vertices in L L L , let N ( S ) N(S) N ( S ) be the neighbors of S S S in R R R . We consider T = R ∖ N ( S ) T = R \setminus N(S) T = R ∖ N ( S ) , there is no edge between S S S and T T T . We want to prove that ∣ T ∣ ≤ 4 α − 1 n / m |T| \le4\alpha^{-1}n/m ∣ T ∣ ≤ 4 α − 1 n / m .
We remark that by definition of a bipartite Ramanujan graph, the non-trivial eigenvalues of H H H have absolute value at most 2 d − 1 2\sqrt{d-1} 2 d − 1 . We can therefore use the bipartite expander mixing lemma (a proof of it can be found in [22 Lemma 4.1] ):
∣ e ( S , T ) − d ∣ S ∣ ∣ T ∣ n ∣ ≤ 2 d − 1 ⋅ ∣ S ∣ ∣ T ∣ \left|e(S,T)-d\frac{|S||T|}{n}\right| \le2\sqrt{d-1}\cdot\sqrt{|S||T|} e ( S , T ) − d n ∣ S ∣∣ T ∣ ≤ 2 d − 1 ⋅ ∣ S ∣∣ T ∣
Where e ( S , T ) e(S,T) e ( S , T ) is the number of edges between S S S and T T T , which by our choice of T T T is 0. Using d = n α d=n^\alpha d = n α :
d ∣ S ∣ ∣ T ∣ n ≤ 2 d ⋅ ∣ S ∣ ∣ T ∣ d ∣ S ∣ ∣ T ∣ ≤ 2 n d ∣ S ∣ ∣ T ∣ ≤ 4 n 2 m ( α n ) ∣ T ∣ ≤ 4 n 2 ∣ T ∣ ≤ 4 α − 1 n / m \begin{aligned}
d\frac{|S||T|}{n} &\le2\sqrt{d}\cdot\sqrt{|S||T|} \\
\sqrt{d}|S||T| &\le2n \\
d|S||T| &\le4n^2 \\
m(\alpha n)|T| &\le4n^2 \\
|T| &\le4\alpha^{-1}n/m
\end{aligned} d n ∣ S ∣∣ T ∣ d ∣ S ∣∣ T ∣ d ∣ S ∣∣ T ∣ m ( α n ) ∣ T ∣ ∣ T ∣ ≤ 2 d ⋅ ∣ S ∣∣ T ∣ ≤ 2 n ≤ 4 n 2 ≤ 4 n 2 ≤ 4 α − 1 n / m
Therefore, N ( S ) ≥ n − 4 α − 1 n / m N(S) \ge n - 4\alpha^{-1}n/m N ( S ) ≥ n − 4 α − 1 n / m , So G 1 G_1 G 1 is indeed a bipartite disperser.
To build G = ( V , E ) G = (V,E) G = ( V , E ) we then identify G 1 G_1 G 1 with the incidence graph of G G G , i.e. we identify V V V with both L L L and R R R , and we add an edge ( u , v ) (u,v) ( u , v ) in G G G if there exists an edge from u u u in L L L to v v v in R R R . By construction, G G G is a directed graph with out-degree m m m and is a ( α n , n − 4 α − 1 n / m ) (\alpha n,n - 4\alpha^{-1}n/m) ( α n , n − 4 α − 1 n / m ) -disperser.
Using the previous theorem, we obtain a biparte version where both sides are not equal:
Theorem 12. For any 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n , there exists an explicit bipartite graph G = ( L ∪ R , E ) G = (L \cup R, E) G = ( L ∪ R , E ) with ∣ L ∣ = n |L| = n ∣ L ∣ = n , ∣ R ∣ = m |R| = m ∣ R ∣ = m and constant left degree such that G G G is a ( n / 3 , 5 m / 6 ) (n/3,5m/6) ( n /3 , 5 m /6 ) bipartite disperser.
Proof. As seen in the proof of the previous theorem, we can build an explicit bipartite graph G 1 = ( L 1 ∪ R 1 , E 1 ) G_1 = (L_1 \cup R_1, E_1) G 1 = ( L 1 ∪ R 1 , E 1 ) with ∣ L 1 ∣ = ∣ R 1 ∣ = n |L_1| = |R_1| = n ∣ L 1 ∣ = ∣ R 1 ∣ = n such that G 1 G_1 G 1 is a ( n / 3 , n − n / 18 ) (n/3,n - n/18) ( n /3 , n − n /18 ) bipartite disperser by using α = 1 / 3 \alpha= 1/3 α = 1/3 and degree d = 4 ∗ 3 ∗ 18 = O ( 1 ) d = 4 * 3 * 18 = O(1) d = 4 ∗ 3 ∗ 18 = O ( 1 ) .
We now partition R 1 R_1 R 1 into m m m groups, each of size ⌊ n / m ⌋ \lfloor n/m\rfloor ⌊ n / m ⌋ or ⌈ n / m ⌉ \lceil n/m\rceil ⌈ n / m ⌉ . Because m ≤ n m \le n m ≤ n , ⌊ n / m ⌋ ≥ ⌈ n / m ⌉ / 2 \lfloor n/m\rfloor\ge\lceil n/m\rceil/2 ⌊ n / m ⌋ ≥ ⌈ n / m ⌉ /2 . We then build G G G by identifying L L L with L 1 L_1 L 1 and R R R with the m m m groups of R 1 R_1 R 1 and defining the edges such that for each edge ( u , v ) ∈ E 1 (u,v) \in E_1 ( u , v ) ∈ E 1 , we add an edge ( u , v ′ ) ∈ E (u,v') \in E ( u , v ′ ) ∈ E where v ′ v' v ′ is the group to which v v v belongs. By construction, G G G has left degree d = 4 ∗ 3 ∗ 18 d = 4 * 3 * 18 d = 4 ∗ 3 ∗ 18 which is constant.
We note that G G G can be a multigraph, but each edge of G G G can be mapped to an edge in G 1 G_1 G 1 . Because G 1 G_1 G 1 is d d d -regular and ⌊ n / m ⌋ ≥ ⌈ n / m ⌉ / 2 \lfloor n/m\rfloor\ge\lceil n/m\rceil/2 ⌊ n / m ⌋ ≥ ⌈ n / m ⌉ /2 , This implies that vertices in R R R are composed of at least n / ( 3 m ) n/(3m) n / ( 3 m ) vertices from R 1 R_1 R 1 . Consider a set S ⊆ L S \subseteq L S ⊆ L of size ∣ S ∣ ≥ n / 10 |S| \ge n/10 ∣ S ∣ ≥ n /10 , let Q = R ∖ N G ( S ) Q = R \setminus N_G(S) Q = R ∖ N G ( S ) . We want to show that ∣ Q ∣ ≤ m / 6 |Q| \le m/6 ∣ Q ∣ ≤ m /6 . We note that N G 1 ( S ) ≥ n − n / 18 N_{G_1}(S) \ge n - n/18 N G 1 ( S ) ≥ n − n /18 , which would imply that Q Q Q is composed of at most n / 18 n/18 n /18 parties in R 1 R_1 R 1 . Because each party in R R R is composed of at least n / ( 3 m ) n/(3m) n / ( 3 m ) vertices from R 1 R_1 R 1 , and there cannot be an edge from S S S to Q Q Q , we have ∣ Q ∣ ≤ ( n / 18 ) / ( n / ( 3 m ) ) = m / 6 |Q| \le(n/18)/(n/(3m)) = m/6 ∣ Q ∣ ≤ ( n /18 ) / ( n / ( 3 m )) = m /6 . Therefore, G G G is a ( n / 10 , 5 m / 6 ) (n/10, 5m/6) ( n /10 , 5 m /6 ) bipartite disperser.
For the following theorem, we first show an intermediate lemma:
Lemma 20. Let G = ( L ∪ R , E ) G = (L \cup R, E) G = ( L ∪ R , E ) be a D D D -regular Ramanujan bipartite graph, with each side having n n n nodes. Let S ⊂ L S \subset L S ⊂ L and H = { v ∈ R , N ( v ) ⊆ H } H = \{v \in R, N(v) \subseteq H\} H = { v ∈ R , N ( v ) ⊆ H } (i.e H H H is the set of nodes whose edges all come from S S S ). Then:
∣ H ∣ ≤ 4 ∣ S ∣ D ⋅ ( 1 − ∣ S ∣ / n ) 2 |H| \le\frac{4|S|}{D \cdot(1 - |S|/n)^2} ∣ H ∣ ≤ D ⋅ ( 1 − ∣ S ∣/ n ) 2 4∣ S ∣
Proof. By definition, we have e ( S , H ) = ∣ H ∣ ⋅ D e(S, H) = |H| \cdot D e ( S , H ) = ∣ H ∣ ⋅ D . We can therefore use the bipartite expander lemma on S S S and H H H ([22 Lemma 4.1] ):
∣ e ( S , H ) − D ⋅ ∣ S ∣ ∣ H ∣ n ∣ ≤ 2 D − 1 ∣ S ∣ ∣ H ∣ \left|e(S,H) - D \cdot\frac{|S||H|}{n}\right| \le2\sqrt{D-1}\sqrt{|S||H|} e ( S , H ) − D ⋅ n ∣ S ∣∣ H ∣ ≤ 2 D − 1 ∣ S ∣∣ H ∣
D ⋅ ∣ H ∣ ( 1 − ∣ S ∣ / n ) ≤ 2 D ∣ S ∣ ∣ H ∣ D \cdot|H|(1 - |S|/n) \le2\sqrt{D|S||H|} D ⋅ ∣ H ∣ ( 1 − ∣ S ∣/ n ) ≤ 2 D ∣ S ∣∣ H ∣
D ⋅ ∣ H ∣ ( 1 − ∣ S ∣ / n ) 2 ≤ 4 ∣ S ∣ D \cdot|H|(1 - |S|/n)^2 \le4|S| D ⋅ ∣ H ∣ ( 1 − ∣ S ∣/ n ) 2 ≤ 4∣ S ∣
∣ H ∣ ≤ 4 ∣ S ∣ D ⋅ ( 1 − ∣ S ∣ / n ) 2 |H| \le\frac{4|S|}{D \cdot(1 - |S|/n)^2} ∣ H ∣ ≤ D ⋅ ( 1 − ∣ S ∣/ n ) 2 4∣ S ∣
:::
Theorem 2. For any α ∈ ] 0 , 1 [ \alpha\in]0, 1[ α ∈ ] 0 , 1 [ , β > 1 \beta> 1 β > 1 , there exists D > 0 D > 0 D > 0 such that for any n > 0 n > 0 n > 0 , there exists an explicit graph G = ( V , E ) G = (V, E) G = ( V , E ) on n n n vertices of bounded degree D D D . Additionally, for any C ⊂ V C \subset V C ⊂ V such that ∣ C ∣ ≤ α ⋅ n |C| \le\alpha\cdot n ∣ C ∣ ≤ α ⋅ n , there exists S ⊆ V S \subseteq V S ⊆ V such that S ∩ C = ∅ S \cap C = \emptyset S ∩ C = ∅ , ∣ S ∣ ≥ n − β ⋅ ∣ C ∣ |S| \ge n - \beta\cdot|C| ∣ S ∣ ≥ n − β ⋅ ∣ C ∣ , and the induced subgraph G [ S ] G[S] G [ S ] is connected and has diameter O ( log n ) O(\log n) O ( log n ) .
Proof. Let n > 0 n > 0 n > 0 , the graph we obtain uses the construction from [26 ] , which is essentially a weaker version of this theorem with fixed α = 1 / 72 \alpha= 1/72 α = 1/72 and β = 6 \beta= 6 β = 6 , as a basis. Using [26 ] , there exists D 1 > 0 D_1 > 0 D 1 > 0 independent of n n n and an explicit D 1 D_1 D 1 -regular graph G 1 = ( V 1 , E 1 ) G_1 = (V_1, E_1) G 1 = ( V 1 , E 1 ) on n n n vertices such that for any C ⊂ V 1 C \subset V_1 C ⊂ V 1 satisfying ∣ C ∣ ≤ n / 72 |C| \le n/72 ∣ C ∣ ≤ n /72 , one can find S ⊂ V 1 S \subset V_1 S ⊂ V 1 such that S ∩ C = ∅ S \cap C = \emptyset S ∩ C = ∅ , ∣ S ∣ ≥ n − 6 ∣ S ∣ |S| \ge n - 6|S| ∣ S ∣ ≥ n − 6∣ S ∣ and the induced subgraph G 1 [ S ] G_1[S] G 1 [ S ] is connected and of diameter O ( log n ) O(\log n) O ( log n ) .
We now consider D 2 = D 2 ( α , β ) D_2 = D_2(\alpha, \beta) D 2 = D 2 ( α , β ) which we will explicit later in this proof. We consider the D 2 D_2 D 2 -regular bipartite Ramanujan graph G 2 = ( L ∪ R , E 2 ) G_2 = (L \cup R, E_2) G 2 = ( L ∪ R , E 2 ) with n n n vertices on each side, such a graph can be built in polynomial time [8 ] . We now explain how to construct the resulting graph G = ( V , E ) G = (V, E) G = ( V , E ) . We identify V V V with L L L and V 1 V_1 V 1 with R R R . Then:
E = { ( u , v ) , ∃ ( u ′ , v ′ ) , ( u , u ′ ) ∈ E 2 , ( v , v ′ ) ∈ E 2 , ( u ′ , v ′ ) } E = \{(u,v), \exists(u',v'), (u,u') \in E_2, (v,v') \in E_2, (u',v')\} E = {( u , v ) , ∃ ( u ′ , v ′ ) , ( u , u ′ ) ∈ E 2 , ( v , v ′ ) ∈ E 2 , ( u ′ , v ′ )}
What we essentially do is layer G 2 G_2 G 2 on top of G 1 G_1 G 1 : G 2 G_2 G 2 maps vertices to groups (a vertex belongs to D 2 D_2 D 2 groups) two vertices are linked in G G G if they each belong to a group which are connected in G 1 G_1 G 1 . A consequence is that vertices have degree at most D 1 ⋅ D 2 D_1 \cdot D_2 D 1 ⋅ D 2 which is independent of n n n .
We now want to prove that G G G satisfies the properties of the theorem with a proper choice of D 2 D_2 D 2 . Let C ⊂ V C \subset V C ⊂ V such that ∣ C ∣ ≤ α ⋅ n |C| \le\alpha\cdot n ∣ C ∣ ≤ α ⋅ n . Let H = { v ∈ R , N G 2 ( v ) ⊆ C } H = \{v \in R, N_{G_2}(v) \subseteq C\} H = { v ∈ R , N G 2 ( v ) ⊆ C } . We want to show that ∣ H ∣ ≤ n / 72 |H| \le n/72 ∣ H ∣ ≤ n /72 and that ∣ H ∣ = O ( 1 ) ⋅ ∣ C ∣ |H| = O(1) \cdot|C| ∣ H ∣ = O ( 1 ) ⋅ ∣ C ∣ . Using Lemma 20, we have ∣ H ∣ ≤ 4 ∣ C ∣ D 2 ( 1 − ∣ C ∣ / n ) 2 |H| \le\frac{4|C|}{D_2(1-|C|/n)^2} ∣ H ∣ ≤ D 2 ( 1 − ∣ C ∣/ n ) 2 4∣ C ∣ . We remark that ∣ C ∣ ≤ α ⋅ n |C| \le\alpha\cdot n ∣ C ∣ ≤ α ⋅ n so ∣ H ∣ ≤ 4 ∣ C ∣ D 2 ( 1 − α ) 2 ≤ 4 n D 2 ( 1 − α ) 2 |H| \le\frac{4|C|}{D_2(1-\alpha)^2} \le\frac{4n}{D_2(1-\alpha)^2} ∣ H ∣ ≤ D 2 ( 1 − α ) 2 4∣ C ∣ ≤ D 2 ( 1 − α ) 2 4 n .
Therefore, by choosing D 2 ≥ 288 / ( 1 − α ) 2 D_2 \ge288/(1-\alpha)^2 D 2 ≥ 288/ ( 1 − α ) 2 , we have ∣ H ∣ ≤ n / 72 |H| \le n/72 ∣ H ∣ ≤ n /72 . As a consequence, by construction of G 1 G_1 G 1 , one can find K ⊆ V 1 K \subseteq V_1 K ⊆ V 1 such that K ∩ H = ∅ K \cap H = \emptyset K ∩ H = ∅ , ∣ K ∣ ≥ n − 6 ∣ H ∣ ≥ 11 n / 12 |K| \ge n - 6|H| \ge11n/12 ∣ K ∣ ≥ n − 6∣ H ∣ ≥ 11 n /12 and G 1 [ K ] G_1[K] G 1 [ K ] is connected with diameter O ( log n ) O(\log n) O ( log n ) .
Let S = N G 2 ( K ) ∖ C S = N_{G_2}(K) \setminus C S = N G 2 ( K ) ∖ C . We want to show that G [ S ] G[S] G [ S ] is connected, has diameter O ( log n ) O(\log n) O ( log n ) and ∣ S ∣ ≥ n − β ∣ C ∣ |S| \ge n - \beta|C| ∣ S ∣ ≥ n − β ∣ C ∣ . To do so, consider v 1 , v 2 ∈ S v_1, v_2 \in S v 1 , v 2 ∈ S , by definition, we can find w 1 , w 2 ∈ K w_1, w_2 \in K w 1 , w 2 ∈ K such that ( v 1 , w 1 ) , ( v 2 , w 2 ) ∈ E 2 (v_1,w_1),(v_2,w_2) \in E_2 ( v 1 , w 1 ) , ( v 2 , w 2 ) ∈ E 2 . Because G 1 [ K ] G_1[K] G 1 [ K ] has diameter O ( log n ) O(\log n) O ( log n ) , one can find w 1 = u 1 , u 2 , … , u k = w 2 w_1 = u_1, u_2, \ldots, u_k = w_2 w 1 = u 1 , u 2 , … , u k = w 2 with k = O ( log n ) k = O(\log n) k = O ( log n ) such that u 1 → u 2 → … → u k u_1 \to u_2 \to\ldots\to u_k u 1 → u 2 → … → u k forms a path in G 2 G_2 G 2 . By definition of K K K , for each u i u_i u i , one can find p i ∈ V ∖ C p_i \in V \setminus C p i ∈ V ∖ C such that ( p i , u i ) ∈ E 1 (p_i,u_i) \in E_1 ( p i , u i ) ∈ E 1 , so p i ∈ S p_i \in S p i ∈ S (otherwise we would have u i ∈ H u_i \in H u i ∈ H ). We remark that v 1 → p 2 → … → p k − 1 → v 2 v_1 \to p_2 \to\ldots\to p_{k-1} \to v_2 v 1 → p 2 → … → p k − 1 → v 2 is by construction a path of length k = O ( log n ) k = O(\log n) k = O ( log n ) between v 1 v_1 v 1 and v 2 v_2 v 2 contains within S S S .
It remains to show that ∣ S ∣ ≥ n − β ∣ C ∣ |S| \ge n - \beta|C| ∣ S ∣ ≥ n − β ∣ C ∣ to complete the proof. Because S = N G 2 ( K ) ∖ C S = N_{G_2}(K) \setminus C S = N G 2 ( K ) ∖ C , it is enough to show that ∣ N G 2 ( K ) ∣ ≥ n − ( β − 1 ) ∣ C ∣ |N_{G_2}(K)| \ge n - (\beta- 1)|C| ∣ N G 2 ( K ) ∣ ≥ n − ( β − 1 ) ∣ C ∣ (which is possible as β > 1 \beta> 1 β > 1 ). Let P = { u ∈ L , N ( u ) ∩ K = ∅ } P = \{u \in L, N(u) \cap K = \emptyset\} P = { u ∈ L , N ( u ) ∩ K = ∅ } . We remark that by definition, N G 2 ( K ) N_{G_2}(K) N G 2 ( K ) and P P P form a partition of L L L , so ∣ N G 2 ( K ) ∣ + ∣ P ∣ = n |N_{G_2}(K)| + |P| = n ∣ N G 2 ( K ) ∣ + ∣ P ∣ = n and thus it is enough to prove that ∣ P ∣ ≤ ( β − 1 ) ⋅ ∣ C ∣ |P| \le(\beta- 1) \cdot|C| ∣ P ∣ ≤ ( β − 1 ) ⋅ ∣ C ∣ . We remark that P P P can be rewritten as P = { u ∈ L , N ( u ) ⊆ R ∖ K } P = \{u \in L, N(u) \subseteq R \setminus K\} P = { u ∈ L , N ( u ) ⊆ R ∖ K } , so we can use Lemma 20 (both sides of a Ramanujan graph have the same properties):
∣ P ∣ ≤ 4 ∣ R ∖ K ∣ D 2 ( 1 − ∣ R ∖ K ∣ / n ) 2 ≤ 4 ( n − ∣ K ∣ ) D 2 ( 1 − ( n − ∣ K ∣ ) / n ) 2 ≤ 4 ⋅ 6 ∣ H ∣ D 2 ⋅ ( 1 / 12 ) 2 ≤ 3456 ⋅ 4 ∣ C ∣ D 2 2 ( 1 − α ) 2 \begin{aligned}
|P| &\le\frac{4|R \setminus K|}{D_2(1-|R \setminus K|/n)^2}\\
&\le\frac{4(n-|K|)}{D_2(1-(n-|K|)/n)^2}\\
&\le\frac{4\cdot6|H|}{D_2\cdot(1/12)^2}\\
&\le3456\cdot\frac{4|C|}{D_2^2(1-\alpha)^2}
\end{aligned} ∣ P ∣ ≤ D 2 ( 1 − ∣ R ∖ K ∣/ n ) 2 4∣ R ∖ K ∣ ≤ D 2 ( 1 − ( n − ∣ K ∣ ) / n ) 2 4 ( n − ∣ K ∣ ) ≤ D 2 ⋅ ( 1/12 ) 2 4 ⋅ 6∣ H ∣ ≤ 3456 ⋅ D 2 2 ( 1 − α ) 2 4∣ C ∣
Because ∣ K ∣ ≥ n − 6 ∣ H ∣ ≥ 11 n / 12 |K| \ge n - 6|H| \ge11n/12 ∣ K ∣ ≥ n − 6∣ H ∣ ≥ 11 n /12
Thus, by taking D 2 ≥ 13824 ( 1 − α ) 2 ( β − 1 ) D_2 \ge\frac{\sqrt{13824}}{(1-\alpha)^2(\beta-1)} D 2 ≥ ( 1 − α ) 2 ( β − 1 ) 13824 , we get ∣ P ∣ ≤ ( β − 1 ) n |P| \le(\beta- 1)n ∣ P ∣ ≤ ( β − 1 ) n and in turn ∣ S ∣ ≥ n − β ∣ C ∣ |S| \ge n - \beta|C| ∣ S ∣ ≥ n − β ∣ C ∣ , so S S S satisfies the conditions.
Finally, by taking D 2 = D 2 ( α , β ) = max ( 288 ( 1 − α ) 2 , 13824 ( 1 − α ) 2 ( β − 1 ) ) D_2 = D_2(\alpha,\beta) = \max\left(\frac{288}{(1-\alpha)^2},\frac{\sqrt{13824}}{(1-\alpha)^2(\beta-1)}\right) D 2 = D 2 ( α , β ) = max ( ( 1 − α ) 2 288 , ( 1 − α ) 2 ( β − 1 ) 13824 ) , the assumptions above are held. □
Missing protocols
We provide here the missing protocols used in our paper. The reason they are only presented here is that they are common knowledge or straightforward implementation of existing work.
Byzantine Agreement
We present here the framework given by Momose and Ren [24 ] to reduce byzantine agreement to weak agreement. We note that their protocol only reduces byzantine agreement to graded agreement, which we give a definition below. We also give a simple reduction from graded agreement to weak agreement, which together show the overall reduction.
Definition 11. A protocol where each party is given an input v i n ∈ { 0 , 1 } v_{\mathrm{in}} \in\{0,1\} v in ∈ { 0 , 1 } and decides an output v o u t ∈ { 0 , 1 } v_{\mathrm{out}} \in\{0,1\} v out ∈ { 0 , 1 } and a grade g ∈ { 0 , 1 } g \in\{0,1\} g ∈ { 0 , 1 } satisfies graded agreement if:
ByzantineAgreement(vin)
Protocol for byzantine agreement for a party p with input vin
If |P| < M for some constant M, use an inefficient cubic byzantine agreement protocol instead.
Partition P into two halves P1 and P2.
(v, g) ← GradedAgreementP(vin)
if p ∈ P1 then
o ← ByzantineAgreementP1(v)
Send o to all parties
end if
if g = 0 and received the same o from a majority of P1 then
v ← o
end if
(v, g) ← GradedAgreementP(v)
if p ∈ P2 then
o ← ByzantineAgreementP2(v)
Send o to all parties
end if
if g = 0 and received the same o from a majority of P2 then
v ← o
end if
Return v
Theorem 13. [24 Lemma 9] ByzantineAgreement Satisfies byzantine agreement.
Lemma 21. The protocol is byzantine robust, has round complexity R B A ( n ) = R B A ( ⌊ n / 2 ⌋ ) + R B A ( ⌈ n / 2 ⌉ ) + 2 R G B A ( n ) + O ( 1 ) R_{\mathrm{BA}}(n) = R_{\mathrm{BA}}(\lfloor n/2 \rfloor) + R_{\mathrm{BA}}(\lceil n/2 \rceil) + 2R_{\mathrm{GBA}}(n) + O(1) R BA ( n ) = R BA (⌊ n /2 ⌋) + R BA (⌈ n /2 ⌉) + 2 R GBA ( n ) + O ( 1 ) and per-party bit complexity B B A ( n ) = B B A ( ⌊ n / 2 ⌋ ) + B B A ( ⌈ n / 2 ⌉ ) + 2 B G B A ( n ) + O ( n κ ) B_{\mathrm{BA}}(n) = B_{\mathrm{BA}}(\lfloor n/2 \rfloor) + B_{\mathrm{BA}}(\lceil n/2 \rceil) + 2B_{\mathrm{GBA}}(n) + O(n\kappa) B BA ( n ) = B BA (⌊ n /2 ⌋) + B BA (⌈ n /2 ⌉) + 2 B GBA ( n ) + O ( nκ ) .
Graded agreement
GradedAgreement(vin)
Protocol for graded agreement for a party p with input vin
v ← WeakAgreement(vin)
w ← 1 if v ∈ {1, ⊥} else 0
b ← WeakAgreement(w)
if v = 1 then
Return (1, 1)
else if b = 1 then
Return (1, 0)
else if b = 0 then
Return (0, 1)
else
Return ( 0 , 0 ) (0, 0) ( 0 , 0 ) end if
Theorem 14. GradedAgreement satisfies graded agreement. Proof. Termination follows from weak agreement’s termination. If all honest parties have the same input 1, then using weak agreement’s validity, v = 1 v = 1 v = 1 and then b = 1 b = 1 b = 1 , so all honest parties return ( 1 , 1 ) (1, 1) ( 1 , 1 ) . If all honest parties have the same input 0, then similarly, v = 0 v = 0 v = 0 and then b = 0 b = 0 b = 0 , so all honest parties return ( 0 , 1 ) (0, 1) ( 0 , 1 ) . Thus, validity is satisfied.
We now consider graded agreement. Assume an honest party p i p_i p i returns ( 1 , 1 ) (1, 1) ( 1 , 1 ) . Then v i = 1 v_i = 1 v i = 1 , so using weak agreement, all honest parties have v ∈ { 1 , ⊥ } v \in\{1, \perp\} v ∈ { 1 , ⊥ } , so they all have w = 1 w = 1 w = 1 , therefore using weak agreement’s validity, all honest parties have b = 1 b = 1 b = 1 , and will decide either ( 1 , 1 ) (1, 1) ( 1 , 1 ) or ( 1 , 0 ) (1, 0) ( 1 , 0 ) . We consider the second case where p i p_i p i returns ( 0 , 1 ) (0, 1) ( 0 , 1 ) . This implies that b i = 0 b_i = 0 b i = 0 . We note that the previous part shows that no honest party could decide ( 1 , 1 ) (1, 1) ( 1 , 1 ) , so it only remains to show that ( 1 , 0 ) (1, 0) ( 1 , 0 ) cannot be decided. But if a party p j p_j p j decides ( 1 , 0 ) (1, 0) ( 1 , 0 ) , then b j = 1 b_j = 1 b j = 1 , which contradicts weak agreement, given that b i = 0 b_i = 0 b i = 0 . Thus, graded agreement is satisfied.
Lemma 22. The protocol is byzantine robust, has round complexity R G B A ( n ) = 2 R W B A ( n ) R_{\mathrm{GBA}}(n) = 2R_{\mathrm{WBA}}(n) R GBA ( n ) = 2 R WBA ( n ) and per-party bit complexity B G B A ( n ) = 2 B W B A ( n ) B_{\mathrm{GBA}}(n) = 2B_{\mathrm{WBA}}(n) B GBA ( n ) = 2 B WBA ( n ) .
Multivalued Byzantine Agreement
Although our target is binary byzantine agreement, our protocol itself relies on multivalued byzantine agreement, i.e when the value to agree on is an L L L -bit input. We give a simple reduction from multivalued byzantine agreement to binary byzantine agreement, which only uses κ + 1 \kappa+ 1 κ + 1 calls to binary byzantine agreement.
MVBA($v_{\mathrm{in}}$)
Protocol for multi-valued for a party $p_j$ with input $v_{\mathrm{in}}$
Let $h = h_1 \ldots h_\kappa$ be the binary representation of the accumulator of $v_{\mathrm{in}}$.
in parallel $i = 1, \ldots, \kappa$ do
$d_i \leftarrow \mathrm{ByzantineAgreement}(h_i)$
$b \leftarrow 1$ if $h = d$ else 0
$a \leftarrow \mathrm{ByzantineAgreement}(b)$
if $a = 0$ then
Return $\perp$
end if
if $h = d$ then
Encode $v_{\mathrm{in}}$ into $n$ shares along their witnesses
Send the $i$-th share to the $i$-th party
end if
if $p_j$ receives the valid $j$-th share $s_j$ for the accumulator $h$ then
Forward $s_j$ to all parties
end if
if Received a majority of valid shares for the accumulator $h$ then
Decode the shares into $v$
Return $v$
else
Return $\perp$
end if
Lemma 23. MVBA satisfies byzantine agreement.
Proof. Termination follows from the termination of binary byzantine agreement.
If all honest parties have the same input v i n v_{in} v in , the binary agreement’s validity ensures that the hash d d d decided will be the accumulator of v i n v_{in} v in . So all honest parties will enter the last binary agreement with b = 1 b = 1 b = 1 and as a consequence, a = 1 a = 1 a = 1 will be returned. Finally, because all honest parties already have the input matching the accumulator, each honest party will receive a share from each other honest party. Because there is an honest majority, it will be able to reconstruct the input (that it already has) and return it. Thus, validity is satisfied.
We now consider agreement. If the last binary agreement returns a = 0 a = 0 a = 0 , then using BinaryAgreement’s agreement, all honest parties will return ⊥ \perp ⊥ which satisfies agreement. We can now assume that all honest parties have a = 1 a = 1 a = 1 . Because of validity, it implies that at least one honest party has an input whose accumulator is d d d . This honest party will send its share to all other parties, and as a consequence, all honest parties will receive a share from each other honest party. As before, because there is an honest majority, all honest parties will be able to reconstruct the same value and return it. Hence, agreement is satisfied.
Lemma 24. Assuming the binary agreement protocol is byzantine robust, MVBA is byzantine robust, has round complexity R M V B A ( n ) = 2 R B A ( n ) + 2 R_{\mathrm{MVBA}}(n) = 2R_{\mathrm{BA}}(n) + 2 R MVBA ( n ) = 2 R BA ( n ) + 2 and per-party bit complexity B M V B A ( n , L ) = ( κ + 1 ) B B A ( n ) + O ( L + κ n log n ) B_{\mathrm{MVBA}}(n,L) = (\kappa+ 1)B_{\mathrm{BA}}(n) + O(L + \kappa n \log n) B MVBA ( n , L ) = ( κ + 1 ) B BA ( n ) + O ( L + κn log n ) .
Proof. Regarding round complexity, the first κ \kappa κ calls to BinaryAgreement are in parallel. After the following call, only two more rounds are needed to send and receive the shares, giving the round complexity. Parties run ( κ + 1 ) (\kappa+ 1) ( κ + 1 ) instances of BinaryAgreement. Afterwards, each send at most 2 shares to each other party. Each share being of size O ( L / n + κ log n ) O(L/n + \kappa\log n) O ( L / n + κ log n ) , the per-party bit complexity follows.
Group Broadcast
We provide here a simple protocol to implement a group broadcast. A group G ⊆ P G \subseteq\mathcal{P} G ⊆ P of parties with a byzantine minority want to broadcast the same input. This is done efficiently using errasure codes.
GroupBroadcast(v_in, G)
Protocol for group G to broadcast an input v_in, run by a party p
if p ∈ G then
Let i be the index of p in G
Encode v_in into |G| shares and send the i-th along with its witness to all parties
end if
if p receives more than G/2 shares with witnesses for the same accumulator then
Decode the shares into v
Return v
else
Return ⊥
end if
Lemma 25. If G G G has a byzantine minority and all honest parties in G G G have the same input, then all honest parties will return this input.
Proof. If G G G has an honest majority which has the same input, then all of these parties will send their share for the same accumulator to all parties. As a consequence, all honest parties will receive more than ∣ G ∣ / 2 |G|/2 ∣ G ∣/2 shares for the same accumulator, and will be able to decode the input and return it.
Lemma 26. The protocol takes 1 round, each party in G G G sends O ( L n / ∣ G ∣ + κ n log n ) O(Ln/|G|+\kappa n \log n) O ( L n /∣ G ∣ + κn log n ) bits, regardless of what it receives. Parties outside of G G G send no message.
Proof. The protocol ends with each party in G G G sending their share, and as such takes n n n rounds. Each party in G G G sends a share of size O ( L / ∣ G ∣ + κ log ∣ G ∣ ) O(L/|G|+\kappa\log|G|) O ( L /∣ G ∣ + κ log ∣ G ∣ ) to all n n n parties. Because ∣ G ∣ ≤ n |G| \le n ∣ G ∣ ≤ n , this gives the per-party bit complexity. Parties outside of G G G do not send any message.
Reliable Group Broadcast
We describe here a protocol similar to the previous one (group broadcast) except that it is reliable: even if the given group G G G does not have a byzantine minority, or that not all honest parties in G G G have the same input, all honest parties will return the same output. We note that this protocol can simply be implemented GroupBroadcast followed by MVBA. However, while our use case for GroupBroadcast benefits from it having only parties in G G G sending a message, our use case for ReliableGroupBroadcast benefits from it being balanced. As such, erasure coding is used slightly differently in this case.
ReliableGroupBroadcast(v_in, G)
Protocol for group G to broadcast an input v_in, run by a party p_j
if p_j ∈ G then
Send the accumulator of v_in to all parties
Encode v_in into n shares and send the i-th along with its witness to p_i
end if
if p_j receives the same accumulator h from a majority of G and a valid share s_j with a witness for h then
Forward s_j and its witness to all parties
end if
if p_j receives more than n/2 shares and their witnesses for the same accumulator h then
Decode the shares into v
else
v ← ⊥
end if
Return MVBA(v)
Lemma 27. If G G G has a byzantine minority and all honest parties in G G G have the same input, then all honest parties will return this input. Additionally, all honest parties will return the same output, regardless of the state of G G G .
Proof. If G G G has an honest majority which has the same input, then all of these parties will send their share and the same accumulator to all parties. As a consequence, all honest parties will receive the same accumulator value from a majority of G G G and a share for this accumulator, which they will forward. Hence, all honest parties will receive shares from all honest parties, which account for more than n / 2 n/2 n /2 . Thus they will be able to decode the input and MVBA’s validity ensures that it will be returned.
The last point is a direct consequence of MVBA’s agreement.
Lemma 28. The protocol has round complexity R R e l i a b l e G r o u p B r o a d c a s t ( n ) = 2 + R M V B A ( n ) R_{\mathrm{ReliableGroupBroadcast}}(n) = 2 + R_{\mathrm{MVBA}}(n) R ReliableGroupBroadcast ( n ) = 2 + R MVBA ( n ) and per-party bit complexity B R e l i a b l e G r o u p B r o a d c a s t ( n , L ) = O ( L + κ n log n ) + B M V B A ( n , L ) B_{\mathrm{ReliableGroupBroadcast}}(n,L) = O(L + \kappa n \log n) + B_{\mathrm{MVBA}}(n,L) B ReliableGroupBroadcast ( n , L ) = O ( L + κn log n ) + B MVBA ( n , L ) .
Proof. Sending and forwarding the shares takes 2 rounds, followed by the call to MVBA. Each party in G G G sends a share and witness of size O ( L / n + κ log n ) O(L/n + \kappa\log n) O ( L / n + κ log n ) to all n n n parties, and may forward one such in the second round. Adding the MVBA call, the per-party bit complexity follows.