Probabilistic Byzantine Fault Tolerance (Extended Version)
2405.04606
0
0
Abstract
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.
Create account to get full access
Overview
- Presents a probabilistic approach to Byzantine fault-tolerant consensus
- Aims to achieve consensus with high probability even in the presence of Byzantine faults
- Introduces a new <a href="https://aimodels.fyi/papers/arxiv/asymmetric-distributed-trust">asymmetric distributed trust model</a> and a probabilistic consensus protocol
Plain English Explanation
This research paper discusses a new way to achieve consensus, even when some participants in a distributed system are behaving maliciously or unreliably (known as Byzantine faults). The traditional approach to Byzantine fault tolerance relies on a strict quorum of honest participants to make decisions. Instead, this paper proposes a probabilistic approach that can reach consensus with high probability, even if some participants are untrustworthy.
The key innovation is a new trust model where participants have <a href="https://aimodels.fyi/papers/arxiv/role-confidence-trust-based-resilient-consensus-extended">asymmetric levels of trust</a>. This means that some participants are more trusted than others, based on their past behavior and reputation. The protocol then uses this trust information to make decisions, favoring more trusted participants. By relying on probabilities rather than strict quorums, the system can continue to make progress even when a minority of participants are faulty.
Technical Explanation
The paper introduces a <a href="https://aimodels.fyi/papers/arxiv/partial-synchrony-free-new-upper-bounds-byzantine">partially synchronous Byzantine fault-tolerant consensus protocol</a> that achieves consensus with high probability. It assumes an <a href="https://aimodels.fyi/papers/arxiv/nearly-optimal-consensus-tolerating-adaptive-omissions-why">adaptive adversary</a> who can corrupt up to a third of the participants.
The core of the protocol is a new <a href="https://aimodels.fyi/papers/arxiv/fault-tolerant-consensus-anonymous-dynamic-network">asymmetric distributed trust model</a>. Participants maintain a subjective trust value for each other, updated based on their past behavior. The protocol then uses these trust values to weight participants' votes, favoring more trusted nodes. This allows the system to make progress even when a minority of participants are faulty, as long as there is a sufficient number of honest, highly trusted nodes.
The paper analyzes the protocol's safety and liveness properties, showing that it achieves consensus with high probability. It also provides experimental results demonstrating the protocol's efficiency and robustness.
Critical Analysis
The paper presents a novel and promising approach to Byzantine fault-tolerant consensus. By incorporating a probabilistic element and an asymmetric trust model, it can achieve consensus in settings where traditional quorum-based protocols would fail.
However, the trust model introduced in the paper does raise some potential concerns. Maintaining accurate trust values for all participants could be challenging, especially in large, dynamic networks. There are also open questions about how to bootstrap trust in the system and handle Sybil attacks.
Additionally, the paper's analysis assumes a partially synchronous network model, which may not always align with real-world conditions. Further research is needed to understand how the protocol would perform in more asynchronous or adversarial network environments.
Overall, this paper makes an important contribution to the field of Byzantine fault tolerance, demonstrating the potential benefits of probabilistic approaches. But more work is needed to fully address the challenges and limitations of the proposed trust model and consensus protocol.
Conclusion
This research paper presents a novel probabilistic approach to Byzantine fault-tolerant consensus, which aims to achieve consensus with high probability even in the presence of malicious participants. By introducing an asymmetric distributed trust model, the protocol can make decisions that favor more trusted nodes, allowing the system to progress even when a minority of participants are faulty.
The technical details and analysis show this protocol to be a promising step forward in the field of Byzantine fault tolerance. However, the trust model and network assumptions still have room for further exploration and refinement. Continued research in this direction could lead to more robust and practical solutions for achieving consensus in the face of Byzantine failures.
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
📈
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
Knowledge Connectivity Requirements for Solving BFT Consensus with Unknown Participants and Fault Threshold (Extended Version)
Hasan Heydari, Robin Vassantlal, Alysson Bessani
0
0
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.
5/13/2024
Synchronous Consensus in Partial Synchrony
Ivan Klianev
0
0
We demonstrate a deterministic Byzantine consensus algorithm with synchronous operation in partial synchrony. It is naturally leaderless, tolerates any number of $ f<n/2 $ Byzantine processes with 2 rounds of exchange of originator-only signed messages, and terminates within a bounded interval of time. The algorithm is resilient to transient faults and asynchrony in a fraction of links with known size per number of faulty processes. It circumvents asynchronous and faulty links with 3-hop epidemic dissemination. Key finding: the resilience to asynchrony of links and the enabled by it leaderless consensus in partial synchrony ensure algorithm operation with simultaneous validity, safety, and bounded liveness.
5/16/2024