论文: Practical Byzantine Fault Tolerance

PBFT及其变种在区块链共识算法中有很广泛的应用, 所以搞清楚PBFT是很有必要的. 这正是那篇最初的PBFT文章.

1. 引言

前提: n个节点中 至多 向下取整(n-1)/3 的节点是恶意节点.

结果: 能够确保Liveness (网络持续运行, 不会卡死) 和 Safety (安全性, 不会被恶意节点主导)

之前的BFT算法的缺陷:

1. 假设消息是同步的 (危险, 因为相比于控制你的节点, DDOS让你的节点反应变慢更加简单, 轻松破坏"同步"假设)

2. 效率低

只读操作只需要一个round trip.

读写操作只需要两个round trip.

使用基于消息验证代码(Message Authentication Code)来进行高效的验证. public-key cryptography是Rampart的主要吞吐量瓶颈, 在 PBFT中只有当出现错误的时候才会使用.

2. 系统模型

异步分布式系统. 节点可能会让消息发送失败, 延迟, 重放或者乱序.

假设: 失效节点独立性. 即通过每个节点不同密码等各种手段, 确保一个节点失效不会引发别的节点失效, 相互独立.

目标: 防止/检测出信息造假, 重放, 损坏

手段:

1. public-key authentication

2. message authentication codes

3. message digests produced by collision-resistant hash functions.

什么是message digests

https://www.techopedia.com/definition/4024/message-digest

可以理解为checksum, 对文件内容进行hash, 如果文件内容被修改则hash改变, 用以验证文件是否损坏/被修改. MD5, SHA等算法都可以用作生成message digest的算法)

Cryptographic hash function

密码学中将输入数据作为message, 输出数据, 即hash value, 记做message digest = 消息摘要.

仅对message digest进行签名, 而不是对整个message进行签名.

什么是签名

非对称加密中使用私钥对消息+自己的身份进行加密, 外部节点使用公钥进行解密, 可以看到加密方的身份, 即为签名.

3. 服务属性

服务 = 状态 + 操作

PBFT不依赖于同步性来提供安全性, 但依赖于同步性来实现Liveness. (异步系统的共识是无法实现的, 即使只有一个坏节点, 也会导致整个系统无法达成共识).

保证Liveness的前提:

1. 至多 向下取整 (n-1)/3个节点是坏节点

2. delay(t)增长得比t快.delay(t)为消息发出时间t与消息被接收的时间之间的延迟.

结论

当f个节点为恶意节点, 全网需要至少3f+1个节点来确保安全性和liveness.

推理

由于有f个坏节点, 它们可能完全不回复消息, 所以我们要确保客户端只要接收到n-f个消息就足以做出判断. 不能依赖于更多的信息, 否则等待永不回复坏节点就意味着liveness被破坏.

考虑一个最差的情况: 那f个还未回复的节点是好节点, 收到的n-f个消息中有f个坏节点消息. 那么接到的好节点的消息实际上是 n-2f个, 坏节点消息是f个. 根据少数服从多数, 需要n-2f>f, 即n>3f.

综上, 全网总节点数n至少是3f+1才能确保安全性和Liveness.

4. 算法

一个应用于分布式系统, 在不同节点上运行状态完全一致的状态机. 每一个状态机维护当前的状态, 同时对外暴露一些操作. 客户端可以调用这些操作来修改整个网络的状态.

限制条件:

1. 状态机必须是确定性的, 即给定状态下的输出必须一致

2. 所有节点必须从同一个状态开始运行.

这两个条件用以确保: 所有节点能够对客户端请求的整体顺序(全序, 即所有信息的序号都是有序的)达成共识.

n=3f+1是下限. 如果n>3f+1, 并不会让系统更加健壮, 反而只会降低性能, 因为需要交换更多的信息)

重要概念: View.

节点运行过程中, 全网络的配置(configuration)是在不断变化的. 比方说现在的配置是A节点是主节点, 其余节点都是从节点, 那么一段时间后, 这个配置可能改变为B节点为主节点, 其余从节点.

我们将每一次的配置状态称为一个View. 整个网络就是不断在不同的View之间切换的.

记当前View的编号为v, 编号为p = v % n的节点就作为主节点, 其余作为从节点. 当主节点失效时, 进行View的切换.

算法流程:

1. 客户端发送请求到主节点, 调用"操作"

2. 主节点向从节点广播请求.

3. 所有节点(包含主节点?)都将自己的处理结果发送给客户端.

4. 客户端接收到f+1个来自不同节点的相同回复后, 就可以将这个相同回复作为操作的结果.

为什么是f+1个? 坏节点可以无限重放坏消息, 但是无法仿造别人的签名. 所以f个坏节点能产生的带不同签名的坏回复至多f个. 那么f+1个相同的消息就必然是好节点发出的.

4.1 客户端

客户端c将操作o发送到主节点, 消息记做 <REQUEST, o, t, c>sigma_c 其中, o是操作, t是时间戳, c是客户端编号.

节点直接将操作结果发送给客户端, 记做<REPLY, v, t, c, i, r>sigma_i. 其中, v是View编号, t是请求的时间戳, c是客户端编号, i是节点编号, r是操作结果.

客户端接收到f+1个, 带有相同t和r, 但是不同节点编号的消息后, 就将r作为操作结果.

如果客户端在一段时间内没有接收到足够的回复(可能因为主节点没能广播成功等原因), 它就自己广播请求到所有节点.

如果节点已经处理过这个请求, 直接重发上一次的回复. 否则, 如果是从节点, 它要将这个消息转发给主节点. 如果从节点发现主节点还不广播消息, 从节点就会怀疑主节点坏了. 这样的从节点一旦达到一定数目, 就进行View变更, 换掉主节点.

4.2 操作

每一个节点的状态, 包含:

1. 整个服务的状态.

2. 消息日志(messagelog)

3. 一个代表节点当前view的整数

主节点p接收到客户端请求m后, 使用一个具有三阶段的协议进行原子性的广播操作. 如果请求太多, 主节点会将请求buffer起来稍后再处理.

三阶段分别为

1. pre-prepare

2. prepare

3. commit

其中,

pre-prepare和prepare是用来确保同一个View中的请求是全排序的, 即使主节点是坏的.

prepare和commit是用来确保所有View中的请求整体都是全排序的.

pre-prepare阶段, 主节点对请求m编号为n, 将消息广播到所有从节点, 同时加入自己的message log. 消息为<<PRE_PREPARE, v, n, d>sigma_p, m>, 其中v是View编号, m是请求信息, d是m的digest.

(那m的请求信息是啥????)

此pre-prepare消息用作消息m在View v中被编号为n的证明.

注意, 请求的内容并没有放在pre-prepare消息中, 这样pre-prepare消息就非常小, 如此一来:

1. 将排序的协议和广播请求的协议解耦合

2. 我们可以用适合短消息的协议来发送pre-prepare消息, 而用适合长消息的协议来发送真正的请求.

满足以下条件时, 从节点会接受pre-prepare消息:

1. 请求和pre-prepare消息的签名都正确, d是m的digest

2. 从节点在View v中.

3. 它没接收过同在View v中且编号同为n, 但是digest不一样的pre-prepare消息

4. 编号n在下限h和上限H之间. (这是为了避免坏的主节点通过设置一个超大的n来穷尽编号)

从节点若不同意接受pre-prepare消息就什么都不做.

若同意接受pre-prepare消息<<PRE_PREPARE, v, n, d>sigma_p, m>, 则进入"prepare"阶段:

广播<PREPARE, v, n, d, i>sigma_i到所有节点; 将pre-prepare和prepare消息都加入到message log.

节点(包含主节点)接收到prepare消息后, 进行验证: 签名正确; View编号和节点当前View编号一致; 编号n在h和H之间. 验证通过就将prepare消息加到message log.

当且仅当节点i将如下消息插入到message log后, 我们才认为节点进入准备完毕状态, 记做prepared(m, v, n, i).

1. 请求m

2. 针对m, v, n的pre-prepare消息

3. 2f个来自不同从节点的对应于pre-prepare的prepare消息(算上自己的那个prepare消息). 如何验证对应关系? 通过v, n和digest.

**为什么是2f个****? **

因为prepare消息主节点不参与发送, 这样全网3f+1个节点刨去主节点和恶意节点(f+1)个, 剩下的是2f个好节点.

[prepared谓词]

进入准备完毕状态后, 节点i进入commit阶段, 广播消息<COMMIT, v, n, D(m), i>sigma_i到所有节点.

节点接收到commit消息后, 进行验证: 签名正确; View编号和节点当前View编号一致; 编号n在h和H之间. 验证通过就将commit消息加到message log.

[committed, committed-local谓词]

如果有f+1个好节点进入到prepared(m, v, n, i)状态, 则记为commited(m, v, n)状态

如果节点i在prepared(m, v, n, i)状态下接收到了2f+1个来自不同节点(包含自身)的commit消息, 则进入committed_local(m, v, n, i)状态. 验证commit和pre-prepare的关联性通过View v, 编号n和digest.

结论: 一旦有一个节点进入committed-local(m, v, n, i)状态, 则全网进入committed(m, v, n)状态.

PBFT

流程图解释:

编号0是主节点, 3是坏节点. 1和2是从节点.

1. 客户端发送request给主节点

2. pre-prepare. 主节点广播pre-prepare消息给从节点.

3. prepare

4. 从节点广播prepare消息给所有节点.

5. 节点接收到2f个prepare消息(算上自己)后进入commit状态.

6. commit

7. 所有节点广播commit消息

8. 节点接收到2f+1个commits(算上自己)后, 进入committed-local状态, 开始执行操作并将结果回复给client.

4.3 垃圾回收

本章核心概念, checkpoint.

节点必须保持消息保存在message log中, 直到它知道这个消息已经被f+1个节点执行, 而且它可以在view-change的时候向其他节点证明这一点(被f+1节点执行).

每次操作都生成proof太耗费资源. 节点只有在一定请求数目之后才会生成proof. 将运行这一系列操作后得到的状态, 命名为 checkpoint. 一个有proof的checkpoint被称为stable checkpoint.

记checkpoint的编号 = 该checkpoint的最后一个请求的编号

节点保存多个状态:

1. 最近一个stable checkpoint

2. 若干个不stable的checkpoint

3. 目前节点自身的状态.

checkpoint的正确性验证方法如下:

1. 节点i创建checkpoint之后, 向其他节点广播<CHECKPOINT, n, d, i>_sigma_i. 其中: n是此checkpoint的编号, d是该checkpoint的digest.

2. 每个节点将收到的checkpoint消息保存到message log中.

3. 当节点收到2f+1个对应于同一个n和d的, 不同的节点发出的checkpoint消息后, 这2f+1个消息就可以作为checkpoint的proof.

新的编号为n的stable checkpoin产生后, 节点就可以将自己保存的所有编号≤n的pre-prepare, prepare, commit消息从log中丢弃.

checkpoint协议还会修改前文提到的编号的上下界h和H. 新的下界h等于最近一个stable checkpoint的编号 (即该checkpoint的最后一个请求编号);上界H=h+k, 其中k要足够大, 以避免节点等待checkpoint变成stable的. 举例来说, 如果每100个请求一个checkpoint, 那k可以是200.

4.4 View-change

view-change存在的意义: 主节点坏掉了, 更换view(即更换主节点), 以此来保证全网的liveness.

从节点触发View Change

从节点会通过timeout来决定是否进行view-change. 从节点接收到请求后就会开启timer, 如果timeout时间内处理完请求则停止timer, 否则就会进行view-change, 从v到v+1.

从节点广播View Change

此时从节点将不再接受消息, 广播<VIEW-CHANGE, v+1, n, C, P, i>_sigma_i消息到所有节点.

其中:

n是节点i的最近一次stable checkpoint "s"的编号.

C是用来证明s合法的那2f+1个checkpoint消息.

P是一个包含若干个Pm的集合. 其中Pm的定义: 对于编号大于n且已经在节点i prepared的消息m, Pm包含一个合法的pre-prepare消息(不带对应的client消息)和2f个对应的, 由不同节点签名的prepare消息(v, n, D(m)要一样)

新的主节点上位

View v+1的主节点p接收到2f个来自不同其他节点的view-change消息后, 就广播<NEW-VIEW, v+1, V, O>_sigma_p到所有节点.

其中:

V: 集合{p接收到的view-change消息, p发送(或者应该发送)的对于v+1的view-change消息} 后者不就是本消息么?

O: 一个包含若干pre-prepare消息的集合(不顺带请求), 包含如下内容:

1. 主节点从V中找到

2. min-s, 即最近一次stable checkpoint的编号.

3. V中所有prepare消息的最大的编号max-s.

4. 对min-s和max-s之间的每个编号n, 主节点创建一个新的pre-prepare消息, 用于View v+1. 两种情况:

5. V中的某个编号为n的view-change消息, 其P集合不为空. 这种情况下, 主节点创建一个新的pre-prepare消息<PRE-PREPARE, v+1, n, d>_sigma_p, 其中d是V中pre-prepare message????

6. 其P集合为空. 主节点创建一个新的pre-prepare消息<PRE-PREPARE, v+1, n, d^null>_sigma_p, 其中d^null是一个特殊的null请求的digest. 该操作什么都不做.

然后, 主节点将O中的信息插入到log中. 如果min-s大于它最近一个checkpoint的编号, 主节点要计算编号为min-s的checkpoint的proof, 并将其插入到log中, 然后按照4.3中所讲进行垃圾回收.

至此, 主节点正式进入View v+1, 可以接受关于v+1的消息.

从节点接受新的主节点

如果从节点接受的new-view消息满足如下条件

1. 签名合法

2. V中的view-change消息合法.

3. O合法 (算法类似于主节点创建O的算法)

从节点会将这些消息加入到log中(跟上一段的主节点操作一样), 然后对于O中的每一个pre-prepare消息, 广播对应的prepare消息到所有节点并插入log, 正是进入View v+1.