The security of large-scale blockchains relies on successful message flooding among the honest nodes, on an overlay topology. The crux of doing such flooding successfully is to have a robust and low-degree overlay topology: Robust means that even if the malicious parties all refuse to relay messages, the remaining honest parties should still constitute a connected component in the overlay network. Low-degree means that the nodes in the overlay network should have relatively small node degrees. The central challenge of designing such robust and low-degree topology is that in a permissionless blockchain context, the adversary is often bounded by resource (such as computation power or stake), rather than by the total number of malicious parties. We show that existing works of designing robust overlay against such resource-bounded adversaries all require excessively large node degrees (e.g., about 50000 or more under real-world settings). As our main contribution, we propose a novel LOR overlay topology that is robust against such resourcebounded adversaries. Our design is the very first such design with practically-feasible node degrees (e.g., several hundreds to about a thousand, under real-world settings with up to 100000 nodes).

Committees are extensively used in the designs of various Proof-of-Stake (PoS) blockchains. A committee is simply a randomly selected subset of the parties/nodes in the system. Ideally, the committee should i) be as small as possible, and ii) properly represent the entire system, in terms of the corruption ratio. Existing committee selection schemes all follow the principle of proportionality, which says that a committee member should neither over-represent nor under-represent the stake it holds.

The security of large-scale blockchains relies on successful message flooding among the honest parties, on an overlay topology. The crux of doing such flooding successfully is to have a robust and low-degree overlay topology: Robust means that even if the malicious parties all refuse to relay messages, the remaining honest parties should still constitute a connected component in the overlay network. Low-degree means that the nodes in the overlay network should have relatively small node degrees. The central challenge of designing such robust and low-degree topology is that in permissionless blockchain context, the adversary is often bounded by resource (such as computation power or stake), rather than by the total number of malicious parties. We show that existing works of designing robust overlay against such resource-bounded adversaries all require excessively large node degrees (e.g., 25000 or more under real-world settings). As our main contribution, we propose a novel LoR overlay topology that is robust against such resource-bounded adversaries. Our design is the very first such design with practically-feasible node degrees (e.g., 200 to 400 under real-world settings with up to 100000 nodes).

Permissionless blockchains commonly use resource challenges to defend against sybil attacks. For example, popular resource challenge designs include Proof-of-Work and Proof-of-Stake. It is well-known that simultaneously exploiting multiple resources can help make a permissionless blockchain more robust. For example, combining PoW and PoS can help to keep a blockchain secure, even when the attacker controls more than 50% of the computational power in the system. While there have been existing efforts for combining multiple resources in blockchains, they only provide partial solutions. Specifically, it is currently still unclear how to combine PoW and PoS, or multiple resources in general, to achieve optimal resilience . Here, by optimal resilience , we mean that the blockchain can tolerate every security region , unless that security region is proven to be impossible to tolerate. Existing designs are not able to achieve such optimal resilience. As our central contribution, this work proposes the novel design and formal security analysis of a blockchain protocol that combines PoS and PoW, which can be further generalized to multiple resources. Our blockchain is the very first blockchain that can achieve optimal resilience . Our design also overcomes a common tricky issue of PoW difficulty adjustment in previous designs. We have further implemented a research prototype of our blockchain design and experimentally demonstrated its good end-to-end performance.

Permissionless blockchains commonly use resource challenges to defend against sybil attacks. For example, popular resource challenge designs include Proof-of-Work and Proof-of-Stake. It is well-known that simultaneously exploiting multiple resources can help make a permissionless blockchain more robust. For example, combining PoW and PoS can help to keep a blockchain secure, even when the attacker controls more than 50% of the computational power in the system.While there have been existing efforts for combining multiple resources in blockchains, they only provide partial solutions. Specifically, it is currently still unclear how to combine PoW and PoS, or multiple resources in general, to achieve optimal resilience. Here by optimal resilience, we mean that the blockchain can tolerate every security region, unless that security region is proven to be impossible to tolerate. Existing designs are not able to achieve such optimal resilience.As our central contribution, this work proposes the novel design and formal security analysis of a blockchain protocol that combines PoS and PoW, which can be further generalized to multiple resources. Our blockchain is the very first blockchain that can achieve optimal resilience. Our design also overcomes a common tricky issue of PoW difficulty adjustment in previous designs. We have further implemented a research prototype of our blockchain design, and experimentally demonstrate its good end-to-end performance.

The robustness of a blockchain against the adversary is often characterized by the maximum fraction (fmax) of adversarial power that it can tolerate. While most existing blockchains can only tolerate ${f_{\max }} < \frac{1}{2}$ or lower, there are some blockchain systems that are able to tolerate a malicious majority, namely ${f_{\max }} \geq \frac{1}{2}$. A key price paid by such blockchains, however, is their large confirmation latency. This work aims to significantly reduce the confirmation latency in such blockchains, under the common case where the actual fraction f of adversarial power is relatively small. To this end, we propose a novel blockchain called Flint. Flint tolerates ${f_{\max }} \geq \frac{1}{2}$ and can give optimistic execution (i.e., fast confirmation) whenever f is relatively small. Our experiments show that the fast confirmation in Flint only takes a few minutes, as compared to several hours of confirmation latency in prior works.

Fault tolerance of a blockchain is often characterized by the fraction f of “adversarial power” that it can tolerate in the system. Despite the fast progress in blockchain designs in recent years, existing blockchain systems can still only tolerate f below 0.5. Can practically usable blockchains tolerate a malicious majority, i.e., f above 0.5? This work presents a positive answer to this question. We first note that the well-known impossibility of byzantine consensus for f above 0.5 does not carry over to blockchains. To tolerate f above 0.5, we use byzantine broadcast, instead of byzantine consensus, as the core of the blockchain. A major obstacle in doing so, however, is that the resulting blockchain may have extremely low throughput. To overcome this central technical challenge, we propose a novel byzantine broadcast protocol OverlayBB, that can tolerate f above 0.5 while achieving good throughput. Using OverlayBB as the core, we present the design, implementation, and evaluation of a novel Proof-of-Stake blockchain called BCube. BCube can tolerate a malicious majority, while achieving practically usable transaction throughput and confirmation latency in our experiments with 10000 nodes and under f=0.7. To our knowledge, BCube is the first blockchain that can achieve such properties.

This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined by an adversary. The adversary promises that in every T consecutive rounds, the T (potentially different) topologies in those T rounds contain a common connected subgraph that spans all nodes. Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max. Our algorithms are the first algorithms whose complexities do not contain an Ømega(N) term, under constant T values. Previous sublinear algorithms require significantly larger T values.

Many blockchain consensus protocols have been proposed recently to scale the throughput of a blockchain with available bandwidth. However, these protocols are becoming increasingly complex, making it more and more difficult to produce proofs of their security guarantees. We propose a novel permissionless blockchain protocol OHIE which explicitly aims for simplicity. OHIE composes as many parallel instances of Bitcoin's original (and simple) backbone protocol as needed to achieve excellent throughput. We formally prove the safety and liveness properties of OHIE. We demonstrate its performance with a prototype implementation and large-scale experiments with up to 50,000 nodes. In our experiments, OHIE achieves linear scaling with available bandwidth, providing about 4-10Mbps transaction throughput (under 8-20Mbps per-node available bandwidth configurations) and at least about 20x better decentralization over prior works.

In a sybil attack, an adversary creates many fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: nodes that fail to solve the puzzle in time will no longer be accepted by other nodes. However, a malicious node can behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes constitute the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). All existing view reconciliation protocols so far have a similar Θ(N) time complexity, with N being the number of honest nodes in the system. As this paper's main contribution, we propose a novel view reconciliation protocol whose time complexity is only Θ(ln N/ln ln N). To achieve such an exponential improvement, we aggressively exploit randomization. The hidden constant factor in the asymptotic complexity of our protocol, however, is considerably larger than in previous protocols. Concrete numerical comparisons show that our protocol is more suitable for large-scale systems, while existing protocols are better for smaller-scale systems.

In a sybil attack, an adversary creates a large number of fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: If a node fails to solve the puzzle in a timely fashion, it will no longer be accepted by other nodes. However, it is still possible for a malicious node to behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes should form the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). For example, in CRYPTO 2015, Andrychowicz and Dziembowski proposed a view reconciliation protocol with Θ(N) time complexity, with N being the number of honest nodes in the system. All existing view reconciliation protocols so far have a similar Θ(N) time complexity. As this paper's main contribution, we propose a novel view reconciliation protocol with a time complexity of only Θ([ln N/ln ln N]). To achieve such an exponential improvement, we aggressively exploit randomization.