arXiv:2607.29244v1 [cs.CR] 31 Jul 2026
J UNO: Aggregated Vector Consensus for Optimal Asynchronous Common Subset Liangrong Zhao
Qin Wang
Joseph K. Liu
Jiangshan Yu∗
Monash University [email protected]
CSIRO Data61, Australia [email protected]
Monash University [email protected]
University of Sydney [email protected]
Abstract—In this paper, we propose aggregated vector consensus, a new vector consensus primitive designed for asynchronous networks. The primitive achieves agreement by outputting a vector of values aggregated from independent process inputs. We then introduce J UNO, an asynchronous common subset (ACS) protocol that fully implements our aggregated vector consensus to attain optimal O(n2 ) message complexity. We further implement and evaluate J UNO in comparison with the legacy HoneyBadgerBFT and the state-of-the-art Dory. Experiment results demonstrate its efficacy and efficiency. Our protocol demonstrates an average throughput performance improvement of 93% compared with HoneyBadgerBFT and a 47% improvement compared with Dory. Notably, our study makes significant progress in addressing the gap in applying vector consensus protocol in fully asynchronous networks. Index Terms—Asynchronous Common Subset, Aggregation, Byzantine Fault Tolerance, Vector Consensus
I. I NTRODUCTION Byzantine fault tolerance (BFT) protocols [1] allow a distributed network of n processes (i.e., other consensus nodes) to reach consensus despite the presence of f malicious (i.e., Byzantine) processes. Traditional BFT protocols enable the correct processes to agree on a single value. However, this approach is insufficient for modern distributed systems with multiple inputs and outputs. A leader might propose a set of n transactions (e.g., in the context of blockchain [2]), but correct processes may only want to accept a subset of these transactions rather than accepting or rejecting the entire block. The vector consensus problem generalizes this concept by allowing processes to agree on a vector of values rather than a single value [3]. In vector consensus, processes propose their values and converge on a single vector that should include the majority of the values proposed by the correct processes. However, vector consensus was originally explored in synchronous networks or relied on additional mechanisms like muteness detectors or “wormholes” [3][4]. Most vector consensus primitives, in the worst cases, depend on partial synchrony [4][5][6], which can be problematic when applied directly to asynchronous networks. Processes in asynchronous networks might have different responses (or votes from an agreement perspective) due to arbitrary delays. If more than f processes disagree on a transaction in the proposed set, the ∗ Corresponding author
consensus process might be aborted or fail, compromising liveness. To our knowledge, there have been very limited efforts to apply vector consensus in asynchronous networks [7]. The other closely related concept is asynchronous common subset (ACS), which requires that the output of each correct process contains n − f values, with at least n − 2f of them originally proposed by correct processes. ACS is a fundamental primitive for constructing asynchronous BFT protocols [8][9][10][11][8][12][13][14]. An ACS protocol typically consists of two phases: the broadcast phase, where processes disseminate transactions to others, and the agreement phase, where a common subset is decided by collecting a sufficient number of input values from different processes. Most ACS constructions adhere to a few fixed design patterns and primarily rely on two paradigms (see details in Table I). Ben-Or, Kelmer, and Rabin [9] introduced the practical ACS framework known as the BKR paradigm by incorporating multiple reliable broadcast (RBC) and asynchronous binary agreement (ABA) instances. This framework has inspired subsequent studies, including HoneyBadgerBFT [8], BEAT [12], PACE [14] and EPIC [15]. Cachin, Kursawe, Petzold, and Shoup [10] proposed the CKPS paradigm, which shifted the construction paradigm by leveraging asynchronous multivalued validated Byzantine agreement (MVBA). This approach was followed by a series of works on the Dumbo family of protocols [11][13][16]. MVBA-based constructions provide optimal time complexity, partially addressing BKR’s performance bottleneck due to its linear message complexity (per transaction) and constant time complexity. Compared to BKR, which requires n parallel ABA invocations, MVBA can utilize vectors with multiple values as inputs, enabling a single agreement execution to select a vector of values rather than a single value [16]. This leads to an asymptotic improvement in message complexity [17]. Nonetheless, similar to vector consensus, MVBA typically assumes that one of the input vectors will be selected as the final decision. In other words, the consensus protocol aims to unanimously decide which of the proposed vectors to accept. Such a design overlooks the fact that correct processes in an asynchronous network might have different votes due to unbounded delays. This creates a challenging scenario where votes from a correct process may not be entirely accurate. Consequently, a single input vector may not yield the best consensus outcome because even vectors from correct processes
of O(n2 ) by employing aggregated vectors in consensus procedures. In traditional ABA settings, each process participates in all n ABA instances. At each step of the agreement phase, every one of the n processes sends n vote messages to each of the n recipients, resulting in a message complexity of O(n3 ). In contrast, we adopt an AVC implementation where, at each step of the agreement phase, each of the n processes sends only one vote message to each of the n recipients, reducing the message complexity to O(n2 ). This is accomplished by aggregating a process’s n vote messages — each containing a vote intended for a single ABA instance — into a single message that includes a vector of n binary votes for all n ABA instances. Each element of the vector represents an individual vote for a specific ABA instance.
can contain incorrect values due to poor network conditions, particularly in asynchronous settings. Compared with MVBA-based ACS primitives with vector features, the independent relationships among transactions are more effectively featured and utilized in BKR with n separate ABA instances. PACE enhances this approach by replacing the traditional ABA with a re-proposable ABA, which biases the agreement preference towards one, considering that correct processes might initially have “wrong” votes [14]. This motivates us to explore the BKR paradigm. However, BKR constructions have been criticized for their redundant message complexity due to the n parallel RBC and ABA instances, resulting in an overall message complexity of O(n3 ). This is asymptotically higher than the O(n2 ) complexity in MVBA. What is aggregated vector consensus? Inspired by the parallel ABA design in the BKR paradigm, we propose a new aggregated vector consensus (AVC) primitive where the final agreement outcome is aggregated rather than selected from input vectors. Processes can individually vote and reach a consensus for each value in the final vector consensus outcome. Aggregated vector consensus is an agreement where a process pi (where 1 ≤ i ≤ n) inputs a vector Vi and correct processes attempt to decide on a vector V while satisfying related properties (formally defined in Definition 2). In particular, the agreed V could be either a proposed Vi , or a vector of aggregated elements from different proposed vectors. Road to use AVC to achieve a better ACS. We aim to develop an ACS protocol that enhances normalcase performance through independent value processing, while also maintaining the optimal message complexity achieved by recent MVBA-based ACS protocols [14][17][18]. We start from reviewing the technical roots of constructing ACS protocols and try to adopt the vector design to lower the overall complexity. We show our efforts in both two phases (namely, broadcast and agreement). Replacing the existing RBC with a lighter provable broadcast (PB), as inspired by previous works [19][17], is challenging in the BKR paradigm due to the absence of all-toall communication in PB, which is essential for achieving the agreement property required in the subsequent agreement phase. Specifically, RBC guarantees that all correct processes can eventually deliver the same value if there is a value to deliver (i.e., agreement), while PB only ensures that if two correct processes deliver, they deliver the same value (i.e., consistency). This “property loss” presents challenges for ACS constructions, as the subsequent agreement phase typically relies on the agreement property to ensure that all correct processes have the same delivery outcomes. MVBA protocols, such as VABA [19] and Speeding Dumbo [17], require either additional PB invocations, more communication rounds, or extra phases like the recovery phase [17]. We aim to design an agreement protocol that allows us to replace RBC with PB without adding any extra communication overhead. We shift our focus to the agreement phase and discover that it is feasible to achieve a reduced overall message complexity
Contributions. Based on this design principle, we formally deliver a series of research outputs. A new primitive: aggregated vector consensus. We introduce a new concept called the aggregated vector consensus (AVC) primitive (Sec.II). In AVC, the final agreement is formed by aggregating input vectors instead of selecting from them. Each process votes on individual values within these vectors to reach a consensus on the final vector. Our study of AVC fills the gap by (i) applying a vector consensus protocol in fully asynchronous networks; and (ii) exploring the potential of adapting the PB module to the BKR paradigm (Table I). Surprisingly, our approach simplifies the complex communication patterns of parallel ABA designs, reducing the required communication steps compared to stateof-the-art vector-based MVBA implementations. TABLE I: Comparisons for ACS & Asynchronous BFTs Protocols
Paradigm
Broadcast
Agreement
Message
HoneybadgerBFT [8] BEAT [15] EPIC [15] PACE [14]
BKR BKR BKR PACE*
RBC RBC RBC RBC
ABA ABA ABA rABA**
O(n3 ) O(n3 ) O(n3 ) O(n3 )
VABA [19] Dumbo [11] Speeding Dumbo [13] Dory [20]
CKPS CKPS CKPS CKPS
PB RBC PB PB
MVBA MVBA MVBA MVBA
O(n2 ) O(n3 ) O(n2 ) O(n2 )
J UNO
BKR
PB
AVC
O(n2 )
Design Pattern
Complexity
* The paradigm for Pace is similar to BKR. ** rABA stands for the reproposable ABA.
A new ACS construction riding on the new primitive. We propose J UNO, an instantiated construction that fully implements our aggregated vector consensus primitive (Sec.III). J UNO consists of two refined protocols. Firstly, we design an agreement protocol based on our newly proposed aggregated vector consensus. Our protocol adopts the vector input approach to have a single agreement instance, encapsulating the n parallel agreement instances. The overall message complexity of the agreement phase matches
2
the optimal O(n2 ) for n instances. Our aggregated vector consensus can merge n messages into a single message, reducing communication costs for n − 1 authenticators for each process in each round. Secondly, we present a provable broadcast (PB) protocol tailored for our aggregated vector agreement. We design a lightweight broadcast protocol with linear message complexity to match the agreement protocol. Our PB protocol facilitates the following agreement phase, where the delivery statuses recorded during the broadcast determine the agreement inputs. Full implementation of J UNO with evaluations. We developed, evaluated, and examined our protocol J UNO, addressing aspects of performance, complexity, and security (Sec.V). In our implementation, J UNO demonstrates significant improvements in throughput and latency. We conducted a comparative simulation, assessing J UNO against prominent protocols such as the open-source HoneyBadgerBFT (improved by 93%) and Dory (by 47%). J UNO is capable of tolerating up to f Byzantine faults in a system comprising (3f + 1) total processes. The message complexity remains O(n) per transaction and O(n2 ) when processing n parallel transactions.
RBC-none-duplication: No correct process delivers message m more than once. • RBC-integrity: If a correct process delivers a message m with a correct sender p, then the message m was previously broadcast by p. • RBC-agreement: If some correct process delivers a message m, then every correct process eventually delivers m. •
2) Provable broadcast.: Recent works on MVBA-based ACS protocols have explored the option of using a much cheaper provable broadcast primitive to bring down the high communication cost of the broadcast phase. Compared with the all-to-all communication pattern in the reliable broadcast, the provable broadcast’s all-to-one pattern only incurs a linear communication cost. Different sets of properties can be achieved by varying the number of sequential invocations of provable broadcast. In general, provable broadcast primitives can obtain the following properties 1 : • PB-validity: If a correct process p broadcasts a message m, then every correct process eventually delivers m. • PB-none-duplication: No correct process delivers message m more than once. • PB-integrity: If a correct process delivers a message m with a correct sender p, then the message m was previously broadcast by p. • PB-consistency: If some correct process delivers a message m and another correct process delivers a message m’, then m = m’.
II. ACS AND AGGREGATED V ECTOR C ONSENSUS We revisit BKR-based ACS protocols and introduce a new primitive, denoted as the aggregated vector consensus (AVC). A. Asynchronous Common Subset In ACS protocols, each process broadcasts a value, typically known as a transaction in the context of blockchains, as input. All correct processes will output a common subset S of these inputs, ensuring that transactions from at least n − f processes are included. Formally, a secure ACS protocol satisfies the following properties [8]: • ACS-validity: If a correct node outputs S, then |S|≥n-f, and S contains the inputs of at least n-2f correct nodes. • ACS-agreement: If a correct node outputs S, then every correct node outputs S. • ACS-totality: If n-f correct nodes receive an input, then all correct nodes produce an output. In general, ACS protocols consist of two phases: (i) broadcast: transactions are disseminated to all other processes; and (ii) agreement: correct processes reach an agreement regarding which transactions should be included in the final subset.
C. The Agreement Phase A Byzantine agreement protocol enables processes to reach a mutual agreement in the presence of malicious parties. Typically, a Byzantine agreement invocation decides the acceptance of a single value proposed by some process. Equivalently, the protocol aims to select a correct value and ensure that all correct processes eventually accept this value as the sole outcome. As a result, multiple agreement invocations are necessary if different values proposed by different processes need to be accepted simultaneously. 1) Vector consensus: The concept of using vectors in Byzantine consensus was first introduced in the vector consensus problem [3] as a reduction method for atomic broadcast primitives. In the vector consensus problem, correct processes aim to agree on a set of values represented as a vector. A similar design was also introduced in MVBA. It replaced the generalized multi-valued input with a vector containing multiple values, allowing the agreement protocol to output one of the selected vectors from inputs rather than a single value. Formally, the vector consensus problem is defined as [3]:
B. The Broadcast Phase 1) Reliable broadcast: Transactions have to be disseminated as the votes in the subsequent agreement phase rely on their delivery status. Most of the ACS protocols employ the well-explored RBC as their broadcast primitive for its reliability in asynchronous networks. Bracha’s original doubleecho RBC protocol results in a total communication overhead of O(n2 ) as it requires rounds of all-to-all communication to satisfy the following properties [21]. • RBC-validity: If a correct process p broadcasts a message m, then every correct process eventually delivers m.
Definition 1 (Vector consensus). Vector consensus is a form of agreement where each process inputs a value v and correct processes attempt to decide on a vector V of values so that the following properties are satisfied: 1 While different papers assign varied names and definitions, we adhere to a consistent set of reliable broadcast properties for easy comparison in the following sections [21]
3
VC-agreement: If two correct processes decide V and V’, then V = V’. • VC-termination: All correct processes eventually decide. • VC-validity: If a correct process decides V, then V satisfies the following conditions: – For every 1 ≤ i ≤ n, if process pi is correct, then V[i] is either the vi , initial value of pi , or ⊥. – at least f+1 elements of the vector V are the initial values of correct processes.
D. New Primitive: Aggregated Vector Consensus
•
We accordingly propose a new set of property definitions that better align with the requirements of the ACS protocol and the features of vector consensus. Definition 2 (Aggregated Vector Consensus). Aggregated vector consensus is an agreement where a process pi , 1 ≤ i ≤ n, inputs a vector Vi and correct processes attempt to decide on a vector V so that the following properties are satisfied: • AVC-agreement: If two correct processes decide V and V’, then, V = V’. • AVC-termination: All correct processes will eventually decide. • AVC-validity: If a correct process decides V, then, for each 1 ≤ i ≤ n, there exists a correct process pj such that V[i] = Vj [i].
Compared to ACS, vector consensus has a slightly different validity property: it requires the final vector output to contain at least f + 1 correct values, whereas ACS only requires the inclusion of n − f correct values. The difference is caused by their ways of handling inputs and outputs: in vector consensus, each process inputs a single value and outputs a vector of values, while in MVBA, each process inputs a vector and selects one of the input vectors as the output. Another major difference is the definition of validity.
Our definition of validity ensures that the overall agreement vector’s validity relies on the validity of each individual element of proposed vectors, rather than just considering the vector as a whole. Moreover, our aggregated vector consensus allows correct processes to propose conflicting values, as long as the final decided value has been proposed by at least one correct process and will be unanimously agreed upon. Intuitively, our definition can be viewed as a generalized version of vector consensus, where each process proposes n inputs instead of just one. If process pi ’s input vector Vi contains only a single value Vi [i] with all other elements in Vi being ⊥, our definition aligns closely with the classic definition of vector consensus given in Definition 1.
2) Validity: Validity is a critical property for an asynchronous Byzantine agreement as it determines the criteria of correctness of the agreement outcome. There are two common validity definitions: strong validity and weak validity [10]. • Strong validity: If a correct process decides v, at least one correct process proposes v. • Weak validity: If all correct processes propose v, then every correct process that terminates decides v. Weak validity ensures a minimum termination condition: if all correct processes unanimously propose the same value, this value is guaranteed to be accepted. In contrast, strong validity requires a stronger liveness condition, considering cases where correct processes might propose different values. It ensures the correctness of the agreement decision as long as it is originally proposed by a correct process. MVBA further assumes an external validity to ensure the protocol’s output is not only consistent and reliable but also appropriate and meaningful within the context of the application using it [10]. • External validity: If a correct process decides v, v satisfies the external predict function. However, when adapting to a vector agreement, existing validity definitions overlooked a key point: the elements within a vector are typically considered independent. Each element in the final decision vector should ideally be determined individually, rather than by selecting one of the input vectors as the agreement outcome (e.g., in Dumbo-MVBA [16]). In vector consensus, the validity of each value in the final decision vector follows the principle of strong validity. A value is deemed valid only if it is the input from a correct process. However, the validity definition in vector consensus presents challenges when directly applied in an ACS protocol, where each element in a vector typically represents a vote on the inclusion of a specific transaction. Correct processes might cast incorrect votes due to varying delivery statuses, caused by unpredictable delays in an asynchronous network.
III. J UNO IN A N UTSHELL A. General System Model Processes. We consider a network Π = {P0 , P1 , ..., Pn−1 } of n processes with identifiers known to all in the network. We assume that processes are authenticated, i.e., they can rely on a digital signature scheme to authenticate each other’s messages. We consider up to f ≤ ⌊ n−1 3 ⌋ processes may be Byzantine. Byzantine processes may behave arbitrarily, but cryptographic primitives remain secure. Asynchronous network. We consider an asynchronous network, where messages sent by correct processes are eventually delivered after an unknown delay. Processes are connected in a distributed manner where each process is able to communicate with any other process via a direct connection. The communication link between each pair of processes ensures that no message from the correct sender is lost, duplicated or indefinitely delayed. However, messages can be arbitrarily delayed or reordered. B. J UNO Overview We propose a new ACS protocol, J UNO, which incorporates parallel provable broadcast instances along with a vector agreement instance (the structure diagram given in Fig.1) where each process inputs a transaction and outputs the same vector. Our protocol introduces two new features in its design.
4
P0
tx0
Provable broadcast instance 0 V0 Propose
P1
tx1
P1
P0
Endorse
P1
Lock
P1
P0
Deliver
Commit
P1
P1
P0
P0
P1
P1
P0 P1 V1
P2
P2
P2
P3
P3
P3
Provable broadcast instance 1 P2 P3
tx2 tx3
... P2
P2
P3
P3
Vector outputs (binary values)
V2
Provable broadcast instance 2
Vector Agreement
Provable broadcast instance 3 V3
Fig. 1: Overall structure of J UNO.
that all correct processes will eventually deliver a message when the primary’s correctness is not guaranteed [21]. To complement it, our design bypasses the need for the RBC-agreement property not provided by PB and only relies on its PB-consistency. Compared with the RBC-agreement property, the consistency property does not guarantee totality, which ensures that if a message is delivered to a correct process, every correct process eventually receives the same message [21]. There might be a situation where one correct process delivers a message while another correct process has not yet received it from the sender. VABA’s solution is to introduce a key-lock-commit mechanism that can be implemented with four consecutive PB executions. This is to ensure all correct processes in a later view’s broadcast phase can convince the left-out processes to proceed to the latest view after they lock themselves for a view change after “commit” [19]. Speeding Dumbo manages to reduce two invocations by introducing two additional steps of all-to-all communication in the agreement phase. They also introduce an effective “recovery” phase to allow processes that do not receive a message to retrieve a copy of this message from others using a “help me” function. To address this property loss, we propose a provable broadcast primitive to deliver a transaction to its best capability. If a correct process is unable to deliver a transaction in a timely manner (presumably due to a faulty sender), it will cast a vote based on the stage it has completed with the transaction and let the subsequent agreement protocol decide on it. In our design, we keep a simple message exchange pattern in the broadcast phase while ensuring that such reduction does not impact and can facilitate the progression of the agreement protocol. Our provable broadcast has the following stages:
Design-①: Obtaining a linear broadcast instance. There are n parallel broadcast instances, with each process serving as the sender (referred to as the primary from a consensus view) of an instance. In each instance, the primary initiates a transaction by broadcasting a Propose message. Processes receiving messages respond with Endorse after verification. Once a threshold of E NDORSE messages is reached, the primary broadcasts a Lock message. A process receiving a valid Lock message will return a Commit message. Similarly, the primary broadcasts a Deliver message after collecting enough Commit messages, and processes receiving a valid Deliver message consider the initial transaction as delivered. This design ensures linear message complexity per transaction. Design-②: Reducing message complexity for agreement. Departing from the conventional BKR paradigm that runs a separate ABA instance for each transaction, J UNO utilizes the proposed aggregated vector consensus design to combine a process’s n votes for the parallel ABA instances into a single vector, thereby reducing the message complexity per transaction from O(n2 ) to O(n). C. (Adjusted) Provable Broadcast Prior to commencing binary agreement (BA) for binary decisions, transactions have to be disseminated as the votes in the agreement phase rely on their delivery statuses. We propose to replace the RBC with a more cost-effective PB protocol, which demonstrates linear complexity in only four steps (one-all-one-all-one). This replacement eliminates RBC’s all-to-all communication phases, resulting in a reduction in message complexity. However, it hasn’t been without trade-offs. The lack of all-to-all communication makes the non-primary processes in PB constrained to receiving messages solely from the primary. Consequently, in the event of a faulty primary, not all properties of reliable broadcast can be guaranteed in the PB, even with hardware assistance. Notably, the achievement of RBC-agreement becomes unattainable, as there is no assurance
Propose. The sender broadcasts a transaction. Endorse. A process returns an endorsement message to the sender if the transaction is valid. • Lock. The sender broadcasts a lock message if it has received 2f+1 endorsements. • Commit. A process returns a commit message to the • •
5
•
A. Provable Broadcast Protocol (Step ①-⑤)
sender if the lock message is valid. Deliver. The sender broadcasts a deliver message if it has received 2f+1 commit messages.
Our proposed PB protocol is structured into five distinct phases: propose, endorse, lock, commit, and deliver. Each phase aligns with the type of broadcast message during its respective phase. Here, we outline the abstracted workflow of these steps. Step-①: Propose. At each process Pi , Pi generates a Propose message with its transaction attached and broadcasts it to all other processes.
D. Aggregated Vector Agreement Recall the voting rules in the traditional BKR paradigm: a process votes 1 in an ABA instance only after the corresponding transaction is valid and delivered via RBC. A process votes 0 if the transaction fails to be delivered, and there are n-f transactions that have been delivered. Similarly, the states for a transaction, determined by its delivery status in the broadcast instance, also play a crucial role in facilitating our agreement protocol. The state of a transaction determines the process’s votes for that transaction. In contrast to the traditional ABA construction in ACS where each process casts a vote for every transaction, we merge the n vote messages into a single message with a nsized vote vector, each element representing a vote for an individual Byzantine agreement for one of the n transactions. As shown in Fig 1, the vector input allows J UNO to merge the n parallel agreement instances into one vector agreement instance where a process exchanges its n-size vectors in a single message instead of sending n messages to n agreement instances. Specifically, a binary decision is independently achieved for each index ranging from 0 to n-1 of the vectors, corresponding to n ABA instances in the traditional BKR paradigm. As a result, the final output from our agreement protocol is a decision vector where each element represents the binary decision corresponding to a specific transaction. The binary decision for a transaction i is derived from the i-th element across all input vectors to the agreement protocol. As in Fig.2: V 0 , V 1 ,..., V n−1 are vote vectors from processes P0 , P1 ,..., and Pn−1 , respectively.
V0 [0]
V1 [0]
Vn-1[0]
V0 [1]
V1 [1]
Vn-1[1]
V0 [2]
V1 [2]
Vn-1[2]
Step-②: Endorse. Upon receiving the Propose message from Pi , processes verify the signature. If valid, they generate an Endorse message and send it back to Pi . Step-③: Lock. Upon receiving 2f+1 Endorse messages, Pi verifies the validity of these messages and creates a Lock message to broadcast. Step-④: Commit. Upon receiving the Lock message from Pi , processes verify the signature. If valid, they generate an Commit message and send it back to Pi . Step-⑤: Deliver. Upon receiving 2f+1 Commit messages, Pi verifies validity and creates a Deliver message to broadcast. Propose
P1
V0
V1[n-1]
Vn-1[n-1]
V1
Vn-1
Agreement Inputs
Lock
P1
Deliver
Commit
P0 P1
P1
P0 P1
P1
P2
P2
P2
P3
P3
P3
Fig. 3: An example of the proposed provable broadcast. B. Agreement Protocol with AVC (Step ⑥-⑧)
BA[0]
1
BA[1]
An agreement protocol ensures that the correct processes share the same set of transactions for inclusion in ACS. Our agreement protocol is based on aggregated vector consensus. Step-⑥: Generating a Vote message. At each process Pi , Pi participates in all n transaction broadcast instances and locally records the delivery statuses of these transactions. Among all n broadcast instances, at least n-f of them eventually guarantee successful delivery, as they are led by correct processes. When Pi has received at least n-f valid Deliver messages in Round 1 (the first round), it will enter the agreement phase and produce a Vote message to broadcast with an n-sized vector containing Pi ’s votes for all n transactions. It is worth emphasizing that although the final agreement decision is a vector of binary values, the votes cast by processes in the agreement protocol are not necessarily binary, as they go beyond just 0 and 1. In other words, the input vote vectors to the agreement protocol might contain nonbinary values, while the output vector (consensus outcome) only contains 0 and 1. Specifically, there are four possible votes: 0, nil, null, and 1.
0
BA[2]
1
... V0[n-1]
Endorse
P0
BA[n-1]
1 Agreement Outputs
Fig. 2: Our agreement protocol with aggregated vector consensus (i.e., vector inputs and outputs). IV. J UNO C ONSTRUCTION In this section, we present the full J UNO protocol2 given as pseudocode in Algorithm 1. 2 We exclude the well-known [22] procedures of termination and message processing in the pseudocode for simplicity.
6
Algorithm 1 J UNO Construction 1: Parameters:
42: 43: 44: 45: 46: 47:
n: total number of processes. f < n/3: maximum number of Byzantine processes.
2: 3:
4: Variables: 5: 6: 7: 8: 9: 10:
T: the transaction a primary intends to propose p: primary’s ID, this is also its instance’s ID σ: the signature for message authentication coin: the binary common coin value v[]: vote values (vector) r: the round number, starting from 1
break if ⟨Lock, h, σp ⟩ where h != hash(⟨Propose, T, σp ⟩) break h ← hash(⟨Lock, h, σp ⟩) Send ⟨Commit, h, σi ⟩ to p vi [p] ← null
48: upon event receiving a Deliver message from p do 49: if ⟨Deliver, h, σp ⟩ where verify(σp ) == false 50: break 51: if ⟨Deliver, h, σp ⟩ where h != hash(⟨Lock, h, σp ⟩) 52: break 53: vi [p] ← 1
11: As a primary p
54: upon event i has at least n-f 1 in its vote vector v in round 1 do 55: for index x in [0...n-1] where no Propose message is received from process x 56: vi [x] ← 0 57: Broadcast ⟨Vote, v, r, σi ⟩
12: upon event p proposes transaction T do 13: Broadcast ⟨Propose, T, σp ⟩ 14: upon event receiving Endorse messages from 2f+1 processes do 15: //check if there is any message with invalid signature 16: if ∃ ⟨Endorse, h, σj ⟩ where verify(σj ) == false 17: break 18: //check if there is any duplicate messages 19: if ∃ ⟨Endorse, h, σj ⟩ and ⟨Endorse, h, σm ⟩ where σj == σm 20: break 21: //check if any message corresponds to the incorrect Propose message 22: if ∃ ⟨Endorse, h, σj ⟩ where h != hash(⟨Propose, T, σ⟩) 23: break 24: h ← hash(⟨Propose, T, σp ⟩) 25: Broadcast ⟨Lock, h, σp ⟩
58: upon event receiving n-f Vote messages do 59: //for the first round, the coin value is 1 60: coin ← CommonCoin(n-f σ, r) 61: //try to reach an agreement for each instance 62: for index x in [0...n-1] 63: if ∃ f+1 Vote messages where v[x] == 1 then 64: vi [x] ← 1 65: if ∃ 2f+1 Vote messages where v[x] == null and coin == 1 then 66: vi [x] ← 1 67: if ∃ f+1 Vote messages where v[x] == null and vi [x] ̸= 1 and coin == 1 then 68: vi [x] ← null 69: if ∃ 2f+1 Vote messages where v[x] == nil and vi [x] == 0 or nil and coin == 1 then 70: vi [x] ← null 71: if ∃ 2f+1 Vote messages where v[x] == nil or 0 and vi [x] == nil and coin == 0 then 72: vi [x] ← 0 73: if ∃ 2f+1 Vote messages where v[x] == 1 and coin == 1 then 74: Decide 1 for instancex 75: if ∃ 2f+1 Vote messages where v[x] == 0 and coin == 0 then 76: Decide 0 for instancex 77: if all instances have been decided 78: //indexes and hash values of included transactions 79: Broadcast ⟨ACS, index[], hash[], σi ⟩ //the ACS is achieved 80: else 81: //rebroadcast the Vote message for next round 82: r++ 83: Broadcast ⟨Vote, v, r, σi ⟩
26: upon event receiving Commit messages from 2f+1 processes do 27: //check if any message corresponds to the incorrect Lock message 28: if ∃ ⟨Commit, h, σj ⟩ where h != hash(⟨Lock, h, σ⟩) 29: break 30: //the message duplication and signature verification remain the same, omitted here for simplicity 31: h ← hash(⟨Lock, h, σp ⟩) 32: Broadcast ⟨Deliver, h, σp ⟩ 33: Each process i 34: upon event receiving a Propose message from p do 35: //check if there is any message with invalid signature 36: if ⟨Propose, T, σp ⟩ where verify(σp ) == false 37: break 38: h ← hash(⟨Propose, T, σp ⟩) 39: Send ⟨Endorse, h, σi ⟩ to p 40: upon event receiving a Lock message from p do 41: if ⟨Lock, h, σp ⟩ where verify(σp ) == false
A process votes 1 if the transaction is delivered in a valid Deliver message; • A process votes 0 if the transaction is invalid or has never been received; • A process votes nil when the transaction is received in a Propose message from the primary and verified to be valid, but no subsequent Lock message is received from the primary; • A process votes null when receiving a valid Lock message with 2f+1 endorsements.
broadcast, indicating that the transaction has been received but not yet delivered. We use the example given in Fig.3 to further explain different vote conditions:
•
P1 is the sender (presumably malicious). P0 receives a valid Deliver message and the transaction is delivered. P0 will vote 1. • P2 receives a valid Lock message and returns a Commit message to the sender but no subsequent Deliver message is received. P2 will vote null. • P3 receives a valid Propose message and returns a Endorse message to the sender but no subsequent Lock message is received. P3 will vote nil. • (not indicated in the figure) If P3 has never received a valid Propose message, it will vote 0. •
Votes are determined by a transaction’s delivery status. Typically, a vote of 1 represents acceptance of a transaction upon successful delivery, while a vote of 0 indicates rejection when the transaction is invalid or not received. The votes nil and null reflect intermediate states during the provable
Step-⑦: Exchanging and updating the Vote message. After
7
broadcasting the Vote message, Pi awaits the reception of nf Vote messages and adjusts the vote messages accordingly. Similar to the reproposable ABA [14] with a bias towards 1, the updating logic is designed to give preference to 1, increasing its likelihood of becoming the final decision. If Pi receives f+1 valid Vote message proposing 1 for a transaction (an element of the vector is 1) and Pi ’s own vote is not 1, it will change its vote to 1.
and eventually decide 1 if the common coin is 1; (ii) a 0 vote can convert nil to 0 and eventually decide 0 if the common coin is 0. Specifically, we solve this issue by enabling the following conditions if there is no decision made after Round 5: (i) A 0 or nil vote can be converted to null upon receiving f+1 null votes if the common coin is 1; (ii) A 0 or nil vote can be converted to 1 upon receiving 2f+1 null votes if the common coin is 1; (iii) A 0 or nil vote can be converted to null upon receiving 2f+1 nil votes if the common coin is 1; (iv) A nil vote can be converted to 0 upon receiving 2f+1 nil and 0 votes if the common coin is 0. In summary, the agreement procedure tends toward deciding 1 when the common coin is 1 or toward deciding 0 when the common coin is 0. The null votes and nil votes interchangeably “flip” until the common coin facilitates one of the two decisive conditions, leading to a universal decision. 2) Network partition: Given the assumption of asynchrony, potential challenges arise where a correct process may fail to receive messages from other processes promptly due to network delays, causing a lag in progress compared to others. To address this, similar to protocols such as Hybster, we implement an arranging window mechanism [23]. The window is defined by the counter number of the last achieved ACS, serving as the lower watermark, while the upper bound is set slightly higher. Only transactions falling within this interval are considered valid. Correct processes broadcast ACS messages once an ACS is attained. These messages contain the counter number (as transactions within an ACS share the same counter number), along with the indexes and hash values of transactions. A lagging process can catch up by gathering a quorum of ACS messages and retrieving all transactions from finalized ACSs from other processes upon request. In an asynchronous network, messages might be delivered in a different order than their initial orders. Hence, if a process receives a new message with a higher counter number from a primary while it is working on a lower-numbered transaction, it temporarily stores the new message until preceding transactions from the same primary are finalized. Importantly, a process will only store transactions with counter numbers within the ordering window. Transactions with counter numbers higher than the high watermark will be discarded, as correct processes will issue any counter number before the previous one is finalized and their transactions can hardly have far-advanced counter numbers. This prevents a faulty process from overwhelming the external storage of correct processes by sending multiple messages with far subsequent counter numbers. Nonetheless, the counter number in an ACS message may exceed the ordering window due to network partitions, risking the rejection of the latest transactions by lagging processes. In this case, an up-to-date ACS message can synchronize the slow process and update its ordering window.
Step-⑧: Flipping the coin and converging to agreements. After collecting n-f Vote messages, a common coin is tossed, and Pi endeavors to achieve an agreement when conditions are met. Notably, the common coin value is optimistically set to 1 in the first round (Round 1) before outputting either 0 or 1 with equal probability in subsequent rounds. For each index x, ranging from 0 to n-1, in an n-size vector representing n processes: • Upon receiving n-f Vote messages where elements x are all 1, Pi decides 1 for x if the coin value is 1. • Upon receiving n-f Vote messages where elements x are all 0, Pi decides 0 for x if the coin value is 0. • Upon receiving n-f Vote messages where elements x are all null, Pi decides 1 for x if the coin value is 1. C. Special Cases 1) Blockage situation: We must account for scenarios where correct processes have different delivery statuses for the same transaction. If we were to simply split their votes between 0 and 1 based on whether the transaction was delivered, treating nil and null as 0, some correct processes voting 1 would eventually decide on 1, while others voting 0 would be unable to decide if faulty processes choose to equivocate. The root cause is that correct processes are likely to vote differently due to varying delivery statuses, and there is no guarantee that these delivery statuses will eventually converge to the same state. As a result, the “reproposable agreement” idea proposed by PACE does not address this issue. The inclusion of nil and null votes addresses the property loss caused by the provable broadcast. This prevents a deadlock scenario that can compromise the termination property, indefinitely stalling the protocol (breaking system liveness). A blockage situation might happen when votes from correct processes are divided between null and nil. It happens when some correct processes have received the Lock message while others have not. However, none of them have received the Deliver message to be converted to vote 1. Consequently, the correct processes might become stuck and fail to reach a consensus because none of the decisive conditions for consensus can be met as long as the Byzantine processes choose not to send any message. In this case, we assert that the relevant transaction is valid, as a nil or null vote can be produced only when the corresponding Propose message is authenticated. As a result, both 1 and 0 can be acceptable as long as correct processes eventually converge to the same decision. The general logic to solve the blockage is: (i) a null vote can convert 0 or nil to null
V. A NALYSIS AND E VALUATION A. Complexity Analysis In this paper, the message complexity refers to the total number of messages generated by correct processes and
8
the communication complexity refers to the total number of bits exchanged among correct processes [10]. We achieve lower message complexity while communication complexity is aligned to other asynchronous BFT protocols. We analyze both the message complexity, indicating the total number of messages exchanged among processes, as well as the communication complexity, which is the total number of bits exchanged. J UNO’ message complexity is O(n2 ) and O(n) per transaction while the overall communication complexity is asymptotically O(5n2 + |m|n2 log n). The 5n2 is due to n parallel instances of provable broadcast with five communication steps (2.5 rounds) and |m|n2 log n comes from the agreement phase where |m| is the Vote message size and log n indicates the number of Vote message exchange rounds required for reaching agreement. A Vote message includes a 2n-bit vote vector along with metadata such as process identifiers and signatures, which far predominate over the vote vector in size when n is within a reasonable range.
the performance gap becomes more pronounced as f grows. Indeed, a higher number of processes can better leverage the parallel benefits of the vector consensus. In heavy-load scenarios, the performance of J UNO slightly drops when the batch size exceeds 7000 in a network with 20 processes. This might occur when the workload surpasses capacity. Additionally, increasing the number of processes may elevate the probability of requiring additional rounds to complete the agreement phase (i.e., exchanging the vote vectors) in J UNO. 5
103 Throughput (tx/sec)
4
B. Evaluation
3
2
1
We benchmark J UNO against the legacy HoneybadgerBFT and state-of-the-art Dory for assessing the performance of an ACS protocol [24][20]. Configuration. Building on the open-source ResilientDB framework [25], we implement both J UNO and HoneyBadgerBFT and deploy them on Google Cloud. We also deploy the open source implementation3 of Dory [20] on Google Cloud as another baseline. We deploy the protocol with a geodistributed network configuration comprising E2-standard-8 machines with 8 vCPUs and 32GB memory, deployed across several regions: Sydney, Hong Kong, and Atlanta. The measured experimental settings of the network are presented in Table II. The transaction size is set to 250 bytes, and each data point represents the average results over 20 runs.
0
4000
6000 Batch size (tx)
8000
10000
Juno, f=1 Juno, f=5 Juno, f=30 HoneyBadgerBFT, f=1 HoneyBadgerBFT, f=5 HoneyBadgerBFT, f=30 Dory, f=1 Dory, f=5 Dory, f=30
Latnecy (sec)
50 40 30 20 10 0
229 137.4
2000
60
Sydney-HK HK-Atlanta Sydney-Atlanta 164 57.3
0
(a) Throughput for different batch sizes
TABLE II: Round trip time & bandwidth between each region
Round trip (ms) Bandwidth (Mbps)
Juno, f=1 Juno, f=5 Juno, f=30 HoneyBadgerBFT, f=1 HoneyBadgerBFT, f=5 HoneyBadgerBFT, f=30 Dory, f=1 Dory, f=5 Dory, f=30
0.50
0.75
1.00
121 59.7
1.25 1.50 1.75 104 Throughput (tx/sec)
2.00
2.25
2.50
(b) Latency vs throughput
Abbrev. HK for Hong Kong
Juno n=100 Juno n=31
Throughput analysis (see Fig.4a). Compared to HoneyBadgerBFT, J UNO achieves significantly higher throughput rates due to its reduced communication and message complexity. As the batch size increases, the performance disparity becomes even more pronounced. While HoneyBadgerBFT’s throughput plateaus, J UNO’s throughput continues to scale, demonstrating superior management of larger transaction loads. Particularly in the range of 8,000 to 10,000 transactions, J UNO maintains a consistent upward trajectory, indicating its robustness in highload scenarios. In comparison with Dory, J UNO demonstrates superior overall throughput performance. We observe that
Juno n=10 Dory n=100 Dory n=31
Broadcast phase Agreement phase Broadcast phase Agreement phase
Dory n=10 0
5
10
15 Latency (s)
20
25
(c) Latency breakdown for J UNO & HoneyBadgerBFT
Fig. 4: Performance evaluation. Latency analysis (see Fig.4b&Fig.4c). J UNO maintains an
3 https://github.com/xygdys/Dory-BFT-Consensus
9
Broadcast protocols. Reliable broadcast protocols are widely used for their message delivery properties in asynchronous settings. RBC protocols exhibit a message complexity of O(n2 ) as a result of the all-to-all communication rounds involved [33][34]. Provable broadcast protocols, which are employed in pipelined BFT systems [35][36][37], demonstrate linear message complexity. However, there is an absence of studies examining their potential application within ACS.
overall lower latency than HoneyBadgerBFT (cf. Fig.4b), with an improvement margin increasing as the network scales. This improvement is primarily due to the reduced message propagation required to achieve equivalent throughput levels. In comparison with Dory, J UNO’s latency is similar when f = 1. When the network size is small, the benefits of parallel processing in the vector consensus are not significant. However, as the network size grows, J UNO can achieve the same throughput level with a smaller batch size, resulting in approximately 21% lower overall latency compared to Dory. To provide a more detailed understanding, we present a latency analysis of J UNO and Dory breaking down the two phases of ACS protocols. The batch size is set to 25,000tx (around 6.25MB) to evaluate performance under heavy loads. As depicted in Fig.4c, latencies in both phases of J UNO are lower than those of Dory, especially the broadcast phase. Although both protocols use provable broadcast, J UNO’s broadcast phase requires far fewer communication rounds. While the agreement phase remains a substantial portion of the overall runtime for both protocols, J UNO’s agreement phase is considerably faster due to its message aggregation approach, resulting in fewer communication rounds in normal cases.
Vector consensus. The vector consensus problem, introduced by Doudou et al. [3], is a method for achieving atomic broadcast in distributed systems, where nodes must agree on a vector of values rather than a single value. Neves et al. [4] explored this problem in asynchronous networks, utilizing a “wormhole” mechanism to provide reliable and timely hybrid services. Vaidya et al. [38] demonstrated the impossibility of solving the vector consensus problem without additional support and distinguished between two variants: exact vector consensus, applicable in synchronous networks with strict requirements, and approximate vector consensus, suitable for asynchronous networks with more relaxed conditions. Additionally, Cachin et al. [5] proposed an anonymitypreserving Byzantine vector consensus protocol by combining ring signatures with vector consensus, thereby reducing the vector consensus problem to a binary consensus problem.
VI. R ELATED W ORK ACS paradigms. The asynchronous common subset [26] is a type of Byzantine consensus under asynchronous networks. Each distributed processes propose a value as input and reach an agreement on a common subset (i.e., n-f ) as output. ACS can be extended to construct many distributed protocols, such as distributed key generation [27][28], secret sharing [29], and multi-party computation (MPC) [30][31]. In practice, ACS are implemented using two classic paradigms [14]: BKR and CKPS. The BKR paradigm [9] involves a broadcast instance and an agreement instance for each participant in the network, and has been further refined in subsequent research [8][12][15]. On the other hand, the CKPS paradigm [10] replaces ABA with MVBA, facilitating consensus on multi-value inputs. This approach has been advanced by a series of works aimed at optimizing performance [13][16][17]. Our study focuses on the BKR paradigm. Asynchronous Byzantine agreements. HoneyBadgerBFT [8] is a recent asynchronous BFT protocol that utilize parallel instances to reduce computing complexity and guarantees liveness without relying on timing assumptions. HoneyBadgerBFT has inspired a series of subsequent works aimed at enhancing its efficiency and scalability. The Dumbo family, for instance, improves upon HoneyBadgerBFT by transitioning from binary to multi-valued Byzantine Agreement (BA)[11], incorporating a linear broadcast protocol and a compact consensus protocol[17]. The BEAT family enhances HoneyBadgerBFT through a modular design approach [12]. Further advancements include PACE [14], which introduced a binary BFT protocol with fewer steps per round and a more efficient common coin algorithm. WaterBear [32] extends the security guarantees to partially synchronous settings. FIN [18] offers a signature-free ACS with optimal time complexity.
VII. C ONCLUSION In this paper, we introduce a novel primitive called aggregated vector consensus (AVC) for constructing efficient and optimal asynchronous common subset protocols. AVC allows for the collection of multiple independent instance inputs and their aggregation into a single vector-based output. Building on AVC, we design and implement J UNO, a practical ACS protocol. J UNO achieves optimal O(n2 ) message complexity. Experimental evaluations demonstrate that it outperforms HoneyBadgerBFT (by 93%) and Dory (47%). R EFERENCES [1] Miguel Castro, Barbara Liskov, et al. Practical Byzantine fault tolerance. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), volume 99, pages 173–186, 1999. [2] Sisi Duan and Haibin Zhang. Recent progress on BFT in the era of blockchains. National Science Review, 9(10):nwac132, 2022. [3] Assia Doudou and André Schiper. Muteness detectors for consensus with byzantine processes. In Proceedings of the seventeenth annual ACM Symposium on Principles of Distributed Computing (PODC), page 315, 1998. [4] Nuno Ferreira Neves, Miguel Correia, and Paulo Verissimo. Solving vector consensus with a wormhole. IEEE Transactions on Parallel and Distributed Systems (TPDS), 16(12):1120–1131, 2005. [5] Christian Cachin, Daniel Collins, Tyler Crain, and Vincent Gramoli. Anonymity preserving Byzantine vector consensus. In European Symposium on Research in Computer Security (ESORICS), pages 133–152. Springer, 2020. [6] Miguel Correia, Nuno Ferreira Neves, and Paulo Veríssimo. From consensus to atomic broadcast: Time-free byzantine-resistant protocols without signatures. The Computer Journal, 49(1):82–96, 2006. [7] Henrique Moniz, Nuno Ferreria Neves, Miguel Correia, and Paulo Verissimo. RITAS: Services for randomized intrusion tolerance. IEEE Transactions on Dependable and Secure Computing (TDSC), 8(1):122– 136, 2008.
10
[8] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 31–42, 2016. [9] Michael Ben-Or, Boaz Kelmer, and Tal Rabin. Asynchronous secure computations with optimal resilience. In ACM symposium on Principles Of Distributed Computing (PODC), pages 183–192, 1994. [10] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference (CRYPTO), pages 524–541. Springer, 2001. [11] Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Dumbo: Faster asynchronous BFT protocols. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 803–818, 2020. [12] Sisi Duan, Michael K Reiter, and Haibin Zhang. BEAT: Asynchronous BFT made practical. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 2028–2041, 2018. [13] Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Dumbo-NG: Fast asynchronous BFT consensus with throughputoblivious latency. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1187–1201, 2022. [14] Haibin Zhang and Sisi Duan. PACE: Fully parallelizable BFT from reproposable Byzantine agreement. ACM SIGSAC Conference on Computer and Communications Security (CCS), 2022. [15] Chao Liu, Sisi Duan, and Haibin Zhang. EPIC: Efficient asynchronous BFT with adaptive security. In IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 437–451. IEEE, 2020. [16] Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. DumboMVBA: Optimal multi-valued validated asynchronous Byzantine agreement, revisited. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 129–138, 2020. [17] Bingyong Guo, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Speeding Dumbo: Pushing asynchronous BFT closer to practice. Network and Distributed System Security (NDSS), 2022. [18] Sisi Duan, Xin Wang, and Haibin Zhang. FIN: Practical signaturefree asynchronous common subset in constant time. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2023. [19] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 337–346, 2019. [20] Zongyang Zhang, You Zhou, Sisi Duan, Haibin Zhang, Bin Hu, Licheng Wang, and Jianwei Liu. Dory: Faster asynchronous BFT with reduced communication for permissioned blockchains. Cryptology ePrint Archive, 2022. [21] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. In Springer Science & Business Media, 2011. [22] Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signaturefree asynchronous Byzantine consensus with t< n/3 and o(n2) messages. In ACM Symposium on Principles of Distributed Computing (PODC), pages 2–9, 2014. [23] Johannes Behl, Tobias Distler, and Rüdiger Kapitza. Hybrids on steroids: SGX-based high-performance BFT. In Proceedings of the European Conference on Computer Systems (EuroSys), pages 222–237, 2017. [24] Bellemare Sylvain, Miller Andrew, dantengsky, and Schroeder Brian. HoneyBadgerBFT Github. In Retrived in https:// github.com/ initc3/ HoneyBadgerBFT-Python/ , 2023. [25] cjcchen et al. ResilientDB Github. In Retrived in https:// github.com/ resilientdb/ resilientdb/ tree/ resilientdb-legacy-eurosys23, 2023. [26] Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In ACM Symposium on Theory of Computing (STOC), pages 52–61, 1993. [27] Eleftherios Kokoris Kogias, Dahlia Malkhi, and Alexander Spiegelman. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1751–1767, 2020. [28] Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, and Ling Ren. Practical asynchronous distributed key generation. In IEEE Symposium on Security and Privacy (SP), pages 2518–2534. IEEE, 2022. [29] Sourav Das, Zhuolun Xiang, Lefteris Kokoris-Kogias, and Ling Ren. Practical asynchronous high-threshold distributed key generation and
distributed polynomial sampling. In USENIX Security Symposium (USENIX Security), pages 5359–5376, 2023. [30] Annick Chopard, Martin Hirt, and Chen-Da Liu-Zhang. On communication-efficient asynchronous MPC with adaptive security. In International Conference on Theory of Cryptography (TCC), pages 35– 65. Springer, 2021. [31] Donghang Lu, Thomas Yurek, Samarth Kulshreshtha, Rahul Govind, Aniket Kate, and Andrew Miller. Honeybadgermpc and asynchromix: Practical asynchronous mpc and its application to anonymous communication. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 887–903, 2019. [32] Haibin Zhang, Sisi Duan, Boxin Zhao, and Liehuang Zhu. WaterBear: Practical asynchronous BFT matching security guarantees of partially synchronous BFT. In USENIX Security Symposium (USENIX Security), pages 5341–5357, 2023. [33] Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987. [34] Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal Byzantine computing. International Symposium on Distributed Computing (DISC), 2021. [35] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In ACM Symposium on Principles of Distributed Computing (PODC), pages 347–356, 2019. [36] Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K Reiter. Communication-efficient BFT using small trusted hardware to tolerate minority corruption. In International Conference on Principles of Distributed Systems (OPODIS). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023. [37] Jérémie Decouchant, David Kozhaya, Vincent Rahli, and Jiangshan Yu. DAMYSUS: streamlined BFT consensus leveraging trusted components. In Proceedings of the European Conference on Computer Systems (EuroSys), pages 1–16, 2022. [38] Nitin H Vaidya and Vijay K Garg. Byzantine vector consensus in complete graphs. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 65–73, 2013.
11