Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBolt-Dumbo Transformer: Asynchronous Consensus As Fast As Pipelined BFT
120
0
0.0
(
0
)
Added by
Zhenliang Lu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Byzantine fault-tolerant (BFT) protocols allow a group of replicas to come to a consensus even when some of the replicas are Byzantine faulty. There exist multiple BFT protocols to securely tolerate an optimal number of faults $t$ under different network settings. However, if the number of faults $f$ exceeds $t$ then security could be violated. In this paper we mathematically formalize the study of forensic support of BFT protocols: we aim to identify (with cryptographic integrity) as many of the malicious replicas as possible and in as a distributed manner as possible. Our main result is that forensic support of BFT protocols depends heavily on minor implementation details that do not affect the protocols security or complexity. Focusing on popular BFT protocols (PBFT, HotStuff, Algorand) we exactly characterize their forensic support, showing that there exist minor variants of each protocol for which the forensic supports vary widely. We show strong forensic support capability of LibraBFT, the consensus protocol of Diem cryptocurrency; our lightweight forensic module implemented on a Diem client is open-sourced and is under active consideration for deployment in Diem. Finally, we show that all secure BFT protocols designed for $2t+1$ replicas communicating over a synchronous network forensic support are inherently nonexistent; this impossibility result holds for all BFT protocols and even if one has access to the states of all replicas (including Byzantine ones).
For asynchronous binary agreement (ABA) with optimal resilience, prior private-setup free protocols (Cachin et al., CCS 2002; Kokoris-Kogias et al., CCS 2020) incur $O({lambda}n^4)$ bits and $O(n^3)$ messages; for asynchronous multi-valued agreement with external validity (VBA), Abraham et al. [2] very recently gave the first elegant construction with $O(n^3)$ messages, relying on public key infrastructure (PKI), but still costs $O({lambda} n^3 log n)$ bits. We for the first time close the remaining efficiency gap, i.e., reducing their communication to $O({lambda} n^3)$ bits on average. At the core of our design, we give a systematic treatment of reasonably fair common randomness: - We construct a reasonably fair common coin (Canetti and Rabin, STOC 1993) in the asynchronous setting with PKI instead of private setup, using only $O({lambda} n^3)$ bit and constant asynchronous rounds. The common coin protocol ensures that with at least 1/3 probability, all honest parties can output a common bit that is as if uniformly sampled, rendering a more efficient private-setup free ABA with expected $O({lambda} n^3)$ bit communication and constant running time. - More interestingly, we lift our reasonably fair common coin protocol to attain perfect agreement without incurring any extra factor in the asymptotic complexities, resulting in an efficient reasonably fair leader election primitive pluggable in all existing VBA protocols, thus reducing the communication of private-setup free VBA to expected $O({lambda} n^3)$ bits while preserving expected constant running time. - Along the way, we improve an important building block, asynchronous verifiable secret sharing by presenting a private-setup free implementation costing only $O({lambda} n^2)$ bits in the PKI setting. By contrast, prior art having the same complexity (Backes et al., CT-RSA 2013) has to rely on a private setup.
As an emerging technology, blockchain has achieved great success in numerous application scenarios, from intelligent healthcare to smart cities. However, a long-standing bottleneck hindering its further development is the massive resource consumption attributed to the distributed storage and computation methods. This makes blockchain suffer from insufficient performance and poor scalability. Here, we analyze the recent blockchain techniques and demonstrate that the potential of widely-adopted consensus-based scaling is seriously limited, especially in the current era when Moores law-based hardware scaling is about to end. We achieve this by developing an open-source benchmarking tool, called Prism, for investigating the key factors causing low resource efficiency and then discuss various topology and hardware innovations which could help to scale up blockchain. To the best of our knowledge, this is the first in-depth study that explores the next-generation scaling strategies by conducting large-scale and comprehensive benchmarking.
Blockchain has received tremendous attention in non-monetary applications including the Internet of Things (IoT) due to its salient features including decentralization, security, auditability, and anonymity. Most conventional blockchains rely on computationally expensive consensus algorithms, have limited throughput, and high transaction delays. In this paper, we propose tree-chain a scalable fast blockchain instantiation that introduces two levels of randomization among the validators: i) transaction level where the validator of each transaction is selected randomly based on the most significant characters of the hash function output (known as consensus code), and ii) blockchain level where validator is randomly allocated to a particular consensus code based on the hash of their public key. Tree-chain introduces parallel chain branches where each validator commits the corresponding transactions in a unique ledger. Implementation results show that tree-chain is runnable on low resource devices and incurs low processing overhead, achieving near real-time transaction settlement.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
