拜占庭容错
绝大多数区块链都被设计为去中心化的、由分布式计算机节点网络维护的数字账本。因此,区块链技术允许创建去信任的经济系统,即,可以在不需要中介的情况下执行透明和可靠的金融交易。
就像大多数分布式计算系统一样,加密货币网络的参与者需要定期就区块链的当前状态达成一致,这就是我们所说的达成共识。然而,以安全有效的方式就分布式网络达成共识绝非易事。
那么,如果某些节点可能出现故障或不诚实行为,分布式计算机节点网络如何就决策达成一致呢?这是所谓拜占庭将军问题,由此产生了拜占庭容错的概念。
拜占庭将军问题
问题假设拜占庭邻邦的将军们要攻打拜占庭,每个将军都有自己的军队,并且每个军队都位于拜占庭周围的不同位置。将军们需要就进攻或撤退达成一致。进攻或撤退都无所谓,只要所有将领达成共识就好——即一致同意一个共同的决定,以便协调执行。 因此,我们需要考虑以下要求:
- 每个将军必须决定:进攻还是撤退
- 决定一经作出,不得更改
- 所有将军必须就同一决定达成一致,并以同步方式执行
由于每位将军都只能通过信使与另一位将军进行沟通,因此,消息很可能会以某种方式延迟、破坏或丢失。
此外,即使消息传递成功,别的将军可能会选择恶意行事,并发送欺诈性消息以混淆其他将军,从而导致兵败。
如果我们将困境应用到区块链的上下文中,每个将军代表一个网络节点,节点需要就系统的当前状态达成共识。换句话说,分布式网络中的大多数参与者必须同意并执行相同的操作。
我们使用更加 formal 的语言来定义这一问题:
给定一个包含 \(n\) 个节点的系统,其中 \(t\) 个是不诚实的,并假设所有节点之间只有点对点通道。 每当一个节点 A 尝试广播一个值 \(x\) 时,允许其他节点相互讨论并验证 A 广播的一致性,并最终确定一个共同的值 \(y\)。拜占庭容错系统遵循以下原则:
- 在 A 是诚实的情况下,所有诚实的节点都同意 \(x\) 的值
- 在所有情况下,所有诚实的节点都同意相同的值 \(y\)
拜占庭容错只关心广播一致性,即当一个节点向其他节点广播相同的值时,它们都接收到完全相同的值;而在广播不一致的情况下,其他节点同意一个共同的值。这种容错不能验证值本身的正确性。
拜占庭容错
解决方案要求超过 \(\frac{2}{3}\) 或者一半的节点都同意一个相同的消息,也就是大多数原则。它考虑了可能伪造消息的场景,只要不忠的将军的数量少于将军的三分之一,它就会是拜占庭容错的。
但是,假设我们有一个叛国的指挥官A,和两个中尉B和C:当A告诉B进攻,却让C撤退,那么当B和C互相确认时,B和C都不能找出谁是叛徒,因为另一个中尉可能伪造了据称来自 A 的消息。可以证明,如果 \(n\) 是将军总数,\(t\) 是叛徒的数量,那么只有当 \(n > 3t\) 并且通信同步时,才能够实现拜占庭容错。51% 攻击就是利用的这个原理。
此外,解决方案需要不可伪造的消息签名(通常是非堆成公钥密码体制)。事实上,即使是 CRC 也是一种高效且有效的拜占庭容错机制。
PBFT
拜占庭将军问题最早是由 Leslie Lamport 在The Byzantine Generals Problem 中提出的。若将军总数 \(n>3f\) ,背叛者为 \(f\) 或者更少时,忠诚的将军可以达成命令上的一致,即 \(3f+1\leq n\) 。算法复杂度为 \(O(n^{f+1})\)。
Miguel Castro 和 Barbara Liskov 的 Practical Byzantine Fault Tolerance 提出 PBFT 算法,该算法将复杂度降低到了 \(O(n^2)\)。
我们首先定义几个量:
-
v
:view,也就是当前主节点编号 -
n
:客户端对主节点请求的编号 -
d
:消息内容摘要 -
m
:消息 -
i
:节点编号 - checkpoint:某节点正在处理的请求的编号
- stable checkpoint:当前所有节点达成共识的消息的最大编号,也称 low level
- high level:low level + L,L 是一个设定的值
PBFT 主要有以下几步:
- 客户端发送请求给主节点
- pre-prepare:主节点广播请求
((pre-prepare,v,n,d),m)
给其它节点,其它节点收到请求后有两种选择:- 拒绝:如果
v
和n
之前出现过,但d
和m
却不同,节点就会拒绝。因为主节点不会发送这样的消息。或者,这个消息的编号不在 low level 和 high level 之间,则也直接拒绝。 - 接受:其余情况,节点执行下一步
- 拒绝:如果
- prepare:节点向其它节点发送
(prepare,v,n,d,i)
同时接收其它节点发送的消息,当收到 \(2f\) 个不同消息(不包括自己)后,停止发送。如果未能收到足够的消息,则验证失败。 - commit:节点向其它节点发送
(commit,v,n,d,i)
同时接收其它节点发送的消息,当收到 \(2f+1\) 个消息(包括自己)后,停止发送,达成共识,执行请求。如果未能收到足够的消息,则验证失败。
如果主节点挂了或者不受信任了,则需要更换主节点。我们先定义几个量:
-
v
:上一个 view 的编号 -
n
:stable checkpoint 编号 -
C
:\(2f+1\) 个节点的 checkpoint 集合 -
P
:编号大于 \(n\) 且完成 prepare 步骤的消息集合 -
V
:新的主节点接收到的 view 为 \(v+1\) 的 view-change 消息集合 -
O
:pre-prepare 消息集合
此时会执行以下步骤:
- view-change:某节点发现主节点挂了,于是向其它节点广播
(view-change,v+1,n,C,P,i)
同时接收其它节点发送的消息,当收到 \(2f\) 个不同消息(不包括自己)后,停止发送。如果未能收到足够的消息,则验证失败。 - new-view:向其它节点广播
(new-view,v+1,V,O)
同时接收其它节点发送的消息,验证O
是否正确。 -
v
=v
+1,处理O
中的消息
综上,PBFT 其实是这么一个过程:将军向士兵发送命令时,当士兵认为将军的命令是有问题时,士兵会拒绝执行。就算士兵认为将军的命令是对的,士兵还会问下其它士兵将军的命令是否是对的,只有大多数士兵都认为将军的命令是对的时候,士兵才会去执行命令。如果将军挂了,或者大多数士兵都认为将军不诚实时,士兵们也会重新选择将军。
reference
- Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.
- Castro M, Liskov B. Practical byzantine fault tolerance[C]//OSDI. 1999, 99(1999): 173-186.
- Byzantine Fault Tolerance Explained. academy.binance.com,Dec. 2018, https://academy.binance.com/en/articles/byzantine-fault-tolerance-explained.
Comments