CAREER: Algorithms Foundations of Blockchains

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

As cryptocurrencies gain popularity, their underlying technology, commonly referred to as distributed ledgers or blockchains, shows great potential for many other applications. However, the research community’s understanding of blockchains is still limited from an algorithm foundation viewpoint. This project develops a more accessible, precise, rigorous, and practical algorithmic foundation for blockchains. The project’s novelty is to take a principled approach to identify and study blockchains’ key innovations. The project’s broader significance and importance are establishing the precise security of blockchains, unifying blockchains into the existing foundation of distributed algorithms, and bridging blockchain research across related fields. This project also includes an educational component, in which K-12 and undergraduate students are involved with the project. This project provides an algorithmic foundation for blockchains deeply rooted in decades of research on fault-tolerant consensus. By contrasting blockchains with classic consensus protocols, the project focuses on the key innovations of blockchains, such as the support for dynamic participation, the use of peer-to-peer networks, and resilience to message loss. The project develops algorithmic foundations to reason about these properties and designs new protocols to achieve them without incurring the drawbacks of current blockchains. Based on these insights, the project also revisits the foundation of fault-tolerant distributed systems and investigates what assumptions and requirements are suitable for these systems in the real world. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.