← 全部课程
COMP5567

Distributed Algorithms and Protocols for Blockchains

期末 70%(开卷)· Project 15% · Lab Test 10% · Assignment 5%。3 小时开卷,范围含 lectures + labs/tutorials + project。

连载中,随课程进度更新,目前到第 11 周 L11e(11-08),后面的讲次上完课再补。

复习资料与自测

非官方复习材料。自测保留英文题干,答案与解析逐题折叠;练习分值和用时不代表正式考试安排。

逐讲

L01a第 1 周 · 9-02

L01a 共享账本:一本账由谁来记

从哈希和数字签名讲起,看中心化账本和去中心化账本各靠什么让一笔转账算数,再看搭一条区块链最少要哪三样东西。

L01a-2第 1 周 · 9-02

L01a-2 区块头与挖矿:80 字节的页眉,和一个个试出来的 nonce

区块头五类字段各管什么、为什么加起来正好 80 字节,矿工怎样反复改 nonce 算哈希,以及难度 H(·) < 2¹⁸⁶ 和前导零的关系。

L01b第 1 周 · 9-02

L01b 改不动的旧账:篡改的代价、最长链和分叉

改一块旧账为什么要重挖后面所有块,两个版本并存时为什么认最长的那条,两个矿工同时出块时全网怎样慢慢收敛。

L01b-2第 1 周 · 9-02

L01b-2 坏节点与分层:两类故障,和这门课只管的那一层

分布式账本里的「分布式」指什么,崩溃故障和拜占庭故障差在哪,区块链技术栈的五层里本课只研究共识层,以及贯穿全课的四步主线。

L02a第 2 周 · 9-09

L02a 分布式系统是什么:少了三样东西,只剩发消息

从单机少掉的三样东西讲起,分清并行和分布式、分布式和去中心化,再学会按消息条数给分布式算法算账。

L02a-2第 2 周 · 9-09

L02a-2 同步模型与 FLP:消息要多久才能到

从「对方是挂了还是只是慢」这个问题讲起,一帧一帧看同步、异步、部分同步三种假设下超时还能不能判故障,以及 FLP 划下的那条边界。

L02a-3第 2 周 · 9-09

L02a-3 安全性、活性与 CAP:怎么说一个协议「对」

先学会用「坏事不发生」「好事终将发生」两句话描述协议的正确性,再一帧一帧看网络断开时,为什么一致和可用只能保一个。

L02b-1第 2 周 · 9-09

L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后

从三类事件和时空图讲起,学会判断一个快照是否一致,再一帧一帧沿时间轴和消息箭头「走路」,判出两件事是先后还是并发。

L02b-2第 2 周 · 9-09

L02b-2 Lamport 时钟:给每个事件发一个号

一帧一帧算 Lamport 时钟的四条规则,看清时钟条件为什么只单向成立,以及加上进程 ID 之后得到的全序能做什么、不能做什么。

L02b-3第 2 周 · 9-09

L02b-3 向量时钟:每台机器记一位,就能判出并发

一帧一帧算向量时钟,学会逐位比较判出先后和并发,弄清它比 Lamport 时钟多花了什么、多换来了什么,最后做完课件的 Take-home 练习。

L03a-1第 2 周 · 9-09

L03a-1 可靠广播(一):收到和交付是两回事,可靠性分三级

从时空图的读法讲起,分清 send、receive、deliver,再一级一级看 best-effort、RB、URB 各保证什么、漏洞在哪、差别落在哪一个词上。

L03a-2第 2 周 · 9-09

L03a-2 可靠广播(二):先转发再交付,一个十行的 URB 协议

把 URB 协议逐帧跑一遍:为什么先发给自己、为什么先转发后交付、MJ 集合管什么,以及课件四节点图里哪些消息没人交付。

L03b-1第 2 周 · 9-09

L03b-1 交付顺序(一):FIFO,同一个人寄的信按先后放

URB 为什么不管顺序,FIFO 只约束什么、合法顺序怎么数,崩溃节点交付的前缀,以及序号加等待队列的实现。

L03b-2第 2 周 · 9-09

L03b-2 交付顺序(二):因果序,回信不能先于原信

m → m′ 的三条规则,用 delivered 和 past 两个向量判断一条消息能不能交付,以及 CO-URB 的代码骨架和正确性性质。

L03b-3第 2 周 · 9-09

L03b-3 交付顺序(三):全序广播,所有人排成同一个序列

全序只要求全体一致、不规定哪种顺序;FIFO TOB 的两种实现,定序器和 Lamport 时钟,以及怎样分两步验证一个交付序列。

L03b-4第 2 周 · 9-09

L03b-4 交付顺序(四):gossip,以及各档广播的强弱

gossip 用概率换规模;区块链把 gossip 和全序叠起来用;从 best-effort 到 FIFO TOB 的强度链,FIFO TOB 与共识等价,普通全序和因果序互不包含。

T01a习题课第 3 周 · 9-16

T01a Tutorial 1(上):两张时钟图,一步不漏地手算

Lamport 和向量时钟手算的三处失分点,以及那个没标字母的黑点。

T01b习题课第 3 周 · 9-16

T01b Tutorial 1(下):四条性质,练习可靠广播判定

选择题考性质名字,简答题考哪条性质被违反,压轴题用性质倒推执行图。

L04a第 3 周 · 9-16

L04a 比特币的钱存在哪:交易、UTXO 与 coinbase

从一笔交易讲起:钱以一张张没花掉的输出存在,花钱就是拆旧票开新票;每块第一笔交易凭空发奖励,奖励每 210,000 块砍一半;最后把同一段历史改写成账户表对照。

L04a-2第 3 周 · 9-16

L04a-2 挖矿到底在算什么:区块头、nBits 与难度调整

先补哈希,再看区块头 6 个字段;把 4 字节的 nBits 解码成目标阈值 T,算出平均要试多少次,最后看难度为什么每 2016 块重算一次。

L04b第 3 周 · 9-16

L04b 链听谁的:分叉、双花与 51% 攻击

两个矿工同时挖到时链怎么分叉、怎么收拢;同一枚币为什么花不了两次,商家为什么要等 6 个确认;算力过半的攻击者怎么回滚付款,又有哪些事做不到。

L04b-2第 3 周 · 9-16

L04b-2 支撑比特币的三项技术:Merkle 树、矿池与 P2P 网络

Merkle 树怎么用一个根锁住整块交易、怎么剪枝、怎么给轻节点出证明;PoW 为什么难算易验,矿池为什么只降方差不改期望;交易和块怎么在没有中心的 P2P 网络里先验证再转发。

T02习题课第 4 周 · 9-23

T02 HotStuff Part 1:三票成证书,三代成提交

四节点 HotStuff demo 的三个字段怎么一格一格右移,以及故障时为什么只能等。

L05a第 4 周 · 9-23

L05a PoW 与 PoS:出块权从烧电换成押币

从零讲 PoW 的合法条件,再讲 PoS 为什么要换资源、只按余额选人为什么富者恒富,以及币龄选择的三条规则和那条公式。

L05a-2第 4 周 · 9-23

L05a-2 Nothing at Stake 与罚没:分叉时为什么要两边都押

先补期望收益,再用同一组分叉概率算 PoW、无罚没 PoS、加罚没 PoS 三种规则下的收益,讲清 Casper 罚没哪几种签名,以及以太坊 2022 年怎样切到 PoS。

L05b第 4 周 · 9-23

L05b 信标链的时钟与选链:slot、委员会和 LMD GHOST

合并之后的以太坊怎么计时、谁在干活、分叉时跟哪条链:12 秒一个 slot、32 个 slot 一个 epoch,三种验证者角色,以及比票重不比块数的 LMD GHOST。

L05b-2第 4 周 · 9-23

L05b-2 检查点与两步敲定:justified、finalized 和 12.8 分钟

Casper FFG 怎样把以太坊的历史敲定:检查点怎么定、空 slot 怎么兜底,(source, target) 两段式投票,justified 到 finalized 的两步规则,以及它和 PoW 概率性最终性的区别。

T03习题课第 5 周 · 9-30

T03 HotStuff Part 2:认证、提交、执行,余额只在最后一步变

跟着一笔 Alice 转给 Bob 的 10 块钱走完交易池、提案、三链和状态机,再看失败转账、孤块和恢复。

L06a第 6 周 · 10-07

L06a 原子提交:一笔事务跨几台机器,要么全做要么全不做

从一次丢钱的跨行转账讲起:什么叫原子提交,本讲的故障模型 Crash-Stop 允许节点怎样坏,ACID 里协议管哪几个字母,以及原子提交和共识差在哪。

L06a-2第 6 周 · 10-07

L06a-2 2PC 协议流程:先问一圈,再敲一锤

从预写日志讲起,一帧一帧走一遍两阶段提交:业务先在 working 里做完,协调者再问 CanCommit?、收齐投票、写下决定、广播结局;每一步先写日志再发消息。

L06a-3第 6 周 · 10-07

L06a-3 2PC 失败与阻塞:协调者一倒,投了同意的人只能干等

按「谁崩溃、崩在哪一阶段」把 2PC 的故障一类一类走一遍:恢复时看日志里有没有最终决定;恢复协调者能救单点崩溃,救不了协调者和参与者一起倒;这就是 2PC 的阻塞。

L06b第 6 周 · 10-07

L06b 3PC 协议与恢复:多敲一锤「预备通过」,倒了也能自己收尾

3PC 把 2PC 的第二阶段拆成 PreCommit 和 DoCommit。PreCommit 让每个人都知道全票通过了,协调者倒下后,恢复协调者问一圈状态,按三条分支就能收尾。

L06b-2第 6 周 · 10-07

L06b-2 分区弱点与取舍:网络一断,两边各判各的

3PC 靠超时换来不阻塞,前提是大家能互相问到。网络分区时两边各选恢复协调者,一边提交一边中止。再把没有协议、2PC、3PC 放在同一笔转账上对照一遍。

Lab1习题课第 6 周 · 10-07

Lab 1 把 2PC 跑起来:一个协调者、三个参与者、四个终端

按课件步骤在本地跑通课程仓库 5567-2PC:三个演示 case、两个超时练习,外加课件没演示的失败率 case。每一步都附实测输出,并把程序和 L06 理论不一致的地方逐条标出来。

L07a第 7 周 · 10-14

L07a 两将军与拜占庭将军:信道会丢,人会撒谎

先看两将军问题为什么在会丢消息的信道上永远确认不了,再把故障升级成会撒谎的拜占庭故障,最后写清整讲的验收标准 Agreement 与 Validity。

L07b第 7 周 · 10-14

L07b 3m+1 下界:为什么 3 个人压不住 1 个叛徒

从三将军的两种情形讲起,说明忠诚副官为什么分不清谁在撒谎,再用「每人扮演一组」把结论推广成 n ≥ 3m+1。

L07c第 7 周 · 10-14

L07c 口头消息算法 OM(m):转述一层套一层,最后数票

从多数函数和默认值 RETREAT 讲起,一帧一帧走完四将军的 OM(1),再展开 OM(m) 的递归,算清转发给几个人、表决时有几个值、要跑几轮。

L07d第 7 周 · 10-14

L07d OM 的代价与 PBFT 预告:消息一层层乘上去

按层数清 OM(m) 的消息量,看懂 (n−1)(n−2)…(n−k) 和 O(nᵐ) 从哪来;再读 PBFT 的五阶段图,数出 22 条箭头,记住 2f、2f+1、f+1 三个法定人数。

L07e第 7 周 · 10-14

L07e 签名消息算法 SM:叛徒没法冒充别人

从数字签名讲起,看签名怎样一层层嵌套;走一遍三将军的 SM,看叛徒指挥官怎样被自己的签名揭穿;最后把 OM 和 SM 放进一张表对照。

Lab2习题课第 7 周 · 10-14

Lab 2 把 3PC 跑起来:多出来的 PreCommit 和协调者崩溃恢复

按课件步骤在本地跑通课程仓库 5567-3PC:四个演示 case、三个练习,外加一个课件没有的变式。逐条标出课件命令写错的地方,以及程序和 L06 理论不一致的五处,其中恢复逻辑实测能造成三方账本不一致。

L08a第 8 周 · 10-21

L08a VR 正常操作:2f+1 台机器,主节点排号,过半确认

只会宕机、不会撒谎的机器怎样保持副本一致:先补状态机复制,再推出 2f+1 台、等 f+1 个回应和多数集交集,最后一帧一帧跑一遍 VR 正常操作的四条消息。

L08a-2第 8 周 · 10-21

L08a-2 VR 换届与恢复:主节点没了,从过半的日志里拼回账本

VR 的另外两个子协议:先弄懂 k 是「多数副本都已完成的最新操作号」,再一帧一帧跑一遍 view change,最后看崩溃的机器怎样补课、以副本身份回来。

L08b第 8 周 · 10-21

L08b Paxos 两阶段:谁都能提议,但已选定的值只能被再提一遍

没有固定主节点时怎样让多数选出同一个值:先认识 proposer、acceptor、learner 和提案编号,再一帧一帧跑 prepare/promise 与 accept 两阶段,看后来者为什么必须沿用旧值,以及 acceptor 怎样决定接受还是拒绝。

L08b-2第 8 周 · 10-21

L08b-2 活锁与 Multi-Paxos:抢编号会卡住,选一个 leader 就顺了

两个 proposer 轮流用更大编号互相挡掉 accept,Paxos 会卡在活锁里;单一 leader 或指数退避能化解,Multi-Paxos 选一次 leader 后只跑 accept。最后把 Basic Paxos、Multi-Paxos、VR 放在一张表里对照。

Lab3习题课第 9 周 · 10-28

Lab 3 把 VR 跑起来:五个节点的提交、换届和恢复

按课件步骤在本地跑通课程仓库 5567-VR:六个演示 case、两个练习,外加三个课件没有的变式。逐条标出程序和 L08 理论不一致的地方:备份能投 no、新主节点按视图号轮转、恢复只用第一个回应。

L09a第 9 周 · 11-05

L09a PBFT 的舞台:为什么要 3f+1 台机器,谁在台上,说哪几种话

PBFT 开场三件事:消息靠摘要和签名防篡改冒名;容忍 f 个会撒谎的副本至少要 3f+1 个;主节点、backup、客户端三类角色,正常操作、视图切换、检查点三个子协议,一共 8 种消息。

L09b第 9 周 · 11-05

L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停

主节点没出事时,一笔请求走 Request、Pre-prepare、Prepare、Commit、Reply 五步;副本两次凑满 2f+1 个匹配票才执行,客户端等 f+1 个相同回复;票凑不满就停住,保安全性、暂丢活性。

L09c第 9 周 · 11-05

L09c PBFT 视图切换:主节点靠不住就换人,Commit 保证换届不丢账

副本等请求超时就怀疑主节点,按 p = v mod n 轮到下一任;新主节点收齐 2f+1 份 VIEW-CHANGE 后发 NEW-VIEW(v+1, V, O),把已 prepared 的操作原样带进来。去掉 Commit、prepared 就执行,换届后会出 safety violation。

L09d第 9 周 · 11-05

L09d PBFT 检查点与经典协议对照:旧账什么时候能扔,五个协议怎么分

副本定期广播 CHECKPOINT,收到 2f+1 个序号和摘要都相同的消息,检查点就稳定,旧日志可以丢,掉队副本也从这里追上。最后把 BFT、PBFT、VR、Basic Paxos、Multi-Paxos 按故障模型和有没有 leader 放进一张表。

Lab4习题课第 10 周 · 11-04

Lab 4 把 PBFT 跑起来:四个节点数票、拜占庭分票、换视图和检查点

按课件步骤在本地跑通课程仓库 5567-PBFT:七个演示 case、两个练习,外加两个课件没测的情形。标出程序计票的固定加 1、拜占庭节点分票后各节点数出不同的票、恢复节点停在旧视图、检查点少一台就卡住,以及课件里写错的命令。

L10a第 10 周 · 11-01

L10a HotStuff:票交给 leader 攒成一张证书,三轮投票走完一个区块

从零讲 Basic HotStuff 的正常流程:为什么要 3f+1 个节点、每轮等 2f+1 票,leader 怎样把票合成 QC 再广播,四个阶段各做什么,leader 怎样轮换。

L10b第 10 周 · 11-01

L10b HotStuff 换 leader:新 leader 只挑最高的那张 QC

从零讲 HotStuff 的 view change:PBFT 换 leader 为什么要 O(n³),HotStuff 的新 leader 怎样只收 n−f 份 New-View、挑视图号最高的 QC 接着往下提块。

L10c第 10 周 · 11-01

L10c 为什么非得三轮投票:锁早了卡死,锁晚了分叉

从零讲 HotStuff 为什么要 Prepare、Pre-Commit、Commit 三轮投票:课件 p.16 锁在 Commit 丢活性,p.17 锁挪到 Decide 丢安全性,三阶段靠 2f+1 份证据和 f+1 的重叠两头都顾上。

L10d第 10 周 · 11-01

L10d 门限签名:2f+1 份部分签名合成一个签名

从零讲 HotStuff 里 QC 背后的门限签名:模运算和逆元、Shamir 秘密分享、Schnorr 签名,再用拉格朗日系数把 2-of-3 的部分签名合成一个普通签名。

L10e第 10 周 · 11-01

L10e Chained HotStuff:每个新块顺手推进前面三个块

从零讲 Chained HotStuff:每个新块带上一块的 QC,三轮投票叠成流水线;One-Chain、Two-Chain、Three-Chain 三条规则分别对应存证据、上锁、提交,视图失败时看父子链接而不是视图号。

L11a第 11 周 · 11-08

L11a Solana 总览:两种最终性和 PoS + PoH + Tower BFT

从零讲 Solana 这一讲的起点:概率最终性和确定最终性的区别、PoS 的五种做法、Solana 的历史与性能数字,以及 PoS 选 leader、PoH 排序、Tower BFT 投票敲定的整条流水线。

L11b第 11 周 · 11-08

L11b leader 轮值表:按质押抽签,slot、tick、epoch 三层时钟

从零讲 Solana 怎样用 PoS 提前排好每个 slot 的 leader:质押越多被抽中越多;再认识 tick、slot、epoch 三层时间单位,以及换 leader 时用最后一个 PoH 哈希交棒。

L11c第 11 周 · 11-08

L11c PoH:用一条哈希链当时钟

从零讲 Solana 的 Proof of History:哈希为什么只能一个接一个算,交易怎样混进哈希链变成 entry,区块怎样由 entry 组成,验证者怎样拆开并行验算,Turbine 怎样把区块切片传播。

L11d第 11 周 · 11-08

L11d Tower BFT 投票:最重分叉和三级确认

从零讲 Solana 的 Tower BFT 投票:为什么出了块还要投票,分叉怎样产生,最重分叉规则怎样按质押加权选主链,以及 processed、confirmed、finalized 三级确认和 12.8 秒的由来。

L11e第 11 周 · 11-08

L11e Tower BFT 锁定:投了票就不能随便改

从零讲 Solana Tower BFT 的锁定机制:为什么投票要带锁,换分叉要等多久,锁定怎样翻倍,投票塔怎样叠起来,以及课件表格和官方文档在锁定方向上的出入。

期末复习怎么用

开卷的三小时里,翻书能查到的东西价值有限,值钱的是查得快和现场推得出来。复习的产物应该是几张能迅速定位的对照表,加上练到不用提示的几类计算题。

  1. 1按讲把页尾「必背」过一遍,判据类的条目(判因果还是并发、容错上限)要背成反射。
  2. 2每讲的「完整例题」跟着算一遍,然后合上页面做「变式题」,时钟题和难度换算题练到不看提示。
  3. 3把各协议横着填进一张对照表带进考场,顺手扫「课件里的坑」,标了 [课件有误] 的照抄会答错。

要能动笔算的题型

这几类没有思考余量,练到不看提示就能做。

Lamport 标号
给一张时空图,标出每个事件的逻辑时间戳
向量时钟比较
给两个向量,判断因果先后、并发还是同一事件
容错上限代入
n 个节点、f 个故障,这个协议还能不能达成共识
难度换算
目标阈值要求前多少位为 0,阈值变化后难度变几倍
消息复杂度
某协议一轮正常操作发多少条消息,O(n) 还是 O(n²)

复习的产物:自己填的表

填表本身就是复习,抄一份现成的没有用。

  • 协议对照表:故障模型、网络模型、容错上限、消息复杂度、故障时是否阻塞、最终性
  • 时钟规则速查:内部事件、发送、接收各怎么更新,能不能判并发
  • 模型与不可能性:同步/异步/部分同步的延迟假设,超时能不能判故障

累计考点表

各讲页尾「必背」的汇总,随讲次增长。复习时按讲回看,点讲次跳到那一页。

L01a · L01a 共享账本:一本账由谁来记
  1. 哈希把任意长的数据压成固定长度的指纹,SHA-256 输出 256 位即 32 字节;原数据改一点,指纹整串都变
  2. 数字签名只有持私钥的人能生成,任何人用公钥都能验证;它回答「这笔转账是谁授权的」
  3. 中心化账本一人一本、靠信任银行核验同意;去中心化账本全网共用一本、靠数字签名表达同意
  4. 签名回答不了交易顺序和由谁写入,课件由此抛出全课核心问句 Who maintains this ledger?
  5. 区块链 = P2P 网络 + 不断增长的链式结构 + 生成这条链的算法,三者缺一不可;课件注明「实际上不一定是链」
L01a-2 · L01a-2 区块头与挖矿:80 字节的页眉,和一个个试出来的 nonce
  1. 区块头五要素的用途:Prev Hash 成链、Merkle Root 保证块内交易完整性、Target 与 Nonce 做 PoW,另有 Version 和 Time
  2. 区块头固定 80 字节 = 4 + 32 + 32 + 4 + 4 + 4;Magic no 与 Block size 各 4 字节,不算在区块头内
  3. 出块三步:收集有效交易算 Merkle Root → 改 nonce 反复做双 SHA-256 直到哈希小于 target → 广播全网
  4. PoW 是穷举碰运气,每次尝试概率固定且独立,算力直接等价于出块概率
  5. 谜题 H(·) < 2¹⁸⁶ 等价于 256 位哈希的前 70 位全为 0;指数越小,前导零越多,难度越高
L01b · L01b 改不动的旧账:篡改的代价、最长链和分叉
  1. 不可篡改的机制是代价:改一块要重挖其后所有块,而诚实链还在前进
  2. 挖矿 = 获得生产新区块的权利;谜题形式 H(·) < 2¹⁸⁶
  3. Bitcoin 选择有效分支中累计工作量最大者;课件把同难度情形简写为最长链,收敛依赖网络与诚实算力假设
  4. 两个矿工几乎同时出块会分叉,这是正常现象;长度相同时任选一条,最终一条变长、全网收敛
  5. 比特币提供概率最终性,刚上链的块仍可能被更长的另一支盖过;PBFT 一旦提交不回滚,叫确定性最终性
L01b-2 · L01b-2 坏节点与分层:两类故障,和这门课只管的那一层
  1. 分布式账本的「分布式」指复制:每个节点各存一整本完整的账,正常节点之间必须看到一致的内容
  2. 崩溃故障只会停机、之后什么都不发,由 2PC、3PC、Paxos、VR、Raft 处理;拜占庭故障可以任意偏离协议,由 PBFT、HotStuff 处理
  3. 「安全」是有条件的:坏节点不超过某个比例时,正常节点仍能达成一致;超过了,保证就不成立
  4. 共识层(PoW – PoS – PBFT)是本课唯一战场;概率最终性与确定性最终性是贯穿全课的对比线索
  5. 全课主线:事件排序 → 消息正确顺序 → 原子提交 → 共识,每层建立在前一层之上
L02a · L02a 分布式系统是什么:少了三样东西,只剩发消息
  1. 六属性里的三个「没有」:无全局物理时钟、无全局共享内存、处理器自治且独立失败,分布式算法的困难全从这里来
  2. 六个属性:无全局物理时钟、自治且独立失败、无全局共享内存、异构、对外一致、并发
  3. 并行系统求高性能、处理器共享内存;分布式系统求容忍部分失败、每个处理器只有本地内存
  4. 所有去中心化系统都是分布式的,反之不成立;distributed 说位置的分布,decentralized 说控制权的分布
  5. 分布式算法的复杂度用消息条数衡量,不是指令条数
L02a-2 · L02a-2 同步模型与 FLP:消息要多久才能到
  1. 同步模型是系统的时序假设,不是事实;选哪种假设是设计分布式协议的第一个决策点
  2. 三种同步模型:同步有已知上界 Δ、异步无上界、部分同步在 GST 之后有界;可靠超时判定需消息、处理与心跳间隔的已知上界;GST 前超时可能误判
  3. FLP:纯异步系统中允许一个崩溃时,确定性共识不能在所有允许执行中同时保证安全与终止;不等于算法不存在或每次都失败
  4. 绕开 FLP 的三条路:加时序假设(部分同步,PBFT、HotStuff 走这条)、加随机性、弱化保证(比特币的概率最终性)
  5. 部分同步的形式定义:存在 Δ 和 GST,GST 最终一定发生但时刻未知,时刻 x 发出的消息须在 Δ + max(x, GST) 之前送达
  6. 安全性在任何时候都保证、活性只在 GST 之后保证,这是绕开 FLP 的标准做法
L02a-3 · L02a-3 安全性、活性与 CAP:怎么说一个协议「对」
  1. 安全性(safety)= 坏事不会发生,例:两个线程不能同时处于临界区;活性(liveness)= 好事终将发生,例:每个线程最终都会进入临界区
  2. 安全性可以被有限的执行片段证伪,活性不能被有限片段证伪
  3. 一个永远不做任何决定的协议绝对安全,却完全没有活性,所以两者都必须要
  4. CAP:发生网络分区时,不能同时保证线性一致性 C 与所有非故障节点的可用性 A;CA 可在不发生分区的假设下讨论
  5. 分布式系统中分区无法避免,P 必选,真正的选择在 C 和 A 之间:CP 分区时关掉不一致的节点,AP 保持可用但可能返回旧数据
  6. 比特币是 AP 只是限定操作语义下的类比,PBFT 类系统偏 CP,节点数不够就停下不出块
L02b-1 · L02b-1 事件、割与 happens-before:没有统一的表,怎么排先后
  1. 事件只有三类:内部事件、消息发送、消息接收
  2. 一致割不存在从未来穿到过去的消息:某条消息的接收在割内而发送在割外,这个割就不一致;发了还没收到是合法的
  3. happens-before 三条判定规则:同进程先后、消息收发、传递;判据是能不能沿时间轴和消息箭头走过去
  4. happens-before 是偏序,允许互不可比的事件,也就是并发 e ‖ f
  5. 逻辑时钟只度量事件的顺序,不参照物理时间;e → f 说的是 e 可能导致了 f
L02b-2 · L02b-2 Lamport 时钟:给每个事件发一个号
  1. Lamport 时钟四条规则:计数器初值 0;每发生一个事件加 1;发消息时带上当前值;收消息时设为 Max(local, received) + 1
  2. 时钟条件:a → b ⟹ LC(a) < LC(b)
  3. Lamport 时钟收消息时取 Max(local, received) + 1;a → b ⟹ LC(a) < LC(b) 成立,反向不成立,因此判不出并发
  4. Lamport 时钟附上进程 ID 打破平局,得到人为的全序,但仍然判不出两个事件是否并发
  5. 课件列的两个问题:两个事件可能有相同的时间戳;没有全局顺序
L02b-3 · L02b-3 向量时钟:每台机器记一位,就能判出并发
  1. 向量时钟四步:初值全 0;内部事件自己那一位加 1;发送时带上整个向量;接收时先给自己那一位加 1,再逐位取 max
  2. 向量时钟判据:每位都 ≤ 且至少一位 < 为因果先后,有的位大有的位小为并发
  3. 向量时钟能检测并发,这正是 Lamport 时钟做不到的
  4. Lamport 时钟占 O(1) 空间、判不了并发;向量时钟占 O(n) 空间、能判并发
  5. 接收事件也要给自己那一位加 1,不能只做 max;发送时带走的是完整向量,不是单个数
L03a-1 · L03a-1 可靠广播(一):收到和交付是两回事,可靠性分三级
  1. send / receive / deliver 是三件事,所有性质只约束 deliver;receive 由网络说了算,协议唯一的手段是收到后先扣住不交
  2. 三级可靠性:best-effort = Validity + No Duplication + No Creation;Reliable 再加 Agreement;Uniform 把 Agreement 前件的「正确进程」换成「任何进程」
  3. best-effort 缺 Agreement,节点之间可以出现不一致的世界观;Validity 只管发送方自己
  4. RB 的漏洞:故障进程可以交付完就崩,把消息带进坟墓
  5. URB 的 Agreement 后件不变,仍只要求正确进程交付;RB 和 URB 的全部差别在前件
L03a-2 · L03a-2 可靠广播(二):先转发再交付,一个十行的 URB 协议
  1. URB 协议一句话:先发给自己,收到后先转发再交付,用 MJ(message judger,已见消息集合)去重;把转发和交付两步对调就退化成 RB
  2. 广播了不等于会被交付:URB 只承诺「有一个进程交付了,所有正确进程都交付」
  3. MJ 集合有两个作用:判断消息是不是第一次收到,既保证 No Duplication,又让互相转发能停下来
  4. URB 完全不管顺序:同一发送方的两条消息,在任何节点(包括发送方自己)都可能颠倒
  5. 课件四节点图里 m3 和 m5 零交付:发送方在自己那份消息绕回来之前就崩了,消息从没离开过它
L03b-1 · L03b-1 交付顺序(一):FIFO,同一个人寄的信按先后放
  1. FIFO 只约束同一发送方的消息,且只对每个节点各自成立;合法交付顺序数 = (a+b+c+…)! / (a! b! c! …)
  2. 崩溃节点在 FIFO 下交付的是每个发送方消息序列的一个前缀,不会跳过中间某条
  3. FIFO 的实现 = 序号 next_i[j] + 等待队列 msg_set_i:序号对上就交付并自增,然后回扫队列;对不上就入队
  4. 排序层坐在 URB 层之上,自动继承四条可靠性性质,只需额外证明新加的顺序性质;换排序策略不用碰可靠性代码
  5. next_i[j] 用「等于」比较:URB 已保证不重复,到来的消息要么正是期待的那条,要么更靠后、要等
L03b-2 · L03b-2 交付顺序(二):因果序,回信不能先于原信
  1. m → m′ 三条规则:同一节点先后广播、交付后再广播、传递性;规则 2 正是 FIFO 做不到的那一条
  2. 因果序蕴含 FIFO 序,反之不成立:FIFO 管不了跨发送方的因果链
  3. 交付条件 DC_i(m):∀k: delivered_i[k] ≥ m.past[k],用 ≥ 不用 =;delivered_i 是会增长的节点状态,m.past 是广播那一刻抄下的快照
  4. 一条消息可以已经 URB-deliver、满足 FIFO,但仍然被因果序禁止 CO-deliver
  5. 自己广播的消息永远满足 DC,所以 wait until done_i 不会死锁
  6. 正确性性质 m → m′ ⟹ ∀k: m.past[k] ≤ m′.past[k] 且至少一位严格小于,是单向的:past 可比不代表有因果关系
L03b-3 · L03b-3 交付顺序(三):全序广播,所有人排成同一个序列
  1. Total order 只要求「所有人一致」,不要求「哪个顺序才对」
  2. 全序广播是复制状态机和区块链账本的必需品:同样的初态 + 同样的命令序列 = 同样的终态
  3. FIFO TOB 两种实现:sequencer(单 leader 定序,有单点)和 Lamport clock(逻辑时间戳 + 确定性打破平局)
  4. Lamport 时钟三条规则:本地事件/发送时 LC++;发送附带 LC;接收时 LC ← max(本地, 收到) + 1;平局按 sender ID 等确定性规则排
  5. 标量时钟能排全序但丢并发信息,向量时钟能判因果但排不出唯一全序
  6. 验证 FIFO TOB 分两步:各进程序列是否相同,再看每个发送方的消息相对次序是否与发送次序一致,允许中间插别人的消息
L03b-4 · L03b-4 交付顺序(四):gossip,以及各档广播的强弱
  1. 概率广播 / gossip 放弃确定性换可扩展性:Validity 从「确定」降为「高概率」,扇出若干个随机 peer 层层转发,少数节点可能永远收不到
  2. 区块链两层分工:网络层用 gossip 散播(要可扩展),共识层用全序定顺序(要一致)
  3. FIFO TOB 与共识等价,FLP 同样适用;TOB 不保证因果性,与因果序不可比,两者都要就是 CO-TOB
  4. 普通 TOB 不必保持因果序;FIFO TOB 在全序也约束故障进程和发送方自交付的前提下强于因果广播
  5. 因果序 / 纯全序 / CO-TOB 在「A→B 加并发 C」这个最小例子上分别允许 3 种(各进程可不同)、6 种(全体必须相同)、3 种(全体必须相同)
T01a · T01a Tutorial 1(上):两张时钟图,一步不漏地手算
  1. Lamport 接收事件:C ← max(本地上一个事件, 消息戳) + 1,max 的另一边是本地上一个事件,不是本进程初值;本地事件与发送事件只做 +1
  2. 向量时钟接收事件先逐分量 max、再只给自己那一维 +1,两步都不能省;发送时先自增再把整个向量附在消息上
  3. 向量时钟判因果:逐维 ≤ 且至少一维严格 < 即 happens-before,互不包含即并发;不同事件的 Lamport 戳相等可判并发;戳较小却不能反推因果
  4. 图里没标字母的黑点默认按内部事件计一格,答卷上先写一句假设
  5. 不计 P3 那个黑点时:Figure 1 里 P3 从 q 起整体减 1,连带 y = 5、z = 6;Figure 2 只有 r、s 两行变
T01b · T01b Tutorial 1(下):四条性质,练习可靠广播判定
  1. TOB 四条标准性质:Validity、Agreement、Integrity(No Duplication + No Creation)、Total Order;FIFO Order 属于 FIFO Broadcast,不在其中
  2. 判定题第一步永远是问「这个没交付的进程是正确进程还是故障进程」:正确进程不交付违反 Agreement,故障进程不交付不违反
  3. 正确进程永远收不到消息属于 perfect links 假设被打破,RB 协议本身没出错;「收到即转发」是为了广播者中途崩溃时其余正确进程仍能收到
  4. 本题固定执行中,三个正确进程都收到足够副本;不能把阈值 2 推广成任意故障模型下的 URB 充分条件,安全阈值还取决于故障上限和转发规则
  5. 重画题解法:先定崩溃集合 → 用 Validity 补出必须被交付的消息 → 用 Uniform Agreement 把正确进程的交付集合拉齐;崩溃进程广播的消息可以无人交付
L04a · L04a 比特币的钱存在哪:交易、UTXO 与 coinbase
  1. 交易 Tx = (Input, Output):输入引用一张旧输出并附它的所有者签名,输出写收款地址和金额
  2. Tx[0] 是 coinbase:不花费已有 UTXO,输出总额至多为区块补贴 + 本块手续费;手续费 = 输入和 − 输出和;UTXO 只能整笔花,找零写成输出
  3. 减半:每 210,000 块(约 4 年)奖励减半,50 → 25 → 12.5 → 6.25 → 3.125;2100 万 = 210,000 × 50 × 2,约 2140 年到顶
  4. UTXO 模型的状态是「未花输出的集合」,账户模型的状态是「余额表」,两者对同一历史等价
  5. UTXO 模型没有余额字段,钱包余额 = 属于你的 UTXO 加总;不同 UTXO 互不影响,可并行验证
L04a-2 · L04a-2 挖矿到底在算什么:区块头、nBits 与难度调整
  1. SHA-256 把任意输入压成 256 位输出;输入改一点输出全变,从输出推不回输入
  2. 区块头 6 字段共 80 字节:Version / Prev Hash / Merkle Root / Time / nBits / Nonce;Magic Num 与 Block Size 不进哈希
  3. nTime 两条规则:大于前 11 块 nTime 的中位数;不超过网络调整时间 2 小时
  4. 正目标 T 按 compact 指数与有效尾数解码,并检查符号位;p = (T+1)/2²⁵⁶,期望尝试次数 = 2²⁵⁶/(T+1)
  5. 600R = 2²⁵⁶/(T+1);T_new = T_old × 实测时长 / (2016 × 600),实测时长取两块 nTime 之差
  6. 32 位 nonce 不够用时,改 coinbase 里的 extraNonce 换出新的 Merkle Root
L04b · L04b 链听谁的:分叉、双花与 51% 攻击
  1. 分叉按累计工作量裁决;stale block 的普通交易仍有效且符合本地策略才可回 mempool,coinbase 作废
  2. 双花:简单的被 UTXO 检查拦下,并发的靠最长链裁决;商家等 6 个确认(本块后再接 5 块)
  3. 确认数越多越安全,因为另一支反超的概率随块数指数下降;前提是攻击者算力不到一半
  4. 51% 攻击流程:公开链付款 → 私链不含这笔 → 私链累计工作量反超后公布 → 付款被回滚
  5. 51% 攻击能双花、能审查交易,不能偷别人的币、不能改规则
L04b-2 · L04b-2 支撑比特币的三项技术:Merkle 树、矿池与 P2P 网络
  1. Merkle 树让区块头只存一个根就锁定全部交易;改任何一笔交易,Root 变,区块哈希变,PoW 作废
  2. 剪枝只需保留兄弟哈希:剪掉 Tx0 到 Tx2 后保留 Hash01 与 Hash2
  3. Merkle 证明只需给沿途的兄弟哈希,大小按 log n 增长,这是 SPV 只存区块头也能验证交易的依据
  4. PoW 三要素:难产生、易验证、满足特定条件;比特币沿用 Hashcash
  5. 矿池降低收益方差、不改变期望;协议 Stratum / GetBlockTemplate
  6. 三类节点:full node 存全链,miner 是出块的 full node,SPV 只存区块头
  7. 块与交易的传播都是「先验证再转发」的泛洪,即 gossip,与可靠广播同源
T02 · T02 HotStuff Part 1:三票成证书,三代成提交
  1. n = 4、f = 1 时 quorum q = 2f + 1 = 3;任意两个 quorum 交集 ≥ 3 + 3 − 4 = 2 > f,加上每 view 一票,同一 view 不可能有两个冲突 QC
  2. 投票的两个安全条件是「或」:提案扩展自己锁定的块,或携带的 QC 的 view 严格高于 LockedQC 的 view;前者保安全,后者防卡死
  3. HighQC 管 leader 往哪接,LockedQC 管副本能不能投,Commit block 是已经最终确定的祖先,三者是不同的状态
  4. 三链提交:块自己有 QC 是 certified,儿子有 QC 成为锁定依据,孙子有 QC 才提交,三个块必须父子直接相连
  5. 正常路径每个 view 七步,STEP 6 / 13 / 20 的 (HighQC, LockedQC, Commit) 依次是 (B1, B0, B0)、(B2, B1, B0)、(B3, B2, B1)
  6. Leader(view) = ((view − 1) mod 4) + 1;超时只换 leader,副本保留 HighQC 和 LockedQC
  7. 故障不降低法定人数:只剩 2 票时没有 QC,系统反复超时等待
  8. demo 用节点 ID 代替签名、用中心队列和逻辑 tick 计时,只演示状态转移,不证明安全性,也不构成性能结论
L05a · L05a PoW 与 PoS:出块权从烧电换成押币
  1. 比特币 PoW 条件是 SHA256(SHA256(header)) ≤ Target;Target 随难度调整,不固定前导零字节数
  2. PoS 的动机是 PoW 的能耗;更准确的说法是安全成本从外部的电力换成了链内的质押资产
  3. PoS 术语:块是 forged / minted,出块人叫 forger / validator;mine / miner 是 PoW 的说法
  4. 只按余额选出块人会富者恒富:出块奖励加到余额上,下一轮更容易再中,形成正反馈;课件给的修正是随机数选择和币龄选择
  5. 课件简化币龄模型:币数 × 天数,满 30 天起参与、用来出块的币龄归零、90 天封顶;不是所有 PoS 的通用参数
  6. 币龄选择条件 Hash(block_header) < Target × CoinAge:币龄越大有效阈值越大,命中概率正比于币龄
L05a-2 · L05a-2 Nothing at Stake 与罚没:分叉时为什么要两边都押
  1. Nothing at Stake:PoS 里支持一个分叉几乎零成本,所以双押是理性的
  2. 双押的期望收益是把两条分支的胜率相加:两边各有一个自己的块,获胜那条上必有一个,不是拿两份奖励
  3. 三格 EV:PoW 劈算力 0.05 + 0.45 = 0.5 < 0.9;无罚没 PoS 双押 0.1 + 0.9 = 1 > 0.9;加罚没后 0.1 + 0.9 − 5 = −4
  4. 罚金 5 是示意值;真实罚没与协议版本、有效余额和同期被罚权重有关,独自失误损失小,协同作恶可能没收全部质押
  5. Casper 的 slashing 针对可被密码学证明的两类行为:同 slot 双提案、FFG 双投/包围投票;惩罚是没收本金 + 强制退出,与「漏投扣奖励」不是一回事
  6. The Merge 发生在 2022-09-15;Beacon Chain 早在 2020-12 就已上线,作为独立链与 PoW 主网并行运行
L05b · L05b 信标链的时钟与选链:slot、委员会和 LMD GHOST
  1. slot = 12 秒,epoch = 32 slot = 6.4 分钟;每 slot 可有多个委员会,128 是目标大小;每个活跃验证者每 epoch 获分配一次投票职责
  2. slot 是一次出块机会,可以为空:提案者离线或块没及时传开时,这个 slot 就没有块
  3. 三种角色:proposer 被伪随机选中出块,attester 投票,aggregator 把多个 attestation 聚合进块;票重按有效余额算,不按人头
  4. LMD GHOST 比累积 attestation 权重,不比链长;逐层贪心选权重最大的孩子,每个验证者只算最新一票
  5. 只算最新一票是为了防止同一验证者的历次投票被重复累计,不能替代双投罚没
  6. Gasper = LMD GHOST(选哪条链)+ Casper FFG(哪段不可回滚),两套机制分工
L05b-2 · L05b-2 检查点与两步敲定:justified、finalized 和 12.8 分钟
  1. checkpoint = (epoch, block root);首个 slot 为空时取该分支此前最近的块,同一块可对应不同 epoch 的检查点
  2. 课件 p.28–29 的图按每 epoch 64 slot 画,主网是 32,考试按 32 答,兜底规则不变
  3. FFG vote = (source, target) 两个检查点,是一条有向链接;两段式才能定义「包围投票」这种可罚没的作恶
  4. justified 要合资格链接取得 ≥ 2/3 活跃有效余额支持;正常相邻 A→B 超多数链接使已认证的 A finalized,通常约 12.8 分钟,非保证
  5. PoW 是概率性最终性,等得越久被反超的概率越低但不为零;以太坊是可追责最终性,冲突最终化会暴露至少 1/3 权重的可罚没行为
  6. 超过 1/3 有效余额离线时无法认证新检查点,最终性停止推进;长期无最终性才触发 inactivity leak,门槛不会立即降低
T03 · T03 HotStuff Part 2:认证、提交、执行,余额只在最后一步变
  1. 认证、提交、执行是三个时刻:QC(B1) 在 STEP 6 形成,B1 在 STEP 20 才提交,余额这时才变
  2. 被提案的交易留在交易池里,直到它所在的块被提交;提交交易不计步、不改余额
  3. 所有副本按同一提交顺序(块序再 payload 序)运行同一转移函数,得到相同余额和回执
  4. 共识最终性和应用层成功相互独立:余额不足的转账照样提交,回执写 rejected,余额不变
  5. 防重复三道关:提交前留池、打包时排除所选父链上的交易 ID、执行时同一 ID 返回已有回执
  6. 本地 ID 去重不防客户端重放:重复的 HTTP 提交拿到新 ID,要靠签名和 nonce
  7. 孤块里的交易会被新分支重新打包,且只执行一次,因为孤块不在新块的父链上
  8. 五条不变量:提交前余额不变、存活副本一致、同一 ID 至多改一次余额、三账户之和为 300、两个投票者出不了 QC
L06a · L06a 原子提交:一笔事务跨几台机器,要么全做要么全不做
  1. Atomic Commit:分布式事务全体 commit 或全体 abort;rollback 回到事务开始前状态
  2. 本讲故障模型是 Crash-Stop(benign):节点只会停、不会说谎;2PC/3PC 还隐含「节点间总能通信」的网络假设
  3. ACID 四性质;2PC/3PC 直接对准的是 Atomicity(及借助 WAL 的 Durability),C、I 更多靠并发控制与应用约束
  4. 课件口径:Atomic Commit 一节点失败就全体 abort,只覆盖决定形成之前;commit 决定已持久化后协调者崩溃要重发 commit(crash ≠ automatic abort);Consensus 容忍故障节点继续决定同一值
  5. Atomic Commit ↔ Crash-Stop、Consensus ↔ Byzantine 是本讲的教学对照,不是唯一的学术划分
  6. 银行 100 元例子:没有提交协议时一边扣了款、一边没入账,钱凭空少了;要求两家同 commit 或同 abort
L06a-2 · L06a-2 2PC 协议流程:先问一圈,再敲一锤
  1. 2PC 角色是 Coordinator + Participants;业务 pre-execution 完成、全体进入 Prepared 之后才启动 2PC
  2. 2PC 三条假设:write-ahead log 在稳定存储、节点最终恢复(fail-recover)、节点间总能通信
  3. 2PC Phase 1 收集 CanCommit? 投票一票否决;Phase 2 先写日志再广播 commit/abort;投 yes 后收决定前锁不能放
  4. 日志写点:协调者先写 prepare to commit 再发 CanCommit?,决定时先写 commit/abort 再广播;参与者先写 agree to commit 或 abort 再回票
  5. 恢复后不能改口:曾经同意 commit 的节点,重启后必须仍能 commit
  6. Lock + 预写日志 ≠ 已提交:真正扣款、入账发生在 Phase 2 收到 commit 之后
L06a-3 · L06a-3 2PC 失败与阻塞:协调者一倒,投了同意的人只能干等
  1. 协调者崩溃:日志无最终决定则恢复发 ABORT;已写 commit/abort 则重发该决定;不能因不确定而悲观 abort
  2. 参与者投票前崩溃 → 协调者当作 NO 并 abort;投 YES 后崩溃 → 重启后处于不确定态,要问协调者或其他参与者
  3. 参与者收到决定后、本地动作做完前崩溃:重启读本地日志,重做 COMMIT 或 ABORT
  4. Recovery Coordinator 可接手收集投票;若另有参与者也崩溃,仍会阻塞
  5. 2PC 最大问题是 blocking:投 yes 后、收到决定前协调者崩溃,参与者握锁干等
  6. 不能悲观地直接 abort:可能有参与者已经 commit 后崩溃,abort 会造成部分提交、部分回滚
L06b · L06b 3PC 协议与恢复:多敲一锤「预备通过」,倒了也能自己收尾
  1. 3PC 把 2PC 第二阶段拆成 PreCommit + DoCommit;PreCommit 让每个参与者都知道投票结果
  2. 3PC 状态:Initial / Waiting / Prepared / Committed / Aborted;无分区、超时可靠时 Prepared 为非阻塞态
  3. 3PC 恢复三分支:已有人 commit → 补 commit;已收 PreCommit → 补发 PreCommit 再提交;无人收到 PreCommit → abort 或重启
  4. 协调者在 CanCommit / PreCommit / DoCommit 阶段崩溃,结果为 Abort / Commit / Commit;前提是协调者唯一崩溃、该阶段消息已送达全体、无分区
  5. PreCommit 阶段参与者超时没回 OK → 协调者当它崩溃,向全体 abort;同在 PreCommit 阶段,结局也可能是 abort
L06b-2 · L06b-2 分区弱点与取舍:网络一断,两边各判各的
  1. 3PC 弱点:网络分区可使一边 commit、一边 abort,愈合后全局不一致
  2. 3PC 用超时换非阻塞,牺牲了分区下的安全性;它隐含依赖一定的网络可靠性
  3. 2PC 保证原子但可能永远等;3PC 降低阻塞但怕分区;没有协议会丢钱
  4. 2PC 的问题在 prepare 之后、commit/abort 之前协调者崩溃;3PC 协调者崩溃时参与者可按规则协商
  5. 答 3PC 优点时必须同时写分区弱点:节点总能通信是强假设
Lab1 · Lab 1 把 2PC 跑起来:一个协调者、三个参与者、四个终端
  1. 2PC 提交需要全体参与者投 YES,2/3 同意也要中止,它不是多数投票
  2. 按 L06,参与者在第二阶段只执行协调者的决定并回 ack,程序允许的 ack abort 是简化,不能当作合法分支
  3. 参与者投票前崩溃或超时,协调者按 NO 处理并中止,这是安全的中止分支
  4. 参与者投了 YES 之后等不到决定,不能凭本地超时自行中止,这就是 2PC 的阻塞窗口
  5. 程序的超时规则:参与者 30 秒不操作就自动投 NO 或自动 ACK,协调者最多等 60 秒,未投票者按 NO 计
  6. 程序没有持久化,崩溃只是内存标志位,恢复只同步已结束的交易,不能当作 WAL 恢复的证据
L07a · L07a 两将军与拜占庭将军:信道会丢,人会撒谎
  1. 两将军问题:两人都忠诚、信道会丢消息,无论发多少条确认,最后一条的发送方总不确定
  2. 两将军是人可靠、信道不可靠;拜占庭将军是信道可靠(消息必达、知道发送者),人可能是叛徒
  3. 崩溃故障只会沉默,拜占庭故障可以任意行为:对不同的人说不同的话、转述时撒谎、故意不发
  4. 拜占庭将军问题两个条件:Agreement(忠诚副官服从同一命令)、Validity(指挥官忠诚时服从他的命令)
  5. 指挥官是叛徒时 Validity 不作要求,只看 Agreement;指挥官忠诚时 Agreement 可由 Validity 推出
L07b · L07b 3m+1 下界:为什么 3 个人压不住 1 个叛徒
  1. 口头消息下可解当且仅当超过 2/3 忠诚,即 n ≥ 3m+1;3 人对付 1 个叛徒无解,因为 L1 分不清谁在撒谎
  2. 三将军论证:情形 1 指挥官叛变,情形 2 副官 L2 叛变,L1 两次收到的消息完全一样(不可区分)
  3. Validity 逼 L1 在情形 2 选 attack,于是情形 1 里 L1 也 attack、L2 retreat,违反 Agreement
  4. 推广:少于 3m+1 位将军无法应对 m 个叛徒,证法是让 3 人各模拟一组 m 人,归约回三将军
  5. n > 3m 和 n ≥ 3m+1 是同一个条件;10 位将军最多容忍 3 个叛徒,18 位将军对 6 个叛徒无解
L07c · L07c 口头消息算法 OM(m):转述一层套一层,最后数票
  1. OM 的三条假设:消息正确送达、接收者知道发送者、能检测到消息缺失;默认值 Retreat
  2. 多数函数:过半数等于 v 就取 v,没有过半数取 RETREAT,例如 (A, A, R, R) → RETREAT
  3. OM(m):副官在 OM(m−1) 中把值转发给 n−2 人,对 n−1 个值取多数,无多数则 RETREAT;共 m+1 轮
  4. n = 4、m = 1 时,无论叛徒是副官还是指挥官,忠诚副官都一致;消息 9 条
  5. n = 5、m = 2 不满足下界,可构造忠诚副官一致撤退、违反 Validity 的反例
  6. n = 7、m = 2 刚好满足 3m+1,两个叛徒的谎言在每个子协议里都被忠诚转述者的多数压住
L07d · L07d OM 的代价与 PBFT 预告:消息一层层乘上去
  1. OM(m−k) 被调用 (n−1)(n−2)…(n−k) 次,每次发 n−1−k 条消息,总量 O(nᵐ)
  2. n = 4、m = 1 共 9 条;n = 7、m = 2 共 6 + 30 + 120 = 156 条、3 轮;n = 10、m = 3 共 3609 条
  3. PBFT(1999 OSDI)复杂度 O(n²);n = 4、f = 1 时课件图中共 22 条消息
  4. PBFT 五阶段箭头数:request 1、pre-prepare 3、prepare 6、commit 9、reply 3
  5. PBFT 法定人数:prepared 要 2f 个 prepare,执行要 2f+1 个 commit,客户端等 f+1 个相同回复;n = 4 时是 2、3、2
  6. PBFT 的安全性不依赖同步,只有活性需要
L07e · L07e 签名消息算法 SM:叛徒没法冒充别人
  1. 签名消息让叛徒无法伪造忠诚者的消息,叛徒指挥官签发矛盾命令会被识破
  2. SM 每转发一次追加一层签名,副官维护命令集合 Vᵢ,最后用同一个 choice 规则做决定
  3. choice 规则:Vᵢ 只有一个元素 v 时取 v,Vᵢ 为空时取 RETREAT
  4. OM 需 n ≥ 3m+1,SM 需 n ≥ m+1,两者都假设同步网络;SM 还需要 PKI
  5. p.23 Exercise 1:L1、L2、L3 的集合都是 {ATTACK, RETREAT},按同一 choice 规则得到同一结果
Lab2 · Lab 2 把 3PC 跑起来:多出来的 PreCommit 和协调者崩溃恢复
  1. 按 L06,3PC 的消息顺序是 CanCommit? → Yes/No → PreCommit → ACK → DoCommit → ack,PreCommit 不是第二次投票
  2. CanCommit 阶段任一 No 或超时,协调者直接中止,不进入 PreCommit
  3. 协调者在 CanCommit 阶段崩溃,恢复时无人 Prepared,中止是安全的
  4. 协调者在 PreCommit 阶段崩溃,只有全体参与者都已 Prepared 才能直接提交,否则先补发 PreCommit 并收齐 ACK
  5. L06 的恢复规则按参与者报告的状态决定;程序只看协调者自己的阶段和 CanCommit 票,实测会造成不一致
  6. 3PC 用多一轮消息换掉了 2PC 的阻塞窗口,但在网络分区下不安全
  7. 程序的投票命令必须带阶段前缀:cancommit vote yes 或 precommit vote yes,带冒号是未知命令
L08a · L08a VR 正常操作:2f+1 台机器,主节点排号,过半确认
  1. VR:2f+1 个副本容忍 f 个崩溃,法定人数 f+1 含主节点;只崩溃不作恶
  2. VR 正常操作四阶段:⟨request op,c,s,v⟩ → ⟨prepare m,v,n⟩ → ⟨prepareok v,n,i⟩ → ⟨reply v,s,x⟩
  3. 任意两个多数集至少共享一个节点:(f+1)+(f+1) > 2f+1,这是 VR 和 Paxos 安全性的共同来源
  4. VR 三个子协议:正常操作、view change、副本恢复
  5. 3PC 解决原子提交(不同服务一起提交或放弃),VR 解决副本一致与操作排序,VR 单独不能做原子提交
  6. 节点数不是 2f+1 时按「超过半数」算门槛:4 个节点要等 3 个回应
L08a-2 · L08a-2 VR 换届与恢复:主节点没了,从过半的日志里拼回账本
  1. VR view change:doviewchange(v,l,k,i) 收 f+1 后换视图,startview(v,l,k);恢复节点收 f+1 个响应后以副本身份回归
  2. k 是多数副本都已完成的最新操作号:三家分别到 op 9、op 10、op 8 时 k = op 9
  3. 触发 view change:客户端长时间收不到回复,或副本联系不上主节点
  4. 换届后操作号接着旧日志往下排;新主节点从 f+1 份日志里拼回所有已提交操作
  5. 备份 PREPAREOK 少于 f 个时操作不提交,主节点不能回复成功;客户端在换届后重试
L08b · L08b Paxos 两阶段:谁都能提议,但已选定的值只能被再提一遍
  1. Paxos 两阶段:prepare(n)/promise 附上已接受的最大编号提案;accept(n,v) 的 v 必须沿用该值,没有才用自己的
  2. Paxos 用 2f+1 个 acceptor 容忍 f 个崩溃;proposer 只有兼任 acceptor 才计入法定人数
  3. Paxos 角色:proposer 提值、acceptor 投票、learner 得知结果;提案编号全局唯一且递增
  4. acceptor 收到 accept(n,v):没向比 n 更大的编号承诺过就接受,否则拒绝;比较只看编号
  5. acceptor 或 proposer 失效:凑得到多数就继续;凑不到就换更大编号重试,接手者从 promise 里拿回已接受的旧值
L08b-2 · L08b-2 活锁与 Multi-Paxos:抢编号会卡住,选一个 leader 就顺了
  1. Paxos 保证一致但不保证可用:活锁靠单一 leader 或指数退避解决;Multi-Paxos 选一次 leader,后续实例只跑 accept
  2. VR 是主备式(主节点提值、换主走 view change);Paxos 是法定人数式(任何 proposer 可提值、失效后换更大编号)
  3. 活锁时一个值都没选出来,安全性没有被破坏,损失的只是可用性
  4. Multi-Paxos 定三条命令:只有实例 1 跑 prepare 并确立 leader,实例 2、3 只跑 accept
  5. Basic Paxos、Multi-Paxos、VR 都是 2f+1 个节点、f+1 的多数法定人数、最多容忍 f 个崩溃,差别在领导者
Lab3 · Lab 3 把 VR 跑起来:五个节点的提交、换届和恢复
  1. VR 用 2f+1 个副本容忍 f 个崩溃,提交、换届、恢复都要 f+1 个回应,包括发起者自己
  2. 按 L08,正常操作的消息是 REQUEST → PREPARE → PREPAREOK → REPLY,备份只回 prepareok,不投 No
  3. 换届的两步是各副本发 doviewchange 给新主节点、新主节点收齐 f+1 个后发 startview
  4. 崩溃节点恢复后发 recovery request,收到 f+1 个响应、同步日志后成为普通副本,不当回主节点
  5. 只崩一个备份不需要换届,只有主节点崩溃才触发 view change
  6. 操作编号跨视图连续,新主节点接着已提交的最大编号往后排
  7. VR 解决副本一致与操作排序,3PC 解决原子提交,两者不能互换
L09a · L09a PBFT 的舞台:为什么要 3f+1 台机器,谁在台上,说哪几种话
  1. PBFT(Castro & Liskov 1999):3f+1 个副本容忍 f 个拜占庭故障,消息量 O(n²)
  2. 三个设计目标:Consistency(两个诚实副本不会提交不同结果)、Availability、Fault Tolerance
  3. n 个副本最多容忍 f = ⌊(n − 1)/3⌋ 个拜占庭副本:4、5、6 个都只扛 1 个,7 个扛 2 个
  4. 3f+1 的来历:只能等 n − f 个回复,其中仍可能有 f 个是假的,诚实的 n − 2f 个要多过 f 个
  5. 三个子协议:正常操作(Request → Pre-prepare → Prepare → Commit → Reply)、视图切换(View change → New view)、检查点
  6. 8 种消息:5 种属于正常操作,2 种属于视图切换,1 种属于检查点
  7. 摘要 h 保内容一致,签名保发送者身份;课件 p.11 把 d 记作签名,p.14、p.18 又把 d 当摘要用
L09b · L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停
  1. 正常操作五个阶段:Request → Pre-prepare → Prepare → Commit → Reply,只有 Pre-prepare 由主节点单独群发
  2. 三道门槛:2f+1 个匹配 prepare 才 prepared,2f+1 个匹配 commit 才执行,客户端等 f+1 个相同回复;f = 1 时是 3、3、2
  3. 两组 2f+1 在 3f+1 个里至少重叠 f+1 个,其中至少 1 个诚实,所以冲突的值凑不齐两组
  4. Prepare、Commit 两轮全员互发,每轮最多 n(n − 1) 条,量级 O(n²)
  5. 客户端等 f+1 个相同回复:最多 f 个是假的,f+1 个里至少 1 个来自诚实副本
  6. 票凑不满就停住不提交:丢活性、保安全性
  7. 5 个节点撑不住 f = 2:要么凑不够 5 票卡死,要么降门槛后交集只剩 1 个、可能出错;至少要 7 个
L09c · L09c PBFT 视图切换:主节点靠不住就换人,Commit 保证换届不丢账
  1. 视图切换:新主节点 p = v mod n(第一个视图是 view 0,副本从 0 编号)
  2. 副本等请求超时就怀疑主节点,向下一任发 VIEW-CHANGE;新主节点收齐 2f+1 个后发 NEW-VIEW(v+1, V, O)
  3. NEW-VIEW 里 V 是收齐的 2f+1 个 VIEW-CHANGE,O 是新视图要处理的 pre-prepare 集合;已 prepared 的请求被带进新视图,没 prepared 的客户端要重发
  4. Commit 阶段让已执行的操作在视图切换后保留;跳过 commit、prepared 就执行会出 safety violation
  5. prepare 保证同一视图内同一序号只有一个值;commit 保证这个值换视图后还在
  6. 作恶主节点最多拖慢进度、逼出视图切换,没法让诚实副本提交不同结果
L09d · L09d PBFT 检查点与经典协议对照:旧账什么时候能扔,五个协议怎么分
  1. 检查点:收到 2f+1 个序号和摘要都相同的 CHECKPOINT 后稳定
  2. 稳定检查点两个作用:丢弃旧日志降低存储;崩溃或掉队的副本从这里取状态再补齐后续日志
  3. BFT、PBFT 防拜占庭故障,要 3f+1 个节点;VR、Paxos、Multi-Paxos 只防崩溃,要 2f+1 个
  4. BFT(OM 算法)没有固定 leader,消息量 O(n^f);PBFT 有轮转 leader,消息量 O(n²)
  5. Basic Paxos 对单个值达成一致(如谁持有锁);Multi-Paxos 对一串操作达成一致(如文件系统元数据)
  6. VR 每个视图一个 primary,2f+1 个副本容忍 f 个崩溃,法定人数 f+1 含 primary
Lab4 · Lab 4 把 PBFT 跑起来:四个节点数票、拜占庭分票、换视图和检查点
  1. PBFT 用 3f+1 台机器容忍 f 台拜占庭节点,Prepare、Commit 各要 2f+1 票;4 台时 f = 1,门槛 3
  2. 正常操作五步:Request → Pre-prepare → Prepare → Commit → Reply,只有 Pre-prepare 由主节点单独群发
  3. 拜占庭节点可以对不同节点说不同的话,各节点数到的票数因此可能不同
  4. 过了 Prepare 门槛只是进入 Commit,Commit 票凑不够照样中止
  5. 主节点崩溃后副本发 VIEW-CHANGE,新主节点按编号轮到下一台,收齐 2f+1 票后发 NEW-VIEW
  6. 检查点要 2f+1 个序号和摘要都相同的 CHECKPOINT 才稳定,之后可丢旧日志、给掉队节点补状态
L10a · L10a HotStuff:票交给 leader 攒成一张证书,三轮投票走完一个区块
  1. HotStuff:BFT 状态机复制,部分同步,n = 3f+1,每轮等 n−f = 2f+1 票
  2. QC = type + viewNumber + sig,sig 是 n−f 个部分签名合成的门限签名;VoteMSG = type + node + partialSig
  3. 星形拓扑:票只发给 leader,leader 广播 QC;正常流程 O(n²) → O(n),换 leader O(n³) → O(n²)(课件口径)
  4. 四阶段:New-View → Prepare → Precommit(存 prepareQC)→ Commit(设 lockedQC)→ Decide(执行 B 及未执行祖先),三轮投票
  5. leader 轮换:第 v 个视图的 leader = v mod N;收到最先到的 n−f 个响应就往下走(Optimistic Responsiveness)
L10b · L10b HotStuff 换 leader:新 leader 只挑最高的那张 QC
  1. PBFT 换 leader 贵:一次 view change 广播 O(n²),最坏连续 O(n) 个 leader 出错,合计 O(n³)
  2. leader 出问题时副本超时进入新视图,把自己最高的 prepareQC 放进 New-View 发给新 leader
  3. HotStuff 换 leader:新 leader 收 n−f 个 New-View,选视图号最高的 QC 作 justify,延伸它指向的块
  4. p.14 例子:C 报 view 5 的 prepareQC(X) 最高,D 广播 Prepare(Y, justify = prepareQC(X)),Y 延伸 X、不冲突
  5. 新 leader 不转发全部证明,只用一张 QC 当依据,换 leader 的消息数是线性的
L10c · L10c 为什么非得三轮投票:锁早了卡死,锁晚了分叉
  1. 安全性(safety)是坏事不会发生,比如诚实节点不会执行冲突的块;活性(liveness)是好事终将发生,比如系统总能继续出块
  2. 两阶段锁在 Commit 会丢活性(锁住的副本拒绝新提案,凑不够票);锁挪到 Decide 会丢安全性(不同副本执行不同块)
  3. 三阶段顺序:先存 prepareQC(证据)→ 再设 lockedQC(锁)→ 再执行,lock restricts future conflicting votes
  4. safeNode 规则:提案从 lockedQC 指向的块延伸出来,或提案的 justify QC 视图号比 lockedQC 更高,二者满足其一就投票
  5. 上锁前已有 2f+1 个副本存了 prepareQC(X),新 leader 收的 n−f 个 New-View 与之至少重叠 f+1 个,其中至少 1 个诚实
L10d · L10d 门限签名:2f+1 份部分签名合成一个签名
  1. Shamir 2-of-3:f(x) = s + a1·x mod p,份额 f(1)、f(2)、f(3);任意 2 份可恢复 s = f(0),1 份不行
  2. Schnorr:私钥 x,公钥 X = xG;随机 r,R = rG;c = H(R‖X‖m);s = r + cx;验证 sG = R + cX
  3. 2-of-3 门限 Schnorr(参与者 1、3):l1 = 3·2⁻¹,l3 = (−2)⁻¹,s = s1 + s3 = r1 + r3 + cx,验证 sG = R + cX
  4. 拉格朗日系数的验算:l1·x1 + l3·x3 = x,所以合并出的签名和用完整私钥签的一样
  5. QC 里只放一个签名,验证成本不随 n 增长;p.19–23 的 n 指椭圆曲线群的阶,不是节点数
L10e · L10e Chained HotStuff:每个新块顺手推进前面三个块
  1. Chained HotStuff:每个新块带上一块的 QC;One-Chain 更新 genericQC,Two-Chain 设 lockedQC,直接父子的 Three-Chain 提交最前面的块
  2. p.26 练习:B1 在 View 2/3/4 依次进入 Pre-Commit/Commit/Decide;处理 B3 时锁 B1;收到 B4 时执行 B1
  3. 收到 B4(带 QC3)时 B2 ← B3 成为 Two-Chain,lockedQC 前移指向 B2;B2、B3 尚未执行
  4. 提交看直接父子链接(b*.justify.node = b*.parent),不看视图号是否连续
  5. p.26 第 4 问:View 2 失败时按字面模型 B3.parent = B1,B1 在 B5(带 QC4)到来时提交;按论文空块规则,B1 作为 B3 的祖先一起执行
L11a · L11a Solana 总览:两种最终性和 PoS + PoH + Tower BFT
  1. 概率最终性:回滚可能随时间下降但存在,要等多个块(例:6 个块 ≈ 60 分钟),假设算力或权益占多数(51%)
  2. 确定最终性:除非 ≥ 1/3 节点恶意否则不回滚,几秒级确认,假设诚实节点 ≥2/3;例子 Cosmos(Tendermint)、Polkadot、Ethereum 2.0
  3. PoS 五类:Chain-based、Committee-based(VRF 随机选)、BFT-based(PoS 选出块者,BFT 确认)、Delegated(投票选固定数量代表)、Liquid(动态委托)
  4. Solana 性能:理论 TPS 65000,日常 4,000–60,000,出块 400–600 ms,手续费 < $0.001,主网验证者 2,340
  5. Solana 分工:PoS 选谁出块,PoH 给交易排序打时间,Tower BFT 投票确认;超过 2/3 质押 → Confirmed,32 块后 → Finalized
L11b · L11b leader 轮值表:按质押抽签,slot、tick、epoch 三层时钟
  1. 每个 epoch 开始前,用各验证者的质押权重和上一个 epoch 最后一个区块里的随机种子,跑确定性算法,一次排出下一个 epoch 的 leader 轮值表
  2. 抽中概率 = 质押占比:40,000 / 30,000 / 10,000 / 20,000 SOL,共 100,000 SOL → 40%、30%、10%、20%
  3. 时间参数:1 tick ≈ 6.25 ms;1 slot = 64 ticks ≈ 400 ms(一个 leader 出一个块);1 epoch = 432 000 slots ≈ 2 天
  4. 每个 slot 结束时,当前 leader 广播最后一个 PoH 哈希,交给下一个 leader
  5. slot 2 的 leader(1 slot = 10 tick,1 tick = 10 哈希)要从 slot 1 开头本地算满 100 个哈希,才开始收交易出块
L11c · L11c PoH:用一条哈希链当时钟
  1. PoH 是内置在验证者里的密码学时钟:用 SHA-256 链式哈希证明时间流逝,顺序生成、并行验证,不需要外部时间源
  2. 防作弊:每个哈希依赖上一个输出,不能并行;知道起始种子和哈希个数就能验证;插队或回滚要重算整条链,成本和真实时间成正比
  3. 交易混进哈希链:H12499 = H(H12498 || H(T1||T2||…));一个 tick 约 12500 个哈希;entry 记 Num_hashes、交易和结果哈希
  4. 区块 = 前一个区块的哈希 + 本 slot 的全部 entry + leader 签名;Block1 的前一块哈希为空
  5. 验证例子:1 tick = 2 个哈希,Entry1 {2, H2, Tx},Entry2 {2, H4, 空};验证者并行检查 H2′ = H2 和 H4′ = H4
L11d · L11d Tower BFT 投票:最重分叉和三级确认
  1. 出了块不等于成为共识块:验证者掉线、网络问题或恶意行为会让块接到非直接祖先上,形成分叉,所以要投票
  2. 最重分叉规则:验证者算每条分叉的质押加权总票数,选票最多的;p.24 中 A1 得 85 > A2 的 15,B1 得 95 > C1 的 5
  3. 三级确认:Processed(交易已在块里)→ Confirmed(超过 2/3 质押投票,乐观确认)→ Finalized(再叠 31 个保持 > 2/3 的 slot,回滚概率视为 0)
  4. 最终性算术:32 slots × 400 ms = 12.8 秒;Block N 里的交易在超多数对 Block N + 32 投票时不可逆
  5. p.31 练习:D3 分叉得 40 + 35 = 75 > 2/3 × 100,虽然最短但最重,D3 分叉有效;Tower BFT 不看链长
L11e · L11e Tower BFT 锁定:投了票就不能随便改
  1. 锁定机制:验证者投了一条分叉后想换到另一条,会被锁一段时间,期间不能投给别的分叉
  2. 锁定按 slot 翻倍:1、2、4、8、16 个 slot,乘 400 ms 得 400 ms、800 ms、1.6 s、3.2 s、6.4 s
  3. p.28 结论:Fork 1 上的验证者投完 E 后想换到 Fork 2,要等 6.4 s 的锁定时间
  4. 投票塔(Tower):验证者维护一个最多 32 张有效票的栈,新票放塔顶、最轻最容易撤;越往底下的票锁得越久,最长到 2^31 个 slot
  5. 锁定让反复横跳有代价:投得越久越深,改主意越慢,网络因此收敛到一条分叉