Communication Efficient Byzantine Agreement with Predictions Muhammad Ayaz Dzulfikar1 and Seth Gilbert1
arXiv:2605.12935v1 [cs.DC] 13 May 2026
1
National University of Singapore May 14, 2026
Abstract In Byzantine agreement with predictions each process begins with an input value and some (unreliable) prediction bits. Recently, it has been shown that with classification predictions— where the predictions predict each process to be honest or faulty—Byzantine agreement can be completed more quickly than without predictions, circumventing the traditional Ω(f ) round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange Ω(n3 ) bits—enough to allow the processes to approximately agree on the classifications. In fact, it almost seemed necessary to share a significant number of prediction bits if one wanted to tolerate a high number of incorrect predictions. In this paper, we show that this high level of communication (and sharing of predictions) is not inherent by developing an unauthenticated algorithm with Õ(n2.5 ) communication complexity. Furthermore, with authentication, we give an algorithm with optimal O(n2 κ) communication complexity (where κ is a security parameter). All of our results have optimal round complexity for any number of errors in the predictions.
1
1
Introduction
Byzantine agreement. Byzantine agreement is a central problem in distributed computing. It appears at the heart of many distributed protocols, like state machine replication [1, 7], blockchain protocols [6, 19, 26], and many others. In Byzantine agreement, there are n processes that want to agree on a decision. Here, up to t processes may be Byzantine, i.e., deviate arbitrarily. It is known that, in general, at most t < n/3 faults can be tolerated; and in the synchronous, authenticated setting, at most t < n/2 faults can be tolerated. Despite its importance, Byzantine agreement is inherently expensive. It is well-known that (synchronous) deterministic Byzantine agreement requires Ω(f ) rounds [23] and exchanges Ω(n + f 2 ) bits [22], where f ≤ t is the actual number of faults during the execution. (Here, t is a parameter of the algorithm, while f is unknown and set by the adversary.) Predictions. To cope with malicious attacks, real-world distributed applications often employ network monitoring tools that can flag suspicious processes. These tools might be based, for example, on AI, such as Darktrace [21] and VectraAI [40]. Intuitively, if we can correctly detect faulty processes, then we should be able to execute protocols more efficiently, leading to faster agreement (or faster block production on a blockchain, etc.). Alas, these tools typically do not provide perfect detection of malicious users: sometimes an honest user is incorrectly flagged as malicious, and sometimes a malicious user goes undetected. Therefore, one might imagine designing an algorithm with the following property: (i) when the detection mechanism is accurate, the algorithm will perform better, and (ii) when it is not, the algorithm will do no worse than a protocol with no such detection mechanism. Faster agreement with predictions. This problem was explored by Ben-David, Dzulfikar, Ellen, and Gilbert [3]; following the paradigm of algorithms with predictions, they study Byzantine agreement with classification predictions. In this problem, along with their inputs, each process also receives an n-bit string denoting an (unreliable) prediction indicating whether each other process is honest or Byzantine. A key parameter for performance is the number of incorrect bits in the predictions, B ≤ n2 . They show that predictions do not help in reducing the communication complexity (number of bits exchanged), i.e., the Ω(n + f 2 ) lower bound still holds. However, classification predictions do help in reducing the round complexity to O(min{B/n, f }) rounds. For example, when the predictions are mostly correct, e.g., B ∈ O(1), then processes can decide in O(1) rounds (which is a significant improvement on the f + 1 rounds otherwise required). Furthermore, when the predictions are quite wrong, the algorithm still performs as well as existing algorithms. Moreover, they also showed that this is asymptotically tight by giving a matching Ω(min{B/n, f }) lower bound. However, these new algorithms came with several caveats. First, in the unauthenticated setting, their algorithms can only handle a limited number of prediction errors. Moreover, all of their algorithms exchange Ω(n3 ) bits. This was because all the proposed protocols required all processes to share their predictions, and this was needed to approximately agree on the classification predictions. Alas, this global reconciliation is expensive! Hence, it is natural to ask: can we design algorithms that achieve optimal O(min{B/n, f }) round complexity for any B, and do so with optimal communication complexity? Our contributions. In this paper, we show that cubic communication complexity is not inherent, but simply a consequence of the global reconciliation used in earlier algorithms. We
1
present several communication-efficient algorithms, unauthenticated and authenticated, that decide in O(min{B/n, f }) rounds for any number of prediction errors B. As an intermediate result, our first result achieves optimal round complexity for any number of prediction errors, while exchanging O(n3 ) bits. In our second result, we reduce the communication complexity to Õ(n2.5 ). Lastly, taking a different approach with the help of cryptography, our third result achieves O(n2 κ) communication complexity (where κ is a security parameter). Our first result focuses on tolerating any number of classification errors, and is built upon the guess-and-double structure from [3]. In a nutshell, by assigning processes into disjoint groups and doing leader election on groups to choose a committee, we build a Byzantine agreement protocol whose round complexity scales with the prediction errors. This yields a resilience of t < ( 13 − ϵ)n, and by plugging it into the aforementioned structure, we obtain the following: Theorem 1. There is an unauthenticated algorithm for Byzantine agreement that tolerates up to t < ( 13 − ϵ)n faulty processes for any constant 0 < ϵ < 13 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 log(min{B/n, f })) messages and O(n3 ) bits. To break the cubic barrier, we introduce a more communication-sensitive leader election mechanism that relies only on truncated prediction information within each group. We use a committeebased approach for each election; by separating the case when the group size is ‘small’ and ‘large’, we can do leader election with less communication. This results in a resilience of t < ( 16 − ϵ)n, and by plugging this leader election into our first result, we obtain the following: Theorem 2. There is an unauthenticated algorithm for Byzantine agreement that tolerates up to t < ( 16 − ϵ)n faulty processes for any constant 0 < ϵ < 16 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 log(min{B/n, f })) messages and O(n2.5 log(n) log(min{B/n, f })) bits. Finally, we give a more efficient authenticated algorithm. Cryptography significantly simplifies the leader election process, allowing processes to attach succinct proofs of leader legitimacy, which eliminates the need for conciliation within groups. This results in near-optimal communication and resilience simultaneously, with t < ( 21 − ϵ)n: Theorem 3. There is an authenticated algorithm for Byzantine agreement that tolerates up to t < ( 12 − ϵ)n faulty processes for any constant 0 < ϵ < 12 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 ) messages and O(n2 κ) bits. A summary of our work, compared with existing results, can be seen at Table 1. Paper Organization. We discuss further related work at Section 2. Next, we describe the system model and preliminaries at Section 3. We present the high-level overview of our techniques at Section 4. We then discuss how the classification predictions will be used at Section 5. Section 6 is dedicated for our unauthenticated algorithms, and Section 7 is dedicated for our authenticated algorithm. Finally, we conclude at Section 8.
2
Related Work
Since the seminal work by Lamport, Pease, and Shostak [28, 36], Byzantine agreement has been widely studied. It is known that any deterministic protocol needs Ω(t) rounds [24, 25] and Ω(n+t2 ) messages [22]. 2
Algorithm
Resilience
Max. Errors
Message
Bit
Cryptography
[3]
n/3
O(n1.5 )
Õ(n2 )
O(n3 )
None
This - 1
( 13 − ϵ)n
O(n2 )
Õ(n2 )
O(n3 )
None
This - 2
( 16 − ϵ)n ( 12 − ϵ)n ( 12 − ϵ)n
O(n2 )
Õ(n2 )
Õ(n2.5 )
None
O(n2 )
Õ(n3 )
Õ(n4 κ)
Threshold Signature
O(n2 )
O(n2 )
O(n2 κ)
Threshold Signature
[3] This - 3
Table 1: Comparison of Byzantine agreement with classification predictions. All algorithms terminate in the optimal O(min{B/n, f }) rounds when the number of prediction errors B is within their respective maximum errors. ϵ ∈ Ω(1) is a small positive constant. κ denotes a security parameter. We use Õ(·) to hide polylog(n) factors. While the authenticated algorithm from [3] only uses PKI, here we present the bit complexity when it is implemented with threshold signatures for fairer comparison. One way to circumvent these lower bounds is by focusing on the actual number of failures during the execution, f . In particular, we can design early-stopping protocols that terminate in O(f ) rounds [29], which is also asymptotically tight [23]. Another promising way to circumvent existing limitations is by using (unreliable) predictions [33, 34]. The goal is to perform better when the predictions are accurate (consistent) and still perform as well as algorithms without predictions when the predictions are inaccurate (robust). In the sequential setting, this resulted in several exciting results, including ski rental [37], load balancing [30], P2P network [20], and online graph algorithms [2, 10]. In the distributed setting, there have been several interesting results for graph algorithms [5], contention resolution [27], and, most relevant to our work, Byzantine agreement [3].1 In their work [3], Ben-David, Dzulfikar, Ellen, and Gilbert study Byzantine agreement where, apart from its input, each process also receives (potentially different) prediction bits. Surprisingly, they show that any form of predictions cannot reduce the communication cost – Byzantine agreement still exchanges Ω(n + f 2 ) messages. They then focus on a form of predictions they call classification predictions, where each process receives an n-bit string predicting whether a process is honest or faulty. They show that with B wrong prediction bits, Byzantine agreement can be done in O(min{B/n, f }) rounds, which is much faster when the predictions are quite accurate. Moreover, they also show that this is asymptotically tight. They gave two algorithms with trade-offs: an unauthenticated algorithm that can tolerate B ≤ n1.5 wrong prediction bits (and otherwise, terminates in O(f ) rounds), and an authenticated algorithm that can tolerate any number of wrong prediction bits, but sends more messages. Furthermore, all of their algorithms exchange Ω(n3 ) bits to approximately agree on the classification of each process. In this work, we show that those limitations can be avoided. An area that is related to our work is accountability. In some sense, the classification predictions can be seen as unreliable accountability. There have been exciting works on implementing accountable Byzantine agreement [11, 16, 17, 18, 38] – that is, on detecting malicious processes. Some works also study how accountability can be used to do Byzantine agreement and broadcast more efficiently [13, 14, 41]. They leverage different notions of accountability to achieve communication-optimal Byzantine agreement, in the single-shot and multi-shot setting. Another line of work that is relevant is failure detectors. Initiated by Chandra and Toueg [9], 1
See https://algorithms-with-predictions.github.io/ for recent works in this topic.
3
the failure detector is a module that is eventually perfect, updating its detections over time until it correctly identifies every faulty process. While initially stated for crash failures, the work by Malkhi and Reiter later addresses Byzantine failures as well [32]. These works focus on implementing the failure detectors and finding the “weakest” failure detectors needed to solve Byzantine agreement [8]. In contrast, our work focuses on using classification predictions (unreliable detection) to do agreement more efficiently.
3
Preliminaries
Processes. We consider a system of n processes Π = {p1 , p2 , . . . , pn }. Up to t processes may deviate from the prescribed protocol. We denote the processes that follow the protocol as honest or correct, and those who do not as Byzantine or faulty. We denote f with 0 ≤ f ≤ t as the actual number of Byzantine processes in an execution. Network. We consider a synchronous network, where an algorithm is executed in a round-toround manner: in each round, a process sends its messages, receives messages, and updates its local state. Furthermore, each process can communicate directly with any other process. Cryptography. For our authenticated protocols, we use a public-key infrastructure (PKI). Each process has a pair of a public key and a private key. By default, each message will be signed by its sender. We also use a (k, n)-threshold signature scheme [31, 39], where we typically use (t + 1, n), (n−t, n), and (⌈(n+1)/2⌉, n) as the parameters. In a (k, n)-threshold signature scheme, each process holds a distinct private key; there exists a single public key. Using its private key, pi produces a partial signature for a message m via ShareSignki (m). This partial signature can be verified via ShareVerifyki (m, psig). Next, given a set S of k partial signatures for the same message, a process can produce a threshold signature for that message via Combinek ({psig i }pi ∈S,|S|=k ). Finally, a process can verify such a threshold signature for a message m by invoking CombinedVerifyk (m, tsig). Where appropriate, we omit explicit invocations of ShareVerifyk· (·) and CombinedVerifyk (·). Importantly, under a security parameter κ, each signature under this scheme consists of O(κ) bits.2 Predictions. Each process pi also receives as a prediction a string ai . We underline that each process may receive a different string. Moreover, we do not make any assumption about the prediction strings. In this paper, we consider classification predictions, where each ai is a binary string of length n. We say pi predicts pj as honest if ai [j] = 1, and Byzantine otherwise. A prediction bit is correct if it matches reality, and wrong otherwise. We denote B as the number of wrong bits in the predictions, which is the number of pairs (i, j), where pi is honest and either (1) ai [j] = 0 and pj is honest, or (2) ai [j] = 1 and pj is faulty. (Note that the wrong bits in the predictions of faulty processes are not counted.) Byzantine Agreement. The problem of Byzantine agreement is defined as follows. Each honest process pi proposes its input vi , and outputs a decision di such that the followings are satisfied: • Agreement: for each honest process pi and pj , di = dj . • Strong unanimity: if each honest process proposes the same value v, then only v can be decided. 2
We assume κ > log(n) to avoid an adversary with exponential computational power and collision between cryptographic signatures.
4
• Termination: each honest process eventually decides. The round complexity of a protocol is defined as the number of rounds until all honest processes decide. Then, the message complexity of a protocol is defined as the number of messages that honest processes send until all honest processes decide. Similarly, the communication complexity or bit complexity of a protocol is defined as the number of bits that honest processes send throughout the protocol. In this paper, we assume the size of each input to be constant.
4
Technical Overview
Using the Classification Predictions. We first revisit how the predictions are used in [3], specifically their unauthenticated result. First, they use a voting procedure, where each process broadcasts its prediction string. Then, a process pi classifies pj as honest if it receives more than n/2 strings that predict pj as honest; otherwise, it classifies pj as Byzantine. They observe that if there are f < ( 12 − ϵ)n faults, then there are at most O(B/n) processes that are misclassified by some honest process, where B is the number of erroneous prediction bits. Next, suppose each process orders processes based on their classification, putting those classified as honest first. Each process may have a different ordering. However, they showed that, using those orderings in phaseking style [29], we can implement Byzantine agreement that terminates in O(k) rounds with at √ most k misclassified processes when k ∈ O( n). They then combine that agreement protocol alongside an early-stopping Byzantine agreement that terminates in O(f ) rounds, glued together by a weaker agreement primitive called graded consensus. By guessing the actual number of k and f and limiting the rounds executed in each protocol, along with doubling the estimate when decision is not reached yet, they achieve Byzantine agreement that terminates in O(min{B/n, f }) rounds as long as B ∈ O(n1.5 ). Group-based Approach. An interesting alternative approach for achieving better tolerance to prediction errors is partitioning the processes into groups and choosing a representative leader from each group to help drive the agreement protocol. One option, suggested in the conclusion of [3], is to deterministically divide processes into 3k similar-sized groups. Each process picks a process in the i-th group as its i-th leader. They hinted that there will be a “good group” where all honest processes choose the same honest process as their leader, which is a sufficient condition for success. In this paper, we explore such group-based approaches, using different grouping and election procedures to achieve better communication complexity while maintaining good round complexity. We present several implementations to pick a leader from a group, which we call group leader election. The election is guaranteed to elect the same honest leader for all processes if the group is “good”. Here, we say a group is good if (1) it has at least one honest process, and (2) no misclassified process. We can observe, for example, if t < n/2, at most k processes are misclassified, and we have m = 3k groups, then at least one of the groups will necessarily be good.3 Furthermore, with a little “slack” in resilience, we can obtain many good groups. If t < ( 13 − ϵ)n, where 0 < ϵ < 13 is a constant, and we have m ∈ Θ(k) groups, then we will have more than 2m 3 good groups, which is an important ingredient for our unauthenticated results. 3
t Specifically, there are at most k groups with misclassified processes, and there are at most n/m < m = 3k groups 2 2 without honest process. So there are at most 5k/2 < 3k groups that are not good.
5
Optimal Messages and Near-Optimal Resilience. For our first result, we implement Byzantine agreement with predictions using this partitioning approach, where the leaders from the groups form a committee to execute agreement. Each process then decides on the majority value output by the committee members. Here, we set the number of groups m to be Θ(k̂) such that when at most k̂ processes are misclassified, there will be more than 2m 3 good groups. (In the full protocol, we use k̂ to denote the current estimate of misclassified processes during the guess-and-double strategy.) We can do the group leader election using a simple voting procedure. That is, each process picks the smallest process in the group where more than n/2 processes predict the process to be honest. Note that processes only need to send the predictions once to all processes; after that, each election can be done with zero communication. Although each process may perceive a different committee, they will contain a common subset of more than 2m 3 (unknown) honest processes. This honest core of committee members (even if unknown) ensures that the agreement will succeed. Thus, when there are at most k̂ misclassified processes, the protocol correctly solves Byzantine agreement. Moreover, the protocol terminates in O(k̂) rounds and exchanges O(n2 ) bits. When plugged into the framework from [3], we obtain a Byzantine agreement protocol tolerating up to t < ( 31 −ϵ)n faults that terminates in O(min{B/n, f }) rounds while exchanging Õ(n2 ) messages and O(n3 ) bits. Achieving Sub-Cubic Communication. The communication bottleneck in our first result is in the group leader elections, where, overall, we need to send O(n3 ) bits to handle every election. Thus, our next focus is to reduce the communication complexity of the election. Our key idea is to first strengthen the “good group” definition. Specifically, a group is good only if it has an honest majority (rather than just having at least one honest process) and no misclassified process. This allows us to use a committee-based approach: all processes only need to send (some part of) their predictions to those in the committee, who do the election among themselves, and then each process elects the process chosen by the majority of the committee. Small group. Next, let us observe a simple way to do group leader election on a group of processes G. Each process sends its prediction bits regarding processes in G to the committee (consisting of processes in G). Then, each member of the committee picks the smallest process in G that was predicted by more than n/2 processes to be honest as the leader, and broadcasts this process. Finally, each process elects the process broadcast by the majority of the committee. We can see that, in a good group, each process will elect the same honest process. Furthermore, this is done in O(1) rounds and with O(n|G|2 ) bits of communication. Now, suppose that we run this group leader election during our guess-and-double phase with m similar-sized groups, each with 3 n n 2 O( m ) processes. The total communication will be O(n · ( m ) · m) = O( nm ). In other words, when n the group is ‘small’, i.e., m ∈ o(n), then using this simple approach will cause the elections during a phase to exchange sub-cubic bits of communication. Large group. However, the same approach will result in O(n3 ) bits when the group size is n ‘large’, with m ∈ Ω(n). We need to limit the information sent to the committee. One natural √ approach is to vote only for the smallest c n processes predicted to be honest for some constant c. Then, each committee picks the smallest process voted for by more than n/2 processes. However, this does not solve the election. If all processes send every relevant prediction bit, the smallest honest process in the group will receive enough votes to be elected. However, since we are only √ √ sending c n votes, there may be an honest process that wrongly predicts c n smaller Byzantine processes as honest and so, will not vote for the smallest honest process. This will allow the adversary to influence the result of the election and cause disagreement.
6
But, recall that if the size of the group is large, it means that we are currently estimating a small √ number of misclassified processes. Turns out, if we assume there are at most O( n) such processes, there are some nice properties on the set of processes Li containing processes where pi , a member of the committee, receives more than n/2 votes for each of them. In a good group G, (1) each Li √ consists of only honest processes, (2) the size of each Li is at most O( n), and (3) there is a “core set” C such that C ⊆ Li and |C| ≥ |Li |/2 for each process pi in the committee. This allows us to use conciliation with core set [3], which the committee can use to agree on an honest process in G. √ The primitive terminates in O(1) rounds and will exchange O(|G|2 |L| log(n)) = O(|G|2 n log(n)) bits. Thus, by adding this additional step of conciliation, we obtain a group leader election that exchanges O(n1.5 |G| log(n)) bits. When used in the guess-and-double framework, this will yield O(n2.5 log(n)) bits of communication. Combining both cases. Finally, we can combine both approaches in the following. When √ our estimate of k̂ is at most c n for some constant c, we use the algorithm for a large group and otherwise, use the algorithm for a small group. Therefore, the group leader elections in each phase will exchange O(n2.5 log(n)) bits. When used in our unauthenticated algorithm before, this gives an algorithm that exchanges Õ(n2.5 ) bits, achieving sub-cubic communication. Lastly, let us remark on the price that we must pay to use this approach. Recall that in a guess-and-double phase, we always use m groups such that there are more than 2m 3 good groups. As we use a stronger good group property, we need to reduce the resilience to ensure having many good groups. In particular, this halves the resilience to ( 16 − ϵ)n where 0 < ϵ < 16 is a constant. Optimal Communication and Near-Optimal Resilience with Authentication Our authenticated algorithm, apart from having optimal O(n2 κ) communication, is arguably simpler. It uses the standard reduction from strong unanimity to Byzantine agreement with external validity (also known as validated Byzantine agreement), with O(n2 κ) bits and O(1) rounds [12, 13]. Next, we implement the validated Byzantine agreement with a leader-based protocol where the leaders are chosen alternating between round-robin and using group leader election results, where the length before switching follows the guess-and-double strategy from before. Finally, our algorithm builds on an efficient group leader election and validated Byzantine agreement with the help of cryptography. In our group leader election, each process sends its signature to every process it predicts honest. Then, every process pi that receives more than n/2 such signatures can broadcast them (or a smaller aggregate) to tell other processes to classify pi as honest. By having each process elect the smallest process in the group that it classifies as honest, all honest processes will elect the same honest process in a good group. (Here, we only need at least one honest process in a good group.) Furthermore, processes only need to send signatures and convince others that they are honest once; after that, the group leader election can be done without communication. Using threshold signatures to aggregate the signatures, the group leader elections can be done by spending O(n2 κ) bits and O(1) rounds at the start. Lastly, our validated Byzantine agreement implementation is heavily based on some aspects of the Byzantine broadcast protocol from [41]. However, we need to take into account that each process may have different leaders, which will break the safety of the original protocol. Roughly speaking, in the original protocol, processes will forward the message from the leader to other processes. They must accept the forwarded message if it is signed by the leader, which is the same process for everyone. In a nutshell, the problem with having different leaders is that the process does not know whether it should accept the message (because the forwarder is honest) or not. The fix is quite simple. At every phase, each process sends a signature to the process it considers as its leader. Next, a leader must attach ⌈ n+1 2 ⌉ such signatures to its messages. Thus,
7
when receiving a forwarded message, a process must accept it if it contains ⌈ n+1 2 ⌉ signatures for the original sender. This fixes the issue and also allows us to limit the number of ‘leaders’ to be constant during every phase. Using threshold signatures, the communication complexity of the validated Byzantine agreement will be O(n2 κ), and will terminate as soon as all honest processes have the same honest leader. Altogether, our authenticated protocol has near-optimal resilience with t < ( 12 − ϵ), deciding in O(min{B/n, f }) rounds by exchanging O(n2 κ) bits.
5
Using the Classification Predictions
In this section, we explain how we are using classification predictions, define good groups, and prove key combinatorial lemmas on the existence of good groups. In our algorithms, we use classification predictions to enable each process to pick a sequence of processes. This sequence will be used, for example, as a sequence of leaders in a leader-based protocol. This sequence is obtained as follows. First, for a parameter m, we will partition the processes into m disjoint groups. In each group, processes participate in what we call the group leader election to elect the leader of the group. Then, the elected m leaders will form the sequence of processes. Importantly, the result of the group leader election will depend on the quality of predictions regarding the processes in that group. We will show that, when a group is “good”, then all honest processes will select the same honest process as the leader. Furthermore, we will also show that when m is chosen properly, we can obtain (many) good groups. Thus, there will be (many) indices in the sequence where everyone has the same honest leader. Our first goal is to define the group leader election and what it means for a group to be good. To do that, we first define misclassified process. Definition 1 (Misclassified Process). A process pi is misclassified if it is Byzantine and at least n/2 − f honest processes predict pi as honest, or pi is honest and at least n − f − n/2 honest processes predict pi as Byzantine. 4 The motivation behind this definition is the following: One simple way to improve the quality of the predictions is to exchange the predictions and use the majority of the prediction bits to classify a process as either Byzantine or honest. That is, when more than n/2 processes predict pi as honest, then pj classifies pi as honest and otherwise, Byzantine. Hence, a process pi can be misclassified if, at the start, sufficiently many honest processes predict pi wrongly. Moreover, using a similar observation as the one from [3], we can obtain the following. Observation 1. If f < ( 21 − ϵ)n for some constant 0 < ϵ < 12 , then there are at most O(B/n) misclassified processes. This is because at least ϵn ∈ Ω(n) incorrect prediction bits from honest processes are needed to misclassify a process. Next, we explain what it means for a group to be good. Definition 2 (c-Good Group). A group G of |G| processes is c-good if none of the processes is misclassified and fewer than ⌈c|G|⌉ processes are Byzantine. For example, a 1-good group contains at least one honest process and a 12 -good group has an honest majority. Furthermore, observe that for any 0 < c1 < c2 ≤ 1, a c1 -good group is also a 4
Let us remark that our definition is stronger compared to the one from [3], in the sense that (1) a misclassified process according to [3] is also misclassified according to our definition, but (2) our misclassified process might not be misclassified according to [3].
8
c2 -good group. As we will see, it is possible for honest processes to (efficiently) agree on an honest member of a 1-good group. We are now ready to define the group leader election problem. Definition 3 (Group Leader Election). Each process pi inputs the same 1-good group G along with its prediction bits ai . Then, each process outputs ℓi such that the followings are satisfied: • Agreement: for each honest process pi and pj , ℓi = ℓj . • Validity: ℓi ∈ G and ℓi is an honest process. While leader election is typically not useful for deterministic protocols (because the adversary can corrupt the elected leader), this is not the case when predictions are available. In Algorithm 1, we show a simple implementation that solves this problem. In a nutshell, all processes exchange all predictions they have regarding the processes in the group. Then, each process outputs the smallest process that more than n/2 processes predict as honest. Algorithm 1 Simple Group Leader Election: Pseudocode (for process pi ) 1: Input parameters: 2: Group Gi 3: Prediction ai
▷ ai is pi ’s prediction string
4: SimpleElection(Gi , ai ): 5: let vi be a binary string where vi [j] = ai [Gi [j]] for each 1 ≤ j ≤ |gi | 6: broadcast ⟨vote, vi ⟩ 7: 8:
let j be the smallest index such that pi received more than n/2 ⟨vote, v ⟩ with v [j] = 1 return Gi [j]
We can verify that Algorithm 1 solves the group leader election. Lemma 1. There is a group leader election algorithm for a 1-good group G. The algorithm terminates in 1 round, exchanges O(n2 ) messages, and exchanges O(n2 |G|) bits. Proof. As G is a 1-good group, no process is misclassified. Thus, each process will obtain the same index j. Moreover, as G is a 1-good group, Gi [j] must be an honest process. Finally, the complexities follow from the algorithm. The communication complexity of Algorithm 1 is upper bounded by O(n3 ), i.e., when the group size is O(n). However, if we need to run it on multiple such big groups, we can instead exchange the predictions of all processes once (i.e., with G = Π), exchanging O(n3 ) bits in 1 round. Then, each process can do the election locally on all groups based on the received predictions. Lemma 2. There is a group leader election algorithm for a 1-good group G. The algorithm has a pre-processing step that terminates in 1 round, exchanging O(n2 ) messages and O(n3 ) bits. After that, all elections can be done without communication. Next, we prove several key combinatorial lemmas on the existence of good groups that are crucial for our results. We start by examining how the processes are grouped: roughly speaking, each group has a similar size. Definition 4 (m-Grouping). A grouping of all processes into m disjoint and non-empty groups is said to be m-grouping if each group has either ⌊n/m⌋ or ⌈n/m⌉ processes.
9
As long as n ≥ m, an m-grouping exists and can be computed deterministically. In particular, our results only require all processes to compute the same m-grouping for each value of m. We are now ready to state the key lemmas. Intuitively, when B ∈ o(n2 ), only o(n) processes are misclassified (i.e., this is the regime where we want our predictions to be useful). We will choose the number of groups to be proportional to the number of misclassified processes. Looking ahead, Lemma 3 and Lemma 4 will be used for our unauthenticated algorithms that necessitate more than 2/3 groups being good, and Lemma 5 will be used for our authenticated algorithms that only need the existence of a good group. Lemma 3. Suppose there are f < ( 13 − ϵ)n faulty processes and k misclassified processes, where 0 < ϵ < 31 is a constant. Then, there exist two positive constants c1 and c2 such that, if c1 k < m < c2 n, then for any grouping satisfying the m-grouping, more than 2m 3 groups are 1-good. Proof. If a group is not c-good, then it either has a misclassified process, or at least ⌈c|G|⌉ of its f members are Byzantine. As c = 1, at most k + ⌈⌊n/m⌋⌉ groups are not 1-good. Next, we set c1 = 2ϵ ϵ and c2 = 2/3−ϵ . Thus, at least m−k−
f (1/3 − ϵ)n >m−k− ⌈⌊n/m⌋⌉ n/m − 1 (1/3 − ϵ)mn =m−k− n−m (1/3 − ϵ)mn > m − k − (2/3−2ϵ)n (2/3−ϵ)
ϵ > m − m − (1/3 − ϵ/2)m 2 = 2m/3 groups are 1-good groups. Using the same method, we can also prove the following. Lemma 4. Suppose there are f < ( 16 − ϵ)n faulty processes and k misclassified processes, where 0 < ϵ < 61 is a constant. Then, there exist two positive constants c1 and c2 such that, if c1 k < m < 1 c2 n, then for any grouping satisfying the m-grouping, more than 2m 3 groups are 2 -good. Lemma 5. Suppose there are f < ( 12 − ϵ)n faulty processes and k misclassified processes, where 0 < ϵ < 21 is a constant. Then, there exist two positive constants c1 and c2 such that, if c1 k < m < c2 n, then for any grouping satisfying the m-grouping, some of the groups are 1-good. We defer the proofs to Appendix A.
6
Unauthenticated Algorithm
Our unauthenticated algorithm runs two algorithms in parallel: (i) a Byzantine agreement protocol with a round complexity that scales with how accurate the predictions are; and (ii) an early-stopping Byzantine agreement with a round complexity that scales with how many Byzantine processes there are. Our primary focus is on implementing the first one. At a high level, the key idea is to use Byzantine agreement on an implicit committee, where each process chooses a set of processes they think are the committee. By using m-grouping and group 10
leader elections for choosing those processes, in good groups, each process will choose the same honest process, which will constitute the implicit committee. Moreover, by setting m such that there will be many good groups (and so, bigger implicit committee), the algorithm will correctly solve Byzantine agreement when there are not too many misclassified processes. After that, we also show that there is a group leader election which, combined with the Byzantine agreement with an implicit committee and the approach from [3], yields Byzantine agreement that terminates in O(min{B/n, f }) rounds and sends Õ(n2.5 ) bits. We first describe the Byzantine agreement with an implicit committee in Section 6.1. Next, we present the group leader election that is crucial for our agreement that exchanges Õ(n2.5 ) bits in Section 6.2. Finally, we describe how they are used along with the approach from [3] in Section 6.3.
6.1
Byzantine Agreement with an Implicit Committee
In our agreement with an implicit committee, besides their proposal, each process pi is also given a vector of processes Li . Processes may input different vectors of processes. However, we assume that (1) they all have the same size, (2) for each pi , there is at most one j with Li [j] = pi , and (3) there are more than 2|L| 3 indices j, such that Li [j] is the same honest process for each honest process pi . Let us note that the third assumption is where the ‘implicit committee’ comes in, as there exists a committee (common set), but processes do not know who they are. In our full algorithm, the first two assumptions are due to the m-grouping, while the last assumption will be due to the group leader election on each group. Before describing the algorithm, let us remark on the following existing Byzantine agreement protocol that our algorithm relies on. Lemma 6 (Restated from [4]). There is a Byzantine agreement algorithm that tolerates up to t < n/3 Byzantine processes. The algorithm terminates in O(n) rounds, and each honest process sends O(n) bits. Importantly, the complexities hold even if there are more than t faults (although processes may then disagree). We present our protocol in Algorithm 2. If a process pi considers itself a part of the committee (pi ∈ Li ), it then participates in the Byzantine agreement protocol from Lemma 6. Here, pi participates assuming there are |Li | processes, where the j-th process is Li [j] (line 6). After that, pi broadcasts its decision at line 7. Finally, every process pi decides using the majority value it receives from the processes in its Li . Algorithm 2 Byzantine Agreement with Implicit Committee: Pseudocode (for process pi ) 1: Input parameters: 2: Vector(Process) Li 3: Value vi 4: AgreementWithImplicitCommittee(vi , Li ): 5: if pi ∈ Li : 6: let di ← ByzantineAgreement(vi ) over Π′i = {p′1 , . . . , p′|Li | } with p′j = Li [j] 7: broadcast ⟨decision, di ⟩ 8: 9:
let decision i be the majority value of decision messages from Li return decision i
We now prove the guarantees of the algorithm. Lemma 7. The algorithm correctly solves Byzantine agreement. 11
▷ Lemma 6
Proof. The execution of the Byzantine agreement from Lemma 6 will be equivalent to the one with Π∗ = {p∗1 , . . . , p∗|L| } where for each 1 ≤ j ≤ |L|: • p∗j is honest if Li [j] is the same honest process for each honest process pi , and • p∗j is Byzantine otherwise. In other words, those in the implicit committee are honest, and the rest are Byzantine. As there are more than 2|L| 3 indices j where Li [j] is the same honest process for each honest process pi , there will be less than |L| 3 Byzantine processes. Therefore, the output of processes in the implicit committee will satisfy agreement and strong unanimity. Moreover, the value they broadcast at line 7 will be the majority value received by any honest process. Hence, each honest process will agree on a value that satisfies strong unanimity. Lemma 8. The algorithm terminates in O(|L|) rounds and exchanges O(n2 ) bits. Proof. There is only one additional round besides the invoked Byzantine agreement, hence the round complexity follows from Lemma 6. From the assumptions, Lemma 6, and line 7, each honest process sends O(n) bits. Furthermore, due to Lemma 6, the complexities hold even if there are fewer than 2|L| 3 processes in the implicit committee. This will be important later, as we invoke this algorithm.
6.2
Group Leader Election
We now focus on an efficient algorithm for group leader election. Our goal is to prove the following lemma. √ Lemma 9. Assume that if the group size |G| = Ω( n), then B = O(n1.5 ) (where B is the number of erroneous prediction bits). There is a group leader election algorithm for 12 -good group G, assuming f < ( 21 − ϵ)n for any constant 0 < ϵ < 12 . The algorithm terminates in O(1) rounds, exchanges O(n|G|) messages, and exchanges O(n1.5 |G| log(n)) bits. Let us stress that the lemma works for any group size |G|, as long as the assumption stated in √ the lemma holds when |G| = Ω( n). At a high level, if we work with a 12 -good group, we can use a committee-based approach.5 That is, processes only send their predictions to those in the group. The processes in the group then do the election, and broadcast who they elected as the leader. Then, all processes take the process elected by the majority of the group as the leader. While this immediately yields a sub-cubic algorithm when the group is small, e.g., with size at most o(n), unfortunately the algorithm still exchanges cubic bits when the group is large. Our √ key idea is, instead of sending all prediction bits for a group, each process only sends the O( n) processes it predicts as honest. Then, an additional sub-protocol is run to allow the processes in the group to agree on an honest leader. By running the second algorithm when the group size is √ Ω( n) and running the first algorithm otherwise, we obtain a group leader election algorithm with O(n1.5 |G| log(n)) communication complexity for any group of processes G. We outline the algorithm for a small group in Section 6.2.1 and the algorithm for a large group in Section 6.2.2. 5
Recall that a 21 -good group is also a 1-good group, so this still satisfies the definition of group leader election.
12
6.2.1
Small Group
We present the algorithm for a small group in Algorithm 3. Observe that this is the same as Algorithm 1, except each process only sends its prediction bits to the committee (the group G). Each process in the committee then broadcasts the smallest process it classifies as honest. Finally, each process outputs the process it receives the most from the committee. Algorithm 3 Group Leader Election for Small-Sized Groups: Pseudocode (for process pi ) 1: Input parameters: 2: Group Gi 3: Prediction ai 4: SmallSizedElection(Gi , ai ): 5: let vi be a binary string where vi [j] = ai [Gi [j]] for each 1 ≤ j ≤ |gi | 6: send ⟨vote, vi ⟩ to each pj ∈ Gi 7: 8: 9:
if pi ∈ Gi : let j be the smallest index such that pi received more than n/2 ⟨vote, v ⟩ with v [j] = 1 broadcast ⟨leader, Gi [j]⟩
10: 11:
let pℓ ∈ Gi be a process such that pi received ⟨leader, pℓ ⟩ from more than |Gi |/2 processes in Gi return pℓ
We now prove the guarantees of the algorithm, assuming all honest processes input the same group G. Lemma 10. If G is a 12 -good group, then all honest processes output the same honest process pj ∈ G. Proof. As G is a 21 -good group, each process pi ∈ G will obtain the same index j where G[j] is an honest process. Thus, there is a process pℓ broadcast by all honest processes in G. As more than half of the processes in G are honest, all processes output the same honest process pℓ . Next, observe that the algorithm terminates in 2 rounds. Furthermore, communications are done between all processes and processes in G, where each message contains either O(|G|) bits or O(log(n)) bits. We can thus conclude with the following. Lemma 11. There is a group leader election algorithm for a 12 -good group G. The algorithm terminates in 2 rounds, exchanges O(n|G|) messages, and exchanges O(n|G|(|G| + log(n))) bits. 6.2.2
Large Group
At a high level, our algorithm for a large group (Algorithm 4) is similar to the one for a small group. However, instead of sending the prediction bit of each process in the group, each process pi √ votes by sending the smallest 30 n processes that pi predicts to be honest (or less, if pi predicts √ less than 30 n processes are honest in the group).6 Observe that each committee member can no longer simply take the smallest process with more than n/2 votes as the leader. For an example, assume f < ( 12 − ϵ)n for a constant 0 < ϵ < 21 . As the group G is a 12 -good group, less than ϵn honest processes predict the smallest honest process in the √ group, pi , as Byzantine. However, there can be an honest process that predicts 30 n Byzantine processes smaller than pi as honest and so, will not vote for pi . Thus, although pi cannot be misclassified if all honest processes send out all their prediction bits, here, pi can be misclassified. 6
While we believe we can reduce the number of votes, we did not try to optimize it to simplify the proof.
13
More importantly, the vote from Byzantine processes can influence whether an honest process classifies pi as honest or Byzantine. Therefore, we add an extra step before each committee member can decide on a leader. Each process in the committee will run an algorithm for conciliation with core set [3]. In this problem, each process pi inputs a value vi and a set of processes Li , where (1) Li contains only honest T Li and |C| > 12 |Li | for each processes, and (2) there is a ‘core set’ C, such that C ⊆ pi is honest
honest process pi . Then, each process pi outputs vi′ , such that the followings are satisfied: • Agreement: for each honest process pi and pj , vi′ = vj′ . • Honest-Input Validity: there is an honest process pj that inputs vj = vi′ . Let us note that although our definition of the problem is different from the one described in [3], their implementation (with an appropriate modification) can also be used for our definition. We elaborate this further in Appendix B. Lemma 12. There is an algorithm for conciliation with core set. The algorithm terminates in 1 round, exchanges O(n2 ) messages, and exchanges O(n2 (|v | + |L| log(n))) bits, where |v | denotes the size of the input value and |L| denotes the maximum size of the input process set. Each process in the committee broadcasts its conciliation output, and all processes take the process broadcast by the majority of the committee members as the elected leader. Algorithm 4 Group Leader Election for Large-Sized Groups: Pseudocode (for process pi ) 1: Input parameters: 2: Group Gi 3: Prediction ai 4: LargeSizedElection(Gi , ai ): 5: let Vi be the set of index j with pj ∈ Gi and ai [j] = 1 √ √ 6: if |Vi | > 30 n, only keep the smallest 30 n indices in Vi 7: send ⟨vote, Vi ⟩ to each pj ∈ Gi 8: 9: 10: 11: 12: 13:
if pi ∈ Gi : let Li be the set of index j in Gi where pi received more than n/2 ⟨vote, V ⟩ with j ∈ V √ √ if |Li | > 30 n, only keep the smallest 30 n indices in Li let vi be the smallest index in Li let ℓi ← ConciliationWithCoreSet(vi , Li ) executed among processes in Gi broadcast ⟨leader, pℓi ⟩
14: 15:
let pℓ ∈ Gi be a process such that pi received ⟨leader, pℓ ⟩ from more than |Gi |/2 processes in Gi return pℓ
We now prove the guarantees of the algorithm, assuming all honest processes input the same group G. Furthermore, to prove that all honest processes will output the same honest process pj ∈ G, we also assume that (1) there are f < ( 12 − ϵ)n faults for some constant 0 < ϵ < 12 , (2) √ √ |G| ≥ 60 n, (3) G is a 21 -good group, and (4) there are B ≤ ϵn n error bits in the predictions. Lemma 13. If G is a 12 -good group, then ∪pi ∈G Li is a subset of G and does not contain faulty process. Proof. Only processes in G are included in any Li . Next, from the definition of 12 -good group, even if each honest process sends all indices it predicts as honest, there will be fewer than n/2 votes for any Byzantine process.
14
√ √ Lemma 14. If G is a 12 -good group, f < ( 12 − ϵ)n, and B ≤ ϵn n, then | ∪pi ∈G Li | ≤ 35 n. Proof. From Lemma 13, only honest processes can be included in Li . We then argue that only the √ smallest 35 n honest processes in G can be included in any Li . √ Suppose an honest process pj ∈ G is not among the smallest 35 n honest processes in G. √ Thus, if an honest process sends a vote containing pj , it must have predicted at least 5 n honest B processes smaller than pj as Byzantine. There can be at most 5√ ≤ 5ϵ n such processes. As there n can be at most f + 5ϵ n < n/2 votes for pj , pj cannot be included in any Li . √ √ Lemma 15. If G is a 12 -good group, |G| ≥ 60 n, f < ( 21 − ϵ)n, and B ≤ ϵn n, then | ∩pi ∈G Li | ≥ √ 20 n. Proof. Again, from Lemma 13, only honest processes can be included in Li . As G is a 12 -good √ √ group, at least 30 n of its members are honest. We will argue that, among the smallest 27 n √ honest processes in G, at least 20 n are in the intersection of all Li . √ For any process pj among the smallest 27 n honest processes of G, an honest process does not √ √ √ vote for pj if (a) it predicts at least 30 n − 27 n = 3 n Byzantine processes smaller than pj as B honest, or (b) it predicts pj as Byzantine. From the first case, pj would lose at most 3√ ≤ 3ϵ n n votes from honest processes. Combined with the second case, pj is not a part of an Li if at least √ B (n−f )−n/2− 3ϵ n > 6ϵ n honest processes predict pj as faulty. Thus, there can be at most ϵn/6 ≤6 n √ processes among the first 27 n honest processes in G which is not a part of some Li . Therefore, √ √ √ at least 27 n − 6 n > 20 n honest processes are in the intersection of all Li . Observe that Lemma 13, Lemma 14, and Lemma 15 imply the assumptions required by the conciliation with core set are satisfied. Thus, we can prove the following. √ √ Lemma 16. If G is a 12 -good group, |G| ≥ 60 n, f < ( 21 − ϵ)n, and B ≤ ϵn n, then all honest processes output the same honest process pℓ ∈ G. Proof. From the agreement of the conciliation with core set, each honest process pi returns the same ℓi . Furthermore, because of the honest-input validity, this must be an index input by an honest process. As each honest process pi inputs the smallest index in Li , from Lemma 13, this must correspond to an honest process in G. Finally, as G is a 21 -good group, more than |G|/2 honest processes in G broadcast ⟨leader, pℓ ⟩ for the same honest process pℓ ∈ G, ensuring all honest processes output pℓ . Lastly, we prove the complexities. Note that they hold as long as all honest processes input the same group G. Lemma 17. The algorithm terminates in 3 rounds. Furthermore, honest processes exchange O(n|G|) messages and O(n1.5 |G| log(n)) bits. Proof. From Lemma 12 and line 9, the conciliation with core set among processes in G terminates √ in 1 round, and exchanges O(|G|2 ) messages and O(|G|2 n log(n)) bits. Apart from that, the communications are done between all processes and processes in G, where 2 rounds are done and each √ message contains O( n log(n)) bits. Summing everything, we get the round and communication complexities as desired. Therefore, we obtain the following.
15
√ Lemma 18. There is a group leader election algorithm for a 12 -good group G, assuming |G| ≥ 60 n, √ there are f < ( 12 −ϵ) faults, and there are B ≤ ϵn n wrong prediction bits. The algorithm terminates in 3 rounds, exchanges O(n|G|) messages and exchanges O(n1.5 |G| log(n)) bits. √ By using Lemma 11 when |G| ≤ c n for some constant c and Lemma 18 otherwise, we obtain Lemma 9. Furthermore, the complexities also hold even if the input group G is not 12 -good. √ Note that we will use the value of B to set the size of the group, such that when B ≤ ϵn n, then √ |G| ≥ c n for some constant c. More specifically, when we are estimating B erroneous prediction bits, we will create Θ(B/n) groups of size Θ(n2 /B); so we will only rely on Lemma 18 when B is in the desired range. √ Lemma 9. Assume that if the group size |G| = Ω( n), then B = O(n1.5 ) (where B is the number of erroneous prediction bits). There is a group leader election algorithm for 12 -good group G, assuming f < ( 21 − ϵ)n for any constant 0 < ϵ < 12 . The algorithm terminates in O(1) rounds, exchanges O(n|G|) messages, and exchanges O(n1.5 |G| log(n)) bits.
6.3
Full Algorithm
In our unauthenticated algorithm for Byzantine agreement with classification predictions, we adopt the same general “guess-and-double” structure as [3] (see Algorithm 5). Let us describe the approach from a high-level perspective. The algorithm goes through phases. In each phase, the algorithm estimates k̂, the maximum number of actual faults and misclassified processes.7 The algorithm then runs an early-stopping Byzantine agreement sub-protocol that terminates in O(f ) rounds (with f actual faults), and a Byzantine agreement sub-protocol that, when there are at most k misclassified processes, terminates in O(k) rounds. Then, using the estimate k̂ from before, we abort both agreement instances after O(k̂) rounds, (line 11 and line 20). Graded consensus instances are then used to ensure safety while adopting the output of each Byzantine agreement. Graded consensus is a weaker consensus primitive that ensures agreement when all honest processes begin with the same proposal (but does not guarantee agreement when honest processes differ in proposals); in addition, it outputs a 0 or 1 grade for each decision wherein if any honest process outputs a value with a grade of 1, every honest process outputs that same value with a grade of 0 or 1. Each process runs a graded consensus before invoking a Byzantine agreement sub-protocol (line 14 and line 23), and only adopts the output of the agreement if it decides with grade 0 from the graded consensus; otherwise, it commits to the output of the graded consensus (line 12 and line 21). Lastly, termination is guaranteed when the estimate k̂ is big enough, as at least one of the two agreement sub-protocols will terminate fast enough (and correctly). By doubling the k̂ in each phase, the algorithm will terminate in O(min{B/n, f }) rounds. We now focus on our agreement sub-protocol that terminates in O(k) rounds when there are at most k misclassified processes (which is the new contribution in this paper). Here, we use the Byzantine agreement with an implicit committee from Section 6.1. In a phase, we set the number of groups m ∈ Θ(k̂) such that if B ∈ o(n2 ) and k̂ ≥ cB/n for some constant c, there will be 1 more than 2m 3 1-good groups (for Theorem 1) or 2 -good groups (for Theorem 2) at line 15; such m exists due to Lemma 3 (1-good groups) and Lemma 4 ( 12 -good groups). Then, each process pi deterministically computes an m-grouping Gi . For each computed group, each process participates in a group leader election to produce a vector Li ; these can be run in parallel (line 19). Then, using 7
Regarding the number of misclassified processes, we are actually estimating the prediction errors B. However, this is fine as by estimating B, we are also estimating the number of misclassified processes, which is O(B/n).
16
the vector of processes Li , each process invokes the Byzantine agreement with implicit committee (line 20). Therefore, the sub-protocol will terminate in O(m) = O(k̂) rounds. Algorithm 5 Unauthenticated Byzantine Agreement with Classification Predictions: Pseudocode (for process pi ) 1: Input parameters: 2: Value vi 3: Prediction ai 4: Local variables: 5: Grade gi ← ⊥ 6: Value decision i ← ⊥ 7: UnauthenticatedAgreement(vi , ai ): 8: for Integer ϕ ← 1 to ⌈log2 (t)⌉ + 1: ▷ estimates at most k̂ = 2ϕ−1 faults or misclassified processes 9: (vi , gi ) ← GradedConsensus(vi ) 10: let T ← α · 2ϕ−1 11: let v ′ ← ByzantineAgreement(vi ) executed for T rounds ▷ early-stopping Byzantine agreement 12: if gi = 0: 13: vi ← v ′ 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28:
(vi , gi ) ← GradedConsensus(vi ) let m ← β · 2ϕ−1 let Li ← [p1 , p2 , . . . , pm ] let Gi ← M Grouping(Π, m) for Integer j ← 1 to m: Li [j] ← GroupLeaderElection(Gi [j], ai ) let v ′ ← AgreementWithImplicitCommittee(vi , Li ) if gi = 0: vi ← v ′ (vi , gi ) ← GradedConsensus(vi ) if decision i ̸= ⊥: return decision i and halt else if gi = 1: decision i ← vi return decision i
▷ m ∈ Θ(k̂) such that there are > 2m good groups 3 ▷ see Definition 4 ▷ run in parallel ▷ Algorithm 2
▷ will decide in the next iteration ▷ if has not halted yet
In [3], it was proven that the overall algorithm correctly solves Byzantine agreement if the Byzantine agreement protocol with predictions works as claimed. The graded consensus and earlystopping Byzantine agreement are sufficient to prove safety and liveness, while the predictionbased Byzantine agreement is used to ensure the improved round complexity. Therefore, our main challenge is to analyze the round and communication complexities of the algorithm. We start by focusing on the number of phases run until all honest processes decide. Lemma 19 (Restated from [3]). Suppose at phase ϕ, the output of the early-stopping Byzantine agreement or the Byzantine agreement with implicit committee satisfies both strong unanimity and agreement. Then, all honest processes decide by the end of phase ϕ + 1. Lemma 20. Suppose B ∈ o(n2 ), and there are k misclassified processes. Then, in a phase ϕ with 2ϕ−1 ≥ k, the output of the Byzantine agreement with implicit committee satisfies both strong unanimity and agreement. Proof. In phase ϕ, we set m to be Θ(2ϕ−1 ) such that when there are at most 2ϕ−1 misclassified 2 processes, there will be more than 2m 3 1-good groups. Note that such m exists as B ∈ o(n ), due to Lemma 3 (1-good groups) and Lemma 4 ( 12 -good groups). From the group leader election, in a 1-good group, all honest processes will elect the same honest process. As each honest process pi 17
computes the same grouping G, and there will be more than 2m 3 indices j with Li [j] being the same honest process in all honest processes, the assumptions needed by the Byzantine agreement with implicit committee are satisfied. Therefore, the output of the Byzantine agreement with implicit committee will satisfy both strong unanimity and agreement. Let us note that since a 12 -good group is also a 1-good group, Lemma 20 also holds when we 1 aim to have more than 2m 3 2 -good groups, i.e., in Theorem 2 when m is chosen via Lemma 4. The earliest phase where the output of the early-stopping Byzantine agreement satisfies both strong unanimity and agreement is at most log2 (f ) + O(1) (when it is run for long enough). Then, from Lemma 20, if B ∈ o(n2 ), the earliest phase where the output of the Byzantine agreement with implicit committee satisfies both properties is at most log2 (B/n) + O(1). As B ∈ Ω(n2 ) implies B/n ∈ Ω(n), we claim the following. Lemma 21. All honest processes decide within log2 (min{B/n, f }) + O(1) phases. Next, to prove our main unauthenticated results, we use the following implementation for our graded consensus and early-stopping Byzantine agreement. Lemma 22 (Graded consensus, restated from [15]). There is an unauthenticated algorithm for graded consensus that tolerates up to t < n/3 faulty processes. The algorithm terminates in O(1) rounds, exchanges O(n2 ) messages, and exchanges O(n2 ) bits. Lemma 23 (Early-stopping Byzantine agreement, restated from [29]). There is an unauthenticated algorithm for Byzantine agreement that tolerates up to t < n/3 faulty processes. The algorithm terminates in O(f ) rounds (where f ≤ t is the actual number of faults), exchanges O(n2 ) messages, and exchanges O(n2 ) bits. Note that from Lemma 8, when our Byzantine agreement with implicit committee is run on O(2ϕ ) groups, will terminate in O(2ϕ ) rounds, exchange O(n2 ) messages, and exchanges O(n2 ) bits. Next, observe that if we ignore the group leader elections, each phase ϕ runs for O(2ϕ ) rounds, exchanges O(n2 ) messages, and exchanges O(n2 ) bits. Furthermore, recall that the group leader elections can be run in parallel. Combined with Lemma 21, we obtain the following. Lemma 24. Assuming each group leader election terminates in O(1) rounds, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, ignoring the communication done in each group leader election, the algorithm exchanges O(n2 log(min{B/n, f })) messages, and exchanges O(n2 log(min{B/n, f })) bits. We are now ready to prove our main unauthenticated results. Theorem 1. There is an unauthenticated algorithm for Byzantine agreement that tolerates up to t < ( 13 − ϵ)n faulty processes for any constant 0 < ϵ < 13 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 log(min{B/n, f })) messages and O(n3 ) bits. Proof. We use the group leader election from Lemma 2. Next, we apply Lemma 3 to choose the value of m during a phase. From Lemma 3, Lemma 22 (graded consensus), and Lemma 23 (earlystopping Byzantine agreement), the algorithm tolerates up to t < ( 31 − ϵ)n Byzantine processes. Combined with Lemma 24, we obtain the stated complexities. Theorem 2. There is an unauthenticated algorithm for Byzantine agreement that tolerates up to t < ( 16 − ϵ)n faulty processes for any constant 0 < ϵ < 16 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 log(min{B/n, f })) messages and O(n2.5 log(n) log(min{B/n, f })) bits. 18
Proof. We use the group leader election from Lemma 9. As it requires a 12 -good group, we use Lemma 4 to choose the value of m during a phase. From Lemma 4, Lemma 9 (group leader election), Lemma 22 (graded consensus), and Lemma 23 (early-stopping ByzantinePagreement), the algorithm tolerates up to t < ( 16 − ϵ)n Byzantine processes. Then, observe that g∈G |g| = n for each computed m-grouping G in any phase. Thus, in each phase, honest processes exchange O(n2 ) messages and O(n2.5 log(n)) bits across all group leader elections. Combined with Lemma 21 and Lemma 24, we obtain the stated complexities.
7
Authenticated Algorithm
In this section, we describe our Byzantine agreement with classification predictions that uses cryptography. The algorithm can tolerate up to t < ( 12 − ϵ)n Byzantine processes, terminates in O(min{B/n, f }) rounds, and exchanges O(n2 κ) bits. The algorithm is based on a well-known reduction from Byzantine agreement with strong unanimity to the one with external validity (also known as validated Byzantine agreement), where a decision v must satisfy a pre-determined predicate externallyValid(·) (that is, externallyValid(v) = true). Importantly, the reduction takes constant rounds, and exchanges O(n2 κ) bits (see Appendix C for the details). Next, a key component in our result is efficient group leader election that, after a pre-processing step with constant rounds and O(n2 κ) bits, can do the election with zero communication. Then, by using a leader-based validated Byzantine agreement and alternating between round-robin leaders and leaders obtained from the predictions (via m-grouping and group leader election), we get an algorithm with the complexities as desired. We first describe our validated Byzantine agreement in Section 7.1. Next, we describe the group leader election we use in Section 6.2. Finally, we describe our full algorithm in Section 7.3, where we use the predictions along with the validated Byzantine agreement to obtain the desired result.
7.1
Validated Byzantine Agreement
In the validated Byzantine agreement problem, each process has to agree on a value v that satisfies a pre-determined predicate externallyValid(·). Here, each process proposes a value that is externallyvalid, i.e., satisfies the predicate. For our use case, besides their proposal, each process pi also has a vector of processes Li as an input. Our algorithm will work in a leader-based manner, where pi will consider Li [j] as the leader for view (iteration) j. Note that we do not assume all processes input the same vector, and so, during a view, two honest processes may perceive a different process as their leader. Our implementation (Algorithm 6) that tolerates up to t < ( 12 − ϵ)n faults for some constant 0 < ϵ < 12 is based on the agreement part of the Byzantine broadcast protocol from [41]. At a high level, they employ quorum-based agreement, where the resilience is strengthened by the use of expander graph: a graph (that typically has a low degree) with a good expansion property. In their algorithm, they use the following (n, 2ϵ, 1 − 2ϵ)-expander graph from Momose and Ren [35]. Lemma 25 ((n, 2ϵ, 1 − 2ϵ)-expander graph, restated from [35]). For any constant 0 < ϵ < 21 and any positive integer n, there is a constant degree graph with n vertices such that any set of 2ϵn vertices is connected to a set of at least (1 − 2ϵ)n vertices. The graph is used to forward the messages from the leader, which, as we show later, is important in strengthening the resilience. However, there is a subtle problem we need to deal with. As mentioned before, the expander graph is used to forward the messages from the leader. Previously, this was fine because in a view, 19
each process had the same leader. However, as now processes may have different leaders, the proof would not work anymore. There is a quite simple fix. We define leader proof, a cryptographic object that proves a certain process is considered a leader by sufficiently many honest processes. Definition 5 (Leader Proof). For a process pℓ and a view j, a leader proof for pℓ during view j is a threshold signature µ where CombinedVerifyn−t (µ, ⟨leader, pℓ , j⟩) = true. Then, each process that has a leader proof is considered the leader(s) of the view, and has to attach the leader proof in their messages to prove that they are indeed qualified as the leader. This solves the subtle correctness problem we had, and also allows us to bound the communication complexity per view. The rest of the protocol is quite similar to the original version; we describe it again for completeness. Before describing the protocol, let us describe the following two cryptographic objects that will be crucial for the correctness of the protocol. Definition 6 (Commit Certificate). For a value v and a view j, a commit certificate for v during view j is a threshold signature µ where CombinedVerifyn−t (µ, ⟨commit, v, j⟩) = true. Definition 7 (Decision Proof). For a value v, a decision proof for v is a threshold signature µ where CombinedVerifyn−t (µ, ⟨decide, v⟩) = true. Now, let us describe the protocol as presented in Algorithm 6. First, the protocol uses an expander graph G from Lemma 25. Next, the protocol goes through |L| views, where |L| is the size of every Li input by an honest process pi (line 13). We now focus on how a view goes. First, each process sends to its leader a partial signature for its leader proof, along with a value. This value is either a value with the highest commit certificate the process has (line 16), or its input value if it does not have any commit certificate (line 18). In the former case, the process also sends the commit certificate. Next, if a process receives n − t messages, it can produce a leader proof for itself. It does so, and then it checks whether it receives any value with a commit certificate. If it does, it proposes the value which commit certificate’s view is the highest, and otherwise, it broadcasts any externally-valid value v (line 23); the process also attaches its leader proof in the message. Then, upon receiving a proposal for the value v from its leader, a process forwards the message to its neighbors in G (line 25). If no message with a different value is received through G, then the process sends a partial signature for a commit certificate for the value v proposed by its leader (line 27). Next, if a process previously managed to produce its leader proof and it receives n − t partial signatures for a commit certificate for a value v, it forms a commit certificate for v and broadcasts it (line 30). Then, upon receiving a value v with its commit certificate from its leader, a process stores them, forwards the received message (that also contains a leader proof) to its neighbors in G (line 33), and then sends a partial signature for a decision proof for v to its leader (line 34). Note that here, processes only disseminate the committed value and its certificate through G, and always partially sign a decision proof (see line 34 and line 36). Then, similar to before, if a process has a leader proof and receives n − t partial signatures for a decision for a value v, it forms a decision proof for v and broadcasts it (line 39). Lastly, if a process receives a value accompanied by its decision proof from its leader, it stores them (line 41) to be used as the final decision after all views have concluded (line 42). We now prove the correctness of the algorithm. Lemma 26. If in a view, a commit certificate for the value v and v ′ exists, then v = v ′ .
20
Algorithm 6 Validated Byzantine Agreement: Pseudocode (for process pi ) 1: Uses: 2: ExpanderGraph, instance G
▷ see Lemma 25
3: Input parameters: 4: Value vi 5: Vector(Process) Li
▷ externally-valid value
6: Local variables: 7: Value commit value i ← ⊥ 8: CommitCertificate commit cert i ← ⊥ 9: Value decision value i ← ⊥ 10: DecisionProof decision proof i ← ⊥ 11: LeaderProof leader proof i ← ⊥ 12: ValidatedAgreement(vi , Li ): 13: for Integer j ← 1 to |Li |: 14: let ℓi ← Li [j] 15: if commit cert i ̸= ⊥: 16: send ⟨val, commit value i , commit cert i , ShareSignn−t (⟨leader, ℓi , j⟩)⟩ to ℓi i 17: else: 18: send ⟨val, vi , ShareSignn−t (⟨leader, ℓi , j⟩)⟩ to ℓi i 19: 20: 21: 22: 23:
if pi = ℓi and received n − t val messages: leader proof i ← Combinen−t ({psig | psig is received from n − t processes}) let v , cert be the value with the highest commit view and its commit certificate from the received messages (if there is none, then v is any valid value and cert = ⊥) broadcast ⟨propose, v , cert, leader proof i ⟩
24: 25: 26: 27:
if received ⟨propose, v , cert, lp⟩ from ℓi and it is from a view at least as high as pi ’s commit: forward to pi ’s neighbor in G if no conflicting value with a leader proof is received through G: send ⟨ack, v , ShareSignn−t (⟨commit, v , j ⟩)⟩ to ℓi ▷ partially sign the value proposed by leader i
28: 29: 30:
if pi has a leader proof for view j and pi received n − t ack messages for the same v : let cc ← Combinen−t ({psig | psig is received from n − t processes}) broadcast ⟨commit, v , cc, leader proof i ⟩
31: 32: 33: 34:
if received ⟨commit, v , cc, lp⟩ from ℓi : commit value i ← v ; commit cert i ← cc forward to pi ’s neighbor in G send ⟨commit, commit value i , ShareSignn−t (⟨decide, commit value i ⟩)⟩ to ℓi i
35: 36:
if received valid ⟨commit, v , cc, lp⟩ through G: commit value i ← v ; commit cert i ← cc
37: 38: 39:
if pi has a leader proof for view j and pi received n − t commit messages for the same v : let dp ← Combinen−t ({psig | psig is received from n − t processes}) broadcast ⟨decide, v , dp, leader proof i ⟩
40: 41: 42:
if received ⟨decide, v , dp, lp⟩ from ℓi : decision value i ← v ; decision proof i ← dp return (decision value i , decision proof i )
Proof. A commit certificate must be partially signed by at least n − t − f ≥ n − 2t > 2ϵn honest processes. Honest processes that partially sign a commit certificate for v must have forwarded the value v through G at line 25, which will be accepted by at least (1 − 2ϵ)n > 2t processes (note that the forwarded message must contain a valid leader proof). Hence, at least 2t + 1 − f honest processes would have received the forwarded value at line 26, in which they would not partially sign a commit certificate for a value v ′ ̸= v. As at most n − f − (2t + 1 − f ) = n − (2t + 1) < n − t − f honest processes could partially sign a commit certificate for a value v ′ ̸= v, there would not be enough signatures to produce a commit certificate for v ′ ̸= v.
21
Lemma 27 (Agreement). If a decision proof for the value v and v ′ exists, then v = v ′ . Proof. Let us focus on the first view where a decision proof exists, and suppose it is for the value v. At least n − t − f > 2ϵn honest processes partially signed for a decision proof for the value v. These processes forwarded the commit certificate for v through G, which will be received by at least (1 − 2ϵ)n > 2t processes, out of which at least 2t + 1 − f are honest. By Lemma 26, at this point, only a decision proof for v may exist, and the commit certificate for the highest view is for v. Moreover, in the future views, at least 2t + 1 − f honest processes will only sign the commit certificate (and thus, decision proof) for the value v (due to the check at line 24). Finally, no commit certificate nor decision proof for the value v ′ ̸= v can be produced (as there are not enough honest processes that would support it). Lemma 28 (External Validity). If a decision proof for the value v exists, then v satisfies external validity. Proof. If a decision proof for the value v exists, then a commit certificate for the value v exists. If a commit certificate for the value v exists, either v satisfies external validity (externallyValid(v) = true) or a commit certificate for v from a lower view exists. From induction, in the latter case, v also satisfies external validity. Hence, safety is guaranteed. We then argue that when all honest processes have the same honest leader, then they all obtain a decision and its proof. Lemma 29 (Conditional Termination). In a view j where for each honest process pi , Li [j] = pℓ for some honest process pℓ , each honest process obtains a decision and its decision proof. Proof. In such a view, pℓ will receive ⟨val⟩ messages from all honest processes. Thus, pℓ can build a leader proof for itself, and obtain a value with a commit certificate that all honest processes will accept. pℓ then broadcast them via ⟨propose⟩ message. Moreover, as there can be no process with a leader proof in that view besides pℓ , all honest processes will send ⟨ack⟩ for the received value. Thus, pℓ can build a commit certificate for that value, and broadcast that value along with the commit certificate. Similarly, each honest process will accept this value and send a partial signature for its decision proof. Finally, pℓ builds a decision proof for that value and broadcast them to all honest processes. Therefore, as long as at least one of the views has the same honest leader, the algorithm correctly solves Byzantine agreement with external validity, given there are at most t < ( 12 − ϵ)n faulty processes. Lastly, we prove the complexities of the algorithm. Specifically, we will focus on the complexities of each view. Lemma 30. In each view, at most O(1) processes have a leader proof. Proof. Each leader proof needs n − t partial signatures, so at least n − t − f ≥ n − 2t came from n 1 n honest processes. Thus, there are at most n−2t < 2ϵn = 2ϵ ∈ O(1) such processes. Lemma 31. Each view lasts for O(1) rounds. In each view, honest processes exchange O(n) messages and O(nκ) bits. Proof. The number of rounds can be observed from the algorithm. Then, observe that each message contains O(κ) bits. Furthermore, communications are done in a leader-to-all, all-to-leader pattern, along with the message forwarding through the expander graph. As there are O(1) leaders (Lemma 30) and the expander graph has constant degree, O(n) messages and O(nκ) bits are exchanged in each view. 22
7.2
Group Leader Election
We now present a simple way to do the group leader election efficiently with cryptography (see Algorithm 7). Here, we use partial signatures to vote for each process in the group that is predicted to be honest. When those processes have more than n/2 votes, they can use the (aggregated) votes to prove that more than n/2 processes predict that they are honest.8 In a 1-good group, taking the smallest process with such a voting proof ensures each honest process will elect the same honest process as the leader. Algorithm 7 Authenticated Group Leader Election: Pseudocode (for process pi ) 1: Input parameters: 2: Group Gi 3: Prediction ai 4: AuthenticatedElection(Gi , ai ): 5: for each pj ∈ Gi with ai [j] = 1: ⌈(n+1)/2⌉ 6: send ⟨vote, pj , ShareSigni (⟨vote, pj ⟩)⟩ to pj 7: 8: 9:
if pi ∈ Gi : let vote proofi ← Combine⌈(n+1)/2⌉ ({psig | psig is received from ⌈(n + 1)/2⌉ vote messages for pi }) broadcast ⟨vote proof, pi , vote proofi ⟩
10: 11:
let ℓi be the smallest process in Gi that sent valid ⟨vote proof⟩ message to pi return ℓi
We now prove the correctness of the algorithm, assuming all honest processes input the same 1-good group G. Lemma 32. If G is a 1-good group, then all honest processes output the same honest process pj ∈ G. Proof. Since G is a 1-good group, each honest process in G will be able to collect more than n/2 votes while no Byzantine process can do so. Hence, each honest process in G will broadcast the threshold signature formed from the votes. Therefore, all honest processes will output the smallest honest process in G. Next, we can observe that the algorithm terminates in 2 rounds, where in total, O(n|G|) messages are sent. Furthermore, O(n|G|κ) bits are sent. Therefore, Lemma 33. There is a group leader election algorithm for a 1-good group G. The algorithm terminates in 2 rounds, exchanges O(n|G|) messages, and exchanges O(n|G|κ) bits. Similar to Lemma 1, we can also do a pre-processing once, and then each process can do the election locally. By doing the algorithm on G = Π, each process will receive the aggregated votes for any honest process that cannot be misclassified. Hence, by exchanging O(n2 κ) bits in 2 rounds, all elections afterward can be done with zero communication. Lemma 34. There is a group leader election algorithm for a 1-good group G. The algorithm has a pre-processing step that terminates in 2 rounds, exchanging O(n2 ) messages and O(n2 κ) bits. After that, all elections can be done without communication. 8
In the pseudocode, we use ⌈(n + 1)/2⌉ votes to ensure the quantity is an integer. This does not affect our proofs.
23
7.3
Full Algorithm
Our full authenticated algorithm is presented at Algorithm 8. First, each process runs the reduction to validated Byzantine agreement (line 8), where each process will obtain a pair of (value, certificate). Here, the certificate is a cryptographic object that proves the value is indeed admissible according to strong unanimity (see Appendix C). Thus, by employing the predicate such that externallyValid(v) = true if and only if v = ⟨v ′ , cert⟩ where cert is a certificate for v ′ , the decision from a validated Byzantine agreement would satisfy strong unanimity. Next, we use the validated Byzantine agreement from Section 7.1 in a similar guess-and-double manner as our unauthenticated algorithm. The algorithm goes through phases. In each phase, the algorithm estimates k̂, the maximum number of actual faults and misclassified processes. This estimate is then used to allocate the leader sequence used by each process. Each process will use the first k̂ processes as the first k̂ + 1 leaders in the validated Byzantine agreement, followed by m = Θ(k̂) processes obtained through group leader elections on m-grouping (see line 10 to line 14). These ensure that when there are indeed at most k̂ faults or misclassified processes, the validated Byzantine agreement will output a valid decision and its decision proof, due to the conditional termination of the sub-algorithm (see Lemma 29). By doubling the estimate k̂ in each phase, the algorithm will terminate in O(min({B/n, f })) rounds. To ensure processes can halt soon enough after obtaining a valid decision, we use the fact that the validated Byzantine agreement also outputs a cryptographic object that proves the legitimacy of the decision (the decision proof). Right before deciding, a process broadcasts the decision and decision proof from the validated Byzantine agreement (line 19). Therefore, all processes may decide by the end of the next phase (see line 16). Before concluding on the algorithm description, let us remark on a small detail regarding the validated Byzantine agreement. Let us note that the agreement and external validity of the validated Byzantine agreement come from the commit certificate used therein (see Definition 6). Thus, in our algorithm, the commit certificate from the validated Byzantine agreement during a phase should be carried over to the one in the phase after. We omit this in our implementation detail for clarity. Alternatively, one can view our full algorithm as a single validated Byzantine agreement instance, where the leaders are chosen alternating between round-robin and group leader elections. We now prove the correctness of the algorithm. We start by proving that all honest processes will decide. In fact, we will prove a stronger statement: all honest processes decide by the end of phase ⌈log2 (f )⌉ + 1 (recall that f ≤ t denotes the actual number of Byzantine processes). Lemma 35. Suppose an honest process decides at phase ϕ < ⌈log2 (t)⌉ + 1. Then, each honest process decides by the end of phase ϕ + 1. Proof. Before deciding, the honest process broadcasts its decision and a decision proof at line 19. All processes will receive them at phase ϕ + 1 at line 16 and so, will decide by the end of the phase. Lemma 36 (Termination). All honest processes decide by the end of phase ⌈log2 (f )⌉ + 1. Proof. Suppose an honest process decides at some phase ϕ′ < ⌈log2 (f )⌉ + 1. Then, from Lemma 35, all honest processes will decide by the end of phase ϕ′ + 1. Thus, suppose that by the start of phase ⌈log2 (f )⌉ + 1, no honest process has decided yet. As 2⌈log2 (f )⌉ ≥ f , there is j with 1 ≤ j ≤ f + 1 where for each honest process pi , Li [j] = pℓ for some honest process pℓ . From the conditional termination of the validated Byzantine agreement (Lemma 29), all honest processes will obtain a decision and its decision proof from the sub-protocol and so, will decide by the end of the phase.
24
Algorithm 8 Authenticated Byzantine Agreement with Classification Predictions: Pseudocode (for process pi ) 1: Input parameters: 2: Value vi 3: Prediction ai 4: Local variables: 5: Value certified value i ← ⊥ 6: Certificate cert i ← ⊥
▷ proves certified value i satisfies strong unanimity; see Appendix C
7: AuthenticatedAgreement(vi , ai ): 8: (certified value, cert i ) ← StrongCertification(vi ) 9: for Integer ϕ ← 1 to ⌈log2 (t)⌉ + 1: 10: let m ← β · 2ϕ−1 11: let Li ← [p1 , p2 , . . . , p2ϕ−1 +1+m ] 12: let Gi ← M Grouping(Π, m) 13: for Integer j ← 1 to m: 14: Li [2ϕ−1 + 1 + j] ← GroupLeaderElection(Gi [j], ai ) 15: 16: 17: 18: 19: 20: 21:
▷ see Appendix C ▷ m ∈ Θ(k̂) such that there is a good group
let (decision i , decision proof i ) ← ValidatedAgreement(⟨certified value i , cert i ⟩, Li ) if received valid ⟨decision, d , d proof ⟩ from the previous phase: decision i ← d ; decision proof i ← d proof if decision i ̸= ⊥: broadcast ⟨decision, decision i , decision proof i ⟩ let (v, cert) ← decision i return v and halt
▷ see Definition 4 ▷ run in parallel ▷ Algorithm 6
Next, strong unanimity follows from the reduction to external validity and the employed predicate. Lemma 37 (Strong unanimity). If all honest processes propose the same value v, then all honest processes will decide v. Proof. From Lemma 36, all honest processes will decide. Furthermore, due to the external validity of the validated Byzantine agreement (Lemma 28) and the employed externallyValid(·) predicate, each decision is a value v ′ that has a certificate obtained from the strong unanimity to external validity reduction (see Appendix C). Finally, as a certificate proves that v ′ is admissible under strong unanimity, v ′ = v. Finally, agreement follows from the agreement of the validated Byzantine agreement. Lemma 38 (Agreement). Each honest process decides the same value v. Proof. From the agreement of the validated Byzantine agreement (Lemma 27), only a single value may have a decision proof. As each process decides v such that there is a decision proof for (v, ·), the lemma statement holds. Hence, the algorithm correctly solves Byzantine agreement. We now focus on the complexities. Lemma 39. All honest processes decide within log2 (min{B/n, f }) + O(1) phases. Proof. If B ∈ Ω(n2 ), then this follows from Lemma 36. Thus, suppose B ∈ o(n2 ). From Lemma 36, honest processes decide in at most ⌈log2 (f )⌉ + 1 phases. Furthermore, since B ∈ o(n2 ), there exists a phase ϕ′ ≤ log2 (B/n) + O(1) where, due to Lemma 5 (which we use to pick the number of groups m), there exists a 1-good group from the m-grouping done in phase ϕ′ . Hence, from the properties ′ ′ of the group leader election, during phase ϕ′ , there is j with 2ϕ −1 + 1 < j ≤ 2ϕ −1 + 1 + m such 25
that for each honest process pi , Li [j] = pℓ for some honest process pℓ . Due to the conditional termination of the validated Byzantine agreement (Lemma 29), all honest processes will decide by the end of phase ϕ′ . Therefore, all honest processes decide in log2 (min{B/n, f }) + O(1) phases. Next, observe that in phase ϕ, the size of Li for each honest process pi is 2ϕ−1 + 1 + Θ(2ϕ−1 ). Hence, during the validated Byzantine agreement at phase ϕ, each process will go through that many views. Therefore, Lemma 40. Assuming each group leader election has O(1) rounds, all honest processes decide in O(min{B/n, f }) rounds. Furthermore, ignoring the communications done in each group leader election, honest processes exchange O(n2 ) messages and O(n2 κ) bits. Proof. The size of Li in phase ϕ is Θ(2ϕ ). As honest processes decide in log2 (min{B/n, f }) + O(1) phases (Lemma 39) and each view in the validated Byzantine agreement has O(1) rounds (Lemma 31), in total, O(min{B/n, f }) rounds are spent for the validated Byzantine agreement. Finally, the reduction to external validity has O(1) rounds (Lemma 43), and each phase has additional 1 round to broadcast the decision (at line 19). Thus, all honest processes decide in O(min{B/n, f }) rounds. Next, as each view of the validated Byzantine agreement exchanges O(n) messages and O(nκ) bits, honest processes exchange O(n · min{B/n, f }) messages and O(n · min{B/n, f }κ) bits in the sub-protocol. Then, the reduction to external validity exchanges O(n2 ) messages and O(n2 κ) bits (Lemma 43), and broadcasting the decision at line 19 incurs O(n) messages and O(nκ) bits per honest process. Therefore, O(n2 ) messages and O(n2 κ) bits are exchanged. We finally conclude with our main authenticated result. Theorem 3. There is an authenticated algorithm for Byzantine agreement that tolerates up to t < ( 12 − ϵ)n faulty processes for any constant 0 < ϵ < 12 . Given classification predictions with B error bits, the algorithm terminates in O(min{B/n, f }) rounds. Furthermore, the algorithm exchanges O(n2 ) messages and O(n2 κ) bits. Proof. We use the group leader election from Lemma 34. Next, recall that we use the reduction from Appendix C, validated Byzantine agreement from Section 7.1, and Lemma 5 (to choose m). Therefore, the algorithm tolerates up to t < ( 21 − ϵ)n faulty processes. Finally, combined with Lemma 40, we obtain the complexities as stated.
8
Conclusion
In this paper, we present several implementations for Byzantine agreement with classification predictions that achieve optimal O(min{B/n, f }) round complexity for any number of prediction errors B. We first give an algorithm that tolerates up to t < ( 13 − ϵ)n faults while exchanging Õ(n2 ) messages, but still sends O(n3 ) bits. Then, we present an algorithm that exchanges Õ(n2.5 ) bits, at the cost of reducing the resilience to ( 16 − ϵ)n. Finally, via threshold signature, we give an algorithm tolerating up to t < ( 21 − ϵ)n faults that exchanges optimal O(n2 κ) bits. Several questions remain. First, is it possible to further lower the communication complexity? For general Byzantine agreement, only O(n2 ) communication is needed—so there is reason to believe further improvement is possible. At the same time, current approaches require some coordination of predictions to achieve improved round complexity, and so this overhead may be inherent to using predictions effectively.
26
Next, is it possible to achieve current results but with better resilience? The current approach, based on good groups, makes it structurally difficult to achieve better resilience. At the same time, it seems plausible that other approaches can do better. Lastly, it would be interesting to see whether the classification predictions can help in weaker synchrony settings, such as partial synchrony. Many of the techniques in this paper seem transferable to partially synchronous settings, and so there is clear room for future work.
References [1] Abd-El-Malek, M., Ganger, G. R., Goodson, G. R., Reiter, M. K., and Wylie, J. J. Fault-Scalable Byzantine Fault-Tolerant Services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles 2005, SOSP 2005, Brighton, UK, October 23-26, 2005 (2005), ACM, pp. 59–74. [2] Azar, Y., Panigrahi, D., and Touitou, N. Online Graph Algorithms with Predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022 (2022), J. S. Naor and N. Buchbinder, Eds., SIAM, pp. 35–66. [3] Ben-David, N., Dzulfikar, M. A., Ellen, F., and Gilbert, S. Byzantine Agreement with Predictions. In Proceedings of the ACM Symposium on Principles of Distributed Computing (New York, NY, USA, 2025), PODC ’25, Association for Computing Machinery, p. 3–14. [4] Berman, P., Garay, J. A., and Perry, K. J. Bit Optimal Distributed Consensus. In Computer science: research and applications. Springer, 1992, pp. 313–321. [5] Boyar, J., Ellen, F., and Larsen, K. S. Brief Announcement: Distributed Graph Algorithms with Predictions. In Proceedings of the ACM Symposium on Principles of Distributed Computing (2025), PODC ’25, Association for Computing Machinery, p. 322–325. [6] Buchman, E. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. PhD thesis, University of Guelph, 2016. [7] Castro, M., and Liskov, B. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (USA, 1999), OSDI ’99, USENIX Association, p. 173–186. [8] Chandra, T. D., Hadzilacos, V., and Toueg, S. The weakest failure detector for solving consensus. J. ACM 43, 4 (1996), 685–722. [9] Chandra, T. D., and Toueg, S. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (Mar. 1996), 225–267. [10] Choo, D., Gouleakis, T., Ling, C. K., and Bhattacharyya, A. Online bipartite matching with imperfect advice. In Proceedings of the 41st International Conference on Machine Learning (2024), ICML’24, JMLR.org. [11] Civit, P., Collins, D., Gramoli, V., Guerraoui, R., Komatovic, J., Vidigueira, M., and Zarbafian, P. Scalable accountable byzantine agreement and beyond. Cryptology ePrint Archive, Paper 2025/1277, 2025.
27
[12] Civit, P., Dzulfikar, M. A., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J., and Vidigueira, M. Byzantine consensus is Θ(n2 ): the Dolev-Reischuk bound is tight even in partial synchrony! Distributed Computing 37, 2 (Jun 2024), 89–119. [13] Civit, P., Dzulfikar, M. A., Gilbert, S., Guerraoui, R., Komatovic, J., and Vidigueira, M. DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (2024), PODC ’24, Association for Computing Machinery, p. 145–156. [14] Civit, P., Dzulfikar, M. A., Gilbert, S., Guerraoui, R., Komatovic, J., and Vidigueira, M. Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (2025), PODC ’25, Association for Computing Machinery, p. 15–27. [15] Civit, P., Dzulfikar, M. A., Gilbert, S., Guerraoui, R., Komatovic, J., Vidigueira, M., and Zablotchi, I. Efficient Signature-Free Validated Agreement. In 38th International Symposium on Distributed Computing (DISC 2024) (2024), vol. 319 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 14:1–14:23. [16] Civit, P., Gilbert, S., and Gramoli, V. Polygraph: Accountable byzantine agreement. In Proceedings of the 41st IEEE International Conference on Distributed Computing Systems (ICDCS’21) (Jul 2021). [17] Civit, P., Gilbert, S., Gramoli, V., Guerraoui, R., and Komatovic, J. As easy as abc: Optimal (a)ccountable (b)yzantine (c)onsensus is easy! In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2022), pp. 560–570. [18] Civit, P., Gilbert, S., Gramoli, V., Guerraoui, R., Komatovic, J., Milosevic, Z., and Seredinschi, A. Crime and punishment in distributed byzantine decision tasks. In 42nd IEEE International Conference on Distributed Computing Systems, ICDCS 2022, Bologna, Italy, July 10-13, 2022 (2022), IEEE, pp. 34–44. [19] Crain, T., Gramoli, V., Larrea, M., and Raynal, M. DBFT: Efficient Leaderless Byzantine Consensus and its Applications to Blockchains. In Proceedings of the 17th IEEE International Symposium on Network Computing and Applications (NCA’18) (2018), IEEE. [20] Dallot, J., Caldeira, C., Pourdamghani, A., Goussevskaia, O., and Schmid, S. LASLiN: A Learning-Augmented Peer-to-Peer Network, 2025. [21] Darktrace. https://darktrace.com. Accessed: 2026-02-05. [22] Dolev, D., and Reischuk, R. Bounds on information exchange for Byzantine agreement. Journal of the ACM (JACM) 32, 1 (1985), 191–204. [23] Dolev, D., Reischuk, R., and Strong, H. R. Early stopping in Byzantine agreement. J. ACM 37, 4 (1990), 720–741. [24] Dolev, D., and Strong, H. R. Authenticated Algorithms for Byzantine Agreement. SIAM Journal on Computing 12, 4 (1983), 656–666. [25] Fischer, M. J., and Lynch, N. A. A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14, 4 (1982), 183–186. 28
[26] Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017 (2017), ACM, pp. 51–68. [27] Gilbert, S., Newport, C., Vaidya, N. H., and Weaver, A. Contention resolution with predictions. In PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021 (2021), A. Miller, K. Censor-Hillel, and J. H. Korhonen, Eds., ACM, pp. 127–137. [28] Lamport, L., Shostak, R. E., and Pease, M. C. The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4, 3 (1982), 382–401. [29] Lenzen, C., and Sheikholeslami, S. A Recursive Early-Stopping Phase King Protocol. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (2022), PODC’22, Association for Computing Machinery, p. 60–69. [30] Li, S., and Xian, J. Online unrelated machine load balancing with predictions revisited. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (2021), M. Meila and T. Zhang, Eds., vol. 139 of Proceedings of Machine Learning Research, PMLR, pp. 6523–6532. [31] Libert, B., Joye, M., and Yung, M. Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares. Theoretical Computer Science 645 (2016), 1–24. [32] Malkhi, D., and Reiter, M. Unreliable intrusion detection in distributed computations. In Proceedings 10th Computer Security Foundations Workshop (1997), pp. 116–124. [33] Mitzenmacher, M., and Vassilvitskii, S. Algorithms with predictions, 2020. [34] Mitzenmacher, M., and Vassilvitskii, S. Algorithms with predictions. Commun. ACM 65, 7 (June 2022), 33–35. [35] Momose, A., and Ren, L. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021) (2021), vol. 209 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 32:1–32:16. [36] Pease, M. C., Shostak, R. E., and Lamport, L. Reaching agreement in the presence of faults. J. ACM 27, 2 (1980), 228–234. [37] Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems (2018), S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, Eds., vol. 31, Curran Associates, Inc. [38] Sheng, P., Wang, G., Nayak, K., Kannan, S., and Viswanath, P. BFT protocol forensics. In CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 - 19, 2021 (2021), Y. Kim, J. Kim, G. Vigna, and E. Shi, Eds., ACM, pp. 1722–1743.
29
[39] Shoup, V. Practical Threshold Signatures. In Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding (2000), vol. 1807 of Lecture Notes in Computer Science, Springer, pp. 207–220. [40] Vectra AI. https://www.vectra.ai. Accessed: 2026-02-05. [41] Wan, J., Momose, A., Ren, L., Shi, E., and Xiang, Z. On the Amortized Communication Complexity of Byzantine Broadcast. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (2023), PODC ’23, Association for Computing Machinery, p. 253–261.
A
Missing Proofs in Section 5
In this section, we provide the proofs for Lemma 4 and Lemma 5. Lemma 4. Suppose there are f < ( 16 − ϵ)n faulty processes and k misclassified processes, where 0 < ϵ < 61 is a constant. Then, there exist two positive constants c1 and c2 such that, if c1 k < m < 1 c2 n, then for any grouping satisfying the m-grouping, more than 2m 3 groups are 2 -good. Proof. Recall that if a group is not c-good, then it either has a misclassified process or at least f ⌈c|G|⌉ of its members are Byzantine. As c = 12 , at most k + ⌈ 1 ⌊n/m⌋⌉ groups are not 12 -good. Next, 2
ϵ we set c1 = 1ϵ and c2 = 1/3−ϵ . Thus, at least
m−k−
(1/6 − ϵ)n
f
>m−k− 1 ⌈ 12 ⌊n/m⌋⌉ 2 · (n/m − 1) =m−k− >m−k−
(1/3 − 2ϵ)mn n−m (1/3 − 2ϵ)mn (1/3−2ϵ)n (1/3−ϵ)
> m − ϵm − (1/3 − ϵ)m = 2m/3 groups are 12 -good groups. Lemma 5. Suppose there are f < ( 12 − ϵ)n faulty processes and k misclassified processes, where 0 < ϵ < 21 is a constant. Then, there exist two positive constants c1 and c2 such that, if c1 k < m < c2 n, then for any grouping satisfying the m-grouping, some of the groups are 1-good. ϵ Proof. We use a similar observation as in Lemma 3 and Lemma 4. Here, we set c1 = 2ϵ and c2 = 1−ϵ .
30
Therefore, at least m−k−
f ·(1/2 − ϵ)n >m−k− ⌈⌊n/m⌋⌉ n/m − 1 (1/2 − ϵ)mn =m−k− n−m (1/2 − ϵ)mn >m−k− (1−2ϵ)n (1−ϵ)
ϵ > m − m − (1/2 − ϵ/2)m 2 = m/2 groups are 1-good groups.
B
Conciliation with Core Set
Let us recall the problem of conciliation with core set. In this problem, each process pi inputs a value vi and a set of processes LT i , where (1) Li contains only honest processes, and (2) there is a ‘core set’ C, such that C ⊆ Li and |C| > 12 |Li | for each honest process pi . Then, each pi is honest
process pi outputs a value such that all honest processes output the same value (agreement) and it was input by some honest process (honest-input validity). In their paper [3], Ben-David, Dzulfikar, Ellen, and Gilbert described an implementation for the problem. However, their definition of the problem is quite different from the one we use. First, their assumptions differ, where (1) they assume each process inputs set of processes with the same size (which we do not assume), and (2) the ‘core set’ C has size of more than 2/3 of each set of processes (which we assume has size of more than 1/2 instead). Next, they guarantee agreement and strong unanimity, while we guarantee agreement and honest-input validity. We will explain their implementation and our small modifications, and argue that this implementation solves our definition of the problem. That is, we will prove Lemma 12. Lemma 12. There is an algorithm for conciliation with core set. The algorithm terminates in 1 round, exchanges O(n2 ) messages, and exchanges O(n2 (|v | + |L| log(n))) bits, where |v | denotes the size of the input value and |L| denotes the maximum size of the input process set. The algorithm in [3] is as follows. First, each honest process pi with pi ∈ Li broadcasts its input value vi and set of processes Li . Then, each process pi constructs a graph with vertex set Ti and edges Ei , where: • Ti consists of processes that sent pi a message, and • Ei contains all directed edges (pa , pb ) where pb sent the set L with pa ∈ L to pi . Next, for each pj ∈ Ti , pi defines mi [j] as the smallest value sent by a process that can reach pj in pi ’s graph. Finally, pi takes the majority value from the multiset Mi = {mi [j] | pj ∈ Li } as its output. The ideas behind its guarantees are the following. First, from the assumptions, in each honest process’ graph, for an honest process pi , only the same set of honest processes can reach pi , and no Byzantine process can reach pi . Hence, for each honest process pa , pb , pc , ma [c] = mb [c]. Moreover, the core set C will form a clique in each graph and so, for each honest process pa , pb , pc , with 31
pb , pc ∈ C, ma [b] = ma [c]. As C is a majority in each Li , each honest process will agree on the output. Then, if all honest processes input the same value v, Mi only contains v, so only v can be output. Lastly, we can see that the algorithm terminates in 1 round, exchanges O(n2 ) messages, and exchanges O(n2 (|v| + |L| log(n))) bits. We now describe our modifications. First, each honest process pi always broadcasts its input value vi and its set Li . Then, for each honest process pi , the vertex set Ti consists of all processes. We can observe that these changes still solve the conciliation with core set as defined in [3] with the same complexities. Next, we claim that this implementation also solves our definition of conciliation with core set. Proof of Lemma 12. Let us note that the arguments for agreement require C to be the majority of each Li , which is satisfied by our new assumption. Then, since an honest process can only be reached by an honest process, the value mi [j] for each honest process pi , pj must come from an honest process. Therefore, the set Mi of each honest process pi only contains input values from honest processes, and so, the output of pi must be an input value of some honest process.
C
Strong Unanimity to External Validity
With cryptography, there is a well-known reduction from strong unanimity to external validity [12, 13]. The idea is to produce a certificate, a cryptographic object that proves a certain value is admissible according to the strong unanimity. Then, by employing Byzantine agreement with external validity that admits value in the form of v = ⟨v ′ , cert⟩, where cert is a certificate proving that v ′ is admissible according to strong unanimity, we get Byzantine agreement with strong unanimity. The implementation we use for the reduction is presented at Algorithm 9. Note that this tolerates up to t < n/2 Byzantine processes. Here, there are two types of certificates. First, a threshold signature µ such that CombinedVerifyt+1 (µ, ⟨certify, v ⟩) = true for v ̸= ⊥, that proves v is admissible according to strong unanimity. The last one is a threshold signature µ such that CombinedVerifyt+1 (µ, ⟨certify, ⊥⟩) = true, which proves that any value is admissible according to strong unanimity. Algorithm 9 Strong Unanimity Certification: Pseudocode (for process pi ) 1: Input parameters: 2: Value proposal i 3: StrongCertification(proposal i ): 4: broadcast ⟨certify, proposal i , ShareSignt+1 (⟨certify, proposal i ⟩)⟩ i 5: 6: 7: 8: 9:
if received t + 1 ⟨certify, v , psig⟩ for a value v : let cert ← Combinet+1 ({psig | psig is received from t + 1 proposal messages}) broadcast ⟨certified, v , cert⟩ else: broadcast ⟨no-common, ShareSignt+1 (⟨certify, ⊥⟩)⟩ i
10: 11: 12: 13: 14:
if received valid ⟨certified, v , cert⟩: return (v , cert) else ▷ must receive t + 1 no-common let cert ← Combinet+1 ({psig | psig is received from t + 1 no-common messages}) return (proposal i , cert)
We first prove that if t < n/2, any value with a certificate must be valid according to strong unanimity, and each honest process outputs a value along with a certificate supporting it.
32
Lemma 41. If a certificate for a value v exists, then v is admissible according to strong unanimity. Proof. If µ such that CombinedVerifyt+1 (µ, ⟨certify, v ⟩) = true for v ̸= ⊥ exists, at least one honest process must have partially signed it. As v is a proposal of some honest process, v is admissible. Next, we argue that if all honest processes input the same value v, µ such that CombinedVerifyt+1 (µ, ⟨certify, ⊥⟩) = true cannot exist. This is because at least n − t ≥ t + 1 honest processes will broadcast partial signatures for v, and so, there will be no honest process that partially signs for ⊥. Lemma 42. Each honest process outputs (v, cert), where v is admissible according to strong unanimity and cert is a certificate for v. Proof. Suppose that at line 5, an honest process received t + 1 certify messages for a value v. Then, all honest processes will receive v and its certificate at line 11. Otherwise, all honest processes will broadcast no-common messages, and since n − t ≥ t + 1, all honest processes will obtain a certificate for any value at line 14. Finally, the complexities are straightforward from the algorithm. Lemma 43. The algorithm terminates in 2 rounds, exchanges O(n2 ) messages, and exchanges O(n2 κ) bits.
33