Knowledge Connectivity Requirements for Solving BFT Consensus with Unknown Participants and Fault Threshold (Extended Version)
2405.06055
0
0
Abstract
Consensus stands as a fundamental building block for constructing reliable and fault-tolerant distributed services. The increasing demand for high-performance and scalable blockchain protocols has brought attention to solving consensus in scenarios where each participant joins the system knowing only a subset of participants. In such scenarios, the participants' initial knowledge about the existence of other participants can collectively be represented by a directed graph known as knowledge connectivity graph. The Byzantine Fault Tolerant Consensus with Unknown Participants (BFT-CUP) problem aims to solve consensus in those scenarios by identifying the necessary and sufficient conditions that the knowledge connectivity graphs must satisfy when a fault threshold is provided to all participants. This work extends BFT-CUP by eliminating the requirement to provide the fault threshold to the participants. We indeed address the problem of solving BFT consensus in settings where each participant initially knows a subset of participants, and although a fault threshold exists, no participant is provided with this information -- referred to as BFT Consensus with Unknown Participants and Fault Threshold (BFT-CUPFT). With this aim, we first demonstrate that the conditions for knowledge connectivity graphs identified by BFT-CUP are insufficient to solve BFT-CUPFT. Accordingly, we introduce a new type of knowledge connectivity graphs by determining the necessary and sufficient conditions they must satisfy to solve BFT-CUPFT. Furthermore, we design a protocol for solving BFT-CUPFT.
Create account to get full access
Overview
- Explores knowledge connectivity requirements for solving Byzantine Fault-Tolerant (BFT) consensus with unknown participants and fault threshold
- Proposes a new model for consensus with unknown participants and fault threshold
- Analyzes the theoretical limits of BFT consensus in this setting
Plain English Explanation
This paper examines the challenges of reaching agreement, or consensus, in a system where some participants may be unreliable or even actively trying to disrupt the process (known as Byzantine faults). The researchers focus on a scenario where the identities and number of faulty participants are unknown, which makes the problem even more complex.
To address this, the researchers propose a new model for consensus with unknown participants and fault threshold. Their model relies on the concept of "knowledge connectivity," which looks at how information flows between participants and how that affects the system's ability to reach consensus.
The key idea is that for the system to reliably reach consensus, there needs to be a certain level of "knowledge connectivity" - that is, the participants need to be able to share information and verify each other's actions to a sufficient degree. The paper analyzes the theoretical limits of what's possible in this type of setting, providing insights into the minimum requirements for achieving Byzantine Fault-Tolerant (BFT) consensus when the participants and fault thresholds are unknown.
This research has important implications for the design of blockchain and other distributed systems that need to reach consensus in the face of unreliable or malicious participants.
Technical Explanation
The paper begins by defining the problem of BFT consensus with unknown participants and fault threshold. In this setting, the system must reach agreement on a common decision, even when some of the participants are faulty or adversarial. However, the identities and number of faulty participants are not known in advance.
To model this, the researchers introduce the concept of "knowledge connectivity," which captures how information flows between participants and how that affects the system's ability to reach consensus. They define several key properties of knowledge connectivity, such as the "knowledge graph" that represents the information available to each participant.
The paper then analyzes the theoretical limits of what's possible in this setting, proving fundamental bounds on the knowledge connectivity required to solve BFT consensus. Specifically, they show that a certain level of "advice complexity" - the amount of information that needs to be shared between participants - is necessary for the system to reliably reach consensus.
The researchers also explore connections between this problem and other topics in distributed trust and resilient consensus, providing a unified framework for understanding the challenges of reaching agreement in the face of unknown faults.
Critical Analysis
The paper provides a rigorous theoretical analysis of the knowledge connectivity requirements for solving BFT consensus with unknown participants and fault threshold. This is an important contribution, as it helps establish the fundamental limits of what's possible in this challenging setting.
However, the paper focuses primarily on the theoretical aspects and does not delve into practical implementation details or empirical evaluations. While the theoretical insights are valuable, it would be helpful to see how these ideas could be applied in real-world distributed systems, such as blockchain networks.
Additionally, the paper does not address some potential limitations or edge cases, such as how the model might handle dynamic changes in the participant set or the impact of network delays and other real-world system constraints. Exploring these aspects could further strengthen the practical relevance of the research.
Overall, this paper represents a significant step forward in our understanding of the theoretical foundations of BFT consensus with unknown participants and fault threshold. Future work could build on these insights to develop more practical, deployable solutions for this important problem.
Conclusion
This paper presents a comprehensive analysis of the knowledge connectivity requirements for solving Byzantine Fault-Tolerant (BFT) consensus in a setting where the participants and fault threshold are unknown. By introducing the concept of "knowledge connectivity," the researchers have provided a rigorous theoretical framework for understanding the fundamental limits of what's possible in this challenging problem domain.
The insights from this work have important implications for the design of blockchain, distributed ledger, and other decentralized systems that need to reach agreement in the face of unreliable or adversarial participants. While the focus is primarily theoretical, the findings lay the groundwork for the development of more practical, deployable solutions in this area.
As the field of distributed systems continues to evolve, research like this that examines the core theoretical limits of consensus-building will be crucial for enabling the creation of secure, resilient, and scalable decentralized technologies that can withstand the challenges of the real world.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Probabilistic Byzantine Fault Tolerance (Extended Version)
Diogo Avel~as, Hasan Heydari, Eduardo Alchieri, Tobias Distler, Alysson Bessani
0
0
Consensus is a fundamental building block for constructing reliable and fault-tolerant distributed services. Many Byzantine fault-tolerant consensus protocols designed for partially synchronous systems adopt a pessimistic approach when dealing with adversaries, ensuring safety in a deterministic way even under the worst-case scenarios that adversaries can create. Following this approach typically results in either an increase in the message complexity (e.g., PBFT) or an increase in the number of communication steps (e.g., HotStuff). In practice, however, adversaries are not as powerful as the ones assumed by these protocols. Furthermore, it might suffice to ensure safety and liveness properties with high probability. In order to accommodate more realistic and optimistic adversaries and improve the scalability of the BFT consensus, we propose ProBFT (Probabilistic Byzantine Fault Tolerance). ProBFT is a leader-based probabilistic consensus protocol with a message complexity of $O(nsqrt{n})$ and an optimal number of communication steps that tolerates Byzantine faults in permissioned partially synchronous systems. It is built on top of well-known primitives, such as probabilistic Byzantine quorums and verifiable random functions. ProBFT guarantees safety and liveness with high probabilities even with faulty leaders, as long as a supermajority of replicas is correct, and using only a fraction of messages employed in PBFT (e.g., $20%$). We provide a detailed description of ProBFT's protocol and its analysis.
6/12/2024
📈
Towards Rational Consensus in Honest Majority
Varul Srivastava, Sujit Gujar
0
0
Distributed consensus protocols reach agreement among $n$ players in the presence of $f$ adversaries; different protocols support different values of $f$. Existing works study this problem for different adversary types (captured by threat models). There are three primary threat models: (i) Crash fault tolerance (CFT), (ii) Byzantine fault tolerance (BFT), and (iii) Rational fault tolerance (RFT), each more general than the previous. Agreement in repeated rounds on both (1) the proposed value in each round and (2) the ordering among agreed-upon values across multiple rounds is called Atomic BroadCast (ABC). ABC is more generalized than consensus and is employed in blockchains. This work studies ABC under the RFT threat model. We consider $t$ byzantine and $k$ rational adversaries among $n$ players. We also study different types of rational players based on their utility towards (1) liveness attack, (2) censorship or (3) disagreement (forking attack). We study the problem of ABC under this general threat model in partially-synchronous networks. We show (1) ABC is impossible for $n/3< (t+k) <n/2$ if rational players prefer liveness or censorship attacks and (2) the consensus protocol proposed by Ranchal-Pedrosa and Gramoli cannot be generalized to solve ABC due to insecure Nash equilibrium (resulting in disagreement). For ABC in partially synchronous network settings, we propose a novel protocol textsf{pRFT}(practical Rational Fault Tolerance). We show textsf{pRFT} achieves ABC if (a) rational players prefer only disagreement attacks and (b) $t < frac{n}{4}$ and $(t + k) < frac{n}{2}$. In textsf{pRFT}, we incorporate accountability (capturing deviating players) within the protocol by leveraging honest players. We also show that the message complexity of textsf{pRFT} is at par with the best consensus protocols that guarantee accountability.
5/14/2024
⚙️
CFT-Forensics: High-Performance Byzantine Accountability for Crash Fault Tolerant Protocols
Weizhao Tang, Peiyao Sheng, Ronghao Ni, Pronoy Roy, Xuechao Wang, Giulia Fanti, Pramod Viswanath
0
0
Crash fault tolerant (CFT) consensus algorithms are commonly used in scenarios where system components are trusted -- e.g., enterprise settings and government infrastructure. However, CFT consensus can be broken by even a single corrupt node. A desirable property in the face of such potential Byzantine faults is emph{accountability}: if a corrupt node breaks protocol and affects consensus safety, it should be possible to identify the culpable components with cryptographic integrity from the node states. Today, the best-known protocol for providing accountability to CFT protocols is called PeerReview; it essentially records a signed transcript of all messages sent during the CFT protocol. Because PeerReview is agnostic to the underlying CFT protocol, it incurs high communication and storage overhead. We propose CFT-Forensics, an accountability framework for CFT protocols. We show that for a special family of emph{forensics-compliant} CFT protocols (which includes widely-used CFT protocols like Raft and multi-Paxos), CFT-Forensics gives provable accountability guarantees. Under realistic deployment settings, we show theoretically that CFT-Forensics operates at a fraction of the cost of PeerReview. We subsequently instantiate CFT-Forensics for Raft, and implement Raft-Forensics as an extension to the popular nuRaft library. In extensive experiments, we demonstrate that Raft-Forensics adds low overhead to vanilla Raft. With 256 byte messages, Raft-Forensics achieves a peak throughput 87.8% of vanilla Raft at 46% higher latency ($+44$ ms). We finally integrate Raft-Forensics into the open-source central bank digital currency OpenCBDC, and show that in wide-area network experiments, Raft-Forensics achieves 97.8% of the throughput of Raft, with 14.5% higher latency ($+326$ ms).
6/4/2024
🏋️
Motorway: Seamless high speed BFT
Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, Natacha Crooks
0
0
Today's practical, high performance Byzantine Fault Tolerant (BFT) consensus protocols operate in the partial synchrony model. However, existing protocols are inefficient when deployments are indeed partially synchronous. They deliver either low latency during fault-free, synchronous periods (good intervals) or robust recovery from events that interrupt progress (blips). At one end, traditional, view-based BFT protocols optimize for latency during good intervals, but, when blips occur, can suffer from performance degradation (hangovers) that can last beyond the return of a good interval. At the other end, modern DAG-based BFT protocols recover more gracefully from blips, but exhibit lackluster latency during good intervals. To close the gap, this work presents Motorway, a novel high-throughput BFT protocol that offers both low latency and seamless recovery from blips. By combining a highly parallel asynchronous data dissemination layer with a low-latency, partially synchronous consensus mechanism, Motorway (i) avoids the hangovers incurred by traditional BFT protocols and (ii) matches the throughput of state of the art DAG-based BFT protocols while cutting their latency in half, matching the latency of traditional BFT protocols.
5/13/2024