Resilient and Secure Distributed Ledgers: Adversary Models, Efficient Consensus, and System Design

Abstract

Byzantine Fault-Tolerant (BFT) protocols enable distributed ledgers to operate without a single trusted party, tolerating up to a threshold of Byzantine faults. While traditional BFT was designed for closed systems with few participants, blockchain applications are open systems with thousands of internet-connected participants. This transition introduces two critical vulnerabilities unaddressed by classical BFT: (1) nodes' susceptibility to internet Denial-of-Service (DoS) attacks, and (2) potential correlated failures when participants use similar configurations, violating the fault independence assumption.

This thesis addresses these vulnerabilities through three contributions. First, it introduces the Mobile Crash Adaptive Byzantine (MCAB) adversary model, capturing mobile DoS attacks. Protocols are proven to require either concealment (hiding node identities until after broadcasting) or abundance (having more nodes per role than the adversary can target) to maintain liveness under MCAB.

Second, it expands modern Directed Acyclic Graph (DAG) based BFT for system models captured by MCAB. The first constant latency dynamically available DAG-based BFT protocol is proposed. A novel primitive, Graded Common Prefix (GCP), enables nodes to agree on a common DAG subset without standard consensus. Combining these yields a flexible protocol allowing clients to choose between prioritizing liveness or safety while benefiting from modern DAG BFT's high performance.

Third, the thesis addresses fault independence through incentive mechanisms encouraging diverse node configurations. Since costs related to various configurations—from software implementation to geo-location—are hard to quantify, control mechanisms from reinforcement learning and control theory are leveraged, as they function without requiring analytical solutions to the underlying system.