Techniques for Enhancing Robustness of Permissionless Distributed Systems
Abstract:
Distributed systems are fundamental to the modern interconnected world. Within these systems, vast numbers of machines — from thousands to millions — collaboratively offer services. This collaboration results in impressive scalability, consistent 24x7 availability, and a global reach. As our dependence on these systems intensifies, the emphasis on security grows in tandem. Ensuring that these distributed services remain secure is pivotal for their continued development and widespread adoption. This thesis delves into enhancing the security of distributed systems in two parts.
The first part addresses the challenge of tolerating majority failure in permissionless distributed systems. A distinguishing feature of distributed systems is their resilience against Byzantine failures. In such failures, nodes don't merely break down; they actively become malicious, colluding with other compromised nodes to undermine the system. There is a clear separation in the design of systems tolerating more than half of all nodes undergoing Byzantine failure (i.e. majority failure) and those tolerating less than half. Tolerating more Byzantine failure is a desirable property, but it's also challenging to achieve in many distributed systems. For example, despite tremendous research efforts invested into blockchain systems in the past decade, they mostly improve other parts of the system, such as scalability and privacy. In contrast, in terms of security, there is no existing practical blockchain system can tolerate more than half of the nodes being malicious. Our research takes a significant step forward by introducing BCUBE. This is the first blockchain that stays practically usable and still endures majority failure. We've subjected BCUBE to rigorous formal analysis, confirming its security even under majority failure. Additionally, evaluations of BCUBE's implementation further validate its practical usability.
Our next work further builds upon BCUBE by improving their confirmation latency. Confirmation latency refers to the duration required for BCUBE to validate a transaction. Although BCUBE have made substantial progress in terms of practicality, their confirmation latency is still mediocre comparing to modern protocols that do not deal with majority failure. Our work creates a general framework to build Byzantine broadcast protocols that tolerate majority failure, while providing optimistic fast confirmation. Leveraging this framework, we derive a new Byzantine broadcast protocol FlintBB, and build a blockchain Flint with FlintBB. Flint doesn't just resist majority failure but also trims the typical confirmation latency.
In the second part, our attention turns to the defenses against Sybil attacks in permissionless systems. In a Sybil attack, an attacker generates a multitude of fake identities to get advantage and potentially fail the system. A prevalent defense strategy involves resource challenges. Here, establishing a new identity mandates a demonstration of resources, for example, computational power. However, current designs usually create significant resource waste during resource challenge. A notable instance is Bitcoin's proof-of-work, which consumes electricity comparable to entire nations, primarily for Sybil defense. Our research proposes an innovative design, Selfied, which builds Sybil defense on in-protocol resources consumption — specifically, bandwidth. By doing so, Selfied sidesteps the need for extra resource consumption in Sybil defense. Selfied is the first design that purely relies on in-protocol resources to do effective Sybil defense. This shift signifies a sustainable approach to build permissionless distributed systems. Our formal analysis confirms Selfied's security. Practical evaluations, based on actual implementation, further attest to the practicality of Selfied.
The thesis takes a further step in using in-protocol resources for Sybil defense in two directions. In the first direction, we use an entirely different design paradigm from Selfied and use recursive view construction to improve bandwidth-based Sybil defense. Using the new paradigm, we achieved better scalability and tolerance against bandwidth-bound adversary. In the second direction, we explored combining bandwidth consumption with other resource-based Sybil defense to enhance the resilience of the blockchain system. By combining bandwidth consumption with stake, we achieved a higher tolerance against resource concentration, a common threat in permissionless systems than existing protocols.