Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTaiJi: Longest Chain Availability with BFT Fast Confirmation
126
0
0.0
(
0
)
Added by
Songze Li
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Most state machine replication protocols are either based on the 40-years-old Byzantine Fault Tolerance (BFT) theory or the more recent Nakamotos longest chain design. Longest chain protocols, designed originally in the Proof-of-Work (PoW) setting, are available under dynamic participation, but has probabilistic confirmation with long latency dependent on the security parameter. BFT protocols, designed for the permissioned setting, has fast deterministic confirmation, but assume a fixed number of nodes always online. We present a new construction which combines a longest chain protocol and a BFT protocol to get the best of both worlds. Using this construction, we design TaiJi, the first dynamically available PoW protocol which has almost deterministic confirmation with latency independent of the security parameter. In contrast to previous hybrid approaches which use a single longest chain to sample participants to run a BFT protocol, our native PoW construction uses many independent longest chains to sample propose actions and vote actions for the BFT protocol. This design enables TaiJi to inherit the full dynamic availability of Bitcoin, as well as its full unpredictability, making it secure against fully-adaptive adversaries with up to 50% of online hash power.
rate research
Read More
In the field of distributed consensus and blockchains, the synchronous communication model assumes that all messages between honest parties are delayed at most by a known constant $Delta$. Recent literature establishes that the longest-chain blockchain protocol is secure under the synchronous model. However, for a fixed mining rate, the security guarantees degrade with $Delta$. We analyze the performance of the longest-chain protocol under the assumption that the communication delays are random, independent, and identically distributed. This communication model allows for distributions with unbounded support and is a strict generalization of the synchronous model. We provide safety and liveness guarantees with simple, explicit bounds on the failure probabilities. These bounds hold for infinite-horizon executions and decay exponentially with the security parameter. In particular, we show that the longest-chain protocol has good security guarantees when delays are sporadically large and possibly unbounded, which is reflective of real-world network conditions.
Optimistic asynchronous atomic broadcast was proposed to improve the performance of asynchronous protocols while maintaining their liveness in unstable networks (Kursawe-Shoup, 2002; Ramasamy-Cachin, 2005). They used a faster deterministic protocol in the optimistic case when the network condition remains good, and can safely fallback to a pessimistic path running asynchronous atomic broadcast once the fast path fails to proceed. Unfortunately, besides that the pessimistic path is slow, existing fallback mechanisms directly use a heavy tool of asynchronous multi-valued validated Byzantine agreement (MVBA). When deployed on the open Internet, which could be fluctuating, the inefficient fallback may happen frequently thus the benefits of adding the optimistic path are eliminated. We give a generic framework for practical optimistic asynchronous atomic broadcast. A new abstraction of the optimistic case protocols, which can be instantiated easily, is presented. More importantly, it enables us to design a highly efficient fallback mechanism to handle the fast path failures. The resulting fallback replaces the cumbersome MVBA by a variant of simple binary agreement only. Besides a detailed security analysis, we also give concrete instantiations of our framework and implement them. Extensive experiments show that our new fallback mechanism adds minimal overhead, demonstrating that our framework can enjoy both the low latency of deterministic protocols and robust liveness of randomized asynchronous protocols in practice.
The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamotos longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamotos PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence.
Byzantine fault tolerant (BFT) consensus protocols are traditionally developed to support reliable distributed computing. For applications where the protocol participants are economic agents, recent works highlighted the importance of accountability: the ability to identify participants who provably violate the protocol. We propose to evaluate the security of an accountable protocol in terms of its liveness resilience, the minimum number of Byzantine nodes when liveness is violated, and its accountable safety resilience, the minimum number of accountable Byzantine nodes when safety is violated. We characterize the optimal tradeoffs between these two resiliences in different network environments, and identify an availability-accountability dilemma: in an environment with dynamic participation, no protocol can simultaneously be accountably-safe and live. We provide a resolution to this dilemma by constructing an optimally-resilient accountability gadget to checkpoint a longest chain protocol, such that the full ledger is live under dynamic participation and the checkpointed prefix ledger is accountable. Our accountability gadget construction is black-box and can use any BFT protocol which is accountable under static participation. Using HotStuff as the black box, we implemented our construction as a protocol for the Ethereum 2.0 beacon chain, and our Internet-scale experiments with more than 4000 nodes show that the protocol can achieve the required scalability and has better latency than the current solution Gasper, while having the advantage of being provably secure. To contrast, we demonstrate a new attack on Gasper.
An important feature of Proof-of-Work (PoW) blockchains is full dynamic availability, allowing miners to go online and offline while requiring only 50% of the online miners to be honest. Existing Proof-of-stake (PoS), Proof-of-Space and related protocols are able to achieve this property only partially, either putting the additional assumption that adversary nodes to be online from the beginning and no new adversary nodes come online afterwards, or use additional trust assumptions for newly joining nodes.We propose a new PoS protocol PoSAT which can provably achieve dynamic availability fully without any additional assumptions. The protocol is based on the longest chain and uses a Verifiable Delay Function for the block proposal lottery to provide an arrow of time. The security analysis of the protocol draws on the recently proposed technique of Nakamoto blocks as well as the theory of branching random walks. An additional feature of PoSAT is the complete unpredictability of who will get to propose a block next, even by the winner itself. This unpredictability is at the same level of PoW protocols, and is stronger than that of existing PoS protocols using Verifiable Random Functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
