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, we present our Vector Commitment (VC) data structure, Hyperproofs, to improve 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 single 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. Finally, we 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, we present protocols to improve security of distributed consensus against powerful network adversaries that can delay or delete any message in the following settings: (1) We describe the first protocol to show that it is possible to achieve permissionless consensus even after relaxing the standard synchrony assumption. (2) We present the first expected constant-round Byzantine broadcast under a strongly adaptive and dishonest majority setting.