2017/2018 Edition

Introduction to cryptocurrencies

Lecturer: Stefan Dziembowski (University of Warsaw).

About the lecturer | Course Summary | Slides | Assignment (corrected!)

About the lecturer: Stefan Dziembowski is professor at the University of Warsaw. He is interested in theoretical and applied cryptography.

Dziembowski received an MSc degree in computer science in 1996 from the University of Warsaw, and a PhD degree in computer science in 2001 from the University of Aarhus, Denmark. He was a post-doc at the ETH Zurich, CNR Pisa and the University of Rome "La Sapienza", where he joined the faculty in 2008. In 2010 he moved to the University of Warsaw where he leads the Cryptography and Data Security Group.

His papers appeared at leading computer science conferences (FOCS, STOC, CRYPTO, EUROCRYPT, ASIACRYPT, TCC, LICS), and journals (Journal of Cryptology and IEEE Transactions on Information Theory). He also served as a PC member of several international conferences, including CRYPTO, EUROCRYPT, ASIACRYPT, Theory of Cryptography Conference (TCC), and the International Colloquium on Automata, Languages and Programming (ICALP). He served as the general chair of the Twelfth Theory of Cryptography Conference (TCC'15).

He is a recipient of an ERC Starting Independent Researcher Grant grant, an FNP Welcome grant and a Marie-Curie Intra-European Fellowship (2006-2007). He is a co-author of two papers that won the Best Paper Awards (on Eurocrypt 2014 and on IEEE S&P 2014).

Course summary: The cryptographic currencies (also dubbed the cryptocurrencies) are a fascinating recent concept whose popularity exploded in the last 3 years. The most prominent of them is the Bitcoin, introduced in 2008 by an anonymous developer using a pseudonym "Satoshi Nakamoto". These currencies quickly gained noticeable attention among the general public, and their economic importance is rapidly growing - the current capitalization of Bitcoin is around 4 billion USD, and the average number of transactions per day is well above 100,000. The security of Bitcoin is based on an assumption that a large fraction of computing power in the system is controlled by the honest parties. This is verified using the so-called proofs of work (PoWs) [Dwork and Naor, CRYPTO 1992].

This tutorial will consist of two parts. The goal of the first part is to provide a research-oriented introduction to the cryptocurrencies. We will start with a description of Bitcoin and its main design principles. We will then discuss some of its weaknesses, including the so-called selfish mining attack, and show some ideas for dealing with these problems. We will talk about the mechanics of the mining pools and ideas for discouraging the mining pool creation. We will also provide an introduction to the smart contracts, and give some examples of them, including the multiparty lotteries.

In the second part we will discuss some recent efforts to better understand and improve Bitcoin. First, we will talk about our recent paper [Andrychowicz and Dziembowski, CRYPTO 2015] whose goal is to provide foundations for the distributed consensus based on the PoWs. We will present the main technical contribution of this work, which a broadcast protocol based on the assumption that the adversary has a limited computing power (i.e. he can solve a limited number of PoWs in a given timeframe).

We will then present a new tool called the proof of space (PoS) [Dziembowski, Faust, Kolmogorov, and Pietrzak, CRYPTO 2015] which is an alternative to the PoWs. In the PoS a service requestor must dedicate a significant amount of disk space as opposed to computation. We will show a construction of secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees. We discuss some applications, including follow-up work [Park et al., 2015] where a decentralized cryptocurrency that uses PoS (called Spacecoin) is constructed.


Slides to the lecture can be found here.


Assignment: You can find the corrected problem set here. Please submit the solutions at the address provided on the problem sheet by Wednesday, June 22.