Sie können Operatoren mit Ihrer Suchanfrage kombinieren, um diese noch präziser einzugrenzen. Klicken Sie auf den Suchoperator, um eine Erklärung seiner Funktionsweise anzuzeigen.
Findet Dokumente, in denen beide Begriffe in beliebiger Reihenfolge innerhalb von maximal n Worten zueinander stehen. Empfehlung: Wählen Sie zwischen 15 und 30 als maximale Wortanzahl (z.B. NEAR(hybrid, antrieb, 20)).
Findet Dokumente, in denen der Begriff in Wortvarianten vorkommt, wobei diese VOR, HINTER oder VOR und HINTER dem Suchbegriff anschließen können (z.B., leichtbau*, *leichtbau, *leichtbau*).
Der Artikel stellt das Prioritized Multi-Valued Byzantine Agreement (pMVBA) Protokoll vor, einen neuen Ansatz zur Entwicklung optimaler asynchroner byzantinischer Vereinbarungen. Das Protokoll zielt darauf ab, die Komplexität der Kommunikation zu verringern und gleichzeitig Widerstandsfähigkeit und Korrektheit zu erhalten, wodurch es sich für großflächige dezentrale Anwendungen eignet. Zu den wichtigsten Neuerungen zählen die Integration einer auf Ausschüssen basierenden Methode und des Protokolls Asynchronous Binary Byzantine Agreement (ABBA). Der Artikel liefert eine gründliche theoretische Analyse, die zeigt, dass pMVBA eine erwartete konstante asynchrone Rundenzahl und optimale Nachrichtenkomplexität erreicht. Fallstudien und Leistungsbewertungen zeigen, dass pMVBA traditionelle MVBA-Protokolle in Bezug auf asynchrone Runden und Berechnung übertrifft. Die Effektivität des Protokolls wird durch verschiedene Szenarien veranschaulicht, darunter das Vorhandensein fehlerhafter Knoten und die ungleiche Nachrichtenverteilung. Der Artikel schließt mit einem Vergleich des pMVBA mit anderen MVBA-Protokollen, der seine Vorteile in der Kommunikationskomplexität und asynchronen Runden hervorhebt.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
Multi-valued Byzantine agreement (MVBA) protocols are critical components in designing atomic broadcast and fault-tolerant state machine replication protocols in asynchronous networks. While these protocols have seen significant advancements, challenges remain in optimizing their communication and computation efficiency without sacrificing performance. In this paper, we address the challenge of achieving agreement in MVBA without incurring extra computation and communication rounds. Our approach leverages an analysis of message distribution patterns in asynchronous networks, observing that a subset of \(f+1\) parties, including at least one honest party, can achieve an agreement more efficiently than relying on all n parties, where \(n=3f+1\), f maximum number of faulty parties. We introduce a novel protocol, Prioritized-MVBA (pMVBA), which integrates a committee-based selection process and the asynchronous binary Byzantine agreement (ABBA) protocol. In this design, a randomly selected subset of \(f+1\) parties broadcast their requests, collect verifiable proofs, and utilize these proofs within the ABBA framework to reach an agreement. The proposed pMVBA protocol is resilient to up to \(\lfloor \frac{n}{3} \rfloor \) Byzantine failures and achieves optimal performance, with an expected runtime of O(1), message complexity of \(O(n^2)\), and communication complexity of \(O((l+\lambda )n^2)\), where n is the number of parties, l is the input bit length, and \(\lambda \) is the security parameter.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Byzantine Agreement (BA) protocols are fundamental to implementing decentralized infrastructures, particularly in the context of blockchain and decentralized applications. These protocols ensure agreement among parties, even in the presence of malicious actors, making them crucial for maintaining the integrity and functionality of distributed systems. The renewed interest in BA protocols has been driven by the success of Bitcoin [1] and other decentralized applications [2], which rely heavily on these protocols for achieving agreement [3]. Despite the existence of practical BA protocols [4‐9], their reliance on time parameters for ensuring liveness poses challenges in designing agreement protocols. The FLP impossibility results [10] demonstrate that deterministic BA protocols cannot guarantee agreement in asynchronous networks. This necessitates the development of efficient asynchronous Byzantine Agreement protocols [4, 6, 11‐17] that can overcome the limitations of existing approaches, particularly in terms of communication complexity.
Achieving agreement in asynchronous networks efficiently remains a significant challenge. Classic Multi-Valued Byzantine Agreement (MVBA) protocol like Cachin’s [18], while effective, suffers from high communication complexity, often involving terms like \(O(n^3)\). This high complexity is impractical for large-scale systems, necessitating new approaches to reduce communication overhead while ensuring optimal resilience and correctness. Cachin et al. [18] introduced the concept of MVBA, where nodes agree on a value from a large input space rather than a binary decision. Cachin’s MVBA protocol employs a polynomial-time computable predicate \( Q \), where each party submits a value \( v \) that must satisfy the condition defined by \( Q \) but suffers from high communication overhead, with a complexity of \(O(ln^2+ \lambda n^2 + n^3)\). VABA [4] introduced a view-based approach to eliminate the \(O(n^3)\) term, while Dumbo-MVBA [13] used erasure codes to handle large input sizes more efficiently, reducing the communication complexity to \(O(ln + \lambda n^2)\). However, these optimizations often introduced additional rounds of communication and computation. Mostefaoui et al. provides a signature-free deterministic reduction in [19] from their signature-free binary agreement protocol [20] that solves asynchronous Byzantine Agreement with Weak validity. But, Cachin’s [18] protocol, VABA [4] and Dumbo-MVBA [13] solve asynchronous Byzantine Agreement with strong validity.
Anzeige
In this context, we propose a novel approach to optimizing MVBA protocols by introducing the Prioritized Multi-Valued Byzantine Agreement (pMVBA) protocol. Our goal is to achieve agreement in each instance without the need for extra computation and communication rounds, maintaining optimal performance metrics. The key innovation of our approach is the integration of a committee-based method within the classical MVBA framework, where a randomly selected subset of parties, rather than the entire set of parties, broadcasts proposals. The pMVBA protocol leverages the concept of a committee, wherein a subset of \(f + 1\) parties is chosen to broadcast their proposals. This approach ensures that at least one honest party is always included in the subset, enhancing the protocol’s resilience. By dynamically selecting parties for each protocol instance, we mitigate the risk of adversarial attacks targeting specific nodes. This method significantly reduces the number of broadcast messages and the associated communication overhead. Central to our protocol is the integration of the Asynchronous Binary Byzantine Agreement (ABBA) protocol, which facilitates reaching an agreement on one of the proposals broadcast by the committee members. The ABBA protocol ensures that one of the selected parties’ proposals are agreed upon with probability 1, maintaining the integrity and functionality of the distributed systems.
Our pMVBA protocol achieves several key improvements over existing MVBA protocols while exhibiting optimal resilience against Byzantine failures, with an expected runtime of \(O(1)\), optimal message complexity of \(O(n^2)\), and optimal communication complexity of \(O((l + \lambda )n^2)\), where \(n\) is the number of parties, \(l\) is the bit length of the input, and \(\lambda \) is the security parameter. The key improvements include removing the need for multiple instances of the protocol or extra rounds of messages and cryptographic computation to reach an agreement on a party’s request while keeping the optimal communication complexity. These enhancements make the pMVBA protocol suitable for large-scale decentralized applications, addressing the scalability challenges faced by traditional MVBA protocols.
Fig. 1
Comparison of two protocols. We show the communication complexity of each sub-protocol and the step where our protocol wins in terms of communication. The tx represents the transaction, the ts represents the threshold signature. 1, 1, 1, 0 represents the bit array and each color for the particular party and its messages
In Figure 1, we provide an intuitive comparison between the two protocols and illustrate how the proposed protocol achieves a communication complexity of \(O((l+\lambda )n^2)\), whereas the classic protocol has a communication complexity of \(O((l+\lambda )n^2)+O(n^3)\). In the classic protocol (see Figure 1a), there are n proposals; consequently, n threshold signatures are generated and transmitted during the Propose step. In the Commit step, each party sends an O(n)-bit array indicating which \(2f+1\) messages it has received; this information cannot be falsified. Since n parties each send O(n) information to the other n parties, the resulting communication complexity is \(O(n^3)\). This step ensures that the protocol reaches agreement within \(f+1\) ABBA instances. In contrast, the proposed protocol (see Figure 1b) has only \(f+1\) proposals. During the Propose step, these \(f+1\) proposals are broadcast to \(3f+1\) parties, ensuring that one or more proposals reach one or more parties (as demonstrated by our simulations in the Case Study section). In the Recommend step, each party recommends the proposal it has received, which requires only O(1) communication. Since one or more proposals are recommended by one or more parties, at least one proposal is guaranteed to reach \(2f+1\) parties (as proven in the Analysis section) and it ensures the protocol reaches an agreement on a proposal. Because there are only \(f+1\) proposals, the protocol necessarily terminates within \(f+1\) ABBA instances.
The main contributions of this paper are as follows:
We introduce a committee selection protocol that ensures the presence of at least one honest party in the selected subset, enhancing the protocol’s resilience against Byzantine failures.
We propose the pMVBA protocol, which reduces the communication complexity from \(O(n^3)\) [21] to \(O((l + \lambda )n^2)\) by dynamically selecting a subset of parties to broadcast their proposals. In Figure 1, we demonstrate the differences of our protocol with the classic MVBA protocol and the improvement point.
Our protocol integrates the ABBA protocol to achieve agreement with probability 1 on a proposal broadcast by the committee members, ensuring robust agreement mechanisms.
We provide a thorough theoretical analysis demonstrating that the pMVBA protocol achieves an expected constant asynchronous round count while maintaining optimal resilience and correctness.
We present extensive case studies and performance evaluations, showing that the pMVBA protocol is effective and scalable for large-scale decentralized applications, outperforming the traditional MVBA protocols in terms of asynchronous rounds and computation.
Anzeige
2 System Model
We use the standard notion [21, 22] to describe a distributed algorithm involving \( n \) parties and an adversary in an authenticated setting. This section explains the foundational assumptions, network model, adversary model, computational model, and cryptographic tools used in our protocol.
2.1 System and Network Assumptions
Parties and Their Setup: There are \( n \) parties, denoted as \( p_1, p_2, \ldots , p_n \). We consider a trusted setup of digital signature [23]. The system provides a secret key and a public key to each party before the protocol starts. A party uses its secret key to sign a message, and other parties use the corresponding public key to verify the signed message. The generation and distribution of these keys are out of the scope of this paper. We follow standard literature for key generation and distribution and refer interested readers to [24‐26]. We use the node and party alternatively throughout the paper.
Network Model: Parties are connected via reliable, authenticated point-to-point channels. Here, reliable implies that if an honest party \( p_i \) sends a message to another honest party \( p_j \), the adversary cannot modify or drop the message. However, the adversary can delay the message delivery to influence the protocol execution time. Since we consider an adaptive adversary that can corrupt a party at any time during the protocol execution, the adversary can corrupt a party \( p_i \) after it sends a message and then make the party \( p_i \) drop the message.
Adversary Model: We consider an adaptive adversary that can corrupt any party during the protocol execution. If the adversary takes control of a party, the party is corrupted, reveals its internal state to the adversary, behaves arbitrarily, and remains corrupted. An honest party follows the protocol, keeps its internal state secret from the adversary, and remains uncorrupted throughout the protocol execution. The adversary can corrupt \( f \) parties among the \( n \) parties, where \( f < \frac{n}{3} \).
Computational Model: We adopt standard modern cryptographic assumptions and definitions from [21, 22]. The assumptions allow the parties and the adversary to be probabilistic polynomial-time interactive Turing machines. This means that upon receiving a message, a party carries out some computations, changes its state, generates outgoing messages if required, and waits for the next incoming message. To rule out infinite protocol executions and restrict the run time of the adversary, we require the message bits generated by honest parties to be probabilistically uniformly bounded by a polynomial in the security parameter \( \lambda \). Therefore, we assume that the number of parties \( n \) is bounded by a polynomial in \( \lambda \).
2.2 Multi-Valued Byzantine Agreement (MVBA):
MVBA protocol enables parties to reach an agreement on an arbitrary string \( \{0,1\}^l \), provided it satisfies a predefined validity condition. This ensures that the agreed-upon value is valid, even in the presence of inputs from malicious parties, which is essential for maintaining the protocol’s correctness. The MVBA protocol employs a polynomial-time computable predicate \( Q \), where each party submits a value \( v \) that must satisfy the condition defined by \( Q \), specific to the application. The MVBA protocol guarantees the following properties with negligible probability of failure:
Liveness: If all honest parties are active, they will eventually reach a decision.
External Validity: Any value \( v \) output by an honest party satisfies the predicate \( Q(v) = \text {true} \).
Agreement: If two honest parties output values \( v \) and \( v' \), then \( v = v' \).
Integrity: The output value \( v \) by honest parties must have originated from one of the parties.
Efficiency: The number of messages generated by honest parties is probabilistically uniformly bounded.
2.3 Preliminaries
Asynchronous Binary Byzantine Agreement Biased Towards 1: The ABBA protocol allows parties to agree on a single bit \( b \in \{0,1\} \). The properties of the protocol are detailed in Appendix A.2.
(1,\(\kappa \), \(\epsilon \))- Committee Selection: The committee selection protocol is executed among \( n \) parties (identified from 1 through \( n \)). This protocol ensures that an honest party outputs a \(\kappa \)-size committee set \( C \) with at least one honest member, given that at least \( f+1 \) honest parties participate. A protocol is a \((1, \kappa , \epsilon )\)-Committee Selection protocol if it satisfies the following properties with negligible probability of failure in the cryptographic security parameter \(\lambda \):
Termination. If \(\langle f+1 \rangle \) honest parties participate in the committee selection and the adversary delivers the messages, then the honest parties will output the set C.
Agreement. Any two honest parties will output the same set C.
Validity. If any honest party outputs the set C, then:
(i) \(|C| = \kappa \),
(ii) the probability of every party \(p_i\) being in C is the same, and
(iii) C contains at least one honest party with probability \(1-\epsilon \).
Unpredictability. The probability of the adversary predicting the committee C before any honest party participates is at most \(\frac{1}{\left( {\begin{array}{c}n\\ \kappa \end{array}}\right) }\).
Guo et al. [12] constructed the \((1, \kappa , \epsilon )\)-Committee Selection protocol using a threshold coin-tossing mechanism (see Appendix A.4), which is derived from threshold signatures. The protocol ensures that at least one honest party is a committee member with overwhelming probability \(1-\epsilon - \text {neg}(\lambda )\), where \(\text {neg}(\lambda )\) is a negligible function in the cryptographic security parameter \(\lambda \), and \(\epsilon \) is \(exp(-\Omega \kappa )\).
Cryptographic Abstractions: We design a distributed algorithm in authenticated settings where we use robust, non-interactive threshold signatures to authenticate messages and a threshold coin-tossing protocol to select parties randomly [22].
1.
Threshold Signature Scheme: We utilize a threshold signature scheme introduced in [22, 27]. The basic idea is that there are \( n \) parties, up to \( f \) of which may be corrupted. The parties hold shares of the secret key of a signature scheme and may generate shares of signatures on individual messages. \( t \) signature shares are both necessary and sufficient to construct a signature where \( f < t \le (n-f) \). The threshold signature scheme also provides a public key \( pk \) along with secret key shares \( sk_1, \ldots , sk_n \), a global verification key \( vk \), and local verification keys \( vk_1, \ldots , vk_n \). Initially, a party \( p_i \) has information on the public key \( vk \), a secret key \( sk_i \), and the verification keys for all the parties’ secret keys. We describe the security properties of the scheme and related algorithms in Appendix A.3.
2.
Threshold Coin-Tossing Scheme: The threshold coin-tossing scheme, as introduced in [22, 27], involves parties holding shares of a pseudorandom function \( F \) that maps the name \( C \) (an arbitrary bit string) of a coin. We use a distributed pseudorandom function as a coin that produces \( k'' \) random bits simultaneously. The name \( C \) is necessary and sufficient to construct the value \( F(C) \in \{0,1\}^{k''} \) of the particular coin. The parties may generate shares of a coin – \( t \) coin shares are both necessary and sufficient where \( f < t \le n-f \), similar to threshold signatures. The generation and verification of coin-shares are also non-interactive. We describe the security properties of the scheme and related algorithms in Appendix A.4.
In this section, we present a protocol for multi-valued Byzantine agreement capable of tolerating up to \( f < \frac{n}{3} \) Byzantine faults. The protocol features an expected communication bit complexity of \( O(ln^2 + \lambda n^2) \) and an expected constant asynchronous round count. Our modular implementation comprises five distinct sub-protocols: Committee Selection (CS), Prioritized Verifiable Consistent Broadcast (pVCBC), Propose-Recommend, Random Order/Permutation Generation, and Sequential-ABBA. The framework of the proposed protocol is illustrated in Figure 2.
3.2 Committee Selection
In the proposed pMVBA protocol, the CS sub-protocol plays a critical role in optimizing efficiency by reducing the communication complexity inherent in Byzantine agreement protocols. Rather than requiring all n parties to broadcast their proposals, our method strategically selects a subset of at least \(f + 1\) parties, based on the party ID and the current instance of the protocol, to perform this task. This selection ensures the protocol’s progress while maintaining its security properties, with the output being a set of \(f + 1\) parties designated as committee members for that specific instance.
To achieve this, the CS protocol utilizes a cryptographic coin-tossing scheme, inspired by Dumbo [12], to dynamically and randomly select \(\kappa = f + 1\) parties for each protocol instance. This selection process guarantees that at least one honest party is included in the committee, thereby preserving the integrity of the protocol.
The dynamic nature of party selection mitigates several risks, including adversarial corruption, ensuring fair participation across all parties and reducing the likelihood of starvation and Denial-of-Service (DoS) attacks. The randomness introduced by the cryptographic coin-tossing scheme is crucial in preventing adversary influence and securing the CS process.
The CS protocol is illustrated in Algorithm 2 and involves the following steps:
Generating Coin-Shares: Upon invocation, each party generates a coin-share \(\sigma _i\) and broadcasts it to all parties. The party then waits to receive \(f + 1\) coin-shares. (lines 4-5)
Verifying Coin-Shares: Upon receiving a coin-share from another party \(p_k\), the receiving party verifies the coin-share and adds it to the set \(\Sigma \) until \(f + 1\) valid shares are collected. (lines 8-10)
Selecting Parties: After collecting \(f + 1\) valid coin-shares, the CToss function is used to determine the selected subset of parties. (lines 6-7)
We have also provided the local variables different protocols are used in Algorithm 1.
Algorithm 1
Local variable initializations for party \(p_{id}\)
The CS protocol, as depicted in Figure 3a, ensures a secure and efficient selection of broadcasting parties, which significantly reduces the overall communication complexity of the pMVBA protocol. Definitions of the cryptographic coin-tossing functions (e.g., CShareVerify) are provided in Appendix A.4.
3.3 pVCBC
Following the selection of committee members through the Committee Selection protocol, each selected member must provide a verifiable proof of their proposal to ensure that it has been broadcast to at least \(f+1\) honest parties. Specifically, the input for this protocol includes the ID, requests, and the selected parties, while the output is a threshold-signature–a verifiable proof that the same requests have been sent to at least \(f+1\) honest parties. This proof is crucial for maintaining the integrity and consistency of the protocol, as it verifies that the proposal has been correctly disseminated among the parties. Traditionally, the Verifiable Consistent Broadcast (VCBC) protocol is used to generate such proofs, enabling every party to produce a verifiable record of their broadcast proposals. The definition of verifiability and the VCBC protocol itself are detailed in Appendix A.1. However, since our protocol restricts broadcasting to only the selected committee members, we utilize a slightly modified version of the VCBC protocol, which we term pVCBC (Prioritized Verifiable Consistent Broadcast).
The pVCBC protocol aligns with the selective broadcasting approach from the Committee Selection process. This adaptation ensures that when a party receives verifiable proof from another, there’s no need to verify its origin from a selected committee member, as the protocol inherently guarantees this (Since only the selected committee members’ can generate verifiable proof). The pVCBC protocol’s construction is detailed in Algorithm 3, and an illustration is provided in Figure 3b, visually representing its interactions and verification steps as a critical component of the overall pMVBA protocol.
Construction of the pVCBC
Upon invocation of the pVCBC protocol, a party sends (ID, requests) to the parties. (lines 03).
Upon receiving a message (requests) from a party \(p_j\), a party checks whether the sender is a selected party. If the sender is a selected party, the party adds its signature share (\(sign-share\)) to the message, resulting in \(\sigma \). The party then replies with \(\langle requests, \sigma _{id} \rangle \) to the sender (lines 11-14).
Upon receiving a signature share \(\sigma _k\) from a party \(p_k\), a selected party adds the signature share \(\sigma _k\) to its set \(\Sigma \) (lines 07 - 09).
A selected party waits for \(\langle n-f \rangle \) valid signature shares. Upon receiving \( n-f \) signature shares, the party combines them to generate a threshold signature \(\rho \) (proof that the party has sent the same request to at least \( f+1 \) honest parties) and returns \(\rho \) to the caller (line 05).
In the pMVBA protocol, the Propose-Recommend step replaces the traditional commit step found in the classical MVBA protocol. This shift is central to enhancing the protocol’s efficiency by significantly reducing complexity. While the classic commit step involves collecting \(n - f\) verifiable proofs and creating an array of length \(n\), our recommend step simplifies the process by broadcasting verifiable proofs directly. The propose step remains largely similar to the one in the classic protocol, but with a key difference: only the selected parties, as determined by the CS process, are responsible for proposing their requests. The input for this step includes a proposal and a threshold-signature, but it does not produce any direct output.
The recommend step then follows, where the input consists of the proposal and the threshold-signature. The output of this step is a list of threshold-signatures (collected from the \(n-f\) recommendation message), ensuring that at least one verifiable proof reaches the majority of parties. This process is critical for moving the protocol towards an agreement.
The recommend step involves the following key actions:
Initialization: A party initializes an empty set \(\Sigma \). (line 2)
Broadcast Recommendation: A party creates a recommendation message and broadcasts it to all parties. (line 5)
Recommendation Collection: Upon receiving a recommendation, a party verifies the threshold-signature and instance. If valid, the party adds the proposal and \(\sigma \) to its set \(\Sigma \). (lines 10-13)
A party waits for \(n - f\) recommendation messages before proceeding. (line 07-08)
The detailed SCR (Send, Collect, Recommend) protocol is shown in Algorithm 4, which formalizes the steps involved in the recommend process.
Following the Propose-Recommend step, the next crucial phase in the pMVBA protocol is to determine the order in which the selected parties will proceed. The purpose of this Random Order step is to generate a random permutation of the selected parties, ensuring that the process remains fair and secure. This step is particularly important for preventing adversaries from manipulating the message delivery order, which could potentially increase the number of asynchronous rounds required to reach an agreement.
The output of this step is a permutation of the selected parties. The random order is generated after the distribution and receipt of the threshold number of recommendation messages, ensuring the process is not vulnerable to adversarial interference. The Random Order protocol involves the following steps :
Coin-Share Generation: Upon invocation of the RandomOrder protocol, a party generates a coin-share \(\sigma _{id}\) for the current instance and broadcasts it to every party. The party then waits for \(2f+1\) coin-shares. (lines 03-06)
Coin-Share Verification: When a party receives a coin-share from another party \(p_k\) for the first time, it verifies the coin-share, ensuring it is from \(p_k\), and accumulates the coin-share in the set \(\Sigma \). The party continues to respond to coin-shares until it has received \(2f+1\) valid shares. (lines 09-11)
Permutation Generation: Once \(2f+1\) valid coin-shares have been received, the party uses its CToss function and the collected coin-shares to generate a permutation of the n parties and filtered the selected parties and return. (line 07 of Algorithm 5).
This process is formalized in the pseudocode for the random-order generation protocol, as shown in Algorithm 5. By generating a random order of the selected parties, this step ensures that the protocol remains robust against adversarial manipulation and maintains the efficiency of the agreement process.
3.6 Sequential-ABBA
The final phase in the pMVBA protocol is the Sequential-ABBA protocol, which is responsible for reaching an agreement on one of the proposals submitted by the selected parties. Building on the random order generated in the previous step, the Sequential-ABBA protocol runs an agreement loop that systematically evaluates each selected party’s proposal. The input to this protocol consists of the permutation list generated in the Random Order step and the list of recommendations obtained from the Propose-Recommend step. The output is the final proposal agreed upon by the parties.
In Sequential-ABBA, we employ an asynchronous binary Byzantine agreement protocol that is biased towards 1, allowing for efficient agreement on proposals. The protocol iterates through the permutation list, running the agreement process for each selected party until an agreement is achieved on a single proposal. This approach ensures that the final decision is reached in a manner that is both robust and fair, in line with the protocol’s overall design. The detailed construction of the Sequential-ABBA protocol is provided below, where the specific steps and mechanisms are described. This protocol serves as the culminating step in the pMVBA process, ensuring that all parties converge on a single, agreed-upon proposal, thus completing the agreement procedure.
Construction of the Sequential-ABBA
Since the Sequential-ABBA protocol guarantees that the parties will eventually reach an agreement on one of the selected party’s proposals, the protocol runs a loop for the selected parties until it agrees on a valid proposal. The pseudocode of the Sequential-ABBA protocol is given in Algorithm 6, and a step-by-step description is provided below:
The Sequential-ABBA protocol takes two arguments: (i) PermutationList, the permutation of the selected parties, and (ii) RecommendationList, the list of verifiable proofs and proposals the party has received (line 1).
Upon invocation of the protocol, a party declares two variables: (i) index, an index number to access the selected parties one by one from the array PermutationList, and (ii) bit, initially set to zero to indicate that the parties have not reached any agreement (lines 2-3).
While loop: Parties are chosen one after another according to the permutation PermutationList of \(\{1, \ldots , f+1\}\). Let index denote the index of the party selected in the current loop (the selected party \(p_{index}\) is called the candidate). Each party \(p_i\) follows these steps for the candidate \(p_{index}\) (lines 4-25):
Broadcasts a VOTE message to all parties containing \(u_{index} = 1\) if party \(p_i\) has received \(p_{index}\)’s proposal and verifiable proof (including the proposal in the VOTE or from RecommendationList), and \(u_{index} = 0\) otherwise. (lines 12-18)
Waits for \(\langle n-f \rangle \)VOTE messages (line 19) but does not count votes indicating \(u_{index} = 1\) unless a valid proposal from the party \(p_{id}\) has been received–either directly or included in the VOTE message (lines 21 - 22).
Runs a binary asynchronous Byzantine agreement biased towards 1 (see Algorithm 8) to determine whether \(p_{index}\) has properly broadcast a valid proposal. Vote 1 if \(p_i\) has received a valid proposal from \(p_{index}\) through RecommendationList and add the protocol message that completes the verifiable broadcast of \(p_{index}\)’s proposal to validate this vote. Otherwise, if \(p_i\) has received \(n-f\)VOTE messages containing \(u_{index} = 0\), then vote 0; no additional information is needed. If the agreement loop decides 1, exit the loop. (lines 21-25)
Upon reaching an agreement, if the proposal is empty, then use the threshold signature \(\rho \) to get the proposal from the selected party and return the proposal. (lines 26-28)
Upon receiving \(\langle ID, VOTE, party, u_{index}, m \rangle \), a party checks whether \(u_{index'} = 1\). If it receives \(u_{index'} = 1\), then it assigns \(m_{index} = m\). (lines 29-33)
The pMVBA protocol achieves an agreement in a Byzantine environment through a sequence of interconnected steps. The process begins with the Committee Selection (CS) protocol, where each party dynamically and randomly selects committee members (Algorithm 7, line 02). Following this, the selected parties broadcast their proposals using the Prioritized Verifiable Consistent Broadcast (pVCBC) protocol, ensuring that their broadcasts are verifiable (Algorithm 7, line 05). After the proposals are broadcast, the parties proceed with the Propose-Recommend phase, where verifiable proofs are shared, and recommendations are collected (Algorithm 7, lines 16-20). Upon receiving the necessary recommendations, a random order of the selected committee members is generated using a cryptographic coin-tossing scheme (Algorithm 7, line 10). Finally, the Sequential-ABBA protocol is executed, where the agreement process is run in the determined order until an agreement is reached on a proposal (Algorithm 7, lines 12-13). Each of these steps ensures the protocol operates efficiently and securely, even in the presence of Byzantine faults.
4 Evaluation and Analysis of the Proposed Protocol
This section evaluates the proposed protocol based on its correctness and efficiency. Correctness ensures that the protocol maintains predefined security properties, making it resilient against adversarial attacks. Efficiency evaluates the protocol’s performance in terms of resource utilization and execution time. In this Section, we conduct extensive evaluation and analysis to answer:
• What are the formal proofs supporting the correctness of the pMVBA protocol? (\(\S \)4.1)
• How does the pMVBA protocol perform in terms of message complexity, communication complexity, and running time? (\(\S \)4.2)
• What are the behaviors and outcomes of the protocol under different network conditions and adversarial strategies? (\(\S \)4.3)
• How does the performance of the pMVBA protocol compare to other MVBA protocols in terms of key metrics? (\(\S \)4.4)
• How does pMVBA’s performance compare to atomic broadcast protocols in communication complexity? (\(\S \)B.1)
4.1 Proof of the Prioritized-MVBA Protocol
The correctness of the proposed protocol is critical to ensure that it adheres to the standard MVBA outcomes. Our goal is to prove that reducing the number of broadcasts does not compromise the protocol’s reliability. The output of a party’s request depends on the output of an ABBA instance within our protocol’s agreement loop, typically resulting in a value of 1. For the ABBA protocol to output 1, at least one honest party must input 1. We substantiate our protocol’s integrity by demonstrating that at least \(2f+1\) parties receive a verifiable proof of a party’s proposal, thus ensuring the necessary input for the ABBA instance.
Lemma 1
At least one party’s proposal reaches \(2f+1\) parties.
Proof
Since both the selected and non-selected parties can be non-responsive (Byzantine or system failure), and the adversary can coordinate with the Byzantine parties to schedule the message delivery in a way that slows down the agreement process. To prove the lemma, we parameterized the number of responsive parties among the selected parties and the total number of responsive parties among both selected and non-selected parties. Below is the parameterized statement.
Among the \(f+1\) selected parties, t parties are responsive where \(1\le t \le f+1\) , and among total n parties, m number of parties are responsive, where \( 2f+1 \le m \le n \). We provide three scenarios below, which are special cases of the above statement. We utilize the special cases to prove the parameterized statement. The special cases are three edge cases where the maximum number of selected and the non-selected parties can be responsive and non-responsive (case 1 and 2)
1.
Among \( f+1\) selected parties, f parties are non-responsive. (The maximum number of selected parties can be non-responsive)
2.
Selected \( f+1 \) parties are responsive, but other f non-selected parties are non-responsive. (The maximum number of non-selected parties can be non-responsive)
3.
Every party is responsive, including the selected \(f+1\) parties. (The maximum number of responsive parties)
We will first prove that the above three scenarios are a special case of the parameterized statement. These three cases are the lower and upper bound for t and m.
1.
For case 1, \(t=1\) (selected responsive parties) and \(m = t+2f = 2f+1\) (since f selected parties are non-responsive, the total number of responsive parties is \(2f+1\) that includes one responsive selected party). So it adheres to the requirements of the parameterized equation.
2.
For case 2, \(t=f+1\) and \(m = t+f = f+1+f\) (\(t = f+1\) selected responsive party and f non-seleted responsive party)\(= 2f+1\). So it also adheres to the requirements of the parameterized equation.
3.
For case 3, \(t=f+1\) and \(m=t+2f=3f+1=n\). Therefore, it also adheres to the requirements of the parameterized equation.
We prove that in every scenario, at least one party’s proposal reaches \(\langle 2f+1 \rangle \) parties. Since we have proved that cases (1), (2), and (3) are the special cases of a parameterized statement, we utilize these cases to prove that even in the scenario of parameterized statement, at least one proposal reaches \(2f+1\) parties.
1.
The proof proceeds by contradiction. Assume that among the \(f+1\) selected parties, f number of parties are nonresponsive, meaning only one party completes the pVCBC protocol and broadcasts the verifiable proof. Under the assumption that no proposal reaches more than 2f parties, the total number of recommendations would be:
Thus, the total number of recommendations is \((2f)(2f + 1)\), which is less than the required \((2f + 1)(2f + 1)\) recommendations.
This leads to a contradiction, as the protocol necessitates a sufficient number of recommendation messages to guarantee progress. Given that honest parties are obligated to provide the necessary number of recommendations, it follows that the proposal must have been received by a minimum of \(2f + 1\) parties. Consequently, the assumption that no proposal reaches more than 2f parties is incorrect, and at least one selected party’s proposal reaches \(2f + 1\) parties, thereby enabling the protocol to function as intended.
2.
We will prove by contradiction. Assume that no proposal reaches more than 2f parties.
Given the assumption that a minimum of \(2f+1\) parties are responsive and that \(f+1\) of these are chosen to propose, it follows that every party must receive a proposal during the propose step. Furthermore, no party commences the Sequential-ABBA protocol until it has received a minimum of \(2f+1\) recommendations and has secured the random order necessary to advance with Sequential-ABBA. This indicates that a total of \((2f+1)(2f+1)\) recommendation messages must be exchanged.
Assuming that no proposal is recommended to more than 2f parties and that \(f+1\) parties submit their requests, the total number of recommendations would be:
Therefore, the total number of recommendations is \((2f)(2f+1)\), which is lesser to the necessary \((2f+1)(2f+1)\) recommendation messages.
This results in a contradiction, as the protocol necessitates the transmission of sufficient recommendation messages for progress to occur. Honest parties are required to ensure the delivery of the necessary number of recommendations; thus, at least one proposal must be received by \(2f+1\) parties. Therefore, our assumption that no proposal reaches more than 2f parties is incorrect. Consequently, at least one party’s proposal successfully reaches \(2f+1\) parties, thereby ensuring the protocol can advance as necessary.
3.
The proof proceeds by contradiction. Assume that no proposal reaches more than 2f parties.
Since we assume that all parties are responsive, each party receives a proposal during the propose step. Additionally, no party engages in the Sequential-ABBA protocol until it has received a minimum of \(2f+1\) recommendations and acquired the random order required to execute the Sequential-ABBA protocol. Thus, the protocol requires a total of \((3f+1)(2f+1)\) recommendation messages.
If no proposal is recommended to more than 2f parties and \(f+1\) parties propose their requests, then the total number of recommendations must not exceed \((f+1)(2f)\). On average, a proposal from a selected party can receive recommendations from \(\frac{3f+1}{f+1}\) parties. Therefore, the total number of recommendations does not exceed:
Therefore, the total number of recommendations can be expressed as \((2f)(3f+1)\). The necessary quantity of recommendations is \((3f+1)(2f+1)\).
While a proposal can be recommended by more than one party, if it is assumed that all recommending parties recommend the same set of 2f parties, the condition of receiving \(2f+1\) recommendations remains unfulfilled. Consequently, for the protocol to advance, it is essential that the honest parties broadcast a sufficient number of recommendation messages, which the adversary will ultimately deliver.
Therefore, a minimum of one proposal must be communicated to \(2f+1\) parties. This contradicts the initial assumption; therefore, at least one party’s proposal has to reach \(2f+1\) parties, thereby ensuring the protocol’s advancement.
We prove that in every scenario, at least one party’s proposal has been shared to \(\langle 2f+1 \rangle \) parties. Having shown that cases (1), (2), and (3) are particular instances of the general parameterized scenario, the proof of these specific cases allow us to extend the result to the parameterized scenario.
In the three scenarios analyzed, it is evident that with m responsive parties, the total number of recommendations are \(m (2f+1)\). If t selected parties are responsive, the total number of recommendations can be represented as \(t ( 2f) ( \frac{m}{t})\). In this context, (t) (2f) indicates that the proposals from each of the t selected parties can reach a maximum of 2f parties. Meanwhile, \(\frac{m}{t}\) denotes the average number of parties that each selected party’s proposal can reach.
Therefore, we establish the subsequent relationship:
This inequality confirms that the number of recommendations from the selected parties is less than the required total number of recommendations, proving that at least one party’s proposal must reach \(2f+1\) parties, ensuring protocol progress. \(\square \)
This lemma ensures that if \(2f+1\) number of parties receive verifiable proof, at least one honest party will input 1 to the ABBA instance, ensuring the protocol reaches an agreement on 1.
Lemma 2
Without any permutation, the adversary can cause at most \(f+1\) iterations of the agreement loop in the Sequential-ABBA protocol.
Proof
Since only \(f+1\) parties are selected, the number of iterations is bounded above by \(f+1\). By Lemma 1, at least one verifiable proof is delivered to \(f+1\) honest parties, which guarantees that the protocol reaches agreement on at least one party’s proposal. We therefore analyze the worst case in which the protocol requires exactly \(f+1\) iterations. If the ABBA execution order of the selected parties is known in advance, an adaptive adversary can schedule message deliveries so that only the proposal of the last party in that order attains recommendations from \(2f+1\) number of parties. Consequently, for all earlier selected parties, less than the threshold number of parties cast \(vote=1\) and the instance decides 0; for the final selected party, at least \(f+1\) honest parties cast \(vote = 1\) and the instance decides 1. . \(\square \)
Lemma 3
Let \(\overline{A} \subseteq \{1, 2,..., f+1\}\) be the set of selected parties for which at least \(f+1\) honest parties receive the verifiable proof, and let \(\Pi \) be a random permutation of the \(f+1\) selected parties. Then, except with negligible probability:
For every party \(p \in \overline{A}\), the ABBA protocol on ID|p will decide 1.
\(|\overline{A}| \ge 1\).
There exists a constant \(\beta > 1\) such that for all \(t \ge 1\), \(Pr[\Pi [1] \notin \overline{A} \wedge \Pi [2] \notin \overline{A} \wedge ... \wedge \Pi [t] \notin \overline{A}] \le \beta ^{-t}\).
Proof
The binary agreement protocol biased towards 1 decides 0 if the honest parties input 0. From the Sequential-ABBA protocol, each party must receive \(\langle n-f \rangle \)\(vote=0\) messages in order to input 0 to an ABBA instance and to decide 0. However, from Lemma 1 at least \(\langle f+1 \rangle \) honest parties receive at least one verifiable proof from a selected party p, then it is not the case for the party \(p\in \overline{A}\). This proves the first claim.
To prove the second claim, we refer to the two special cases of Lemma 1. In case 1, one selected party is responsive and every party receives the verifiable proof of that selected party; therefore, \(|\overline{A}| = 1\). For case 2, every party receives a recommendation for each selected party. Therefore, each selected party’s verifiable proof reaches \(2f+1\) parties, thus \(|\overline{A}| = f+1\). Since Lemma 1 proves that at least one party’s proposal reaches \(2f+1\) parties, it generalizes the claim \(|\overline{A}| \ge 1\).
The third claim follows now because \(|\overline{A}|\) is at least a constant fraction of \(f+1\) and thus, there is a constant \(\beta > 1 \) such that \(Pr[\Pi (i)) \notin \overline{A}] \le \frac{1}{\beta }\) for all \(1 \le i \le t\). Since the probability of the t first elements of \(\Pi \) jointly satisfying the condition is no larger than for t independently and uniformly chosen values, we obtain \(Pr[\Pi [1] \notin \overline{A} \wedge \Pi [2] \notin \overline{A} \wedge .... \wedge \Pi [t] \notin \overline{A}] \le \beta ^{-t}\)1. \(\square \)
Theorem 1
Given a protocol for biased binary Byzantine agreement and a protocol for verifiable consistent broadcast, the Prioritized-MVBA protocol provides multi-valued validated Byzantine agreement for \(n = 3f + 1\) and invokes a constant expected number of binary Byzantine agreement protocols.
Agreement: If an honest party outputs a value v, then every honest party outputs the value v. From Lemma 1, at least one proposal reaches \(2f+1\) parties, and the ABBA protocol reaches an agreement on 1 if \(f+1\) honest parties input 1. The agreement property of the ABBA protocol ensures all honest parties output 1 for that ABBA instance and receive the same value v, which satisfies \(threshold-validate\langle v, \rho \rangle = true\).
Liveness: If honest parties participate and deliver messages, all honest parties decide. From Lemma 1, at least one proposal reaches \(2f+1\) parties, ensuring the ABBA protocol decides 1. Lemma 3 confirms the protocol reaches an agreement after a constant expected number of iterations.
External-validity: If an honest party terminates and decides on a value v, then \(externally-valid\langle v, \rho \rangle = true\). The validity of the ABBA protocol ensures at least one honest party inputs 1 to the ABBA instance, meaning the honest party received a valid \(threshold-signature\)\(\rho \) for v.
Integrity: If honest parties decide on a value v, then v was proposed by a party. The ABBA protocol returns 1 if at least one honest party inputs 1, which requires a valid \(threshold-signature\)\(\rho \). Honest parties reply with \(sign-shares\) only if a value v is proposed, ensuring v was proposed by a party. \(\square \)
4.2 Efficiency Analysis
The efficiency of a Byzantine Agreement (BA) protocol depends on message complexity, communication complexity, and running time. We analyze the proposed protocol’s efficiency by examining its sub-components: the pVCBC sub-protocol, committee-selection and permutation generation, propose-recommend steps, and the Sequential-ABBA sub-protocol.
Running Time:
Each sub-protocol and step, except for Sequential-ABBA, has a constant running time. The running time of the proposed protocol is dominated by the Sequential-ABBA sub-protocol. The Sequential-ABBA sub-protocol runs the ABBA protocol biased towards 1 in an expected constant number of times (Algorithm 6 takes a permutation list of the selected parties as an argument and iterates over that list). Since we take a permutation of the selected parties (see Algorithm 5 line 19-24), the probability of choosing a selected party is an expected constant number. The ABBA protocol also has an expected constant number of asynchronous rounds. Therefore, the running time of the protocol is an expected constant number.
Message Complexity:
In all sub-protocols and steps, except for pVCBC and propose steps, each party communicates with all other parties. Every party transmit O(1) information to all other parties (See line 8 of Algorithm 2, line 6 of Algorithm 4, lines 14 of Algorithm 7, lines 3, 14, and 22 of Algorithm 5, lines 16 and 18 of Algorithm 6. Each of the broadcasts sends O(1) information). Since n parties send O(1) information to the n parties, the message complexity is \(O(n^2)\). The expected message complexity of the Sequential-ABBA protocol is also \(O(n^2)\).
Communication Complexity:
The communication complexity of each sub-protocol and step is \(O(n^2(l + \lambda ))\), where l is the bit length of input values and \(\lambda \) is the bit length of the security parameter. To calculate the communication complexity we use the same approach as message complexity. We observe that in no step a party transmit O(n) information. Thus, the communication complexity is same as message complexity only includes the bit length of the input values and the bit length of the security parameters. The expected communication complexity of the Sequential-ABBA protocol is also \(O(n^2(l + \lambda ))\).
Worst-Case Analysis:
Table 1 presents the analysis of worst-case rounds for each base protocol. The results show that the worst-case rounds are consistent in terms of \(f\) across all the base protocols.
4.3 Case Study
The key contribution of this paper is the reduction in the number of requesting parties and the subsequent utilization of fewer broadcasts to eliminate the expensive sub-components of the classic MVBA protocol. The main challenge is to provide sufficient information to the parties to maintain the protocol’s progress while removing the costly elements. It is crucial to ensure that at least one selected party’s proposal reaches at least \(2f+1\) parties. This is achieved through the pVCBC step and the propose-recommend step. To illustrate the protocol’s effectiveness, we present a case study in two parts. Section 4.3.1 demonstrates how the protocol achieves the desired properties with the minimum number of nodes a system can have. To further clarify that the protocol can maintain these properties with a larger number of nodes, Section 4.3.2 provides a case study using charts for a system with three times the number of faulty nodes.
4.3.1 Message Flow in Different Stages
In an asynchronous network, the presence of a faulty node and the adversary’s ability to manipulate message delivery can delay the agreement process. This section shows how a faulty party can affect message delivery patterns and how the adversary can delay specific messages to prevent a node’s proposal from reaching the majority. Despite these challenges, the goal is to ensure that nodes can still reach an agreement on a party’s proposal.
Figure 4a assumes no faulty nodes, with the adversary delivering messages uniformly, allowing the protocol to reach an agreement on the first try. Figure 4b considers a scenario where one node gets a threshold-signature (ts) early, or the adversary prioritizes one node’s ts delivery over others, preventing one selected node’s proposal from reaching the majority. Figure 5a assumes the selected node \(p_2\) is either faulty or completely isolated by the adversary, and Figure 5b assumes a non-selected node is faulty or isolated, positively impacting the ts delivery of the selected nodes.
In conclusion, the above figures collectively demonstrate that regardless of the message delivery pattern or the presence of faulty nodes, the protocol consistently achieves agreement, thereby proving its robustness and effectiveness.
4.3.2 Message Distribution for More Than One Faulty Node
For this study, we assume a total of \(n=3f+1=10\) parties, with \(f=3\) being faulty. This configuration allows us to explore various message distribution patterns. We require at least one party’s proposal to reach \(2f+1=7\) parties, with a total of \(f+1=4\) selected parties. We examine the impact of different numbers of faulty parties and message distribution patterns. In each figure, the top box indicates selected parties and the number of parties that can recommend the proposal to others (e.g., Party \(p_1\) can receive 3 recommendations for the first selected party (\(R_1\)), 3 for the second selected party (\(R_2\)), and 2 for the third selected party (\(R_3\)), totaling 7). The bottom box counts the number of recommendations received for each selected party (e.g., \(p_1\) receives a total of 7 \(R_1\) recommendations).
Figure 6 assumes no faulty nodes, with the adversary delivering messages uniformly, ensuring that every selected node’s proposal reaches the threshold number of parties. Figure 7 assumes three non-selected non-responding nodes, which also allows every selected node’s proposal to reach the threshold. Figure 8 assumes one honest selected node or the adversary delivering messages from that node, ensuring only the honest selected node’s proposal reaches the threshold. Figure 9 and Figure 10 show scenarios with two and three honest selected nodes, respectively, where their proposals reach the threshold. Figure 11 explores non-uniform message distribution, which may prevent some selected nodes’ proposals from reaching the threshold, but only when all selected nodes are active.
In conclusion, the above scenarios illustrate that the protocol can maintain its effectiveness and achieve agreement even with varying numbers of faulty nodes and different message distribution patterns.
4.4 Analysis of Communication Complexity and Resilience
This section evaluates our protocol’s performance by comparing its communication complexity with classic MVBA protocol and assessing its resilience, termination, and safety properties against committee-based protocols.
4.4.1 Comparison of Asynchronous Rounds in MVBA Protocols
We compare the asynchronous rounds required to reach agreement in our pMVBA protocol with those in classic and traditional MVBA protocols, considering both best-case and worst-case scenarios. To determine the worst-case cost, we first calculate the best-case scenario, identify the concrete rounds, and then estimate the remaining rounds as average ABBA rounds, multiplying by \(f+1\). As shown in Table 1, Dumbo-MVBA requires the most rounds in the best-case scenario. In the worst-case, while all protocols require rounds proportional to \(f\), VABA struggles to guarantee agreement on a complete output after \(f+1\) instances, requiring 13 rounds per instance–twice as many as other protocols. Among existing MVBA protocols, pMVBA offers superior performance in communication complexity and asynchronous rounds. Although Speeding Dumbo achieves lower asynchronous rounds, it is an ACS protocol and cannot avoid the \(O(\lambda n^3 \log n)\) communication complexity.
Fig. 6
All selected parties complete their pVCBC and broadcast their proposals. All parties are non-Byzantine; therefore, all of them recommend their received proposal. Every party’s proposal reaches at least 7 parties
All selected parties complete their pVCBC and broadcast their proposals. Three non-selected faulty parties cannot recommend; consequently, a party receives recommendations for all selected parties. Therefore, all selected parties’ proposals reach at least 7 parties
All selected parties are Byzantine or non-responding except \(P_1\). The non-Byzantine party completes the pVCBC and proposes its requests. Since there is only one proposal, every party receives the same proposal, which is received by every non-Byzantine party. Therefore, the proposal reaches 7 parties
Two selected parties are non-Byzantine and complete the pVCBC protocol, proposing their proposals, which are received by every non-Byzantine party. Each selected party’s proposal reaches more than 7 parties
Three selected parties are non-Byzantine and complete the pVCBC protocol, proposing their proposals, which are received by every non-Byzantine party. Each selected party’s proposal reaches more than 7 parties
This study tests whether non-uniform message distribution affects recommendation reception. Even with non-uniform distribution, at least half of the selected parties’ proposals reach 7 parties
4.4.2 Comparison of communication complexity with MVBA protocols.
Our work focuses on the first polynomial-time asynchronous Byzantine agreement protocol and removes its expensive sub-component. We compare our work with the classic and traditional MVBA protocols, as highlighted in Table 2. Our techniques differ from recent improvements in MVBA protocols, so we compare our protocol with the classic protocol and the following improvement. Our protocol differs from the Cachin-MVBA [21] in communication complexity. VABA [4] is a view-based protocol where each view is a complete protocol execution. VABA does not guarantee agreement in every instance, whereas our protocol ensures parties reach an agreement on a valid proposal in each instance.
We also present a comparison between our proposed protocol and the Dumbo-MVBA [13] protocols. The Dumbo-MVBA protocol is intended for large inputs. It uses the erasure code technique to remove the expensive term. The erasure code first disperses the message and then recovers the message at the end of the agreement, which is expensive in terms of latency and computation and is not worth it for small-size inputs. Our protocol achieves the desired communication complexity (removal of the \(O(n^3)\) term) without the utilization of information dispersal techniques (erasure code) and in one instantiation of the protocol. We can use the information dispersal technique like Dumbo-MVBA in our protocol to reduce the communication complexity to \(O(ln + \lambda n^2)\), but our protocol does not depend on the erasure code to remove the \(O(n^3)\) term. We use a committee to remove the \(O(n^3)\) term it takes only one message and the cryptographic computation. The cryptographic computation is similar to other parts of the protocol.
4.4.3 Comparison of Resilience, Termination, and Safety with Committee-Based Protocols
We compare our work with notable committee-based protocols, specifically focusing on resilience, termination, and safety properties. Table 3 highlights these comparisons. COINcidence [28] assumes a trusted setup and violates optimal resilience. It also does not guarantee termination and safety with high probability (whp). Algorand [29] assumes an untrusted setup, with resilience dependent on network conditions, and does not guarantee termination whp. The Dumbo [12] protocol uses a committee-based approach, but its committee-election protocol does not guarantee the selection of an honest party, thus failing to ensure agreement or termination. Our protocol achieves optimal resilience and guarantees both termination and safety, as our committee-election process ensures the selection of at least one honest party. This guarantees that the protocol can make progress and reach an agreement despite adversarial conditions.
Table 3
Comparison for performance metrics of the committee based protocols
In conclusion, we have compared our protocol with both the classical protocol and the committee-based protocol. Though our protocol differs from the atomic broadcast protocol in a number of proposals, we provide a comparison of our protocol with the atomic broadcast protocol in Appendix B.1.
5 Related Work
This section reviews key developments in Byzantine Agreement (BA) protocols, focusing on four areas: Byzantine Agreement in partially-synchronous networks, MVBA in asynchronous networks, Committee-Based Protocols, and Optimistic Fastlane Mechanisms.
Byzantine Agreement Protocols. Byzantine Agreement protocols are fundamental to fault-tolerant distributed computing, beginning with the Byzantine Generals Problem by Lamport et al. [30], which highlighted the challenges of achieving consensus in the presence of malicious nodes. Early protocols targeted synchronous networks but relied heavily on timing assumptions. The introduction of Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov [5] was a pivotal moment, providing a practical consensus protocol for partially-synchronous networks that inspired further advancements like HotStuff [9] and Tendermint [31].The FLP impossibility result [10] showed that deterministic BA is unattainable in asynchronous networks with a single fault, leading to the development of randomized protocols. Ben-Or’s protocol [32] was an early attempt, and recent works like HoneyBadgerBFT [6] and Dumbo [12] have since optimized Asynchronous Byzantine Agreement (ABA) for better throughput and latency.
Multi-Valued Byzantine Agreement Protocols. MVBA, introduced by Cachin et al. [18], extends BA to larger input spaces but suffers from high communication costs. Later protocols like VABA [4] and Dumbo-MVBA [13] aimed to reduce these costs using view-based approaches and erasure codes, respectively. However, these optimizations often increase complexity or require additional communication rounds. Our approach focuses on reducing communication overhead by limiting the number of broadcasting parties, while maintaining the protocol’s resilience.
Committee-Based Protocols. Committee-based approaches, exemplified by Algorand [29] and COINcidence [28], reduce communication complexity by involving a subset of parties in consensus. Unlike these, our protocol operates within a trusted setup and focuses on single-party requests, ensuring deterministic agreement. Our design contrasts with Dumbo [12], which aggregates multiple parties’ requests, and Beat [11], which combines various optimizations for performance. The recent approach of committee-based BFT protocol includes [33‐37].
Optimistic Fastlane Mechanisms. Optimistic mechanisms, such as those explored by Victor et al. [38] and Cachin et al. [39], operate under the assumption of partial synchrony, falling back to asynchronous protocols in adverse conditions. Recent efforts like Joleton [15] and Boltdumbo [16] continue this approach. Our work leverages asynchronous protocols during Byzantine faults, particularly in pessimistic paths, and focuses on single-party output, distinguishing it from DAG-based protocols like DAG-rider [17] and Aleph [40].
6 Conclusion
In this paper, we introduced pMVBA, a novel MVBA protocol designed to reduce the high communication complexity of classic the MVBA protocol. By incorporating a committee-based approach and the ABBA protocol, pMVBA reduces communication overhead while maintaining resilience and correctness. Key improvements include safety, termination, and reduced asynchronous rounds, achieved by dynamically selecting a subset of parties (\( f + 1 \)) to broadcast proposals, ensuring the inclusion of at least one honest party. The integration of the pVCBC protocol further enhances proposal broadcasting efficiency, and the recommend step replaces the commit step of classic protocol, minimizing communication exchanges. Our theoretical analysis shows that pMVBA achieves an expected constant asynchronous round count and optimal message complexity of \( O(n^2) \) [4, 13], making it suitable for large-scale decentralized applications. Future work will explore adaptive mechanisms for scalability, further optimizations, and extensive empirical evaluations to enhance the protocol’s robustness and applicability.
Declarations
Conflicts of Interest/Competing Interests
Financial interests: Author Nasit S. Sony receives salaries as a teaching assistant from the University of California, Merced. Author Xianzhong Ding receives salaries as a postdoctoral scholar from Lawrence Berkeley National Laboratory. Non-financial interests: none.
Competing interests
The authors declare no competing interests.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The Verifiable Consistent Broadcast, Asynchronous binary Byzantine agreement (ABBA), Threshold Signature Scheme, and Threshold Coin-Tossing are widely used in cryptographic and asynchronous Byzantine agreement protocol designs. Here, we have provided our own description, and it follows our earlier work [36] and is reused here for completeness. The technical contributions of this paper are distinct and focus on a multi-valued Byzantine agreement protocol.
Verifiable Consistent Broadcast
Definition 1
(Verfiability) A consistent broadcast protocol is called verifiable if the following holds, except with negligible probability: When an honest party has delivered m, then it can produce a single protocol message M that it may send to other parties such that any other honest party will deliver m, upon receiving M.
A protocol completes a verifiable consistent broadcast if it satisfies the following properties:
Validity. If an honest party sends m, then all honest parties eventually delivers m.
Consistency. If an honest party delivers m and another honest party delivers \(m'\), then \(m=m'\).
Integrity. Every honest party delivers at most one request. Moreover, if the sender \(p_s\) is honest, then the request was previously sent by \(p_s\).
Asynchronous binary Byzantine Agreement (ABBA)
The ABBA protocol guarantees the following properties. Additionally, the biased external validity property applies to the biased ABBA protocol.
Agreement. If an honest party outputs a bit b, then every honest party outputs the same bit b.
Termination. If all honest parties receive input, then all honest parties will output a bit b.
Validity. If any honest party outputs a bit b, then b was the input of at least one honest party.
Biased External Validity. If at least \(\langle f + 1 \rangle \) honest parties propose 1, then any honest party that terminates will decide on 1.
Threshold Signature Scheme
The \((f+1, n)\) non-interactive threshold signature scheme is a set of algorithms used by n parties, with up to f potentially faulty. The threshold signature scheme satisfies the following security requirements, except with negligible probabilities:
Non-forgeability. To output a valid signature, a party requires tsignature shares. Therefore, it is computationally infeasible for an adversary to produce a valid signature, as an adversary can corrupt up to f parties (\(f < t\)) and thus cannot generate enough signature shares to create a valid signature proof for a message.
Robustness. It is computationally infeasible for an adversary to produce t valid signature shares such that the output of the share combining algorithm is not a valid signature.
The scheme provides the following algorithms:
Key generation algorithm: KeySetup(\(\{0,1\}^\lambda , n, f+1) \rightarrow \{UPK, PK, SK\}\). Given a security parameter \(\lambda \), this algorithm generates a universal public key UPK, a vector of public keys \(PK:= (pk_1, pk_2, \ldots , pk_n)\), and a vector of secret keys \(SK:= (sk_1, sk_2, \ldots , sk_n)\).
Share signing algorithm: SigShare\(_{id}(sk_{id}, m) \rightarrow \sigma _{id}\). Given a message m and a secret key share \(sk_{id}\), this deterministic algorithm outputs a signature share \(\sigma _{id}\).
Share verification algorithm: VerifyShare\(_{id}(m, (id, \sigma _{id})) \)\( \rightarrow 0/1\). This algorithm takes three parameters as input: a message m, a signature share \(\sigma _i\), and the index id. It outputs 1 or 0 based on the validity of the signature share \(\sigma _{id}\) (whether \(\sigma _{id}\) was generated by \(p_{id}\) or not). The correctness property of the signing and verification algorithms requires that for a message m and party index id, \(\Pr [VerifyShare_{id}(m, (id, SigShare_{id}(sk_{id}, m))) {=} 1]\)\( = 1\).
Share combining algorithm: CombineShare\(_{id}(m, \{(id, \sigma _{id})\}_{id \in S}) \rightarrow \sigma / \perp \). This algorithm takes two inputs: a message m and a list of pairs \(\{(id, \sigma _{id})\}_{id \in S}\), where \(S \subseteq [n]\) and \(|S| = f+1\). It outputs either a signature \(\sigma \) for the message m or \(\perp \) if the list contains any invalid signature share \((id, \sigma _{id})\).
Signature verification algorithm: Verify\(_{id}(m, \sigma ) \rightarrow 0/1\). This algorithm takes two parameters: a message m and a signature \(\sigma \), and outputs a bit \(b \in \{0, 1\}\) based on the validity of the signature \(\sigma \). The correctness property of the combining and verification algorithms requires that for a message m, \(S \subseteq [n]\), and \(|S| = f+1\), \(\Pr [\text {Verify}_i(m, \text {Combine}_{id}(m, \{(id, \sigma _{id})\}_{id \in S})) = 1 \mid \forall id \in S, \text {VerifyShare}_{id}(m, (id, \sigma _{id})) = 1] = 1\).
Threshold Coin-Tossing
We assume a trusted third party has an unpredictable pseudo-random generator (PRG) \(G: R \rightarrow \{1, \ldots , n\}^s\), known only to the dealer. The generator takes a string \(r \in R\) as input and returns a set \(\{S_1, S_2, \ldots , S_s\}\) of size s, where \(1 \le S_{id} \le n\). Here, \(\{r_1, r_2, \ldots , r_n\} \in R\) are shares of a pseudorandom function F that maps the coin name C. The threshold coin-tossing scheme satisfies the following security requirements, except with negligible probabilities:
Pseudorandomness. The probability that an adversary can predict the output of F(C) is \(\frac{1}{2}\). The adversary interacts with the honest parties to collect coin-shares and waits for tcoin-shares, but to reveal the coin C and the bit b, the adversary requires at least \(\langle t-f\rangle \)coin-shares from the honest parties. If the adversary predicts a bit b, then the probability is \(\frac{1}{2}\) that \(F(C) = b\) (\(F(C) \in \{0, 1\}\)). Although the description is for single-bit outputs, it can be trivially modified to generate k-bit strings by using a k-bit hash function to compute the final value.
Robustness. It is computationally infeasible for an adversary to produce a coin C and t valid coin-shares of C such that the share-combine function does not output F(C).
The dealer provides a private function \(CShare_i\) to every party \(p_i\), and two public functions: CShareVerify and CToss. The private function \(CShare_i\) generates a share \(\sigma _i\) for the party \(p_i\). The public function CShareVerify can verify the share. The CToss function returns a unique and pseudorandom set given \(f+1\) validated coin shares. The following properties are satisfied except with negligible probability:
For each party \(id \in \{1, \ldots , n\}\) and for every string \(r_{id}\), \(CShareVerify(r_{id}, id, \sigma _{id}) = \text {true}\) if and only if \(\sigma _{id} = CShare_{id}(r_{id})\).
If \(p_{id}\) is honest, then it is impossible for the adversary to compute \(CShare_{id}(r_{id})\).
For every string \(r_{id}\), \(CToss(r, \Sigma )\) returns a set if and only if \(|\Sigma | \ge f+1\) and each \(\sigma \in \Sigma \) and \(CShareVerify(r_{id}, id, \sigma _{id}) = \text {true}\).
Appendix B Miscellaneous
Comparison with Atomic Broadcast Protocol
As discussed earlier, when the inputs of each party are nearly identical, outputting the requests of \(n-f\) parties is not a viable solution. This approach results in higher computational effort without increasing the number of accepted transactions. Table 4 provides a comparison of the communication complexity of our protocol with atomic broadcast protocols. Notably, no atomic broadcast protocol can eliminate the multiplication of \(O(n^3)\) terms. Additionally, atomic broadcast protocols require extra rounds of message exchanges. Here, we focus solely on the communication complexity.
Table 4
Comparison of the communication complexity with the atomic broadcast protocols
To maintain a message complexity of \(O(n^2)\), the classic MVBA protocol incorporates the Verifiable Consistent Broadcast (VCBC) protocol. Additionally, it introduces the concept of external validity, wherein an input is deemed valid if it satisfies certain criteria. The protocol operates as follows:
Each party utilizes the VCBC protocol to broadcast their request and generate a corresponding verifiable proof. Upon completion of this step, the party broadcasts both the verifiable proof and the request, providing evidence that the request has been broadcast to every other party.
Upon receiving verifiable proof from \(n-f\) parties, signaling the completion of the VCBC protocol by the threshold number of parties, a party can initiate the ABBA protocol. However, there exists the possibility that other parties have not received sufficient verifiable proof, or that the adversary manipulates the distribution of proofs in a manner that prevents the majority of ABBA instances from receiving adequate proof.
To address this, each party communicates with others by transmitting an n-bit array, indicating receipt of verifiable proof from \(n-f\) parties. Upon receipt of \(n-f\) verifiable proofs, a party generates a permutation of the parties and invokes ABBA instances based on the order of permutation, ensuring that the number of ABBA instances remains constant on average.
Appendix C Agreement protocol
Asynchronous Binary Byzantine Agreement (ABBA)
The ABBA protocol allows parties to agree on a single bit \(b \in \{0, 1\}\) [19, 41, 42]. We have adopted the ABBA protocol from [22], as given in Algorithm 8. The expected running time of the protocol is O(1), and it completes within O(k) rounds with probability \(1 - 2^{-k}\). Since the protocol uses a common coin, the total communication complexity becomes \(O(kn^2)\). For more information on how to realize a common coin from a threshold signature scheme, we refer interested readers to the [6].
Construction of the ABBA biased towards 1
We use the ABBA protocol from [22]. We optimize and changed the protocol for biased towards 1. The biases towards 1 property ensures that if at least one party input 1 in the pre-process step. The pseudocode of the ABBA protocol biased towards 1 is given in Algorithm 8, and a step-by-step description is provided below:
Pre-process step . Generate an \(\sigma _0\) share on the message and multi-cast the pre-process type message.
Collect \(2f+1\) proper pre-processing messages. (see (Algorithm 8)).
Repeat loop: Repeat the following steps 1-4 for rounds round = 1,2,3,...
Pre-Vote step. (see Algorithm 9)
\(*\) If round = 1, \(b=1\) if there is a pre-processing vote for 1 (biased towards 1, taking one vote instead of majority) else \(b=0\). (see lines 3-4).
\(*\) If round > 1, if there is a threshold signature on main-vote message from round-1 then decide and return. (see lines 18-20)
\(*\) Upon receiving main-vote for 0/1, update b and the justification. (see lines 12-17)
\(*\)\(b= F(ID, r-1)\), all the main-vote are abstain and the justification is the threshold signature of the abstain vote. (see lines 6-7)
\(*\) Produce signature-share on the message (ID, pre-vote, round, b) and multicast the message of the form pre-vote,round,b,justification, signature-share). (lines 9-11)
\(*\) If there are (2f+1) pre-votes for 0/1, \(v=0/1\) and the justification is the threshold-signature of the the sign-shares on pre-vote messages. (lines 5-7)
\(*\) If there are (2f+1) pre-votes for both 0 and 1, \(v=abstain\) and the justification is the two sign-shares from pre-vote 0 and pre-vote 1. (lines 9-10)
\(*\) Produce signature-share on the message (ID, pre-vote, round, v) and multi-cast the message of the form (main-vote,round,v,justification, signature-share) (lines 11-13)
Check for decision. (See Algorithm 11)
\(*\) Collect (2f+1) properly justified main-votes of the round round. (line 3)
\(*\) If these is no abstain vote, all main-votes for \(b\in \{0,1\}\), then decide the value b. Produce a threshold signature on the main votes’ sign-shares and multi-cast the threshold signatures to all parties and return. (lines 4-7)
Otherwise, go to Algorithm 11. line (11)
Common Coin. (See Algorithm 12)
\(*\) Generate a coin-share of the coin (ID, round) and send to all parties a message of the form (coin, round,coin-share). (lines 1-4)
\(*\) Collect (2f+1) shares of the coin (ID,round \(\sigma _k\)), and combine these shares to get the value \(F(ID, round) \in \{0,1\}\). (lines 5-6)
To prove the part of the Lemma 3, we have used the same technique of Lemma 9 from [21]. We also refer interested readers to Lemma 10 of the same paper for the pseudorandom generation.
Buterin, V.: A next-generation smart contract and decentralized application platform. In: White Paper (2014)
3.
Cachin, C., Vukolic, M.: Blockchain consensus protocols in the wild (keynote talk). In: 31st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria (2017)
4.
Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asynchronous byzantine agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, Toronto, Canada, pp. 879–888 (2019). https://doi.org/10.1145/3293611.33316
5.
Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI, pp. 656–666 (1999)
6.
Miller, A., Xia, Y., Croman, K.: Elaine Shi, and Dawn Song: The honey badger of BFT protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communication Security, CCS’16. ACM Press, New York, NY, USA (2016)
7.
Pass, R., Shi, E.: Rethinking large-scale consensus. (2017)
8.
Shrestha, N., Abraham, I., Nayak, K., Ren, L.: On the optimality of optimistic responsiveness. (2020)
9.
Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: Hotstuff: Bft consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 347–356 (2019). https://doi.org/10.1145/3293611.3331591
Duan, S., Reiter, M.K., Zhang, H.: Beat: asynchronous bft made practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS. ACM, Toronto, ON, Canada (2018)
12.
Guo, B., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo: Faster asynchronous bft protocols. In: Proceedings of the ACM Conference on Computer and Communications Security, pp. 803–818 (2020). https://doi.org/10.1145/3372297.3417262
13.
Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In: Proceedings of the 39th Symposium on Principles of Distributed Computing (2020)
14.
Guo, B., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Speeding dumbo: Pushing asynchronous bft closer to practice. Network and Distributed Systems Security (NDSS) Symposium, ??? (2022). https://doi.org/10.14722/ndss.2022.24385
15.
Gelashvili, R., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A., Xiang, Z.: Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. (2021). arXiv:2106.10362
16.
Lu, Y., Lu, Z., Tang, Q.: Bolt-dumbo transformer: Asynchronous consensus as fast as pipelined bft. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (2021). arXiv:2103.09425
17.
Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 165–175 (2021)
18.
Cachin, C., Kursawe, K., Lysyanskaya, A., Strobl, R.: Asynchronous verifiable secret sharing and proactive cryptosystems. In: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 88–97 (2002)
19.
Mostefaoui, A., Raynal, M.: Signature-free asynchronous byzantine systems: from multivalued to binary binary consensus with \(t < n/3\), \(o(n^3)\) messages, and constant time. Acta Inform. 54, 501–520 (2017)MathSciNetCrossRef
20.
Mostefaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous binary byzantine consensus with \(t < n/3\), \(o(n^2)\) messages, and \(o(1)\) expected time. J. ACM 62, 1–21 (2015)CrossRef
21.
Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and Efficient Asynchronous Broadcast Protocols. Cryptology ePrint Archive, Paper 2001/006 (2001). https://eprint.iacr.org/2001/006
22.
Cachin, C., Kursawe, K., Shoup, V.: Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. In: Journal of Cryptology (2000)
23.
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988). https://doi.org/10.1137/0217017MathSciNetCrossRef
24.
Libert, B., Joye, M., Yung, M.: Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. In: Theory of Computer Science, vol. 645, pp. 1–24 (2016)
25.
Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography. PKC ’03, pp. 31–46. Springer, Berlin, Heidelberg (2003)
26.
Kate, A., Goldberg, I.: Distributed key generation for the internet. In: IEEE International Conference on Distributed Computing Systems, pp. 119–128 (2009)
27.
Shoup, V.: Practical threshold signatures. In: Advances in Cryptology–EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000 Proceedings 19, pp. 207–220 (2000). Springer. https://link.springer.com/chapter/10.1007/3-540-45539-6_15
28.
Cohen, S., Keidar, I., Spiegelman, A.: Brief announcement: Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 175–177 (2020)
29.
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, pp. 51–68 (2017)
30.
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef
31.
Buchman, E.: Tendermint: Byzantine fault tolerance in the age of blockchains. PhD Thesis, University of Guelph (2014)
32.
Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 3 (1983)
33.
Sony, N.S.: An efficient validated asynchronous byzantine agreement protocol using committee. arXiv preprint arXiv:2501.00717 (2025)
34.
Sony, N.S., Ding, X.: A committee based optimal asynchronous byzantine agreement protocol w.p. 1. In: Proceedings of the 26th International Conference on Distributed Computing and Networking. ICDCN ’25, pp. 282–283. Association for Computing Machinery, New York, NY, USA (2025). https://doi.org/10.1145/3700838.3703660
35.
Sony, N.S.: An Approach to Optimizing the VABA Protocol Using \(\kappa \)-size Committee. arXiv preprint arXiv:2412.03789 (2024)
36.
Sony, N., Ding, X., Singhal, M.: Slim-ABC: An Optimized Atomic Broadcast Protocol. Int J Netw Distrib Comput 13, 27 (2025)CrossRef
Kursawe, K., Shoup, V.: Optimistic asynchronous atomic broadcast. In: International Colloquium on Automata, Languages, and Programming, pp. 204–215 (2005)
39.
Cachin, C., Kursawe, K., Lysyanskaya, A., Strobl, R.: Asynchronous verifiable secret sharing and proactive cryptosystems. In: Proceedings of the 9th ACM Conference on Computer and Communications Security. CCS ’02, pp. 88–97. Association for Computing Machinery, New York, NY, USA (2002). https://doi.org/10.1145/586110.586124
40.
Gagol, A., Lesniak, D., Straszak, D., Swietek, M.: Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. AFT ’19, pp. 214–228. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3318041.3355467
