SLR210 Algorithmic Basics of Blockchains

P4/2019

Petr Kuznetsov, office hours: C213-2, appointment by email
INFRES, Telecom ParisTech

Matthieu Rambaud
INFRES, Telecom ParisTech

Objectives
News
Slides and exercises
Literature

Objectives

We study the algorithmic basics behind decentralized and consistent storage systems that tolerate churn and malicious behavior of participating nodes. We begin with the study of classical protocols for reconfigurable storage and Byzantine fault-tolerance. Then we explore the protocols designed for "open" systems, exemplified by the prominent blockchain technology.

News

The first lecture: Friday, April 19, 8h30, Amphi Grenat
The project description is available.
The project report is due June 14.
Exam: 26.06.2019, 10h15-11h45, no gadgets, two double-side A4 pages with hand-written notes.

Slides and exercises

Date	Class	Exercises	Solutions	Supplementary
19.04.2019	Introduction, distributed computing at large scale, blockchains and distributed storage	Quiz 1	Sol 1	John Oliver on cryptocurrencies
26.04.2019	Project discussion (reports to be received before 14.06.19 )			AKKA: java tutorial, java patterns
10.05.2019	Consensus, state machine replication, Paxos	Quiz 2		Rachid Guerraoui on Paxos
17.05.2019	Project: indulgent consensus and Paxos
07.06.2019	Byzantine agreement, PBFT, Hyperledger Fabric, permissioned Blockchain	Quiz 3
14.06.2019	Permissionless blockchains: proof-of-work, Bitcoin
21.06.2019	Project presentations
26.06.2016	Q&A session
26.06.2019	Exam

Literature

C. Cachin, R. Guerraoui, L. Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer, 2011
N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers. 1996
M. Castro and B. Liskov Practical Byzantine Fault Tolerance. OSDI 1999.
Jose M. Falerio et al. Generalized Lattice Agreement. PODC 2012
Nakamoto, S. Bitcoin: A peer-to-peer electronic cash system. 2008
Garay, J., Kiayias, A., and Leonardos, N. The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology - EUROCRYPT 2015 (2015).
E. Androulaki et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. Eurosys 2018
Vitalik Buterin and Virgil Griffith Casper the Friendly Finality Gadget.