← COMP5567 全部讲次
L01b-2 · 第 1 周

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

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

一句话版

区块链是一本复制到很多节点上的账,每个节点各存一整本,正常节点手里的那本必须一样。难就难在网络里有两种坏节点:一种会停机,一种会撒谎。这门课只研究技术栈里的共识层,也就是「有坏节点时,大家怎么还能认同一本账」。

篡改和最长链见上一页 L01b。

先认识这几个词

词 全称 / 读法 一句人话
分布式账本 distributed ledger 同一本账复制到很多节点上,每个节点一整本
一致视图 consistent view 任意两个正常节点对同一块的内容回答一样
崩溃故障 crash fault 节点停机,之后什么都不发
拜占庭故障 Byzantine fault 节点可以任意乱来,包括发假消息、对不同人说相反的话
共识层 consensus layer 技术栈里决定「谁能写、写什么算数」的那一层
最终性 finality 一笔记录上链以后,还会不会被推翻

一个类比:六家分店共用一本进货账

一家连锁店有六家分店,每家店里都放着一本完整的进货账,内容应该一模一样。总部规定:任何一家店问「第几页写了什么」,其他店给出的答案都得相同。

麻烦来自两种店。一种是停电关门的店,它不再回任何消息,别人也说不准它是关了门还是电话占线。另一种是店长在捣鬼,他对东边的店说「这批货到了」,对西边的店说「没到」。

对付关门的店,等一等、多问几家就行。对付捣鬼的店难得多,因为它说的话本身就是假的。

类比在哪里失效:

  • 分店之间可以打电话核对,节点之间的消息会延迟、乱序、丢失。
  • 连锁店有总部可以拍板,区块链网络里没有总部,只能靠协议让正常节点自己达成一致。

从零讲起

1. 分布式账本:每个节点一整本

它解决什么问题

前几页一直说「全网共用一本账」。落到机器上,这本账到底存在哪?这一节说清楚:它被完整地复制到每个节点上,而这门课要保证的,是正常节点手里的那几份始终一样。

直觉

「分布式」很容易被理解成「一人保管一部分」。这里的分布式指复制:每个节点各存一整本,从第一块到最新一块全都有。

所以网络里有多少个节点,就有多少份账本。理想状态下它们逐字相同。只要其中两份对某一块的说法不同,系统就出了问题。

一步一步看

目标:看账本存在哪里,以及「一致视图」要求哪几个节点的账本一样。

  1. 课件画了六个节点,节点之间用网络连着。

  2. 其中一个是恶意节点,可能乱说;一个是离线的故障节点,什么都不发;其余四个是正常节点。

  3. 四个正常节点各存一整本账,从 #1 一直到最新的块。

    六个节点用细线连成一张网:四个青绿框是正常节点,各写着从第 1 块到第 800000 块的一整本账;右上黑框是恶意节点,可能乱说;右下灰色虚框是离线节点,什么都不发;右侧注明四个青绿框的账本必须一样

  4. 一致视图的意思是:任取两个正常节点,问它们第 800000 号区块里有什么,回答必须完全一样。

怎么判断

判断一个系统有没有做到一致视图:

  1. 只看正常节点,坏节点的账本不算。
  2. 任取两个正常节点,问同一块的内容。
  3. 回答完全一样,才算一致。

意思是:一致的要求只针对正常节点。难的地方在于,三件现实情况同时存在:网络消息会延迟、乱序、丢失;节点随时可能宕机;还可能有节点故意发假消息。

常见误解

把「分布式」理解成每人保管一部分

这里的分布式指复制,每个节点存的是从创世块到最新块的完整一本。六个节点就有六份互为副本的账本。

以为「安全」就是无法被攻击

安全是有条件的:坏节点不超过某个比例时,正常节点仍能达成一致,已经确认的历史不会被改写。超过了,保证就不成立。这个比例是多少,是后面几讲要推导的结论。

试一下

网络里有八个节点,其中一个离线,一个恶意。哪几个节点的账本必须一致?

剩下的六个正常节点。离线的不发消息,恶意的可能乱说,一致的要求不包括它们。

2. 两类故障:崩溃和拜占庭

它解决什么问题

上一节的六个节点里有两个坏节点,它们坏的方式不一样。后面每学一个协议,第一个要问的就是它对付的是哪一类故障。这一节把两类分清楚。

从哪来(补充)

「拜占庭故障」这个名字来自 Leslie Lamport、Robert Shostak 和 Marshall Pease 在 1982 年论文里的一个寓言:几位将军围城,要商量进攻还是撤退,其中有叛徒会传假话。寓言里原本写的是阿尔巴尼亚将军,后来才改成拜占庭。

出处:Wikipedia: Byzantine fault

直觉

崩溃故障像一个人突然晕倒:他不说话了,但他之前说的都是真的。别人的麻烦只是分不清他是晕倒了还是说话慢。

拜占庭故障像一个人在撒谎:他照常说话,说的内容却可能是编的,还能对不同人说不同的话。你没法只靠「有没有收到他的消息」来判断他好坏。

一步一步看

目标:分清两类坏节点:一类只是不说话,一类会对不同节点说不同的话。

  1. 崩溃故障:节点 X 停机,之后对谁都不发消息。A 和 B 只知道收不到 X 的消息,分不清它是挂了还是只是慢。

    崩溃故障:左边灰色虚框的节点 X 已停机,两条虚线箭头分别指向节点 A 和节点 B,箭头上都写着没有消息,下方说明 A 和 B 分不清 X 是挂了还是只是慢

  2. 拜占庭故障:节点 X 照常在线,对 A 说「Record5 存在」,同时对 B 说「Record5 不存在」。A 和 B 都收到了消息,但消息本身是编的。

    拜占庭故障:左边青绿框的节点 X 发出两条青绿箭头,给节点 A 的写着 Record5 存在,给节点 B 的写着 Record5 不存在,下方说明 A 和 B 都收到了消息,但光看收没收到判断不了

  3. 两类放在一张表里对照:

    崩溃故障 crash fault 拜占庭故障 Byzantine fault
    行为 节点停机,之后什么都不发 节点照常在线,但发送任意内容,包括假消息
    例子 断电、进程崩溃、网线被拔 对节点 A 说「这笔转账存在」,同时对节点 B 说「不存在」
    难在哪 要判断「它是挂了,还是只是慢」 收到的消息本身就可能是编的
    处理它的协议 2PC、3PC、Paxos、VR、Raft PBFT、HotStuff

怎么判断

遇到一个坏节点,按两问归类:

  1. 它还在发消息吗?不发了,是崩溃故障。
  2. 它发的消息可能是假的,或者对不同节点说法不同吗?是,就是拜占庭故障。

意思是:崩溃故障的节点只会少说,拜占庭故障的节点会乱说。容忍拜占庭故障需要更多节点、更多轮消息交换,能容忍的坏节点比例也更低。陌生人组成的开放区块链网络必须假设有人撒谎,所以必须抗拜占庭故障。

常见误解

以为会停机的节点也算拜占庭故障,反正都是坏了

停机属于崩溃故障。拜占庭故障的特点是它还在发消息,而且内容不可信。两类用的协议不同:崩溃故障用 2PC、3PC、Paxos、VR、Raft,拜占庭故障用 PBFT、HotStuff。

试一下

一个节点的网线被拔了,之后再也没发过消息。另一个节点对一半节点说「我投赞成」,对另一半说「我投反对」。两者各属于哪类故障?

第一个是崩溃故障,它只是停了。第二个是拜占庭故障,它照常在线,却对不同节点说相反的话。

3. 五层结构与全课主线

它解决什么问题

区块链牵涉的东西很多:密码学、网络、共识、智能合约。这门课不可能全讲。课件用一张分层图标出了本课只管的那一层,再用一条主线说明各讲之间怎么接起来。

直觉

把区块链技术栈想成一栋五层楼。最底下是机器和容器,往上是数据怎么存,再往上是节点怎么通信,然后是大家怎么达成一致,最顶上是给用户用的应用。

这门课只住在「达成一致」那一层。下面几层的东西(哈希、签名、Merkle 树)当工具用,不深究;上面的智能合约和应用不考。

一步一步看

目标:看本课在五层里只管哪一层,以及各讲沿哪条主线一步步接起来。

  1. 自上而下,五层依次是:应用与表示层(智能合约、Chaincode、DApps、UI)、共识层(PoW – PoS – PBFT)、网络层(P2P、分布式通信)、数据层(Merkle 树、交易、签名)、硬件与基础设施层(虚拟机、容器、消息)。

    区块链技术栈五层结构表,自上而下是应用与表示层、共识层、网络层、数据层、硬件与基础设施层,每层列出对应技术,红色 Focus of this subject 的引线指向中间的共识层一带
    图片来源:COMP5567 Lecture_1-Blockchain-introduction.pdf, p.31
  2. 共识层旁边标着 Focus of this subject,这一层就是本课的全部战场。

  3. 共识这件事本身要一步步搭起来。先能给事件排序,才能保证消息按正确顺序送达;有了正确顺序,才能就一笔交易决定提交还是中止;最后才能在有坏节点时达成共识。

    全课主线四个框从左到右依次相连:事件排序(第 2 讲,时钟)、消息正确顺序(第 3 讲,广播)、提交或中止(第 6 讲,2PC/3PC)、共识(第 7 到 10 讲),最后一框用青绿色标出,下方说明前一层没学扎实后一层学不动

  4. 所以第 2 讲讲时钟,第 3 讲讲广播,后面再讲提交协议和共识协议,每一讲都用到前一讲的结论。

怎么判断

拿到一道题,先问它在问哪一层:

题目在问 属于哪层 本课管不管
智能合约怎么写 应用与表示层 不管
谁能写下一块、分歧时听谁的 共识层 管
节点之间怎么传消息 网络层 当背景
Merkle 树、签名怎么算 数据层 当工具

意思是:问的不是共识层,就不是本课的重点。共识层里还有一条贯穿全课的对比线:比特币这类是概率最终性,PBFT 这类是确定性最终性。

常见误解

以为密码学细节要深挖

数据层的哈希、签名、Merkle 树在本课只当工具用,不深究。上面的智能合约和 DApp 不考。

以为各讲之间是并列的,可以跳着学

主线是递进的:事件排序 → 消息正确顺序 → 原子提交 → 共识,每层建立在前一层之上。时钟和广播没学扎实,后面的 PBFT 一定学不动。

试一下

五层里,Merkle 树在哪一层?PoS 在哪一层?DApp 在哪一层?

Merkle 树在数据层,PoS 在共识层,DApp 在应用与表示层。三者里只有 PoS 是本课重点。

把它们串起来

前几页讲的是比特币这一个系统,这一页把它放回更大的图里。

区块链首先是一本复制到每个节点上的账,正常节点手里的那几份必须一样。让它们一样很难,因为网络会延迟、乱序、丢消息,还有两类坏节点:崩溃的只会少说,拜占庭的会乱说。安全只在坏节点不超过某个比例时成立。

这些问题都落在技术栈的共识层,也就是本课唯一研究的一层。要在这一层上做出东西,得按主线一步步来:事件排序、消息正确顺序、原子提交、共识。下一讲从第一步「事件排序」开始。

课件里的坑

  • 本讲课件未发现错误。p.30 的「分布式」最容易看错:它指每个节点存一整本的复制,不指一人保管一部分。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写两类故障的对照表,重点是「行为」和「处理它的协议」两行;再背出五层结构和本课所在的那一层;然后做两道课件例题、完整例题和变式题;最后用闪卡把 p.35 之后的各讲剧透过一遍。

必背

  1. 分布式账本的「分布式」指复制:每个节点各存一整本完整的账,正常节点之间必须看到一致的内容。
  2. 崩溃故障只会停机、之后什么都不发,由 2PC、3PC、Paxos、VR、Raft 处理;拜占庭故障可以任意偏离协议,由 PBFT、HotStuff 处理。
  3. 「安全」是有条件的:坏节点不超过某个比例时,正常节点仍能达成一致;超过了,保证就不成立。
  4. 共识层(PoW – PoS – PBFT)是本课唯一战场;概率最终性与确定性最终性是贯穿全课的对比线索。
  5. 全课主线:事件排序 → 消息正确顺序 → 原子提交 → 共识,每层建立在前一层之上。

课件例题

例 1(课件 p.30):六个节点的分布式账本,哪些账本必须一致

见下方完整例题。

例 2(课件 p.39):UTXO 表里的余额怎么变

题面:这是第 4 讲的预告页。Block 18 里 Alice 得到 12.5(无输入,输出给 PKAlice)。Block 19 里 Bob 得到 12.5。Block 20 里 Tom 得到 12.5;同一块里还有一笔 Alice → Bob 转 10,带 Alice 的签名,输入是 18[0],输出两条:PKBob 10、PKAlice 2.5。问:Block 18、19、20 之后三人余额各是多少?

提示

链上没有「余额」字段。把每个人名下还没被花掉的输出加起来,就是他的余额。注意 18[0] 被花掉以后就不再算了。

解答

Block 18 之后:Alice 12.5,Bob 0,Tom 0。Block 19 之后:Alice 12.5,Bob 12.5,Tom 0。

Block 20 那笔转账花掉 18[0] 这个 12.5 的输出,产出两条新输出:给 Bob 10,找零给 Alice 2.5。原来那个输出被整个花掉。再加上 Tom 的 12.5,Block 20 之后是 Alice 2.5,Bob 22.5,Tom 12.5。

链上并没有「余额」字段,余额是把一个人所有未花费输出加起来算出来的。

完整例题

题面(课件 p.30):图上有六个节点,节点之间用网络相连。右上那个被标为恶意节点(malicious),右下那个挂着 OFFLINE 图标,是离线的故障节点(faulty),其余四个是正常节点。问:(1) 这个系统里一共有几份账本?(2) 哪些账本必须一致,「一致」具体指什么?(3) 两个坏节点各属于哪类故障,分别会给正常节点带来什么麻烦?

六个蓝色方块节点围成六边形,彼此用网络连线相连,每个节点旁画一个用户头像;右上节点旁站着一个红色戴帽黑衣的恶意者图标(malicious),右下节点旁挂着 OFFLINE 断网图标(离线故障节点),其余四个节点旁是普通用户
图片来源:COMP5567 Lecture_1-Blockchain-introduction.pdf, p.30

解法:

  1. 数账本:分布式指复制,每个节点存一整本完整的账,所以一共有 6 份互为副本的账本。
  2. 谁必须一致:只要求 4 个正常节点的账本一致,恶意节点和离线节点的不算。
  3. 一致的含义:任取两个正常节点,问它们第 800000 号区块里有什么,回答必须完全一样。
  4. 离线节点:它停机后什么都不发,属于崩溃故障。正常节点的麻烦是分不清它挂了还是只是慢,等多久才放弃它要由协议来定。
  5. 恶意节点:它照常在线,却可能对 A 说「这笔转账存在」、对 B 说「不存在」,属于拜占庭故障。正常节点不能只靠「收没收到」来判断,收到的消息本身可能是编的。
  6. 收尾:两类故障用的协议不同,崩溃故障用 2PC、3PC、Paxos、VR、Raft,拜占庭故障用 PBFT、HotStuff。开放的区块链网络必须按拜占庭故障来设计。

要点:「分布式 = 复制」「只要求正常节点一致」「两类坏节点分开归类」三件事写全。

答题格式:先写账本份数和一致的定义,再逐个给坏节点归类并说明麻烦在哪,最后点出对应的协议。

变式题(先自己做)

自编情境:一个网络有 7 个节点。节点 P 断电了;节点 Q 对 A 说「Record5 存在」,对 B 说「Record5 不存在」;其余节点都正常。

(a) 有几个正常节点?它们之间要满足什么? (b) P 和 Q 各属于哪类故障? (c) 有人说「只要用 Raft,就能同时应付 P 和 Q」,这话对吗?

提示

(a) 先把坏节点去掉再数。(b) 对照两类故障的行为那一行。(c) 看对照表最后一行,Raft 处理的是哪一类。

判分点与答案(非官方评分标准)

判分点:① (a) 正常节点数正确并写出一致视图的含义;② (b) 两个定性都对且给出理由;③ (c) 指出 Raft 只处理崩溃故障。

(a) 7 − 2 = 5 个正常节点。任取其中两个,问同一块的内容,回答必须完全一样。

(b) P 是崩溃故障,它只是停了,之后什么都不发。Q 是拜占庭故障,它照常在线,却对不同节点说相反的话。

(c) 不对。Raft 属于处理崩溃故障的那一组(和 2PC、3PC、Paxos、VR 一起),应付不了会说谎的 Q。要容忍 Q 这样的节点,得用 PBFT、HotStuff 这类抗拜占庭故障的协议。

闪卡自测

1. 分布式账本里的「分布式」指什么?

指复制:每个节点各存一整本完整的账,从创世块到最新块都有,而不是一人保管一部分。理想状态下各份逐字相同(p.30)。

2. 「一致视图」的精确含义是什么?

任取两个正常节点,问它们第 800000 号区块里有什么,得到的回答必须完全一样(p.30)。

3. 崩溃故障和拜占庭故障的行为差别是什么?各由哪些协议处理?

崩溃故障是节点停机、之后什么都不发;拜占庭故障允许任意偏离协议,包括停止发送、选择性发送或对不同节点说相反的话。前者由 2PC、3PC、Paxos、VR、Raft 处理,后者由 PBFT、HotStuff 处理(p.30)。

4. 为什么开放的区块链网络必须抗拜占庭故障?

陌生人组成的网络必须假设有人会撒谎,只能容忍崩溃故障的协议应付不了会发假消息的节点(p.30)。

5. p.31 五层里,智能合约在哪一层?Merkle 树在哪一层?本课考哪一层?

智能合约在应用与表示层,Merkle 树在数据层,本课只考共识层(PoW – PoS – PBFT),课件在那一行标了 Focus of this subject(p.31)。

6. 全课主线的四步递进是什么?

事件排序(如向量时钟,L2)→ 消息正确顺序(如 CO-URB、TOB,L3)→ 提交或中止一笔交易(如 3PC,L6)→ 共识(L7–L10)。每一层都建立在前一层之上(p.35)。

7. UTXO 模型里,余额存在链上的哪个字段?

没有这个字段。余额是把一个人所有未花费输出加起来算出来的(p.39)。

8. PBFT 的三个子协议各在什么情况下运行?

Normal Operation 在系统正常时运行,核心三阶段是 Pre-prepare、Prepare、Commit;View Change 在检测到主节点故障时运行;Checkpointing 定期丢弃旧数据,比如清理旧日志(p.44)。

下一讲

L02a 把讨论对象从区块链抽象成「一组要维持一致状态的节点」,先补上分布式系统的基本属性和三种网络时序假设,再进入逻辑时钟。全课主线的第一环「事件排序」就从那里开始。

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

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。