Optimal Subcubic Byzantine Agreement with Plain PKI

Optimal Subcubic Byzantine Agreement with Plain PKI Marc Dufay and Roger Wattenhofer

arXiv:2611.06479v1 [cs.DC] 4 Nov 2026

ETH Zürich {mdufay, wattenhofer}@ethz.ch Abstract We consider Byzantine Agreement (BA), where n parties run a distributed protocol to agree on a common value, despite t parties being byzantine. In the synchronous setting, a choice must be made between the weaker unauthenticated setting, which only allows t < n/3 byzantine parties, and the stronger authenticated setting that allows up to t < n/2 byzantine parties. For this latter setting, BA can be solved with optimal resiliency and optimal bit complexity. However, so far, all optimal solutions rely on the use of threshold signatures. This shows a gap compared to regular signatures, where only protocols with cubic complexity are known for optimal resiliency t < n/2. We wonder whether this cubic complexity is required without the use of threshold signatures and show that this is not the case. More specifically, given κ an upper bound on the size of a √ hash or signature, we describe a deterministic protocol solving BA with bit complexity √ O(κ( 13−1)/2 n( 13+1)/2 ) ≈ O(κ1.303 n2.303 ) while having optimal resiliency t < n/2 and round complexity O(n).

1

Contents 1 Introduction

3

2 Related work

3

3 Overview

4

4 Preliminaries

8

5 Definitions

9

6 Weak byzantine Agreement

11

7 Proof Creation 7.1 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Overall protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Computing accusations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Spreading votes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Computing a Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Putting it together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 12 13 14 17 19 20

8 Validated dispersion

20

9 Parallel agreement 9.1 Committee Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Batch Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Parallel broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 23 24

10 Partial Validated Agreement

25

11 Validated Agreement 27 11.1 Group Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 11.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 12 Putting it all together 31 12.1 Per-party bit complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 12.2 Round complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 13 Message and signature tags

36

14 Conclusion

37

A Expander and Disperser Graphs

40

B Missing protocols B.1 Byzantine Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Graded agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Multivalued Byzantine Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.4 Group Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.5 Reliable Group Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42 42 43 44 45 46

2

1

Introduction

Byzantine Agreement is a fundamental problem in distributed computing, where a set of parties must agree on a single value even in the presence of some malicious parties. In its simplest form, we are given n parties, of which at most t can be byzantine. Without any kind of setup, this problem can only be solved if t < n/3 [25]. However, if we assume the presence of a public key infrastructure (PKI), and more specifically that parties can sign messages, then we can solve the problem with t < n/2. Another important aspect of the problem is the complexity of the protocol. In 1982, Dolev and Reischuk [14] gave a quadratic lower bound for communication complexity. In the authenticated setting, this lower bound was only somewhat recently matched by Momose and Ren [24]. However, when considering optimal resiliency t < n/2, their protocol relies on threshold signatures [5], which are a stronger cryptographic primitive, allowing parties, in certain cases, to compress n signatures into one. Even though threshold signatures are used in practice, they have multiple drawbacks: • Threshold signatures require their keys to be correlated. A consequence is that a trusted dealer setup is needed. This is a strong assumption and requiring a trusted third party, even if only for the setup, for a decentralized protocol is not ideal. Another possible approach is to use a distributed key generation (DKG) protocol, but this is a complex protocol in itself. • Looking in the future, most common signature and threshold signature primitives are not quantum-safe. While regular signatures quantum-safe alternatives exist and have already been thoroughly studied [3, 15], quantum-safe threshold signatures [11, 19] are less mature and have been less studied. • In general, it is interesting to known the best we can do with the least amount of cryptographic assumptions. For these reasons, we consider the problem of solving Byzantine Agreement with optimal resiliency t < n/2 with only regular signatures. To the best of our knowledge, all existing protocols for this setting have cubic complexity. In this work, we show that this is not a requirement and give the following result: Theorem 1. There exists a deterministic byzantine agreement protocol with round complexity √ √ RBA (n) = O(n) and bit complexity BBA (n) = O(κ( 13−1)/2 n( 13+1)/2 ) ≈ O(κ1.303 n2.303 ). Our work builds on the framework laid by Momose and Ren [24], and make use of numerous new techniques, including more refined recursive protocols, improved uses of dispersers and faulttolerant expander graphs, as well as fair cake cutting theory to achieve a subcubic complexity. AI Disclosure: ChatGPT-6 Astra was used to improve and refine ideas in Sections 9 and 11.1. ChatGPT-6 Astra was also used to provide an initial draft, which the authors based their proof of Theorems 9 and 10. Apart of the uses mentioned above, LLMs were only used for grammar and spelling checks.

2

Related work

Deterministic synchronous protocols In the deterministic synchronous setting, the DolevReischuk [14] lower bound shows that a quadratic amount of communication is necessary to solve byzantine agreement. Dolev and Strong [13] also show that t + 1 rounds are necessary to solve 3

deterministic byzantine agreement. In the unauthenticated setting, Berman, Garay and Perry [2] were the first to give a protocol with optimal resiliency t < n/3 and optimal bit complexity O(n2 ). It took until 2020 for Momose and Ren [24] to match this result in the unauthenticated setting. More precisely, they give a protocol with optimal resiliency t < n/2 and quadratic bit complexity O(κn2 ) using threshold signatures. When considering only regular signatures, they provide a protocol with resiliency t < n/(2 + ε) and bit complexity O(κε−1 n2 ), which results in a cubic complexity for t < n/2. Randomized protocols We note that all the previous lower bounds only apply to deterministic algorithms. In the randomized settings, more efficient protocols exist, concerning both round and bit complexity [18]. In particular, even in the much weaker asynchronous setting, when properties are only required to hold with high probability, byzantine agreement can be solved with expected near-linear complexity [4, 9]. Bypassing the lower bound There have been multiple attempts to bypass the deterministic lower bounds by using additional assumptions. Some of them rely on using adaptive algorithms which depend on the actual number of byzantine parties [6, 10]. Others rely on amortizing the cost of byzantine agreement over multiple instances [7, 16]. However, all approaches with resiliency t ≥ n/3 rely on threshold signatures. A notable exception is [16] which can be used to solve Θ(n) concurrent instances of byzantine agreement with an amortized near-linear cost per instance while only using regular signatures. However, this is only achieved with resiliency t < n/(2 + ε).

3

Overview

Our main contribution is a new weak agreement protocol using plain PKI with subcubic message complexity. This protocol consists of 2 main parts: • Proof Gathering: In the first part, parties exchange signed messages between themselves to get a proof that either 0 or 1 can be voted. We note that because of the lack of threshold signatures, a proof must contains at least t + 1 signatures so that byzantine parties cannot forge it. In our protocol it is the case: a proof is made of exactly t + 1 threshold signatures and thus has size Θ(κn). At the end of this part, we require that at least n/10 honest parties have a proof for either 0 or 1. Additionally, if every honest party has the same input, then every honest party will get a proof for this input by the end of the proof gathering. • Validated Dispersion: From the first part, at least n/10 honest parties have a proof. Our goal in this part is to make every honest party hold the same proof, i.e that there is a specific proofv with v ∈ {0, 1} such that every honest party has received proofv by the end of this part. After running consecutively these two parts, if a party has a proof for both 0 and 1, it will decide ⊥. Otherwise, it will decide the value matching the proof it received (validated dispersion ensures at least one proof will be received). Although these two sections sound simple to explain, obtaining a subcubic protocol for both of them is the main difficulty of this paper and requires multiple complex ideas. An overview is given below:

4

Proof construction The goal of proof gathering is that, by the end of it, at least n/10 honest parties have a proof showing that either 0 or 1 can be decided. We first give an initial idea for the proof. A proof for v ∈ {0, 1} allows a party to confirm it can decide v without any additional communication. In particular, if all honest parties have input v, a proof for 1 − v cannot exist. A common construction for such a proof is to have every party sign and send its input. If a party gets t+1 distinct signatures for v ∈ {0, 1}, it shows that at least one honest party had input v and thus that this value can be decided. Using threshold signatures, such a proof can be encoded using O(κ) bits. Here, because only plain signatures are available, such a proof will require (t + 1)κ = O(κn) bits. As such, a protocol should be careful when sending this proof to avoid having a cubic complexity. We present the different ideas used to achieve proof gathering with Õ(κn2 ) bit complexity and O(log n) rounds complexity: I know that I can’t know: As said before, we consider a first round where every party votes for its input and sends its (signed) vote to every other party. Given a party v, this can results in two outcomes for v: • v gets enough votes for 0 or 1 to get a proof for either 0 or 1 • v is not able to get a proof for either 0 or 1. However, in this case, we make the observation that v still gained information from this step: it learned that all honest parties don’t hold the same value (otherwise it would have received n − t ≥ t + 1 votes for this value), and therefore both 0 and 1 are ”fine” to decide. To symbolize this, it sets its input to ⊥. A downside of this approach is that v has no way to prove this observation to other parties. But we show that this simple remark is powerful enough to always get a proof afterward. We note that this approach was already used to obtain optimal adaptive byzantine agreement protocol using threshold signatures [10, 17]. Let nb⊥ be the number of honest parties which set their input to ⊥ (they know that both values are fine). We remark that if nb⊥ ≤ 4n/10, then at least n − t − nb⊥ ≥ n/10 honest parties have a proof and therefore this step is already done. In the case where nb⊥ > 4n/10, we perform a second round of input (which can now be 0, 1 or ⊥) signing and sending. We now observe that byzantine parties can only behave in two different ways. If byzantine parties behave as honest: We consider the first case, where multiple byzantine will send their vote to an honest party, as a way to appear as honest from this party’s point of view. More specifically, we consider the case when any honest party receives at least 7n/10 votes. In this case, we use a disperser to disperse the votes received. Every vote is forwarded to a constant (different for each vote) number of parties. This ensures that any set of 4n/10 honest parties holds enough information together to produce a proof. Afterwards, we give and use the following fault-tolerant expander, which we believe to be of independent interest: Theorem 2. For any α ∈]0, 1[, β > 1, there exists D > 0 such that for any n > 0, there exists an explicit graph G = (V, E) on n vertices of bounded degree D. Additionally, for any C ⊂ V such that |C| ≤ α · n, there exists S ⊆ V such that S ∩ C = ∅, |S| ≥ n − β · |C|, and the induced subgraph G[S] is connected and has diameter O(log n).

5

We note that this is a generalization and stronger version of [26]’s result, which had fixed α = 1/72 and β = 6. Using this graph, we ensure that a subset of 4n/10 honest parties will be able to communicate and all get a proof in O(log n) rounds. If byzantine parties behave as malicious: If the previous case is not reached, it implies that all honest parties received less than 7n/10 votes and thus each honest party can identify at least 3n/10 byzantine parties. We note that in this case, votes only may not be enough to get a proof. Therefore, we combine votes with our next ”trick”: accusations. An honest party can only accuse another party if it is byzantine. Thus, given a signed accusation from pi to pj , we know that either pi or pj is byzantine. This approach is inspired by the work done for repeated agreement [7] and relies on the insight formalized by [21]: instead of trying to determine whether pi or pj is byzantine, we can just discard the two parties. This is implemented by adding accusations into a proof. For example, with n = 5 and t = 2, assume the proof consists of: {votep1 (0), votep2 (⊥), accuse(p3 , p4 )}, we know that either p3 or p4 is byzantine, so at most one party among p1 and p2 is byzantine and thus 0 is a valid value. We note that for this to work, votes and accusations must be disjoint, and in particular, accusations must form a matching. From accusations to fair cake-cutting: In this setting, each honest party wants to get ”rid of” up to 3n/10 non-⊥ votes, and each honest party can accuse at least3n/10 byzantine parties. We view this in another way: consider the set of n parties to be a cake. Each party knows at least 3n/10 byzantine parties which we identify as delicious slices. The goal becomes for a party to split the cake such that each relevant party is given a range which contains what it considers to be a delicious slice: this is fair cake-cutting theory. We adapt an existing algorithm to our setting and show that such an assignment can always be obtained by asking each party to cut a range of the cake into 2 equal parts ⌈log n⌉ times. This approach has bit complexity O(n2 log2 n) and round complexity O(log n).

Validated dispersal Using proof construction, we can guarantee that at least n/10 honest parties hold a proof (possibly not for the same value). Each party running the proof dispersal algorithm will get a set of proofs in return. The main property of proof dispersal is that there exists a proof which is in every set returned by an honest party. This implies that every party will either get a proof for 0 or every party will get a proof for 1. Because a proof for v can only exist if v satisfies weak validity (i.e if all honest party don’t have input 1 − v), we show that deciding v if a party only receives proofs for v or otherwise deciding ⊥ satisfies weak agreement. Validated dispersal in its definition does not consider proofs, it consider any L-bit input which satisfies some external validity predicate (where in our case, the validity predicate is that the value is a valid proof). We note that a really simple implementation of validated dispersal can be to have every party send its input (if it has one) to every other party, then return the set of inputs received. This works and can be done in one round, however, it has cubic complexity. Divide-And-Conquer : The approach we took to improve the complexity in this paper is based on a divide-and-conquer approach (and later recursive calls). We divide the n parties into m := m(n) groups of similar size (where m is decided later) and make two key remarks. The first remark is that by sending messages using a disperser pattern, we can make it so at most n/(10m) honest parties do not have an input, with a bit cost of O(n2 m). The second insight is that if one 6

of the groups has a byzantine minority (which we are guaranteed at least one has), and all honest parties in this group agree on the same value, then, using standard erasure coding techniques, all parties can learn this value using only O(n2 ) communication. Summing this over all m groups, we get the same O(n2 m) bit cost. Validated Agreement: Using the previous idea, we can effectively reduce Validated dispersal to m parallel calls to agreement on a valid value within a group of smaller size n/m. We note that this problem is not exactly regular Validated Byzantine Agreement, as some honest parties may not have an input. We call this problem Partial Validated Agreement. Nevertheless, we show that Partial Validated Agreement can be implemented using O(log n) calls to regular Validated Agreement. Our setting is now Validated Byzantine Agreement with a byzantine minority. An easy way to solve this would be to have every party send its input using Byzantine Broadcast (for example the Dolev-Strong protocol). Although this simple approach would be enough to achieve a subcubic complexity for the overall protocol, there exists better approaches. A first improvement would be to implement Byzantine Broadcast using our own Byzantine Agreement protocol, effectively making our protocol recursive. This is more efficient, but requires n recursive calls in total and also has a high bit-complexity due to multiple inputs sharings. Dynamic Programming approach When considering the previous Validated Agreement running with n parties and input size L, it requires O(κn) recursive binary agreement calls and its dependency on L is O(n2 L). To reduce the dependency on L to O(nL), we take a dynamic programming approach: for a set S of parties, we keep track of a tuple (d, H) where d is the Merkel root of a valid value and H is a set of parties that know the value associated with H. One key invariant we keep is that S H has a byzantine majority (i.e at least half of its parties are byzantine). We show how to merge two disjoint sets S and S ′ where we have a tuple satisfying these properties to obtain a new tuple for S ∪ S ′ using only |S ′ | byzantine agreement calls with an additional O(L|S ′ |) bit complexity. When merging sets in the correct order, this allows the protocol to only have an O(nL) dependency on L. Batching Our dynamic programming approach relies on running multiple independent byzantine broadcast procedures. Each broadcast requires one recursive call to our byzantine agreement protocol, which is expensive. To work around this issue, we show how to use batching to improve the overall bit complexity. Let b := b(n), we consider b independent instances of byzantine broadcast from a set of broadcasters S. We rely on a committee-based broadcast protocol, based on the Dolev-Strong protocol, which is more efficient, but only guarantees agreement if at least one party in the committee is honest. Using S as the committee, each party tries to broadcast its value using the committee-based protocol. Afterwards, a single multi-valued byzantine protocol (implemented on top of our binary BA protocol) is run to check the consistency of all b instances at once. This decreases the number of recursive calls needed from O(κn) to O(κn/b). Parallel execution A point we did not mention up to now is round complexity. Byzantine Agreement requires Ω(n) rounds and our goal is for our algorithm to be optimal in this regard. When implementing the ideas presented above naively while optimizing m and b to minimize the bit complexity, the resulting algorithm would end up with a super-linear round complexity. To solve this, we make a more efficient use of the batching approach above, in particular by batching byzantine broadcasts from multiple independent merges together. This, together with running 7

independent subprotocols in parallel whenever possible, allows the final round complexity to be linear. Overall Complexity As said before, our algorithm is recursive: it recursively calls itself on smaller groups. When computing the bit complexity, we show that the per-party bit complexity BBA (n), while optimizing the parameters m and n is: BBA (n) = 2BBA (n/2) + Õ(κn) +

  κn κn Õ nm + κnb2 /m + 2 + BBA (n/m) b m mb 1≤b≤n/m<n min

√

We get the optimal value by choosing√b = m = Θ̃((κn)( 13−3)/2 ) which leads to the algorithm per-party bit complexity BBA (n) = Õ(n( 13−1)/2 ). Regarding round complexity, the recurrence relation is: RBA (n) = 2RBA (n/2) + O(log n) + m1/3 RBA (n/m) For our optimal choice of m, the resulting round complexity is the expected optimal RBA (n) = O(n).

4

Preliminaries

We consider a set P of n parties, out of which up to t can be byzantine. We focus on fully deterministic protocols. The network is fully connected and channels are authenticated: any party can send a message to any other party, and the receiver will know who the sender is. Model: We consider a synchronous model, where parties communicate in rounds. In each round, parties can send messages to other parties, and all messages will be received by the beginning of the next round. Hashes: We assume the existence of a cryptographic hash function that is collision-resistant: it is computationally infeasible to find two distinct inputs that hash to the same output. We assume that the output of the hash function is κ bits long. Because byzantine parties should not be able to brute force a hash, we assume that κ = Ω(log n). Another assumption made in this work is that κ = polylog(n). Signatures: Each party has a public-private key pair, where the public key is known to all parties, and can sign messages with its private key. We assume that signatures are unforgeable: it is computationally infeasible for a party to forge a signature of another party. The signature size is κ bits. Erasure Coding: Erasure coding allows a message to be split into multiple shares, such that a subset of the shares can be used to reconstruct the original message. We use classical Reed-Solomon codes [27]: Definition 1. An L-bit value can be split into m shares, such that any subset of m/2 shares can be used to reconstruct the original value. Each share has size O(L/m + log m) bits.

8

Cryptographic Accumulator/Merkel Tree: Our work relies on the use of cryptographic accumulators. Given a set S of m elements, a cryptographic accumulator returns an accumulator value h for S as well as a witness ws for each element s ∈ S such that given the accumulator h, an element s and its witness ws , a party can verify that s ∈ S without knowledge of S. When implemented using a Merkel Hash Tree [23], the accumulator has size κ while each witness has size κ⌈log n⌉. We note that more efficient cryptographic accumulator implementations exist [12], however they rely on stronger cryptographic primitives, and a more complex setup, which our work aims to avoid. We always use erasure coding paired with cryptographic accumulators: When generating shares of a value, each share, along with its index, is considered as an element of a set, and the accumulator is computed on this set. This way, a party can verify that a share is valid using its witness.

5

Definitions

All the following protocols are assumed to be run on n parties, out of which at most t < n/2 are byzantine. Definition 2. A protocol where each party is given an input vin and decides an output vout satisfies byzantine agreement if: • Termination: All honest parties decide • Validity: If all honest parties have the same input v, then only v can be decided • Agreement: If two honest parties decide respectively v and v ′ , then v = v ′ . Even though we give (and use) protocols for byzantine agreement where the input is an L-bit value, the target of this paper is binary agreement, where vin ∈ {0, 1}. Definition 3. A protocol where each party is given an input vin ∈ {0, 1} and decides an output vout ∈ {0, 1, ⊥} satisfies weak byzantine agreement if: • Termination: All honest parties decide • Validity: If all honest parties have the same input v, then only v can be decided • Weak Agreement: If two honest parties decide respectively v ̸= ⊥ and v ′ , then v ′ = v or v ′ = ⊥. Definition 4. We consider an external validity function val and a protocol where parties decide an output vout with the following properties: • Termination: All honest parties decide • Validity: If an honest party decides v, then v satisfies the validity function • Agreement: If two honest parties decide respectively v and v ′ , then v = v ′ . If every honest party is given an input vin satisfying the validity function, we say that the protocol satisfies validated agreement. If at least n/10 honest parties are given an input vin satisfying the validity function, we say that the protocol satisfies partial validated agreement. 9

Byzantine minority/majority: When considering a set of Q parties, out of which k are byzantine, we say that Q has a byzantine minority if k < |Q|/2, and a byzantine majority otherwise (i.e when k ≥ |Q|/2). Proofs: Our protocols rely on the creation and dissemination of ”proofs”, which allows parties to verify whether or not they can decide a given value. Definition 5. Assuming all honest parties have an input in {0, 1}, it is computationally infeasible for an adversary to compute a proof for v ∈ {0, 1} if all honest parties have input 1 − v. Byzantine-robust protocols: Our protocols are designed to be able to solve byzantine agreement with resiliency t < n/2, which is optimal in regard to this problem, even with a trusted setup (if all honest parties have input 0 and all byzantine parties act as honest with input 1, BA cannot be solved if t ≥ n/2). However, one of the key points of our protocol is that we partition the n parties into smaller groups then run recursively our algorithm on them. This approach guarantees that at least one of the groups has an honest majority, but this may not be the case of the remaining ones. Although we do not expect anything from the output of protocols run in a byzantine majority, messages sent in this context by honest parties still count toward to the total bit complexity. To prevent any issue in this regard, we define the term of byzantine-robust protocols: Definition 6. Given an upper bound on the bit complexity per party, a protocol is byzantine-robust if this upper bound is satisfied regardless of the messages received. In particular, this applies even if all other parties are byzantine. A byzantine-robust protocol must be balanced, as such it makes more sense to look at the perparty bit complexity (i.e the number of bits sent by a party) rather than the total bit complexity. Given a protocol Π, we denote by BΠ (n) the per-party bit complexity of Π when run on n parties. We also denote by RΠ (n) the round complexity of Π when run on n parties. Because all of our primitives and approaches have a bit cost increasing with the number of parties, we make simplifying assumptions that all our protocols complexities are non-decreasing with the number of parties. This allows us to simplify the analysis of our protocols. Graphs: Given a (possibly directed) graph G = (V, E), the neighborhood of a vertex u ∈ V is S NG (u) = {v ∈ V, u → v ∈ E}. Given a set S ⊆ V , we denote NG (S) = u∈S NG (u). Our work makes multiple uses of dispersers, which are defined below: Definition 7. A graph G = (V, E) is a (a, b)-disperser if for any subset S ⊆ V of size |S| ≥ a, we have |NG (S)| ≥ b. A bipartite graph G = (L ∪ R, E) is a bipartite (a, b)-disperser if for any subset S ⊆ L of size |S| ≥ a, we have |NG (S)| ≥ b. A last point to remark is that many of our protocols are designed to run in parallel, but there is not enough information in the messages to know which instance to target. Moreover, our protocols, as they are written, are weak to replay attacks. We keep them this way for simplicity, but we show in Section 13 how to add tags to messages and signatures to fix these issues, while keeping the same complexity.

10

6

Weak byzantine Agreement

Our Byzantine Agreement protocol uses the framework introduced by Momose and Ren [24], who show how to implement Byzantine Agreement on top of Weak Agreement. Therefore, our focus and main contribution is implementing a weak agreement protocol using plain PKI. For completeness, protocols showing the reduction from byzantine agreement to weak agreement are provided in Sections B.1 and B.2 . Our protocol relies on two subprotocols: proof creation which makes sure at least n/10 honest parties are able to get ahold of a proof and Validated dispersion which makes sure there exists one proof received by every party. We provide formal definitions of these two subprotocols: Definition 8. In a proof creation protocol, each party has an input vin ∈ {0, 1} and outputs a message m such that the following properties are satisfied: • Termination: All honest parties output. • Certifiability: If an honest party outputs a message m ̸= ⊥, then m is a proof for either 0 or 1, relevant to the inputs. • Partial decision: At least n/10 honest parties do not output ⊥. Definition 9. In a validated dispersal protocol, given some external validity function, each party is given an input which is either ⊥ or an L-bit message satisfying the validity function. Additionally, at least n/10 honest parties do not have ⊥ as input. Each party outputs a set S of messages such that: • Termination: All honest parties output. • Validity: All messages output by an honest party satisfy the validity function. • Coverage: The exists a valid L-bit message m such that m is contained in the set of every honest party’s output. Assuming access to these two subprotocols, we provide a simple implementation of weak agreement. The validity function used for validated dispersal is to check whether the message is a valid proof for 0 or 1. We properly define what a valid proof is in TODO: WeakBA Weak Byzantine Agreement protocol for a party p with input vin proof ← ProofCreation(vin ) proof s ← ValidatedDispersal(proof ) if proof s only contains proofs for a single value v ∈ {0, 1} then Decide v else Decide ⊥ end if

Theorem 3. WeakBA is a weak agreement protocol. Proof. We note that ProofCreation ensures that at least n/10 honest parties get a valid proof, and the remaining ones output a ⊥. Therefore, at least n/10 parties start the validated dispersal 11

protocol with a valid input while the remaining ones have input ⊥, so the input conditions for the validated dispersal algorithm are respected. Termination follows from ProofCreation’s and ValidatedDispersal’s termination. If all honest parties have the same input b, then according to the definition of a proof (Definition 5), a proof for 1 − b cannot exist, so any proof obtained can only be for b. Because validated dispersal’s coverage and validity ensure every party gets at least a proof, it must be for b. Hence the protocol will decide b for every honest party, so validity is satisfied. Using validated dispersal’s coverage, there exists a proof for a value b ∈ {0, 1} that every honest party receives. We note this implies that parties can only decide b or ⊥, so weak agreement is satisfied. When considering complexity, we abbreviate WeakBA to WBA, ProofCreation to PC and ValidatedDispersal to VD. Additionally, BVD (n, L) is the per-party bit complexity to disperse an L-bit message among n parties using validated dispersal. Observation 1. Assuming the underlying protocols are byzantine-robust, WeakBA is byzantinerobust. Additionally, BWBA (n) = BPC (n) + BVD (n, κn) and RWBA (n) = RPC (n) + RVD (n).

7

Proof Creation

We now explain the proof creation protocol. The protocol starts, like many weak byzantine protocols, with each party sending its (signed) input to every other party. It differs greatly afterwards: • If a party does not get t + 1 votes for 0 or t + 1 votes for 1, it knows that not all honest parties have the same input. Thus, it can then support votes for both 0 and 1. We symbolize this by setting its input to ⊥. As stated in the overview, this idea was already used by Constantinescu et Al. [10] for adaptive algorithms. But their protocol is leader-based and uses threshold signatures, allowing it to be simpler compared to the approach used here. • Another key idea is to always be able to extract information from byzantine parties: if byzantine parties send votes, honest parties will be able to use them and make signatures. Otherwise, honest parties will be able to identify many byzantine parties, accuse them and use these accusations to form a proof.

7.1

Proofs

Our construction relies on proof, which allows a party to know that a value satisfies validity without any additional communication. Usually, a proof is a single (t + 1)-threshold signature. Because we do not have access to threshold signatures, our proofs require more insight. More specifically, we rely on votes, where a party p signs a message Vote(p, v) for a value v ∈ {0, 1, ⊥}, and accusations, where a party pi signs a message Accuse(pi , pj ) to accuse a party pj . We consider the following properties: • Voting accuracy: An honest party can only vote for v ∈ {0, 1} if its input is v. Moreover, it can only vote for ⊥ if it knows both 0 and 1 are valid (i.e not all honest parties have the same input). • Accusation accuracy: If an honest party pi accuses pj , then pj is byzantine. Using votes and accusation, we can define what is a proof in the context of our algorithm: 12

Definition 10. A message m is a proof for b ∈ {0, 1} if it is made of k votes and q accusations such that: • All votes are for b or ⊥ • All parties voting and parties contained in each accusation (both the accuser and accused) are entirely disjoint • k ≥ 1 and k + q = t + 1, i.e there is at least one vote and in total t + 1 votes or accusations. We note that using this definition, a proof has size Θ(κ(t + 1)) = Θ(κn). Lemma 1. Assuming votes and accusations are accurate, a proof, as defined above in Definition 10, satisfies the definition given in Definition 5. Proof. Consider a proof for b ∈ {0, 1}. We want to show that b satisfies validity. Using voting accuracy, it is enough to show that an honest party voted for b or ⊥. The proof is made from k votes for b or ⊥ and q accusations. Using accusation accuracy, each pair of accuser/accused contains at least one byzantine party. Because they are all disjoint, they are at least q byzantine parties among the 2q parties that are part of accusations. Therefore, there are at most t − q = k − 1 byzantine parties remaining. Using disjointness again and the fact that k ≥ 1, this means that there is at least one honest party among the k votes, which shows that b satisfies validity.

7.2

Overall protocol

Our protocol starts with two rounds of signing and sending your own vote to every party, then sharing votes received in the second round in a different way, as well as obtaining accusations if many byzantine parties were silent. After the first round of sending votes, if an honest party does not receive t + 1 votes for the same value, it sets its input to ⊥, which is used for the second round of sending votes. After the second round of voting, all votes received are preserved. Additionally, each party keeps track of other parties which did not send a vote in the previous round. It knows these are byzantine (as they did not follow the protocol) and thus can accuse them later on. ProofCreation Proof creation protocol for a party p with input vin Send signed Vote(p, vin ) to everyone if did not receive t + 1 votes for 0 or t + 1 votes for 1 then vin ← ⊥ end if Send signed Vote(p, vin ) to everyone Let V otes be the set of votes received in the second round Let Accusers be the set of parties which sent a vote for 0 or 1 to p in the second round Let Accused be the set of parties which did not send a vote to p in the second round Accusations ← GetAccusations(Accusers, Accused) V otes ← SpreadVotes(V otes) if ComputeProof(0, V otes, Accusations) or ComputeProof(1, V otes, Accusations) returns a proof p then Return p else Return ⊥ end if

13

In this whole section, let nb⊥ be the number of honest parties which changed their input to ⊥, and therefore sent a signed input for ⊥ in the second round. We remark that if a party did not change its input to ⊥, it implies it has already enough votes for a proof. Thus n−t−nb⊥ ≥ n/2−nb⊥ parties already have enough votes for a proof, hence the following observation: Observation 2. If nb⊥ ≤ 4n/10, then at least n/10 honest parties will be able to get a proof. As a consequence, the following protocols (getting accusations and vote spreading) only need to focus on the case where nb⊥ > 4n/10. We now have two different cases, depending on the behavior of byzantine parties: • If at least one honest parties receives many votes from byzantine parties (more specifically, if one honest party receives at least 7n/10 votes), then the vote spreading procedure will ensure that 4n/10 parties will be able to receive enough votes to form a proof. • Otherwise, it means every honest party is able to identify at least 3n/10 byzantine parties. In this case, we remark that if an honest party manages to make n/10 honest parties with non-⊥ votes accuse disjoint byzantine parties, then these accusations along with the ⊥ votes will be enough to form a proof. This is what the accusation procedure does.

7.3

Computing accusations

As stated above, computing accusations is only needed when nb⊥ > 4n/10 and each honest party is able to identify at least 3n/10 byzantine parties. As a consequence, we ignore parties claiming to know less than 3n/10 byzantine parties or when a party needs too many accusations (to be more specific, more than 3n/10). The protocol consists of a leader, asking queries to other parties acting as helpers. It has O(n log2 n) bit complexity, O(log n) round complexity and allows the leader to get its desired matching. We run it in parallel n times, with each party acting as the leader of its own instance. Because we have a set of at most 3n/10 entities, each interested in at least 3n/10 parts of a common set of size n (the parties), we can represent this as a fair cake cutting problem: the cake is the set of parties and each accuser wants a piece of the cake which contains a party to accuse. We adapt the divide and conquer approach described by Even and Paz [20] to the distributed and online setting. By repeatedly asking helpers (accusers) to split a range of the cake (parties) into two equal parts, we can obtain a fair cake cutting with significantly less communication. GetAccusations(Accusers, Accused) Return a set of accusations for a party p Send |Accused| to everyone Let A be the parties in Accusers which accuse at least 3n/10 parties M ←∅ in parallel for i = 1, . . . , n do if p = pi and |A| ≤ 3n/10 then M ← CakeLeader(A, 1, n), in parallel end if Call CakeHelper(pi , Accused), in parallel Return M

We now describe the behavior of a helper party. Given the set of byzantine parties B it knows, it can only answer two kinds of queries: 14

• At most ⌈log n⌉ split queries: given an interval of parties {pl , pl+1 , . . . , pr }, and a position i, it returns the index of the i-th party in B ∩ {pl , pl+1 , . . . , pr }. • At most a single accusation query: given a range of parties, it accuses one of them if it is in B. CakeHelper(pi , B) Help a party pi get accusations by answering queries, for a party p Upon Receiving (Accuse, l, r) from pi if there exists pj ∈ B ∩ {pl , pl+1 , . . . , pr } then Send signed Accusation(p, pj ) to pi end if Stay silent for the rest of the subprotocol for 2⌈log n⌉ rounds do Upon Receiving (SP LIT, l, r, i) from pi Q ← {pl , pl+1 , . . . , pr } ∩ B Let pj be the i-th party in Q if it exists, otherwise j = 0 Send j to pi Wait 2 rounds end for

We can finally describe the protocol used by the leader. This protocol has input a set A of accusers and a range parametrized by two integers 1 ≤ l ≤ r ≤ n. Let I = [l, l + 1, ..., r] and h the number of honest parties in A. We show that this protocol returns a disjoint matching of size at least h between parties in A and parties in {pl , pl+1 , . . . , pr }. To do so, this algorithm divides I into two halves of the same size, then using helper queries, is able to partition A into these two segments and recurse on them. CakeLeader(A, l, r) Return a set of accusations from A to {pl , . . . , pr } if |A| = 1 then Send (Accuse, l, r) to the party in A Wait two rounds and return the set of accusations received else Send (SP LIT, l, m, ⌈|A|/2⌉) to every party in A Wait two rounds for answers (ap )p∈A (ap = 0 if p didn’t answer a positive number) Let Al be the ⌈|A|/2⌉ parties in A with lowest value (aq ) (breaking ties arbitrarily) Let m = maxp∈Al ap in parallel do Ml ← CakeLeader(Al , l, m) Mr ← CakeLeader(A \ Al , m + 1, r) Return Ml ∪ Mr end if

The main reason this protocol achieves its goal is because it is able to preserve the following invariant: Lemma 2. For a party pi , let Bi be the set of parties it can accuse. Then, for any call to

15

CakeLeader with an honest leader and input A, l, r: ∀pi ∈ A, pi is honest ⇒ |Bi ∩ {pl , pl+1 , . . . , pr }| ≥ |A| Proof. We first consider the first instance where GetAccusations calls CakeLeader. We remark that it is only called if the leader has at most 3n/10 accusers who can accuse at least 3n/10 parties. Additionally, it is called with l = 1 and r = n which is the entire set of parties, so in this case: |Bi ∩ {pl , pl+1 , . . . , pr }| = |Bi| ≥ 3n/10 ≥ |A| So the invariant holds. Consider now a call to CakeLeader with input A, l, r, where the invariant already holds. We want to show that it is still the case in the recursive calls. Consider a party pi ∈ A, which is honest. Using the invariant, |Bi ∩ {pl , pl+1 , . . . , pr }| ≥ |A|. The leader sends a query for the ⌈|A|/2⌉-th party in the previous set. Because |⌈|A|/2⌉ ≤ |A|, pi will answer with such a party. Let k be the index of this party. We therefore have: |Bi ∩ {pl , pl+1 , . . . , pk }| = ⌈|A|/2⌉ and |Bi ∩ {pk+1 , pk+2 , . . . , pr }| ≥ |A| − ⌈|A|/2⌉ We now have two cases: • pi ∈ Al , then in this case m = maxp∈Al ap ≥ ai = k, so the recursive call on pi will be made on a set of size ⌈|A|/2⌉ and range [l, m], which contains [l, k], for which pi can accuse at least ⌈|A|/2⌉ parties. • pi ∈ / Al , then by minimality, m ≤ k, so the recursive call on pi will be made on a set of size |A| − ⌈|A|/2⌉ and range [m + 1, r], which contains [k + 1, r], for which pi can accuse at least |A| − ⌈|A|/2⌉ parties. In both cases, pi can accuse at least as many parties in the given range as the size of the new set A. As a consequence, by induction, the invariant is always satisfied. Another key point is that accusations are accurate: Lemma 3. Accuracy: All accusations returned by CakeLeader are accurate: an honest party will only accuse byzantine parties. Proof. Accusations returned by MatchingLeader come from CakeHelper, which themselves come from the set Accused of parties which did not send a vote in the second round of the ProofCreation protocol. Because any party following the protocol will send a vote in the second round, it implies that these parties are byzantine. We also remark that accusations are signed by the accuser, as such a byzantine party cannot generate an accusation made from an honest party if it does not already have it. Using this invariant and accusation accuracy, we can prove the main property of our matching protocols, which is that the accusations produced by honest parties form a disjoint matching. Lemma 4. Consider an honest party, where GetAccusations calls CakeLeader with a set of accusers Acc. Let Acch be the honest parties in Acc, then the set of accusations returned by GetAccusations contains a disjoint matching of size |Acch |, where each edge is made from an accuser in Acch and an accused party being byzantine. 16

Proof. We first note that CakeLeader partitions accusers into two sets and recursively calls itself on these two sets. No accuser gets ”lost” between recursive calls and therefore every accuser will end up in exactly one case where |A| = 1. Let q ∈ Acch . Consider the call to CakeLeader with set A such that A = {q}. Let l, r be the range parameters of the protocol at that point. We remark that using the invariant, |B ∩ {pl , . . . pr }| ≥ |A| = 1 . As such, q will be able to find a party to accuse in {pl , . . . pr }, which won’t ask any other party for an accusation in this range. As a consequence, every honest party in Acc will send an accusation to the leader, they will all be distinct, and using accusation accuracy, they will all target byzantine parties. Finally, looking at these accusations, because the accusers are the parties in Ah and thus honest while all accused parties are all byzantine and distinct, all these accusations are fully disjoint. Lemma 5. GetAccusations has per-party bit complexity O(n2 (log2 n+κ)) and round complexity O(log n). Moreover, it is byzantine-robust. Proof. MatchingLeader cuts into half the number of accusers at each recursion level, starting with at most 3n/10 parties, thus its recursion depth is ⌈log(3n/10)⌉ because of the check in GetAccusations. In each recursion level, the leader sends a query to each party in its original accuser set, which has size at most 3n/10. The query being a tag and a range made of two integers between 1 and n, the overall bit complexity for the leader will be O(n log2 n). And the leader only spending two rounds before the parallel recursive calls means the round complexity is 2⌈log n⌉. Looking at an helper party, for a specific leader, it will respond to at most ⌈log n⌉ queries and send at most one accusation. Because there are n helper for a given leader, this amounts in total to O(log2 n + κ) bits with the same round complexity. GetAccusations makes at most n parallel matching leader calls, one for each party. So, the total per-party bit complexity is O(n(log2 n + κ)) and round complexity O(log n). Finally, we remark that we did not use the resiliency t < n/2 at any point for proofs related to this protocol. As a matter of fact, it supports an arbitrary number of byzantine parties. Thus it is byzantine-robust.

7.4

Spreading votes

The last case to handle happens when at least one honest party is not able to identify many byzantine parties. More specifically, if at least one honest party p is unable to identify at least 3n/10 byzantine parties. For this to happen, most byzantine parties must appear as following the protocol for p and therefore send a vote (for 0, 1 or ⊥) to it. As a consequence, in this case, p will receive at least 7n/10 votes. As a reminder, we can also assume that nb⊥ (the number of ⊥ votes by honest parties) is at least 4n/10. We remark that this is enough for p to get a proof: in addition to 4n/10 ⊥ votes, either 0 or 1 will get at least (7n/10 − 4n/10)/2 votes supporting it, which in total is strictly more than 0.55n > n/2 > t votes. However, getting a single party to get a proof is not enough, we want at least n/10 honest parties to get one. To do so, we remark that p has a ”surplus” of 0.05 votes. So, by forwarding votes to other parties using a disperser pattern, which only requires parties to forward each vote to a constant number of parties, we can make it so that any subset of 4n/10 parties has enough votes together to get a proof. A key insight is that we forward each vote to a different set of parties, so even if a single vote may only be forwarded to byzantine parties, only an arbitrary small fraction of the votes will. Finally, using a fault-proof expander graph, we can find a subset of 4n/10 honest parties which are all at logarithmic distance of each other and such that the graph degree is constant. 17

SpreadVotes(V otes) Spread votes among all parties for a party p Let G1 be a (n/20, 7n/10)-disperser // Using Theorem 11 with α = 1/20 and m = 115 for each vote v from party q in V otes, in parallel do Send v to NG1 (q) end for Let G2 be a fault-tolerant expander // Using Theorem 2 Send V otes to NG2 (p) for O(log n) rounds do Upon Receiving a vote v not in V otes Forward v to parties in NG2 (p) V otes ← V otes ∪ {v} end for Return V otes

Lemma 6. SpreadVotes has per-party bit complexity O(nκ) and round complexity O(log n). Additionally, it is byzantine-robust. Proof. The graphs (G1 and G2 ) used in the protocol using Theorems 2 and 11 have constant degree. We note that there can only exist 3n votes in total: n parties and 3 votes (0, 1 or ⊥) per party, and each vote is O(κ) bits. Because each party sends each unique vote to at most O(1) parties using G1 and G2 , the total per-party bit complexity is O(nκ). Regarding round complexity, the first step takes 1 round while the second step takes O(log n) rounds. So the overall round complexity is O(log n) round. Finally, we remark that the resiliency t < n/2 was not used when computing the complexity, as such this protocol is byzantine-robust. Lemma 7. Consider a party p and a subset S of its votes, where each vote is from a distinct party. For any party q, let Eq ⊆ S be the votes from S it received after the first round. Then for any subset H ⊆ P of parties such that |H| ≥ 4n/10, | ∪q∈H EQ | ≥ |S| − n/20. Proof. Consider a party p and sets S and H as defined in the lemma. Let R be the set of votes from S that were received by no parties in H, i.e R = S \ ∪q∈H EQ . We want to prove that |R| ≤ n/20. Because each vote in S comes from a different party, we can identify votes with the party that emitted it. Because votes were transmitted using the graph G1 , this implies that there is no edge between R and H, so NG1 (R) ⊆ P \ H, so |NG1 (R)| ≤ n − |H| ≤ n − 4n/10 ≤ 6n/10. G1 is a disperser, any set of size n/20 has neighborhood of size at least 7n/10. By contrapositive, |R| < n/20. Lemma 8. If nb⊥ ≥ 4n/10 and an honest party has votes from at least 7n/10 parties, then at least 4n/10 parties will receive enough votes to form a proof. Proof. Assume nb⊥ ≥ 4n/10 and an honest party p has votes from more than 7n/10 honest party. Let R be the set of votes p has, keeping only one per party. We have |R| ≥ 7n/10. Because we only consider one vote per party, we can identify a vote with the party that emitted it. Let Bz be the set of byzantine parties, we have |Bz| ≤ t ≤ n/2. Using the property on G2 (Theorem 2), there exists a set of parties S such that S and Bz are disjoint, i.e S is honest, |S| ≥ 4n/10, and G2 [S] is connected and has diameter O(log n). We can now use Lemma 7 on S and R: there exists R′ ⊆ R such that |R′ | ≥ |R| − n/20 ≥ 7n/10 − n/20 = 6.5n/10 and parties in

18

S together receive all votes of R′ from p in the first round of SpreadVotes. Therefore, after all O(log n) rounds, all parties of S will have all votes of R′ . We now show that votes in R′ are enough to form a proof. Because nb⊥ ≥ 4n/10, there are at least 4n/10 votes for ⊥ in R. Since R′ ⊆ R and |R′ | ≥ |R| − n/20, R′ has at least 4n/10 − n/20 = 3.5n/10 votes for ⊥. Let x be the number of votes for ⊥ in R′ and let y be the number of votes for 0 or 1. We have x + y = |R′ | ≥ 6.5n/10. One of 0 and 1 has at least y/2 votes in R′ . Hence, the votes for ⊥ together with the votes for this value are at least: x+

y x + (x + y) = 2 2 x + |R′ | = 2 3.5n + 6.5n ≥ 2 = n/2

Since t < n/2, there are at least t + 1 such votes, all from distinct parties, so a proof can be formed. Thus, all parties in S will be able to get form a proof and |S| ≥ 4n/10, which concludes the proof.

7.5

Computing a Proof

We finally describe the last step of the protocol, which is to compute a proof from votes and accusations. This is done by computing a maximum matching on accusations where neither accuser nor accused can be used as votes. ComputeProof(b, V otes, Accusations) Compute a proof for b if one can be found Let Q be the votes in V otes for v or ⊥ Let E be the Accusations disjoint from Q, seen as edges Compute a maximum matching M of E if |Q| ≥ 1 and |Q| + |M | ≥ t + 1 then Return a set of t + 1 votes/accusations from Q and M with at least one vote else Return ⊥ end if

The maximum matching can be computed in polynomial time using the Blossom Algorithm. As a side note, looking at how we got accusations, we remark that the undirected graph the matching is computed on comes from a directed graph where each vertex has in-degree and out-degree at most 1. Hence, it is a collection of disjoint paths and cycles, which allows a maximum matching to be computed in linear time. Lemma 9. If there exists a proof for b using V otes and Accusations, then a call to ComputeProof will return a proof for b. Proof. Consider a proof for b, let Q be its set of votes and T its set of accusations. We note that, without loss of generality, we can assume that no party present in T (as an accuser or accused) has a vote for b or ⊥ in V otes. The reason for it is that if this were the case, we could remove the accusation from T and add the vote to Q, which would result in a valid proof. 19

Let Vb be the set of votes in V otes for b or ⊥ and let Eb be the set of accusations in Accusations disjoint from Vb . We have Q ⊆ Vb and, because no accuser or accused in T has a vote for b or ⊥, T ⊆ Eb . As a consequence, |Vb | ≥ |Q| ≥ 1. Moreover, T is a matching of Eb , so there exists a matching of size |T |. By maximality of M , we will have |M | ≥ |T |. Therefore, |Vb | + |M | ≥ |Q| + |T | = t + 1, which shows that ComputeProof(b, V otes, Accusations) will return a proof for b.

7.6

Putting it together

Theorem 4. After running ProofCreation, at least n/10 honest parties will have a proof for 0 or 1. Proof. We remind the reader that nb⊥ is the number of honest parties which changed their input to ⊥. After the first round of sending votes. We now have 3 different cases to consider: • nb⊥ ≤ 4n/10: If a party does not change its input to ⊥, it means it either received t + 1 votes for 0 or t + 1 votes for 1. So, it has already enough votes to form a proof. Because t < n/2, at least n − t − nb⊥ ≥ n/2 − 4n/10 = n/10 honest parties will have enough votes to form a proof. • nb⊥ > 4n/10 and at least one honest party received votes from at least 7n/10 parties: Using Lemma 8, at least 4n/10 parties will receive enough votes to form a proof. • nb⊥ > 4n/10 and every honest party received less than 7n/10 votes: In this case, every honest party is able to identify at least 3n/10 byzantine parties. Moreover, given an honest party p, its set of accusers Acc is made of parties which sent a vote to p different than ⊥. So |Acc| ≤ n − 3n/10 − nb⊥ ≤ 3n/10. As a consequence, GetAccusations will call MatchingLeader for every honest party. Consider an honest party p, either p is counted towards nb⊥ and sent a ⊥-vote to everyone, or it sent a vote for 0 or 1 to everyone, which implies it is in the set of accusers of every other honest party. Using Lemma 4, the set of accusations returned by GetAccusations contains a disjoint matching between all such honest parties as accusers and byzantine parties as accused. Thus, these accusations are disjoint from ⊥-votes of the nb⊥ honest parties. Because each honest party appears exactly once with a ⊥-vote or as an accuser, we have a set of votes and accusations of size n−t ≥ t+1 with at least one vote (nb⊥ > 0), which is enough to form a proof. So all honest parties will be able to form a proof. Finally, using Lemma 9, the n/10 honest parties that have enough votes and accusations will return a proof for 0 or 1. Theorem 5. ProofCreation has bit complexity BPC (n) = O(n2 (log2 n + κ)) and round complexity RPC (n) = O(log n). Additionally, it is byzantine-robust. Proof. The first two rounds of ProofCreation have bit complexity O(n2 κ), as each party sends a vote to every other party. Combining it with Lemmas 5 and 6, we get the expected complexities.

8

Validated dispersion

We now consider the second part of our protocol, which is validated dispersion. After the first part, n/10 honest parties are guaranteed to hold a proof of size O(nκ). The goal of validated dispersion 20

is to ensure that there is one proof which ends up known by all honest parties. We note that a very simple implementation of validated dispersion is to have each party send its proof to all other parties if it has one. Although it is quite simple, the total bit complexity would be O(n3 κ). Our protocol instead relies on partitioning all n parties into m groups of size ⌊n/m⌋ or ⌈n/m⌉, where m := m(n) is a parameter to be determined later. We first remark that, by sending proofs following a disperser graph, we can ensure that all but at most n/(10m) honest parties will have a proof. This has bit complexity O(n2 mκ). Afterwards, we can agree on a proof in each group and broadcast it efficiently using erasure codes. Because one of the groups is guaranteed to have a byzantine minority, this ensures that the proof from this group will reach every party. In the end, the protocol returns the set of proofs received from each group. The group broadcast protocol is described in Section B.4. An assumption we make is that m = O(nα ) for some 0 < α < 1 as a way to simplify the complexity analysis. We show that this assumption is satisfied in Section 12. ValidatedDispersion(proof ) Disperse a proof for a party p proof s ← ∅ Let G be a (n/10, n−n/(10m))-disperser // Using Theorem 11 with α = 1/10 and degree 4∗10∗10∗m Send proof to NG (p) if proof = ⊥ and received a valid proof q then proof ← q end if Partition P into m groups of size ⌊n/m⌋ or ⌈n/m⌉. for each group G in parallel do if p ∈ G then q ← PartialValidatedAgreement(G) end if q ← GroupBroadcast(G, q) if q is valid then proof s ← proof s ∪ {q} end if end for Return proof s

Theorem 6. The protocol satisfies validated dispersion. Proof. Termination comes from PartialValidatedAgreement and GroupBroadcast’s termination. Because a value only gets added to proof s if it is valid, validity follows. We assume that at least n/10 honest parties have a non-⊥ valid input. Because we send values using a (n/10, n − n/(10m))-disperser, at most n/(10m) ≤ ⌊n/m⌋/10 honest parties will not receive a valid input. Parties are partitioned into groups of size at least ⌊n/m⌋/10 . Because the initial set of parties has a byzantine minority, it implies that at least one of the groups has a byzantine minority too. Consider this group G, of size k. It has a byzantine minority, and among the honest parties, at most k/10 do not have a valid input, so at least k − k/10 − k/2 ≥ k/3 honest parties have a valid input. Therefore, using partial validated agreement, all honest parties in G will agree on a valid proof q. Again, because G has an honest majority and all honest parties call it with the same input q, all honest parties in P will receive q. So coverage is also satisfied.

21

Theorem 7. Assuming the partial validated agreement protocol is byzantine-robust, ValidatedDispersion has per-party bit complexity BVD (n, L) = O(mL)+BPVA (⌈n/m⌉, L), round complexity RVD (n) = O(1) + RPVA (⌈n/m⌉, L) and is byzantine-robust. Proof. The disperser G is obtained from Theorem 11 using degree 4 ∗ 10 ∗ 10 ∗ m = O(m), so each party sends its proof of size L to O(m) parties, which gives a per-party bit complexity of O(mL). Afterwards, each party calls PartialValidatedAgreement on a group of size at most ⌈n/m⌉, which gives a per-party bit complexity of BPVA (⌈n/m⌉, L). Finally, the group broadcast has cost O(Ln/⌈n/m⌉ + κn log n) = O(mL) as we assume m = O(nα ) for α > 0. Regarding the round complexity, every part of this protocol except the partial validated agreement takes O(1) rounds.

9

Parallel agreement

Using validated dispersion, we go from solving a problem on n parties to solving it on m << n parties. A consequence, is that we can recursively run our own byzantine agreement protocol on this smaller set of parties. However, this agreement protocol is still expensive. We remark that we mostly use parallel reliable broadcast in our partial validated agreement protocol, and as such, optimizing this use case would improve the overall complexity of our protocol. To do so, we rely on batching, where given a batch size b, we only need to run recursively our byzantine agreement κ times for b parallel invocations.

9.1

Committee Broadcast

We first describe our committee broadcast protocol. This is a variant of the Dolev-Strong protocol, where only a smaller committee of size b is responsible for forwarding signatures, instead of all parties. The advantage of such approach is that it has lower complexity than the original DolevStrong protocol. The disadvantage is that agreement is only guaranteed if at least one honest party in the committee is honest. Our broadcast protocol is used to send a small value. More specifically, we assume the input vin satisfies |vin | = O(κ). CommitteeBroadcast(vin , pin , C) Code for a party pin ∈ C to broadcast a value vin , executed by a party p if p = pin then Sign vin and send it to all parties end if for i = 2 to |C| + 1 do // An iteration lasts 2 rounds Upon receiving a message signed by pin and i − 1 parties from C Forward it to all parties in C // Only applied for two distinct messages received if p ∈ C then Upon receiving a message signed by pin and i − 1 parties from C Add your signature and forward it to all parties // Only applied for two distinct messages received end if end for if received a single message m then Return m else

22

Return ⊥ end if

Lemma 10. If at least one party in C is honest, then the protocol satisfies byzantine broadcast. Proof. Assume there exists a party q ∈ C that is honest. We first show that agreement is satisfied. We remark that if an honest party in C forwards 2 distinct signed messages from the sender, every party will receive these messages and decide ⊥, in which case agreement is satisfied. Otherwise, consider the case where honest parties in C only forward at most one signed message. Consider any honest party p ∈ P that accepts a signed message m, we want to show that every other honest party will receive m. We have two cases: • Either the message was signed by q. This implies that q signed it in a previous iteration, and forwarded it to all parties, so every honest party will receive it. • Or the message was not signed by q. We remark in this case that we are not in iteration |C| + 1, as otherwise the message would have to be signed by all parties in C, including q. In this case, p will forward m to all parties in C including q. Because there is at least one iteration remaining, q will add its signature and forward it to all parties, so every honest party will receive and accept it. As a consequence, the set of messages accepted by all honest parties is the same, so the decided value will be the same: agreement is satisfied. Given that the protocol runs for O(|C|) rounds and then returns a value, termination is satisfied. Finally, assume the sender pin is honest. Then, it will sign and send the same input vin to all parties, which will receive and accept it. Moreover, pin being honest will not sign any other message, so no other message will be accepted. As a consequence, all honest parties will decide vin , so validity is satisfied. Lemma 11. The protocol has round complexity O(|C|). Regardless of messages received, parties in C send O(κn|C|) bits while other parties send O(κ|C|2 )bits. Proof. We note that the protocol runs for exactly 2|C| + 1 rounds. All messages contain an input, which is O(κ) bits and at most |C| signatures, which are each κ bits. Parties in C send at most 2 such messages to each party, while other parties send at most 2 messages to parties in C, hence the result.

9.2

Batch Broadcast

Our previous committee broadcast is reliable as long as at least one party in the committee is honest. We use it to implement batch broadcast, where a group of C parties want to broadcast their L-bit input at the same time. We remind the reader that we assume L = O(κ). We remark that if we use the previous committee broadcast with C being the committee, then either at least one party in C is honest, in which case we are done, or all parties in C are byzantine. In the latter case, we only care about agreement, so we can run a single byzantine agreement on the concatenated output of all broadcast result. This approach allows us to reduce the number of byzantine agreement calls from |C| to 1, which is a significant improvement. The MVBA protocol is described in Section B.3.

23

BatchBroadcast(vin , C) Code for all parties in C to broadcast an input vin , executed by a party p in parallel For each party q ∈ C do Call CommitteeBroadcast(vin , q, C) Let m be the concatenation of all outputs from the previous calls Return MVBA(m)

Lemma 12. The protocol satisfies byzantine broadcast for each party in C. Proof. Termination follows from CommitteeBroadcast and MVBA’s termination. We consider validity. We remark that validity is only relevant if at least one party in C is honest. But in this case, using Lemma 10, the output of each committee broadcast satisfies validity and agreement. As a consequence, each honest party will receive the same output for each broadcast, which is the parties’ input if it is honest. Thus, the concatenated output will be the same for all honest parties, and MVBA’s validity will ensure that the final output is the same as the common input. So every honest party will output the parties’ input if it is honest, and validity is satisfied. Finally, agreement is a consequence of MVBA’s agreement. Lemma 13. The protocol has round complexity O(|C|) + RMVBA (n). Regardless of messages received, parties in C send O(κn|C|2 ) + BMVBA (n, |C|L) bits while other parties send O(κ|C|3 ) + BMVBA (n, |C|L) bits. Proof. This is a direct application of Lemma 11 and the fact that the concatenation of all outputs is of size |C|L.

9.3

Parallel broadcast

We now describe our final protocol for parallel byzantine agreement. The idea is to partition the set of parties into groups of size b := b(n), and run BatchBroadcast on each group in parallel. This allows us to reduce the number of byzantine agreement calls from n to ⌈n/b⌉. We note that there is a trade-off on b: the larger b is, the less amount of recursive byzantine agreement calls we need to make, but at the same time the more expensive the CommitteeBroadcast becomes. The exact choice is left for later, as it is chosen to minimize the bit complexity of the overall byzantine agreement protocol. ParallelBroadcast(vin , C) Code for all parties in C to broadcast an input vin , executed by a party p Partition C into groups of size b (except possibly the last group) for each group Ci in parallel do Call BatchBroadcast(vin , Ci ) end for Return the output of all previous calls

Lemma 14. The protocol satisfies byzantine broadcast for each party in C. Proof. This is a direct consequence of Lemma 12.

24

Lemma 15. The protocol has round complexity O(|C|)
+ RMVBA (n). Regardless of messages received, parties send (|C|/b + 1) O(κb3 ) + BMVBA (n, bL) bits. Parties in C send an additional O(κnb2 ) bits. Proof. The round complexity follows from the fact that we only run parallel executions of BatchBroadcast and Lemma 13. Regarding the bit complexity, we make exactly ⌈|C|/b⌉ ≤ |C|/b + 1 calls to BatchBroadcast, and each of these calls is run with a group size |C| ≤ b. Using Lemma 13, this results in the expected bit complexity. Finally, if a party is in C, exactly one of the batch broadcasts will be on the party’s group, which using Lemma 13 results in the additional O(κn2 b) bits sent.

10

Partial Validated Agreement

We now describe a protocol to reduce partial validated agreement to validated agreement. In partial validated agreement, only n/3 honest parties are guaranteed to have a valid input. The main insight is to have each party broadcast reliably whether it has a valid input or not. Then, we run the validated agreement protocol only on parties that claim to have a valid input. Afterwards, we use a group broadcast protocol to ensure that all parties receive the same decision value. If it is not valid, this implies that the validated agreement protocol was run on a byzantine majority, so the remaining parties form a byzantine minority. Thus, we can first use a disperser graph to ensure that a third of the remaining honest parties have a valid input, then iterate back onto them. One point to note is that we want our protocol to be byzantine-friendly, so we must not iterate too many times if this should not be possible. In particular, if less than a third of the parties claim to have a valid input, this cannot happen with a byzantine minority, so we can just stay silent for the rest of the protocol. The ReliableGroupBroadcast protocol is described in Section B.5. PartialValidatedAgreement(vin ) Agree on a valid input for a party p Q←P for ⌈log3/2 n⌉ iterations do Let G be a (n/3, 5|Q|/6) bipartite disperser // Using Theorem 12 Send vin to NG (p) if vin = ⊥ and received a valid input v from a neighbor then vin ← v end if (bq )q∈Q ← ParallelBroadcast(Q, vin ̸= ⊥) Q1 ← {q ∈ Q : bq = 1} if |Q1 | < |Q|/3 then Stay silent for the rest of the protocol // Can only happen with a byzantine majority end if if p ∈ Q1 then v ← ValidatedAgreementQ1 (vin ) end if v ← ReliableGroupBroadcastQ (Q1 , v) if v is valid then Return v end if Q ← Q \ Q1 end for

25

Theorem 8. PartialValidatedAgreement satisfies partial validated agreement. Proof. We first show by induction that, at the i-th iteration of the protocol, the set Q has a byzantine minority and |Q| ≤ n · (2/3)i−1 . At first, Q = P which has a byzantine minority and size n, so initialization holds. We now consider iteration i and assume Q has a byzantine minority and |Q| ≤ n · (2/3)i−1 . G is a disperser used to send parties’input. Because it is a (n/3, 5|Q|/6)-disperser and at least n/3 honest parties send their valid input through it, at least 5|Q|/6 parties receive a valid input. So at least 5|Q|/6 − |Q|/2 = |Q|/3 parties will have a valid input. Because Q has a byzantine minority, the ParallelBroadcast call will succeed, and thus |Q1 | ≥ |Q|/3. If Q1 has a byzantine minority, then all the conditions for validated agreement are satisfied, so all honest parties in Q1 will agree on a valid input and ReliableGroupBroadcast will ensure that all honest parties receive this input and return. If this does not happen, then it implies that Q1 has a byzantine majority, so Q \ Q1 has a byzantine minority. Moreover, because |Q1 | ≥ |Q|/3, we have |Q \ Q1 | ≤ 2|Q|/3 ≤ n · (2/3)i using the induction hypothesis. Thus, the induction step holds. Finally, after ⌈log3/2 n⌉ iterations, if no output has been returned yet, we have |Q| ≤ n · (2/3)⌈log3/2 n⌉ ≤ 1. Because there is a byzantine majority, it implies that there is exactly one honest party left in Q. It will thus receive a valid input, share it with other parties and they will return it this iteration. Thus, all parties will return the same valid input: the protocol satisfies partial validated agreement. Lemma 16. Assuming the underlying protocols are byzantine-robust, then the protocol is byzantinerobust and: BPVA (n, L) = O(L log n + κnb2 + κb3 log n) + n/b · BMVBA (n, b) + O(log n) · BMVBA (n, L) ⌈log3/2 n⌉

+

X

BVA (n · (2/3)i , L)

i=0

Additionally, ⌈log3/2 n⌉

RPVA (n) = O(log n)(b + RMVBA (n)) +

X

RVA (n · (2/3)i )

i=0

. Proof. We consider the round complexity. We note that in the i-th iteration, an honest party will only consider that at most (2/3)i−1 n parties are participating. However, because we want our protocol to be byzantine robust, this does not mean that at most (2/3)i−1 n honest parties are participating: if there is a byzantine majority, then honest parties may disagree on who is participating and all of them may believe they are participating. We consider the complexity of the i-th iteration, while remarking that a party p will consider itself to be part of at most one set Q1 in the whole protocol: • Sending using the disperser graph: using Theorem 12, G has constant degree, so the per-party bit complexity is O(L). This takes 1 round. • Parallel broadcast: on at most n · (2/3)i−1 parties. Parties broadcast a single bit. Using Lemma 15, this takes b + RMVBA (n · (2/3)i−1 ) rounds and O(κnb2 ) + ((n · (2/3)i−1 )/b + 1) · (O(κb3 ) + BMVBA (n, b)) bits per party. 26

• Validated agreement: has per-party bit complexity BVA (n·(2/3)i−1 , L) and round complexity RVA (n · (2/3)i−1 ). • Reliable group broadcast: Using Lemma 28, this takes O(κn log n) + BMVBA (n · (2/3)i−1 , L) bits and O(1) + RMVBA (n · (2/3)i−1 ) rounds. P⌈log n⌉ Summing these over all iterations, and using the fact that i=0 3/2 (n · (2/3)i−1 ) = O(n), we obtain the expected results.

11

Validated Agreement

We now present our protocol to solve validated byzantine agreement. To do so, we first present initial ideas to perform Validated Agreement and what their limitations are. Dolev-Strong: An initial idea would be to have each party send their input using reliable broadcast and more specifically the Dolev-Strong broadcast protocol. Parties could just then pick up the first valid value they receive. This would have O(n3 (nκ + L)) bit complexity. If used within our framework, this would lead to a protocol solving byzantine agreement with bit complexity Õ(n8/3 ). Although this is subcubic, the cubic cost of Dolev-Strong is the bottleneck in this case. Recursive Application: We remark that we can assume a byzantine minority and that byzantine broadcast can be implemented with a single call to byzantine agreement. This leads to a new idea: instead of using Dolev-Strong to implement Byzantine Broadcast, we can use our own byzantine agreement protocol recursively. Doing so, along with common erasure coding techniques, would lead to validated agreement having a bit complexity of Õ(n2 L + n3.5 ). This would cause the overall bit complexity of our byzantine agreement protocol to be Õ(n2.5 ). Byzantine-Robust protocol: The bottleneck of our protocol is now the O(n2 L) in the bit complexity. If we ignore round complexity for a moment, a simple idea would be to perform the broadcast calls consecutively and stop as soon as one succeeds. Indeed, only the broadcaster has a O(nL) cost and if the broadcaster is honest, the broadcast will succeed. This idea works and decreases the L-dependency to O(nL). However, this approach does not work with our requirements: it is not byzantine-robust. If there is a byzantine majority, they can prevent our broadcast protocol from succeeding, even if the broadcaster is honest and cause the overall bit complexity to go back to quadratic in L. Our solution for these problems is to use a dynamic programming approach: we track for a given group a valid input as well as a set of parties that know this input and we show how to update this information when merging two groups. What remains is to decide how to merge groups to minimize both the round and bit complexity.

11.1

Group Merging

We now provide the proper invariant we maintain on each group. Given a group G ⊆ P, every party keeps track of the tuple: (h, H) Such that h is the accumulator of a valid input, all honest parties in H know the value associated with h and G \ H has a byzantine majority (more specifically, at least (|G| − |H|)/2 parties in G \ H are byzantine). 27

We note that initialization of this tuple is easy: as each honest party p is assumed to have a valid input, it can reliable broadcast the accumulator h associated with that input and all parties in P can set G = {p}, with tuple (h, H) = (h, {p}). We now present how to merge two groups G1 and G2 with their respective tuples (h1 , H1 ) and (h2 , H2 ). We note that parts of the procedure, namely sending the value and broadcasting the decision are implementation details, which will be explained in the next section. The only assumption we make about the implementation is that if a group A sends a value to another group B, then as long as at least one honest party in A is honest, then every party in B will receive the value. MergeGroups Merge two disjoint groups G1 and G2 Input: Two groups G1 and G2 with their respective tuples (h1 , H1 ) and (h2 , H2 ) Output: A valid tuple for G1 ∪ G2 if H1 = ∅ then Return (h2 , H2 ) end if Parties in H1 send the value associated with h1 to parties in H2 Parties in H2 reliable broadcast 1 if they received the value associated with h1 , 0 otherwise Let K be the subset of H2 that broadcasted 0 if |K| ≥ |H1 | then Let K ′ be a subset of K of size |H1 | Return (h2 , H2 \ K ′ ) else Let H1′ be a subset of H1 of size |K| Return (h1 , (H1 \ H1′ ) ∪ (H2 \ K)) end if

Lemma 17. When called on two disjoint groups G1 and G2 with their respective tuples (h1 , H1 ) and (h2 , H2 ) that satisfy the invariant, MergeGroups returns a tuple (h, H) that satisfies the invariant for G1 ∪ G2 . Proof. Let M1 = G1 \ H1 and M2 = G2 \ H2 . Under the invariant, both M1 and M2 have a byzantine majority. Because they are disjoint, M1 ∪ M2 also has a byzantine majority. We consider the first case in the merge procedure: if H1 = ∅, then the tuple (h2 , H2 ) is returned. Using the invariant, we already know that honest parties in H2 know the value associated with h2 , and the set of remaining parties is exactly M1 ∪ M2 , which has a byzantine majority. So the invariant is preserved. Otherwise, we remark that either H1 or K is composed only of byzantine parties. Indeed, if H1 is only made of byzantine properties, this remark is true. Otherwise, H1 has at least one honest party, which knows the value to send according to the invariant. Thus, the send will succeed and all honest parties in H2 will receive the value. Hence, K, which is made of parties that claimed to not receive the value, is composed only of byzantine parties. We remark that in both cases, (G1 ∪ G2 ) \ H = M1 ∪ M2 ∪ H1′ ∪ K ′ , where all these sets are disjoint, H1′ ⊆ H1 and K ′ ⊆ K such that |H1′ | = |K ′ |. Because M1 ∪ M2 already has a byzantine majority, and one of H1′ or K ′ is fully composed of byzantine parties, the resulting set will also have a byzantine majority. Finally, if |K| ≥ |H1 |, then the tuple (h2 , H2 \ K ′ ) is returned. Because all parties in H2 already claim to know the value with accumulator h2 using the invariant, it is preserved. Otherwise, the 28

tuple (h1 , (H1 \ H1′ ) ∪ (H2 \ K)) is returned. Using the invariant, all parties in H1 know the value with accumulator h1 , additionally, all parties in H2 \ K broadcasted that they received the value, so they also know it. Thus, the invariant is preserved in both cases.

11.2

Implementation

Sending value We first explain how to implement the send operation. We note that each party in H1 can send the value to all parties in H2 . However, if |H1 | = |H2 | = n/2, then this would lead to a O(n2 L) bit complexity. Instead, we use erasure codes and have each party encode their input into n shares and share it with all parties along with an accumulator witness. This way, when a party in in H2 wants to receive the value, every party can send its share to it and it can reconstruct it. A key point is that if an honest party p is able to reconstruct a valid value, it will immediatly re-encode it and share it again with other parties. This is so that, even if p was only able to get enough shares with the help of byzantine parties, subsequent reconstruction will always succeed, even without their help. We give the implementation of Deconstruct and Reconstruct: • Deconstruct(p, h): Should only be called if p has the value v with accumulator h. p encodes v into n shares along with their witness, then sends each share to the corresponding party. When receiving a share, the party checks that the witness corresponds to the accumulator h and stores it. p sends O(κn log n + L) bits, while other parties do not send any bits. • Reconstruct(p, h): For every party q, if q has a share with witness corresponding to h, it sends it to p. If p receives enough shares (at least n/2), it reconstructs the value, checks that its accumulator is h, that it is valid and returns it. Otherwise, it returns ⊥. Each party sends a share, of size O(κ log n + L/n). Parallel broadcast We remark that all broadcast operations can be done in parallel. Additionally, if two merges for disjoint groups are done at the same time, their broadcasts can also be done in parallel. We leverage this idea and use our parallel broadcast protocol to perform as many of these broadcasts in parallel. This is needed to make sure the overall round complexity ends up staying linear. Regarding how we merge groups, a first idea would be to merge all groups one by one to a single group. However, this approach cannot be easily parallelized. Another approach is to use a balanced binary tree structure to merge groups, where leafs are the original groups and each internal node represents a merge operation. Although it is more efficient, it would lead to a logarithmic blowup in the bit complexity, as each party would be actively involved in O(log n) merges. Instead, we take an approach which is in between these last two: we merge following a tree of height 3, where each internal node has at most ⌈n1/3 ⌉ children. ValidatedAgreement(vin ) Validated Agreement protocol for a party p Let hin be the accumulator of vin (hp ) ← ParallelBA(P, hin ) for p ∈ P, in parallel do Deconstruct(p, hp ) end for G ← {({p}, hp , {p}), p ∈ P} for 3 iterations do Partition G into sets of size ⌈n1/3 ⌉ G′ ← ∅

29

for each set S = H1 , . . . , Hk , in parallel do (h, H) ← H1 for i = 2, . . . , k do in parallel for each p ∈ Hi do v ← Reconstruct(p, h) if v is valid and has accumulator h then Deconstruct(p, h) end if bp ← 1 if v is valid and has accumulator h, 0 otherwise Call ParallelBA on (bp )p∈Hi (h, H) ← MergeGroups((h, H), (hi , Hi )) using the result of ParallelBA end for G′ ← G′ ∪ {(h, H)} end for G ← G′ end for Let h be the accumulator of the remaining group in G in parallel for each p ∈ P do v ← Reconstruct(p, h) Return v

Lemma 18. The protocol satisfies Validated Agreement. Proof. The protocol starts with n groups. In each iteration, it forms sets of size ⌈n1/3 ⌉ (except the 3 last one) and merges them. As a consequence, after 3 iterations, there is only n/n1/3 = 1 group left. Consider the last group G with tuple (h, H). By the invariant, P \ H has a byzantine majority. Because P has a byzantine minority, this implies that H has a byzantine minority and thus has at least one honest party p. Using the invariant again, this implies that h is the accumulator of a valid input that p has. We note that every time a party p receives a valid value, it calls Deconstruct on it, which ensures that every honest party will be able to reconstruct the value associated with h at the end of the protocol. Thus, all honest parties will output the same valid value associated with h, which satisfies Validated Agreement. Lemma 19. ValidatedAgreement has per-party bit complexity: BVA (n, L) = O(L + κnb2 + κn1/3 b3 ) + O(n/b + n1/3 ) · BMVBA (n, b) + O(n/b) · BMVBA (n, bκ) And round complexity: RVA (n) = O(n1/3 ) · (b + RMVBA (n)) Proof. We remark that a call to Deconstruct has a bit complexity of O(κn log n + L) (the sender sends a share and a witness to every other party) to the sender while a call to Reconstruct has a bit complexity of O(κn log n + L/n) for every party. In each iteration, which there are 3, a party is a member of a unique set Hi . As a consequence, in each iteration, it will only call Reconstruct at most once and be the sender of at most one ParallelBA operation. Additionally, because we batch all parallel broadcasts calls together for independant merges, each iteration will call at most k ≤ ⌈n1/3 ⌋ times the ParallelBA procedure. So in total, we have for a given party p: • Initial ParallelBA call: each party broadcasts its accumulator,
of size 2κ. Hence, using 3 Lemma 15, we have a total of (n/b + 1) O(κb ) + BMVBA (n, κb) + O(κnb ) bits per party. 30

• Deconstruct calls: only the sender sends messages: 1 at the beginning, at most 1 in each iteration, for a total of 4O(κn log n + L) bits. • Reconstruct calls: at most n in each iteration, for a total of 3n(O(κ log n + L/n)) = O(κn log n + L) bits. • ParallelBA calls, ignoring when p is a sender: at most 3n1/3 calls, all parties are a sender at most once in each
iteration. So using Lemma 15, we have a total of 3(n/b + n1/3 ) O(κb3 ) + BMVBA (n) bits per party. • ParallelBA calls, when p is a sender: at most once per iteration, so a total of 3 · O(κnb2 ) bits. Summing all of these together, we get the expected bit complexity. As for round complexity, the Deconstruct and Reconstruct calls at the beginning and the end take 2 rounds. Otherwise, in each iteration, we have up to ⌈n1/3 ⌉ ParallelBA calls which are dependent on each other, so the round complexity becomes: RVA (n) = 2 + 3⌈n1/3 ⌉RP arallelBA (n) = O(n1/3 ) · (b + RMVBA (n))

12

Putting it all together

12.1

Per-party bit complexity

Using Lemma 15

We can now combine all the previous protocols together to get a subcubic byzantine agreement protocol. We first start by simplifying the complexity of the partial validated agreement protocol. Using Lemma 16, we have: BPVA (n, L) = O(L log n + κnb2 + κb3 log n) + n/b · BMVBA (n, b) + O(log n) · BMVBA (n, L) ⌈log3/2 n⌉

+

X

BVA (n · (2/3)i , L)

i=0

Using Lemma 19, we have: BVA (n, L) = O(L + κnb2 + κn1/3 b3 ) + O(n/b + n1/3 ) · BMVBA (n, b) + O(n/b) · BMVBA (n, bκ) Using the fact that

P⌈log3/2 n⌉ i=0

(n · (α)i ) = O(n) for any 0 < α < 1, we have:

⌈log3/2 n⌉

X

BVA (n · (2/3)i , L) = O(L log n + κnb2 + κn1/3 b3 )

i=0

+ O(n/b + n1/3 ) · BMVBA (n, b) + O(n/b) · BMVBA (n, bκ)

31

Using these two equations together, we get: BPVA (n, L) = O(L log n + κnb2 + κn1/3 b3 ) + O(n/b + n1/3 ) · BMVBA (n, b) + O(n/b) · BMVBA (n, κb) + O(log n) · BMVBA (n, L) = O(L log n + κnb2 + κn1/3 b3 + κn2 log n/b + κn4/3 log n) + O(n/b + n1/3 ) · κ · BBA (n)

Using Lemma 24

We now look at the complexity of our weak agreement protocol: BWBA (n) = BPC (n) + BVD (n, κn)

Using Observation 1

2

= O(n(log n + κ)) + BVD (n, κn)

Using Theorem 5

= O(n(log2 n + κ)) + O(nmκ) + BPVA (⌈n/m⌉, κn) 2

= O(nmκ + κnb /m + κn

1/3 3

b /m

1/3

Using Theorem 7

2

2

+ κn log n/(bm ) + κn

4/3

4/3

log n/m

)

+ O(n/(mb) + (n/m)1/3 ) · κ · BBA (⌈n/m⌉) Finally, we can consider the complexity of the binary agreement protocol, for n big enough, we have using Lemmas 21 and 22: BBA (n) ≤ 2BBA (⌈n/2⌉) + 4BWBA (n) So in total, we have: BBA (n) ≤ 2BBA (⌈n/2⌉) + O(nmκ + κnb2 /m + κn1/3 b3 /m1/3 + κn2 log n/(bm2 ) + κn4/3 log n/m4/3 ) + O(n/(mb) + (n/m)1/3 ) · κ · BBA (⌈n/m⌉) √

Theorem 9. For n large enough, by choosing m = b = Θ((κn)( 13−3)/2 ) ≈ Θ((κn)0.3077 ), we obtain √

BBA (n) = O((κn)( 13−1)/2 ) Proof. We note that the depency on κ, which cannot be considered as O(1) in BBA (n)’s relation prevents us from using the Akra-Bazzi method. Our proof relies on the fact that κ = polylog n. This implies that there are some constants C, K > 0 such that κ ≤ K logC n. One thing to note is that although this inequality should be true for the initial number of parties n, it may not hold in the number of parties n′ considered in recursive calls, as that would imply that κ = O(1). Let us √ ( 13−1)/2 define p = (κn) ≈ 1.3077. To give some informal insight regarding the parameters used, we will use m(n) = b(n) ≈ (κn)p−1 ≈ (κn)0.3077 . Let N > 1 large enough such that κ ≤ K logC N . We want to show that there exists constant A depending only on K and C such that BBA (n) ≤ A(κn)p . To do so, we prove by induction that for all 1 < n ≤ N , we have: p

BBA (n) ≤ A(κn)



log(N ) log(n)

D

With D a constant to be determined later. We note that if this property holds for n = N , then we have the expected result.

32

We now give the explicit values of m and n used to obtain this bound: ( (n, 1) If n ≤ Bκ4 (m, b) = (c(κn)p−1 , c(κn)p−1 ) Otherwise Where B and c are large enough constants to be determined later.  D ) Let us define f (n) = A(κn)p log(N . We consider the first case, where 1 < n ≤ Bκ4 . In log(n) this case, we use m = n and b = 1. We note when looking at the validated dispersal protocol that this effectively amounts to parties sending their proof to all other parties if they have one. In fact, looking at the recurrence we have on BBA (n), we obtain: BBA (n) ≤ 2BBA (⌈n/2⌉) + O(κn2 + n · κ · BBA (1)) ≤ 2BBA (⌈n/2⌉) + O(κn2 ) Because byzantine agreement on a single party needs no communication (BBA (1) = 0). A simple P n i i 2 2 induction argument shows that BBA (n) = log i=0 O(κ) · 2 (n/2 ) = O(κn ). Hence, we can find α > 0 such that: BBA (n) ≤ α · κn2 ≤ α · (κn)p n p

≤ α · (κn) Bκ

Because p ≥ 1 4

Because n ≤ Bκ4

≤ α · B · (κn)p K 4 log4C N We remark that we assume κ ≤ K logC N and n ≤ Bκ4 so log n = oN (logβ N ) for any β > 0. Therefore, for N large enough, if D > 4C, we can find B large enough such that: p

BBA (n) ≤ A(κn)



log(N ) log(n)

D = f (n)

We can now consider the second case, where n > Bκ4 . Fix Bκ4 < n ≤ N and assume the invariant already holds for all 1 < n′ < n. We have m = b = c(κn)p−1 ≈ Θ(κn)0.3077 . As a consequence, we can remove out lower-order terms in the recurrence of BBA (n) and simplify it: BBA (n) ≤ 2BBA (⌈n/2⌉) + O(c(κn)p + c−2 (κn)3−2p · BBA (⌈n/m⌉)) = 2BBA (⌈n/2⌉) + C1 · c(κn)p + C2 · c−2 (κn)3−2p · BBA (⌈n/m⌉) For some constant C1 and C2 . First, using the induction hypothesis: D log(N ) 2BBA (⌈n/2⌉) ≤ 2A(κn/2) log(⌈n/2⌉)   log(⌈n/2⌉) D 1−p ≤2 · f (n) log(n) p



 D We note that limn→∞ 21−p · log(⌈n/2⌉) = 21−p < 1. Let h = (21−p + 1)/2 < 1. For n large log(n) enough (which we can ensure by taking B large enough), we therefore have 2BBA (⌈n/2⌉) ≤ hf (n). We consider the second recursive term, using the induction hypothesis again and the fact that

33

⌈n/m⌉ ≤ 2n/m: D log(N ) log(⌈n/m⌉)  D log n −2 3−2p p ≤ C2 · c (κn) (2/m) f (n) log(⌈n/m⌉)  D log n −2−p 3−p−p2 p ≤ C2 · c (κn) 2 f (n) log c + (2 − p) log(n)

C2 · c−2 (κn)3−2p · BBA (⌈n/m⌉) ≤ C2 (κn)3−2p · A(κ⌈n/m⌉)p



√ log n We remark that p = ( 13 − 1)/2 is a solution of 3 − x − x2 = 0. Because limn→∞ log c+(2−p) log(n) = 1/(2 − p) ≈ 1.43, for n large enough (which we can ensure again by taking B large enough), we have: C2 · c−2 (κn)3−2p · BBA (⌈n/m⌉) ≤ C2 · c−2−p 2p 1.5D · f (n) ≤ (1 − h)/2f (n)

By taking c large enough

Finally, by taking A large enough such that C1 · c ≤ A · (1 − h)/2, we have: BBA (n) ≤ hf (n) + (1 − h)/2f (n) + (1 − h)/2f (n) = f (n) So the invariant is preserved. This concludes the proof.

12.2

Round complexity

In the previous section, we described how to choose the parameters m and b to obtain the desired complexity. We now show that given these parameters, our protocol has an optimal linear round complexity. Using Lemma 16, we have: ⌈log3/2 n⌉

RPVA (n) = O(log n)(b + RMVBA (n)) +

X

RVA (n · (2/3)i )

i=0

Using Lemma 19, we have: RVA (n) = O(n1/3 ) · (b + RMVBA (n)) Using the fact that

P⌈log3/2 n⌉ i=0

(n · ((2/3)1/3 )i ) = O(n) , we have:

⌈log3/2 n⌉

X

RVA (n · (2/3)i ) = O(n1/3 ) · (b + RMVBA (n))

i=0

Using these two equations together, we get: BPVA (n, L) = O(n1/3 ) · (b + RMVBA (n))

34

We now look at the complexity of our weak agreement protocol: RWBA (n) = RPC (n) + RVD (n, κn)

Using Observation 1

= O(log n) + RVD (n)

Using Theorem 5

= O(log n) + O(1) + RPVA (⌈n/m⌉)

Using Theorem 7

1/3

= O((n/m)

)(b + RMVBA (⌈n/m⌉))

= O((n/m)1/3 )(b + RBA (⌈n/m⌉))

Using Lemma 24

Finally, we can consider the complexity of the binary agreement protocol, for n big enough, we have using Lemmas 21 and 22: RBA (n) ≤ 2RBA (⌈n/2⌉) + 4RWBA (n) So in total, we have: RBA (n) ≤ 2RBA (⌈n/2⌉) + O((n/m)1/3 )(b + RBA (⌈n/m⌉)) Theorem 10. Using the same parameters for b and m as in Theorem 9, RBA (n) = O(n). Proof. As a reminder, in Theorem 9, we use ( (n, 1) (m, b) = (c(κn)p−1 , c(κn)p−1 )

If n ≤ Bκ4 Otherwise

√ For some constants B and c large enough and p = ( 13 − 1)/2. We show by induction that for all n ≥ 1: RBA (n) ≤ A(n − n0.95 /2) For some constant A large enough. When n = 1, the protocol returns immediately its input, so RBA (1) ≤ 1. Assume 1 < n ≤ Bκ4 . In this case, we have m = n and b = 1, so: RBA (n) ≤ 2RBA (⌈n/2⌉) + O(1) · (1 + RBA (1)) = 2RBA (⌈n/2⌉) + O(1) P n i A simple induction argument shows that RBA (n) ≤ log i=0 O(1)·2 = O(n), so with A large enough, 0.95 we have RBA (n) ≤ An/2 ≤ A(n − n /2). We now consider n > Bκ4 . In this case, we have m = b = c(κn)p−1 . Because κ4 < n, we have κ = O(n1/4 ). Additionally, b = m = Θ((κn)p−1 ) = Ω(n0 .3) and m = b = O(n0.31 ). Therefore: O((n/m)1/3 )(b + RBA (⌈n/m⌉)) = O((n0.7 )1/3 )((κn)0.31 + RBA (⌈n/m⌉)) ≤ O(n0.24 )((n1.25 )0.31 + A(2n0 .7 − n0.7∗0.95 /2)) = O(n0.94 ) For n large enough, which can be ensured by taking B large enough. Moreover, using the induction

35

hypothesis, we have: 2RBA (⌈n/2⌉) ≤ 2A(⌈n/2⌉ − ⌈n/2⌉0.95 /2) ≤ A(n − n0.95 /2) + 2A − (⌈n/2⌉0.95 − n0.95 /2) ≤ A(n − n0.95 /2) − Ω(n0.95 ) Therefore, putting it together, we have: RBA (n) ≤ A(n − n0.95 /2) − Ω(n0.95 ) + O(n0.94 ) ≤ A(n − n0.95 /2) For n large enough, which can be ensured by taking B large enough. The induction is preserved, so this concludes the proof: we have RBA (n) = O(n). So the protocol is linear.

Final Result Theorem 1. There exists a deterministic byzantine agreement protocol with round complexity √ √ RBA (n) = O(n) and bit complexity BBA (n) = O(κ( 13−1)/2 n( 13+1)/2 ) ≈ O(κ1.303 n2.303 ). Proof. Using Theorem 10, the round complexity of the protocol is linear and with Theorem 9, the √ √ per-party bit complexity is O(κ( 13−1)/2 n( 13+1)/2 ). Multiplying this by n, we get the expected upper bound on the total bit complexity.

13

Message and signature tags

We note that the protocols we have described so far have a main weakness: we expect some of them to run in parallel, but messages do not get sufficient information to know which instance of the recipient party it targets. Additionally, our protocols as they are written are weak to replay attacks: a byzantine could take a vote from an earlier or parallel vote and use it in a later vote for a different value. To fix this, we explain how to add tags and prefixes to messages and signatures to ensure that they are unique to a given instance of a protocol. First, we remark that given an instance of byzantine agreement of size n, we never have instances of size n/2 running concurrently. Only instances of size n/m will. Moreover, in each step, we only run at most a linear number of instances in parallel, and there is a bonded number of steps in a given recursion depth. As a consequence, a given instance executing at a given time and recursion depth with n parties can be uniquely identified with a O(log n)-bit tag. As a consequence, the total tag size T (n) needed for any instance at a given time satisfies: T (n) = O(log n) + T (n/m) Because, as seen in Theorem 9, we use m = Ω(nα ) for some α > 0, an immediate induction shows that T (n) = O(log n). Therefore, a O(log n)-bit tag added as a prefix to each message is sufficient to ensure that a party can identify which instance of the protocol a message targets. We remark that all messages exchanged in our protocols already have size Ω(log n), so this does not change the bit complexity of our protocols. We now consider signatures and replay attacks. Adding the previous tag as a prefix to signatures is enough to prevent replay attacks across concurrent instances. However, they are not enough for attacks executed using a signature from an earlier instance in a later instance. A simple workaround

36

is to add the current round number as an additional prefix to each signature, and send it along the signature. Because the protocol has a linear number of rounds, this only adds an additional O(log n) = O(κ) bit to each signature. If the round number of a signature does no match what is expected of the current instance, the whole message is discarded.

14

Conclusion

In this paper, we present the first subcubic deterministic byzantine agreement protocol in the synchronous setting with optimal resiliency t < n/2. To do so, we introduce multiple new approaches, including better recursive techniques, use of fault-tolerant expanders and dispersers as well as fair cake-cutting techniques. We remark that our protocol has an unusual irrational exponent, being √ ( 13 + 1)/2. There are still open questions regarding this problem. The first one would be to close the gap, which is still of a factor n0.303 between the quadratic lower bound of Dolev and Reischuk [14] and our upper bound. We remark that our proof gathering protocol is already near-optimal. As such, any improvement to validated dispersal, which we believe could be simplified would yield a more efficient algorithm.

References [1] Alkida Balliu and Fabian Kuhn, editors. 44th ACM PODC. ACM, June 2025. [2] Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Bit Optimal Distributed Consensus, pages 313–321. Springer US, Boston, MA, 1992. doi:10.1007/978-1-4615-3422-8_27. [3] Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The sphincs+ signature framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, page 2129–2146, 2019. doi:10.1145/3319535.3363229. [4] Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 353–380. Springer, Cham, November 2020. doi:10.1007/978-3-030-64375-1_13. [5] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. Journal of Cryptology, 17(4):297–319, September 2004. doi:10.1007/s00145-004-0314-9. [6] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. DARE to agree: Byzantine agreement with optimal resilience and adaptive communication. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, 43rd ACM PODC, pages 145–156. ACM, June 2024. doi:10.1145/3662158.3662792. [7] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Repeated agreement is cheap! On weak accountability and multishot byzantine agreement. In Balliu and Kuhn [1], pages 15–27. doi:10.1145/3732772.3733520. [8] Michael B. Cohen. Ramanujan graphs in polynomial time. In Irit Dinur, editor, 57th FOCS, pages 276–281. IEEE Computer Society Press, October 2016. doi:10.1109/FOCS.2016.37.

37

[9] Shir Cohen, Idit Keidar, and Alexander Spiegelman. Brief announcement: Not a COINcidence: Sub-quadratic asynchronous byzantine agreement WHP. In Yuval Emek and Christian Cachin, editors, 39th ACM PODC, pages 175–177. ACM, August 2020. doi: 10.1145/3382734.3405708. [10] Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer. From few to many faults: Optimal adaptive byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 177–187, 2026. doi:10.1145/3796701. 3815964. [11] Rafaël Del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, and Markku-Juhani O. Saarinen. Threshold raccoon: Practical threshold signatures from standard lattice assumptions. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part II, volume 14652 of LNCS, pages 219–248. Springer, Cham, May 2024. doi:10.1007/ 978-3-031-58723-8_8. [12] David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Kaisa Nyberg, editor, Topics in Cryptology — CT-RSA 2015, pages 127–144, Cham, 2015. doi:10.1007/978-3-319-16715-2_7. [13] D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045. [14] Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. In Robert L. Probert, Michael J. Fischer, and Nicola Santoro, editors, 1st ACM PODC, pages 132–140. ACM, August 1982. doi:10.1145/800220.806690. [15] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR TCHES, 2018(1):238–268, 2018. URL: https://tches.iacr.org/index.php/TCHES/ article/view/839, doi:10.13154/tches.v2018.i1.238-268. [16] Marc Dufay, Diana Ghinea, and Anton Paramonov. General Convex Agreement with NearOptimal Communication. In William K. Moses Jr. and Keren Censor-Hillel, editors, 40th International Symposium on Distributed Computing (DISC 2026), volume 397, pages 35:1– 35:25, 2026. doi:10.4230/LIPIcs.DISC.2026.35. [17] Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announcement: Optimal Adaptive Multi-Valued Byzantine Agreement. In William K. Moses Jr. and Keren Censor-Hillel, editors, 40th International Symposium on Distributed Computing (DISC 2026), volume 397, pages 63:1–63:7, 2026. doi:10.4230/LIPIcs.DISC.2026.63. [18] Fabien Dufoulon and Gopal Pandurangan. Improved byzantine agreement under an adaptive adversary. In Balliu and Kuhn [1], pages 173–180. doi:10.1145/3732772.3733553. [19] Thomas Espitau, Guilhem Niot, and Thomas Prest. Flood and submerse: Distributed key generation and robust threshold signature from lattices. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 425–458. Springer, Cham, August 2024. doi:10.1007/978-3-031-68394-7_14. [20] S. Even and A. Paz. A note on cake cutting. Discrete Applied Mathematics, 7(3):285–296, 1984. doi:10.1016/0166-218X(84)90005-2. 38

[21] Martin Hirt, Ueli M. Maurer, and Bartosz Przydatek. Efficient secure multi-party computation. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 143–161. Springer, Berlin, Heidelberg, December 2000. doi:10.1007/3-540-44448-3_12. [22] Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraete. Hypergraph ramsey numbers: Triangles versus cliques. Journal of Combinatorial Theory, Series A, 120(7):1491–1507, 2013. doi:10.1016/j.jcta.2013.04.009. [23] Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 369–378, 1988. doi: 10.1007/3-540-48184-2_32. [24] Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209, pages 32:1–32:16, 2021. doi:10.4230/LIPIcs.DISC.2021.32. [25] M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, 1980. doi:10.1145/322186.322188. [26] Eli Upfal. Tolerating linear number of faults in networks of bounded degree. In Norman C. Hutchinson, editor, 11th ACM PODC, pages 83–89. ACM, August 1992. doi: 10.1145/135419.135437. [27] Stephen B. Wicker and Vijay K. Bhargava, editors. Reed-Solomon Codes and Their Applications. John Wiley & Sons, Inc., USA, 1999.

39

A

Expander and Disperser Graphs

A graph is said to be explicit if it can be constructed deterministically in polynomial time. Theorem 11. For any constant 0 < α < 1, 1 ≤ m ≤ n, there exists an explicit directed graph G = (V, E) on n vertices where each vertex has out-degree m and such that G is a (αn, n − 4α−1 n/m)disperser. Proof. Let 1 ≤ m ≤ n, we explain how to build explicitly such a graph and how to get G from it. We consider a regular Ramanujan bipartite graph H = L ∪ R on 2n nodes (n on each side) with degree d = m. Cohen [8] explains how to build such a graph in polynomial time. We want to show that this graph is a (αn, n − 4α−1 n/m) bipartite disperser. To do so, consider a set S of αn vertices in L, let N (S) be the neighbors of S in R. We consider T = R \ N (S), there is no edge between S and T . We want to prove that |T | ≤ 4α−1 n/m. We remark that by definition √ of a bipartite Ramanujan graph, the non-trivial eigenvalues of H have absolute value at most 2 d − 1. We can therefore use the bipartite expander mixing lemma (a proof of it can be found in [22, Lemma 4.1]):

e(S, T ) − d

p √ |S||T | ≤ 2 d − 1 · |S||T | n

Where e(S, T ) is the number of edges between S and T , which by our choice of T is 0. Using d = nα : √ p |S||T | ≤ 2 d · |S||T | d p n d|S||T | ≤ 2n d|S||T | ≤ 4n2 m(αn)|T | ≤ 4n2 |T | ≤ 4α−1 n/m Therefore, N (S) ≥ n − 4α−1 n/m, So G1 is indeed a bipartite disperser. To build G = (V, E) we then identify G1 with the incidence graph of G, i.e. we identify V with both L and R, and we add an edge (u, v) in G if there exists an edge from u in L to v in R. By construction, G is a directed graph with out-degree m and is a (αn, n − 4α−1 n/m)-disperser. Using the previous theorem, we obtain a biparte version where both sides are not equal: Theorem 12. For any 1 ≤ m ≤ n, there exists an explicit bipartite graph G = (L ∪ R, E) with |L| = n, |R| = m and constant left degree such that G is a (n/3, 5m/6) bipartite disperser. Proof. As seen in the proof of the previous theorem, we can build an explicit bipartite graph G1 = (L1 ∪ R1 , E1 ) with |L1 | = |R1 | = n such that G1 is a (n/3, n − n/18) bipartite disperser by using α = 1/3 and degree d = 4 ∗ 3 ∗ 18 = O(1). We now partition R1 into m groups, each of size ⌊n/m⌋ or ⌈n/m⌉. Because m ≤ n, ⌊n/m⌋ ≥ ⌈n/m⌉/2. We then build G by identifying L with L1 and R with the m groups of R1 and defining the edges such that for each edge (u, v) ∈ E1 , we add an edge (u, v ′ ) ∈ E where v ′ is the group to which v belongs. By construction, G has left degree d = 4 ∗ 3 ∗ 18 which is constant. We note that G can be a multigraph, but each edge of G can be mapped to an edge in G1 . Because G1 is d-regular and ⌊n/m⌋ ≥ ⌈n/m⌉/2, This implies that vertices in R are composed of 40

at least n/(3m) vertices from R1 . Consider a set S ⊆ L of size |S| ≥ n/10, let Q = R \ NG (S). We want to show that |Q| ≤ m/6. We note that NG1 (S) ≥ n − n/18, which would imply that Q is composed of at most n/18 parties in R1 . Because each party in R is composed of at least n/(3m) vertices from R1 , and there cannot be an edge from S to Q, we have |Q| ≤ (n/18)/(n/(3m)) = m/6. Therefore, G is a (n/10, 5m/6) bipartite disperser. For the following theorem, we first show an intermediate lemma: Lemma 20. Let G = (L ∪ R, E) be a D-regular Ramanujan bipartite graph, with each side having n nodes. Let S ⊂ L and H = {v ∈ R, N (v) ⊆ H} (i.e H is the set of nodes whose edges all come from S). Then: |H| ≤

4|S| D · (1 − |S|/n)2

Proof. By definition, we have e(S, H) = |H|·D. We can therefore use the bipartite expander lemma on S and H ( [22, Lemma 4.1]): p √ |S||H| ≤ 2 D − 1 |S||H| n p D · |H| (1 − |S|/n) ≤ 2 D|S||H|

e(S, H) − D ·

D · |H| (1 − |S|/n)2 ≤ 4|S| |H| ≤

4|S| D · (1 − |S|/n)2

Theorem 2. For any α ∈]0, 1[, β > 1, there exists D > 0 such that for any n > 0, there exists an explicit graph G = (V, E) on n vertices of bounded degree D. Additionally, for any C ⊂ V such that |C| ≤ α · n, there exists S ⊆ V such that S ∩ C = ∅, |S| ≥ n − β · |C|, and the induced subgraph G[S] is connected and has diameter O(log n). Proof. Let n > 0, the graph we obtain uses the construction from [26], which is essentially a weaker version of this theorem with fixed α = 1/72 and β = 6, as a basis. Using [26], there exists D1 > 0 independent of n and an explicit D1 -regular graph G1 = (V1 , E1 ) on n vertices such that for any C ⊂ V1 satisfying |C| ≤ n/72, one can find S ⊂ V1 such that S ∩ C = ∅, |S| ≥ n − 6|S| and the induced subgraph G1 [S] is connected and of diameter O(log n). We now consider D2 = D2 (α, β) which we will explicit later in this proof. We consider the D2 regular bipartite Ramanujan graph G2 = (L ∪ R, E2 ) with n vertices on each side, such a graph can be built in polynomial time [8]. We now explain how to construct the resulting graph G = (V, E). We identify V with L and V1 with R. Then: E = {(u, v), ∃(u′ , v ′ ), (u, u′ ) ∈ E2 , (v, v ′ ) ∈ E2 , (u′ , v ′ )} What we essentially do is layer G2 on top of G1 : G2 maps vertices to groups (a vertex belongs to D2 groups) two vertices are linked in G if they each belong to a group which are connected in G1 . A consequence is that vertices have degree at most D1 · D2 which is independent of n. We now want to prove that G satisfies the properties of the theorem with a proper choice of D2 . Let C ⊂ V such that |C| ≤ α · n. Let H = {v ∈ R, NG2 (v) ⊆ C}. We want to show that

41

4|C| |H| ≤ n/72 and that |H| = O(1) · |C|. Using Lemma 20, we have |H| ≤ D·(1−|C|/n) 2 . We remark 4|C| 4n that |C| ≤ α · n so |H| ≤ D·(1−α) 2 ≤ D·(1−α)2 . Therefore, by choosing D2 ≥ 288/(1 − α)2 , we have |H| ≤ n/72. As a consequence, by construction of G1 , one can find K ⊆ V1 such that K ∩ H = ∅, |K| ≥ n − 6|H| ≥ 11n/12 and G1 [K] is connected with diameter O(log n). Let S = NG2 (K) \ C. We want to show that G[S] is connected, has diameter O(log n) and |S| ≥ n − β|C|. To do so, consider v1 , v2 ∈ S, by definition, we can find w1 , w2 ∈ K such that (v1 , w1 ), (v2 , w2 ) ∈ E2 . Because G1 [K] has diameter O(log n), one can find w1 = u1 , u2 , . . . , uk = w2 with k = O(log n) such that u1 → u2 → . . . → uk forms a path in G2 . By definition of K, for each ui , one can find pi ∈ V \ C such that (pi , ui ) ∈ E1 , so pi ∈ S (otherwise we would have ui ∈ H). We remark that v1 → p2 → . . . → pk−1 → v2 is by construction a path of length k = O(log n) between v1 and v2 contains within S. It remains to show that |S| ≥ n − β|C| to complete the proof. Because S = NG2 (K) \ C, it is enough to show that |NG2 (K)| ≥ n − (β − 1)|C| (which is possible as β > 1). Let P = {u ∈ L, N (u) ∩ K = ∅}. We remark that by definition, NG2 (K) and P form a partition of L, so |NG2 (K)| + |P | = n and thus it is enough to prove that |P | ≤ (β − 1) · |C|. We remark that P can be rewritten as P = {u ∈ L, N (u) ⊆ R \ K}, so we can use Lemma 20 (both sides of a Ramanujan graph have the same properties):

4|R \ K| D2 (1 − |R \ K|/n)2 4(n − |K|) ≤ D2 (1 − (n − |K|)/n)2 4 · 6|H| ≤ D2 · (1/12)2 4|C| ≤ 3456 · 2 D2 (1 − α)2

|P | ≤

Because |K| ≥ n − 6|H| ≥ 11n/12

√

Thus, by taking D2 ≥ (1−α)13824 2 (β−1) , we get |P | ≤ (β − 1)n and in turn |S| ≥ n − β|C|, so S satisfies the conditions.   √ 13824 288 Finally, by taking D2 = D2 (α, β) = max (1−α) , 2 (1−α)2 (β−1) , the assumptions above are held.

B

Missing protocols

We provide here the missing protocols used in our paper. The reason they are only presented here is that they are common knowledge or straightforward implementation of existing work.

B.1

Byzantine Agreement

We present here the framework given by Momose and Ren [24] to reduce byzantine agreement to weak agreement. We note that their protocol only reduces byzantine agreement to graded agreement, which we give a definition below. We also give a simple reduction from graded agreement to weak agreement, which together show the overall reduction. Definition 11. A protocol where each party is given an input vin ∈ {0, 1} and decides an output vout ∈ {0, 1} and a grade g ∈ {0, 1} satisfies graded agreement if: 42

• Termination: All honest parties decide • Validity: If all honest parties have the same input v, then only v can be decided with grade 1 • Graded Agreement: If an honest party decides v with grade 1, then all honest parties decide v. ByzantineAgreement(vin ) Protocol for byzantine agreement for a party p with input vin If |P| < M for some constant M , use an inefficient cubic byzantine agreement protocol instead. Partition P into two halves P1 and P2 . (v, g) ← GradedAgreementP (vin ) if p ∈ P1 then o ← ByzantineAgreementP1 (v) Send o to all parties end if if g = 0 and received the same o from a majority of P1 then v←o end if (v, g) ← GradedAgreementP (v) if p ∈ P2 then o ← ByzantineAgreementP2 (v) Send o to all parties end if if g = 0 and received the same o from a majority of P2 then v←o end if Return v

Theorem 13. [24, Lemma 9] ByzantineAgreement Satisfies byzantine agreement. Lemma 21. The protocol is byzantine robust, has round complexity RBA (n) = RBA (⌊n/2⌋) + RBA (⌈n/2⌉)+2RGBA (n)+O(1) and per-party bit complexity BBA (n) = BBA (⌊n/2⌋)+BBA (⌈n/2⌉)+ 2BGBA (n) + O(nκ).

B.2

Graded agreement

GradedAgreement(vin ) Protocol for graded agreement for a party p with input vin v ← WeakAgreement(vin ) w ← 1 if v ∈ {1, ⊥} else 0 b ← WeakAgreement(w) if v = 1 then Return (1, 1) else if b = 1 then Return (1, 0) else if b = 0 then Return (0, 1) else

43

Return (0, 0) end if

Theorem 14. GradedAgreement satisfies graded agreement. Proof. Termination follows from weak agreement’s termination. If all honest parties have the same input 1, then using weak agreement’s validity, v = 1 and then b = 1, so all honest parties return (1, 1). If all honest parties have the same input 0, then similarly, v = 0 and then b = 0, so all honest parties return (0, 1). Thus, validity is satisfied. We now consider graded agreement. Assume an honest party pi returns (1, 1). Then vi = 1, so using weak agreement, all honest parties have v ∈ {1, ⊥}, so they all have w = 1, therefore using weak agreement’s validity, all honest parties have b = 1, and will decide either (1, 1) or (1, 0). We consider the second case where pi returns (0, 1). This implies that bi = 0. We note that the previous part shows that no honest party could decide (1, 1), so it only remains to show that (1, 0) cannot be decided. But if a party pj decides (1, 0), then bj = 1, which contradicts weak agreement, given that bi = 0. Thus, graded agreement is satisfied. Lemma 22. The protocol is byzantine robust, has round complexity RGBA (n) = 2RWBA (n) and per-party bit complexity BGBA (n) = 2BWBA (n).

B.3

Multivalued Byzantine Agreement

Although our target is binary byzantine agreement, our protocol itself relies on multivalued byzantine agreement, i.e when the value to agree on is an L-bit input. We give a simple reduction from multivalued byzantine agreement to binary byzantine agreement, which only uses κ + 1 calls to binary byzantine agreement. MVBA(vin ) Protocol for multi-valued for a party pj with input vin Let h = h1 . . . hκ be the binary representation of the accumulator of vin . in parallel i = 1, . . . , κ do di ← ByzantineAgreement(hi ) b ← 1 if h = d else 0 a ← ByzantineAgreement(b) if a = 0 then Return ⊥ end if if h = d then Encode vin into n shares along their witnesses Send the i-th share to the i-th party end if if pj receives the valid j-th share sj for the accumulator h then Forward sj to all parties end if if Received a majority of valid shares for the accumulator h then Decode the shares into v Return v else Return ⊥ end if

44

Lemma 23. MVBA satisfies byzantine agreement. Proof. Termination follows from the termination of binary byzantine agreement. If all honest parties have the same input vin , the binary agreement’s validity ensures that the hash d decided will be the accumulator of vin . So all honest parties will enter the last binary agreement with b = 1 and as a consequence, a = 1 will be returned. Finally, because all honest parties already have the input matching the accumulator, each honest party will receive a share from each other honest party. Because there is an honest majority, it will be able to reconstruct the input (that it already has) and return it. Thus, validity is satisfied. We now consider agreement. If the last binary agreement returns a = 0, then using BinaryAgreement’s agreement, all honest parties will return ⊥ which satisfies agreement. We can now assume that all honest parties have a = 1. Because of validity, it implies that at least one honest party has an input whose accumulator is d. This honest party will send its share to all other parties, and as a consequence, all honest parties will receive a share from each other honest party. As before, because there is an honest majority, all honest parties will be able to reconstruct the same value and return it. Hence, agreement is satisfied. Lemma 24. Assuming the binary agreement protocol is byzantine robust,MVBA is byzantine robust, has round complexity RMVBA (n) = 2RBA (n) + 2 and per-party bit complexity BMVBA (n, L) = (κ + 1)BBA (n) + O(L + κn log n). Proof. Regarding round complexity, the first κ calls to BinaryAgreement are in parallel. After the following call, only two more rounds are needed to send and receive the shares, giving the round complexity. Parties run (κ + 1) instances of BinaryAgreement. Afterwards, each send at most 2 shares to each other party. Each share being of size O(L/n + κ log n), the per-party bit complexity follows.

B.4

Group Broadcast

We provide here a simple protocol to implement a group broadcast. A group G ⊆ P of parties with a byzantine minority want to broadcast the same input. This is done efficiently using errasure codes. GroupBroadcast(vin , G) Protocol for group G to broadcast an input vin , run by a party p if p ∈ G then Let i be the index of p in G Encode vin into |G| shares and send the i-th along with its witness to all parties end if if p receives more than G/2 shares with witnesses for the same accumulator then Decode the shares into v Return v else Return ⊥ end if

Lemma 25. If G has a byzantine minority and all honest parties in G have the same input, then all honest parties will return this input.

45

Proof. If G has an honest majority which has the same input, then all of these parties will send their share for the same accumulator to all parties. As a consequence, all honest parties will receive more than |G|/2 shares for the same accumulator, and will be able to decode the input and return it. Lemma 26. The protocol takes 1 round, each party in G sends O(Ln/|G|+κn log n) bits, regardless of what it receives. Parties outside of G send no message. Proof. The protocol ends with each party in G sending their share, and as such takes n rounds. Each party in G sends a share of size O(L/|G| + κ log |G|) to all n parties. Because |G| ≤ n, this gives the per-party bit complexity. Parties outside of G do not send any message.

B.5

Reliable Group Broadcast

We describe here a protocol similar to the previous one (group broadcast) except that it is reliable: even if the given group G does not have a byzantine minority, or that not all honest parties in G have the same input, all honest parties will return the same output. We note that this protocol can simply be implemented GroupBroadcast followed by MVBA. However, while our use case for GroupBroadcast benefits from it having only parties in G sending a message, our use case for ReliableGroupBroadcast benefits from it being balanced. As such, erasure coding is used slightly differently in this case. ReliableGroupBroadcast(vin , G) Protocol for group G to broadcast an input vin , run by a party pj if pj ∈ G then Send the accumulator of vin to all parties Encode vin into n shares and send the i-th along with its witness to pi end if if pj receives the same accumulator h from a majority of G and a valid share sj with a witness for h then Forward sj and its witness to all parties end if if pj receives more than n/2 shares and their witnesses for the same accumulator h then Decode the shares into v else v←⊥ end if Return MVBA(v)

Lemma 27. If G has a byzantine minority and all honest parties in G have the same input, then all honest parties will return this input. Additionally, all honest parties will return the same output, regardless of the state of G. Proof. If G has an honest majority which has the same input, then all of these parties will send their share and the same accumulator to all parties. As a consequence, all honest parties will receive the same accumulator value from a majority of G and a share for this accumulator, which they will forward. Hence, all honest parties will receive shares from all honest parties, which account for more than n/2. Thus they will be able to decode the input and MVBA’s validity ensures that it will be returned. The last point is a direct consequence of MVBA’s agreement. 46

Lemma 28. The protocol has round complexity RReliableGroupBroadcast (n) = 2 + RMVBA (n) and per-party bit complexity BReliableGroupBroadcast (n, L) = O(L + κn log n) + BMVBA (n, L). Proof. Sending and forwarding the shares takes 2 rounds, followed by the call to MVBA. Each party in G sends a share and witness of size O(L/n + κ log n) to all n parties, and may forward one such in the second round. Adding the MVBA call, the per-party bit complexity follows.

47

Related documents

• Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement#464644
• VaultxGPU: GPU-Accelerated Blockchain Consensus#271782
• T-RBFT: A Scalable and Efficient Byzantine Consensus Based on Trusted Execution Environment for Consortium Blockchain#31241
• Quantum Cadence: Post-Quantum Consensus with Multiple Concurrent Proposers#1448319
• Byzantine Causal Reliable Broadcast with Constant Metadata Overhead#1142218