Foundations of Blockchains (Lecture 1.3: Digital Signature Schemes)

A lecture series on the science and technology of blockchain protocols and the applications built on top of them, with an emphasis on fundamental principles. Full playlist:    • Foundations of Blockchains   Lecture 1: Introduction and Overview (4 videos) Lecture 1 notes: https://timroughgarden.github.io/fob2... Lecture 1 slides: https://timroughgarden.github.io/fob2... Leave comments/questions below or at   / 1487075256900673538  . Lecture 1 tl;dr: 1. This lecture series is about the science and technology of blockchain protocols and the applications built on top of them, with an emphasis on fundamental principles rather than specific protocols. 2. We’re witnessing a new area of computer science blossom in real time, and future generations will be jealous of your opportunity to get in on the ground floor. 3. Roughly 60% of the lectures are about “layer 1,” including consensus (agreeing on a sequence of transactions) and compute (executing those transactions). 4. Roughly 20% of the lectures concern “layer 2,” where the goal is to scale up layer-1 functionality (e.g., transactions processed per second) by orders of magnitude. 5. Roughly 20% of the lectures focus on the application layer (smart contracts and the user-facing applications that interact with them), with a particular focus on decentral- ized finance (DeFi). 6. For us, blockchains will not be about digital money (except as means to an end) but rather a new computing paradigm—–a programmable computer that lives in the sky, that is not owned by anyone and that anyone can use. 7. We will always assume the existence of the Internet (semi-reliable point-to-point com- munication) and cryptography (specifically, cryptographic hash functions and secure digital signatures). 8. A user of a digital signature scheme uses their private key to sign messages, and such signatures can be verified by anyone who knows the corresponding public key. 9. Such a scheme is secure if it’s impossible (or at least computationally infeasible) to forge signatures without knowing the private key. 10. State machine replication (SMR) is the consensus problem most immediately relevant to blockchains. In this problem, a bunch of nodes run a protocol to stay in sync on an ever-growing ordered sequence of transactions that have been previously submitted by clients. 11. A “solution” to the SMR problem is a protocol (i.e., code deployed at each node to control local computation and communication) that satisfies consistency (no pair of nodes ever disagrees on the relative order of a pair of transactions) and liveness (submitted transactions eventually get processed).