Ch3nyang's blog

home

home

person

about

hive

project

collections_bookmark

mindclip

rss_feed

rss

拜占庭容错

calendar_month 2021-11
archive 算法
tag blockchain tag byzantine-fault-tolerance

绝大多数区块链都被设计为去中心化的、由分布式计算机节点网络维护的数字账本。因此,区块链技术允许创建去信任的经济系统,即,可以在不需要中介的情况下执行透明和可靠的金融交易。

就像大多数分布式计算系统一样,加密货币网络的参与者需要定期就区块链的当前状态达成一致,这就是我们所说的达成共识。然而,以安全有效的方式就分布式网络达成共识绝非易事。

那么,如果某些节点可能出现故障或不诚实行为,分布式计算机节点网络如何就决策达成一致呢?这是所谓拜占庭将军问题,由此产生了拜占庭容错的概念。

拜占庭将军问题

问题假设拜占庭邻邦的将军们要攻打拜占庭,每个将军都有自己的军队,并且每个军队都位于拜占庭周围的不同位置。将军们需要就进攻或撤退达成一致。进攻或撤退都无所谓,只要所有将领达成共识就好——即一致同意一个共同的决定,以便协调执行。 因此,我们需要考虑以下要求:

  • 每个将军必须决定:进攻还是撤退
  • 决定一经作出,不得更改
  • 所有将军必须就同一决定达成一致,并以同步方式执行

由于每位将军都只能通过信使与另一位将军进行沟通,因此,消息很可能会以某种方式延迟、破坏或丢失。

此外,即使消息传递成功,别的将军可能会选择恶意行事,并发送欺诈性消息以混淆其他将军,从而导致兵败。

如果我们将困境应用到区块链的上下文中,每个将军代表一个网络节点,节点需要就系统的当前状态达成共识。换句话说,分布式网络中的大多数参与者必须同意并执行相同的操作。

我们使用更加 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) 给其它节点,其它节点收到请求后有两种选择:
    • 拒绝:如果 vn 之前出现过,但 dm 却不同,节点就会拒绝。因为主节点不会发送这样的消息。或者,这个消息的编号不在 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

  1. Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.
  2. Castro M, Liskov B. Practical byzantine fault tolerance[C]//OSDI. 1999, 99(1999): 173-186.
  3. Byzantine Fault Tolerance Explained. academy.binance.com,Dec. 2018, https://academy.binance.com/en/articles/byzantine-fault-tolerance-explained.

Comments

Share This Post