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: [ Ссылка ]
Lecture 4: The Asynchronous Model and the FLP Impossibility Theorem, Part 1 (6 videos)
Lecture 4 notes: [ Ссылка ]
Lecture 4 slides: [ Ссылка ]
Leave comments/questions below or at [ Ссылка ]
Lecture 4 tl;dr:
1. The asynchronous model of communication is the polar opposite of the synchronous model: no shared global clock, and no guarantees on message delivery (other than eventual delivery).
2. Designing fault-tolerant protocols with provable guarantees is challenging in the asynchronous model because of the de facto conspiracy between Byzantine nodes and the sequence of message deliveries.
3. Because the asynchronous model makes only minimal assumptions about the communication network, any consensus protocol with provable guarantees in it is automatically interesting.
4. The Byzantine agreement (BA) problem is a variant of the Byzantine broadcast (BB) problem in which there is no distinguished sender node and every node has a private input.
5. A consensus protocol solves the BA problem if it satisfies termination (defined as for BB), agreement (defined as for BB), and validity (if all honest nodes have the same private input, that should also be their common output).
6. The FLP (Fischer-Lynch-Paterson) impossibility theorem states that no deterministic protocol solves the BA problem in the asynchronous model, even with f = 1 and the most benign type of faulty node (a “crash fault”).
7. The same impossibility result holds for the state machine replication problem.
8. The high-level proof plan for the FLP impossibility theorem is to exhibit, for any deterministic protocol that satisfies agreement and validity on termination, an infinitely long protocol trajectory (ruling out the termination property).
9. The first step of the proof shows that, for every such protocol, there exists a choice of nodes’ private inputs such that the protocol begins in an ambiguous state (with the adversary in control over the honest nodes’ eventual outputs).
10. Such a choice exists because the protocol is assumed to satisfy validity and because a Byzantine node could control the perceived value of a pivotal private input.

свернуть