The decentralized cryptocurrency Bitcoin popularized the notion of permissionless consensus. Bitcoin's solution, now known as the Nakamoto consensus, is to build a proof-of-work (PoW) chain and treat the longest PoW chain as consensus decisions. However, this elegant solution does have limitations. In this talk, I will present techniques to improve consensus protocols on multiple fronts.
A primary drawback of Nakamoto consensus is its long latency to confirm transactions. In contrast, the classic permissioned Byzantine consensus commits consensus decisions instantly. I will present Solida, a permissionless consensus protocol based on reconfigurable Byzantine consensus. I will then present an improved protocol for synchronous and authenticated Byzantine consensus, which tolerates 1/2 malicious participants and runs in expected 4 rounds (compared to expected 24 rounds from best prior work). Finally, Bitcoin's hash-based PoW has raised concerns about fairness and energy consumption. I will describe my work on bandwidth-hard functions and proofs of space to address these concerns.