Bitcoin is the first decentralized cryptocurrency. Its main innovation is the blockchain and the way that this data structure is maintained in a distributed manner by those that participate in the Bitcoin network. Bitcoin was not only an innovative solution to an open problem, the problem of implementing a decentralized transaction ledger, but also a fresh solution to an old, fundamental, and well-studied problem in distributed computing, the problem of consensus. Understanding and analyzing Bitcoin's core protocol, the Bitcoin backbone, entails formally defining several notions: (1) a model in which a solution to the problem can described, (2) the properties that a suggested solution should satisfy, (3) proof that Bitcoin's backbone protocol indeed has the desired properties. We will discuss the above and also a proof that Bitcoin solves the consensus problem.
Nikos Leonardos is currently a post-doctoral researcher at the Department of Informatics and Telecommunications of the University of Athens, Greece. Previously he was a postdoc at the Algorithms and Complexity group of Institut de Recherche en Informatique Fondamentale, Paris 7, France. He holds a PhD in computer science from Rutgers, the State University of New Jersey (USA), MSc in Logic, Algorithms and Computation (Greece), and BSc in Mechanical Engineering from the National Technical University of Athens (Greece). He currently works on the foundations of blockchain systems and the security of cryptocurrencies. His research interests include topics of theoretical computer science, such as cryptography, distributed computation, randomized computation, communication complexity, decision tree complexity, algorithms.