Last year’s Association for Computing Machines (ACM)’s Conference in Vienna, Austria (CCS 2016 – the 23rd ACM Conference on Computer and Communications Security (Hofburg Palace Vienna, Austria / October 24-28, 2016)), hosted a list of good presentations and talks. Following from yesterday’s talk and paper reviewed of a scalable blockchain proposal ELASTICO, I will continue with this interesting list of talks and papers reviews.
Today’s talk and paper are from Andrew Miller & co about their Honey Badger Byzantine Fault-tolerant (BFT) protocol. In contrast with yesterday’s protocol about a scalable blockchain with synchronous assumptions, the Honey Badger start form an asynchronous BFT protocol. Miller & co demonstrate that the bandwidth limitations of current crytocurrencies and blockchains (allowing only a maximum of 7 tx/s) can be addressed by the asynchronicity of protocols like Honey Badger. Against the assumption of synchrony in other scalable proposals, the authors of Honey Badger claim that it is unrealistic to assume it in almost all practical purposes.
Timing assumptions considered harmful. Most existing Byzantine fault tolerant (BFT) systems, even those called “robust,” assume some variation of weak synchrony, where, roughly speaking, messages are guaranteed to be delivered after a certain bound ∆, but ∆ may be time-varying or unknown to the protocol designer. We argue that protocols based on timing assumptions are unsuitable for decentralized, cryptocurrency settings, where network links can be unreliable, network speeds change rapidly, and network delays may even be adversarially induced.
The current assumptions underlying current practical byzantine faut-tolerance (PBFT) is revealed to fail by constructing an adversarial intermittently synchronous network, and the limitations of throughput of current blockchain networks call for new approaches that deal specifically with the weak synchronicity problems. Furthermore a weak asynchronous protocols is also unsuited for cryptocurrencies applications:
First, the liveness properties of weakly synchronous protocols can fail completely when the expected timing assumptions are violated (e.g., due to a malicious network adversary). To demonstrate this, we explicitly construct an adversarial “intermittently synchronous” network that violates the assumptions, such that existing weakly synchronous protocols such as PBFT  would grind to a halt (Section 3).
Second, even when the weak synchrony assumptions are satis- fied in practice, weakly synchronous protocols degrade significantly in throughput when the underlying network is unpredictable. Ideally, we would like a protocol whose throughput closely tracks the network’s performance even under rapidly changing network conditions. Unfortunately, weakly asynchronous protocols require timeout parameters that are finicky to tune, especially in cryptocurrency application settings; and when the chosen timeout values are either too long or too short, throughput can be hampered. As a concrete example, we show that even when the weak synchrony assumptions are satisfied, such protocols are slow to recover from transient network partitions (Section 3).
Andrew Miller & co propose in the paper and in the lively, agreeable talk one new practical asynchronous BFT protocol that tries to tackle these issues:
The surprising success of cryptocurrencies has led to a surge of interest in deploying large-scale, highly robust, Byzantine fault tolerant (BFT) protocols for mission-critical applications, such as financial transactions. Although the conventional wisdom is to build atop a (weakly) synchronous protocol such as PBFT (or a variation thereof), such protocols rely critically on network timing assumptions, and only guarantee liveness when the network behaves as expected. We argue these protocols are ill-suited for this deployment scenario. We present an alternative, HoneyBadgerBFT, the first practical asynchronous BFT protocol, which guarantees liveness without making any timing assumptions.
We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and experimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experiments over Tor, without needing to tune any parameters. Unlike the alternatives, HoneyBadgerBFT simply does not care about the underlying network.
Practical asynchronous BFT
The prevailing wisdom normally assumes that asynchronous atomic broadcast protocols as impractical and inefficient. Miller & co refute this with a demonstration that is sound theoretically but also supported empirically:
We propose HoneyBadgerBFT, the first BFT atomic broadcast protocol to provide optimal asymptotic efficiency in the asynchronous setting. We therefore directly refute the prevailing wisdom that such protocols are necessarily impractical. We make significant efficiency improvements on the best prior-known asynchronous atomic broadcast protocol, due to Cachin et al. , which requires each node to transmit O(Nˆ2) bits for each committed transaction, substantially limiting its throughput for all but the smallest networks.
However, a naïve attempt to eliminate the redundancy compromises the fairness property, and allows for targeted censorship attacks. We invent a novel solution to overcome this problem by using threshold public key encryption to prevent these attacks.
The second cause is the use of a suboptimal instantiation of the Asynchronous Common Subset (ACS) subcomponent. We show how to efficiently instantiate ACS by combining existing but overlooked techniques: efficient reliable broadcast using erasure codes , and a reduction from ACS to reliable broadcast from the multi-party computation literature .
This approach is especially well suited for a cryptocurrency ecosystem, where the network bandwidth is a scarce resource, but the computation is relatively abundant. A new line of understanding: the cryptographic building blocks of public-key encryption are a cumbersome cost for classical byzantine fault-tolerant database settings, where the main goal is to minimize the latency in response time within a set of defined transaction of data. But with HoneyBadger it becomes an advantage with the implementation of a threshold public-key encryption scheme:
HoneyBadgerBFT’s design is optimized for a cryptocurrency like deployment scenario where network bandwidth is the scarce resource, but computation is relatively ample. This allows us to take advantage of cryptographic building blocks (in particular, threshold public-key encryption) that would be considered too expensive in a classical fault-tolerant database setting where the primary goal is to minimize response time even under contention.
Improving as the messages get delivered:
In an asynchronous network, messages are eventually delivered but no other timing assumption is made. Unlike existing weakly synchronous protocols where parameter tuning can be finicky, HoneyBadgerBFT does not care. Regardless of how network conditions fluctuate, HoneyBadgerBFT’s throughput always closely tracks the network’s available bandwidth. Imprecisely speaking, HoneyBadgerBFT eventually makes progress as long as messages eventually get delivered; moreover, it makes progress as soon as messages are delivered.
We formally prove the security and liveness of our HoneyBadgerBFT protocol, and show experimentally that it provides better throughput than the classical PBFT protocol  even in the optimistic case.
Ideal ecosystems: confederated crytpocurrencies and permissionless blockchains
The paper that supports the talk displayed below is an interesting read and academically rich from a computer science, distributed computing and financial technologies perspectives. The authors transparently provide us the two main ecosystems where Honey Badger might encounter its ideal playground: confederated cryptocurrencies and permissionless blockchains:
Confederation cryptocurrencies. The success of decentralized cryptocurrencies such as Bitcoin has inspired banks and financial institutions to inspect their transaction processing and settlement infrastructure with a new light. “Confederation cryptocurrency” is an oft-cited vision [24, 25, 47], where a conglomerate of financial institutions jointly contribute to a Byzantine agreement protocol to allow fast and robust settlement of transactions. Passions are running high that this approach will streamline today’s slow and clunky infrastructure for inter-bank settlement. As a result, several new open source projects aim to build a suitable BFT protocol for this setting, such as IBM’s Open Blockchain and the Hyperledger project . A confederation cryptocurrency would require a BFT protocol deployed over the wide-area network, possibly involving hundreds to thousands of consensus nodes. In this setting, enrollment can easily be controlled, such that the set of consensus nodes are known a priori — often referred to as the “permissioned” blockchain. Clearly HoneyBadgerBFT is a natural candidate for use in such confederation cryptocurrencies.
And the Honey Badger protocol would do well also under randomly selected committee, which yesterday’s paper and talk proposed as well, but under a synchronous assumption:
Applicability to permissionless blockchains. By contrast, decentralized cryptocurrencies such as Bitcoin and Ethereum opt for a “permissionless” blockchain, where enrollment is open to anyone, and nodes may join and leave dynamically and frequently. To achieve security in this setting, known consensus protocols rely on proofs-of-work to defeat Sybil attacks, and pay an enormous price in terms of throughput and latency, e.g., Bitcoin commits transactions every ∼ 10 min, and its throughput limited by 7 tx/sec even when the current block size is maximized. Several recent works have suggested the promising idea of leveraging either a slower, external blockchain such as Bitcoin or economic “proof-of-stake” assumptions involving the underlying currency itself [32, 32, 35, 37] to bootstrap faster BFT protocols, by selecting a random committee to perform BFT in every different epoch. These approaches promise to achieve the best of both worlds, security in an open enrollment, decentralized network, and the throughput and response time matching classical BFT protocols. Here too HoneyBadgerBFT is a natural choice since the randomly selected committee can be geographically heterogeneous.
The paper then goes on with the detailed description of the protocol, and as always The Information Age readers are highly encouraged to read it carefully. For the moment though, in this post, I will briefly sketch the algorithms and display the pseudocode featured within the paper. Below is the enjoyable talk by computer scientist Andrew Miller with a lively and clearly enthusiastic, but sober, voice.
A threshold encryption scheme TPKE is a cryptographic primitive that allows any party to encrypt a message to a master public key, such that the network nodes must work together to decrypt it. Once f +1 correct nodes compute and reveal decryption shares for a ciphertext, the plaintext can be recovered; until at least one correct node reveals its decryption share, the attacker learns nothing about the plaintext.
In our concrete instantiation, we use the threshold encryption scheme of Baek and Zheng . This scheme is also robust (as required by our protocol), which means that even for an adversarially generated ciphertext C, at most one plaintext (besides ⊥) can be recovered. Note that we assume TPKE.Dec effectively identifies invalid decryption shares among the inputs.
The atomic broadcast from an ACS (Asynchronous Common Subset) instance is then fully detailed with the choice of a batching policy. It is claimed a scalable efficient broadcast with a randomized transaction selection from the queue proposed to each node. The Morning Paper blog analyzed this set up, and The Information Age recommends its reading.
The efficient instantiation of the ACS is accomplished by a so-called reliable broadcast (RBC) algorithm:
The video of the talk
Authors: Andrew Miller (University of Maryland), Yu Xia (Tsinghua University), Kyle Croman, Elaine Shi (Cornell University) and Dawn Song (University of California) presented at CCS 2016 – the 23rd ACM Conference on Computer and Communications Security (Hofburg Palace Vienna, Austria / October 24-28, 2016) – organized by SBA Research
featured image: CCS 2016 – The Honey Badger of BFT Protocols