PhD Defense: Data Structures and Protocols for Scalability and Security of Distributed Consensus

Distributed consensus is the problem of reaching an agreement among mutually distrusting nodes in the presence of faults. Despite tremendous progress in achieving internet-scale consensus, prior consensus protocols face scalability and security challenges. This dissertation proposes new authenticated data structures and protocols to improve the scalability (through stateless blockchains) and security (through support for more powerful network adversaries) of distributed consensus, respectively.In the first part, I will present our Vector Commitment (VC) data structure, Hyperproofs, to improve the scalability of blockchains. Our VC is the first construction that is efficiently maintainable (can update all proofs in sublinear time) and aggregatable (can combine multiple individual proofs into a succinct proof). Hyperproofs also incentivize proof computation through a new property called unstealability, which allows a prover to cryptographically bind the proofs she computes irreversibly with her identity. I will also present schemes to succinctly prove and verify the (non-)membership of multiple elements in a cryptographic accumulator for applications in the distributed setting.In the second part, I will show how we improve the resilience of consensus protocols against powerful network adversaries that can delay or delete any message in the network. Specifically, I will describe the first permissionless protocol that is secure even after relaxing the standard synchrony assumption. Finally, I will present the first constant-round Byzantine broadcast under a strongly adaptive and corrupt majority setting.

Examining Committee

Chair:

Dr. Charalampos (Babis) Papamanthou

Dean's Representative:

Dr. Lawrence C. Washington

Members:

Dr. Jonathan Katz

Dr. John Dickerson

Dr. Dana Dachman-Soled