分布式共识算法（拜占庭容错算法）的系列整理一：PBFT、PoW、PoS、DPos_分布式系统容错算法

五篇分布式共识系列文章合集：
分布式共识算法（拜占庭容错算法）的系列整理一：PBFT、PoW、PoS、DPos
分布式共识算法（故障容错算法）系列整理(二)：Bully、Gossip、NWR
分布式共识算法（故障容错算法）系列整理(三)：Paxos
分布式共识算法（故障容错算法）系列整理(四)：Raft
分布式共识算法（故障容错算法）系列整理(五)：ZAB

什么是分布式共识？

• 在多个节点均可独自操作或记录的情况下，使得所有节点针对某个状态达成一致的过程
• 本质是“求同存异”

一致性和共识的区别是什么？

• 一致性：分布式系统中的多个节点之间，给定一系列的操作，在约定协议的保障下，对外界呈现的数据或状态时一致的
• 共识：分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程
• 一致性强调结果，共识强调达成一致的过程，共识算法是保障系统满足不同程度一致性的核心技术

分布式共识的两个关键点是什么？

• 1.获得记账权
• 2.所有节点或服务器达成一致

拜占庭容错算法和非拜占庭容错算法

• 拜占庭将军问题描述的是最困难的，也是最复杂的一种分布式故障场景，除了存在故障行为，还存在恶意行为的一个场景。必须使用拜占庭容错算法（Byzantine Fault Tolerance，BFT）。还有：PBFT 算法，PoW 算法
• 在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法（Crash Fault Tolerance，CFT）。CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议

区块链是什么？

• 由包含交易信息的区块从后向前有序链接起来的数据结构
• 其中区块是指很多交易数据的集合，每个区块包括区块头和区块体
  • 区块体包括前一区块的哈希值、本区块的哈希值和时间戳
  • 区块体用来存储交易数据

PBFT

口信消息型拜占庭问题之解的局限

• 如果将军数为 n、叛将数为 f，那么算法需要递归协商 f+1 轮，消息复杂度为 O(n ^ (f + 1))，消息数量指数级暴增。 如果叛将数为 64，消息数已经远远超过 int64 所能表示的了
• 尽管对于签名消息，不管叛将数（比如 f）是多少，经过 f + 1 轮的协商，忠将们都 能达成一致的作战指令，但是这个算法同样存在“理论化”和“消息数指数级暴增”的痛点

过程

• 客户端向主节点发送请求，主节点收到请求后，执行三阶段协议
• 主节点进入预准备（Pre-prepare）阶段，构造包含客户端提议的值的预准备消息，并广播给其他从节点
• 从节点收到预准备消息后，进入准备（Prepare）阶段，并分别广播包含客户端提议的值的准备消息给其他节点
• 当某个节点收到 2f 个一致的包含客户端提议的值的准备消息后，会进入提交（Commit） 阶段，各节点分别提交消息给其它节点，告诉其它节点自己已经准备就绪
• 当某个节点收到 2f + 1 个验证通过的提交消息后，说明达成共识，可接受客户端提议的值，并发送执行成功的消息给客户端
• 客户端收到 f+1 个相同的响应消息时，说明节点已达成共识

达成共识的举例

• 场景
  • 先假设苏秦制定的作战指令是进攻，而楚是叛徒（为了演示方便）：
  • 
  • 注意，所有的消息都是签名消息，也就是说，消息发送者的身份和消息内容都是 无法伪造和篡改的（比如，楚无法伪造一个假装来自赵的消息）
• 首先，苏秦联系赵，向赵发送包含作战指令“进攻”的请求
  • 
• 当赵接收到苏秦的请求之后，会执行三阶段协议（Three-phase protocol）
• 赵将进入预准备（Pre-prepare）阶段，构造包含作战指令的预准备消息，并广播给其他将军（魏、韩、楚）
  • 
  • 注意：魏、韩、楚，收到消息后，不能直接执行指令，因为他们不能确认自己接收到的指令和其它人接收到的指令是相同的
• 接收到预准备消息之后，魏、韩、楚将进入准备（Prepare）阶段，并分别广播包含作战指令的准备消息给其他将军。比如，魏广播准备消息给赵、韩、楚（如图所示）。为了方便演示，我们假设叛徒楚想通过不发送消息，来干扰共识协商（你能看到，图中的楚是没有发送消息的）。
  • 
• 当某个将军收到 2f 个一致的包含作战指令的准备消息后，会进入提交（Commit） 阶段（这里的 2f 包括自己，其中 f 为叛徒数，在演示中是 1）
• 注：这时该将军（比如魏）还是不能执行指令，因为魏不能确认赵、韩、楚是否收到了 2f 个一致的包含作战指令的准备消息
• 进入提交阶段后，各将军分别广播提交消息给其他将军，也就是告诉其他将军，我已经准备好了，可以执行指令了
  • 
• 最后，当某个将军收到 2f + 1 个验证通过的提交消息后（包括自己，其中 f 为叛徒数，在演示中为 1），也就是说，大部分的将军们已经达成共识，这时可以执行作战指令了，那么该将军将执行苏秦的作战指令，执行完毕后发送执行成功的消息给苏秦
  • 
• 最后，当苏秦收到 f+1 个相同的响应（Reply）消息时，说明各位将军们已经就作战指令达成了共识，并执行了作战指令（其中 f 为叛徒数，在我的演示中为 1）
• 在这里，苏秦采用的就是简化版的 PBFT 算法。在这个算法中：
  • 可以将赵、魏、韩、楚理解为分布式系统的四个节点，其中赵是主节点（Primary node），魏、韩、楚是从节点（Secondary node）
  • 将苏秦理解为业务，也就是客户端
  • 将消息理解为网络消息
  • 将作战指令“进攻”，理解成客户端提议的值，也就是希望被各节点达成共识，并提交给状态机的值

几个注意点

• PBFT 算法是通过签名(或消息认证码 MAC)约束恶意节点的行为，即每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另一个节点的消息。最终，基于大多数原则(2f+1)实现共识的
• 最终的共识是否达成，客户端是会做判断的，如果客户端在指定时间内未收到请求对应的 f + 1 相同响应，就认为集群出故障了，共识未达成，客户端会重新发送请求
• PBFT 算法通过视图变更（View Change）的方式，来处理主节点作恶，当发现主节点在作恶时，会以“轮流上岗”方式，推举新的主节点
• 尽管 PBFT 算法相比口信消息型拜占庭之解已经有了很大的优化，将消息复杂度从 O(n ^ (f + 1)) 降低为 O(n ^ 2)，能在实际场景中落地，并解决实际的共识问题。但 PBFT 还是需要比较多的消息。比如在 13 节点集群中（f 为 4）一次共识协商需要 237 个消息，推荐在中小型分布式系统中使用 PBFT 算法
  • 请求消息：1
  • 预准备消息：3f = 12
  • 准备消息：3f * (3f - f) = 96
  • 提交消息：(3f - f + 1) * (3f + 1)= 117
  • 回复消息：3f - 1 = 11

PoW

PoW算法是什么

• 以每个节点或服务器的计算能力来竞争记账权的机制，即使用工作量证明机制的共识算法

工作量证明(Proof Of Work)是什么

• 请求方做了一些运算，解决了某个问题，然后把运算结果发送给验证方，进行核验，验证方根据运算结果，就能判断请求方是否做了相关的工作
• 这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则是比较简单的，易于验证的
• 

区块链如何实现 PoW 算法的

• 由区块头、区块体 2 部分组成的
  • 区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的
  • 区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易
• 拥有 80 字节固定长度的区块头，就是用于区块链工作量证明的哈希运算中输入字符串，只有通过双重 SHA256 哈希运算计算出的哈希值，只有小于目标值(target)，才是有效的，否则哈希值是无效的，必须重算，以此来证明自己的工作量
• 计算出符合条件的哈希值后，矿工就会把这个信息广播给集群中所有其他节点，其他节点验证通过后，会将这个区块加入到自己的区块链中，最终形成一串区块链

假设每个节点会划分多个区块用于记录用户交易，PoW算法获取记账权的原理是什么？

• 利用区块的index、前一区块的哈希值、交易的时间戳、区块数据和nonce值，通过SHA256计算出一个哈希值
• 判断前k个值是否都为0
  • 如果不是，递增nonce值，重新按照上述方法计算
  • 如果是，本次计算的哈希值为要解决的题目的正确答案
• 谁最先计算出正确答案，谁就获得这个区块的记账权
• 注：nonce值是用来找到一个满足哈希值的数字；k 为哈希值前导零的个数，标记了计算的难度，0 越多计算难度越大

PoW达成共识的过程，其本质是？

• 即获得记账权的节点将该区块信息广播给其它节点，其它节点判断该结点找到的区块中的所有交易都是有效且之前未存在过的，则认为该区块有效，并接受该区块

基于PoW的共识记账过程是怎样的？(以分散在世界各地的 5 台服务器为例，假设客户端A产生一个新的交易)

• 
• 1.客户端A产生新的交易，向全网进行广播，要求对交易进行记账
• 2.每个记账节点接收到这个请求后，将受到的交易信息放入一个区块中
• 3.每个节点通过PoW算法，计算本节点的区块的哈希值，尝试找到一个具有足够工作量难度的工作量证明
• 4.若节点D找到了一个工作量证明向全网广播。当且仅当包含在该区块中的交易都是有效且之前未存在过的，其它节点才会认同该区块的有效性
• 5.其它节点接收到广播信息后，若该区块有效，接受该区块，并跟随在该区块的末尾，制造新区块延长该链条，将被接受的区块的随机哈希值视为新区块的随机哈希值
• 核心：谁的计算能力强，获得记账权的可能性就越大。但必须保证其记 账的区块是有效的，并在之前未存在过，才能获得其他节点的认可

51%攻击是什么

• 算力越强，系统大概率会越先计算出这个哈希值。这也就意味着，如果坏人们掌握了 51% 的算力，就可以发起 51% 攻击，比如，实现双花（Double Spending），即同一份钱花 2 次
• 具体说是，攻击者掌握了较多的算力，能挖掘一条比原链更长的攻击链，并将攻击链向全网广播，这时，按照约定，节点将接受更长的链，也就是攻击链，丢弃原链
• 注意：即使攻击者只有 30% 的算力，他也有可能连续计算出多个区块的哈希值，挖掘出更长的攻击链，发动攻击； 另外，即使攻击者拥有 51% 的算力，他也有可能半天无法计算出一个区块的哈希值，也就是攻击失败。也就是说，能否计算出符合条件的哈希值，有一定的概率性，但长久来看，攻击者攻击成功的概率等同于攻击者算力的权重

比特币中如果采用 Raft 算法实现共识而不是 Pow 算法的区块链会发生什么

• 当恶意节点当选为领导者后，可以不断地告诉其他节点，这些比特币都是我的，按照 Raft 的约定，其他节点也就只能接受这种情况，最终就会出现，所有的比特币都被恶意节点盗走的情况

优点

• 实现了相对的公平。PoW 的容错机制允许全网 50% 的节点出错，如果要破坏系统，则需要投入极大成本（若你有全球 51% 的算力，则可尝试攻击比特币）

缺点

• 共识达成的周期长、效率低，资源消耗大。每次达成共识需要全网共同参与运算，增加了每个节点的计算量。如果题目过难，会导致计算时间长、资源消耗多；而如果题目过于简单，会导致大量节点同时获得记账权，冲突多。这些问题，都会增加达成共识的时间

PoS

核心原理

• 由系统权益代替算力来决定区块记账权，拥有的权益越大获得记账权的概率就越大
• 权益，即每个节点占有货币的数量和时间，而货币就是节点所获得的奖励

基于 PoS 算法获得区块记账权的方法相比基于 PoW 的方法的不同之处是？

• PoS是根据结点拥有的股权或权益进行计算的

通过 PoS 算法决定区块记账权的流程和 PoW 算法的唯一不同的是？

• 每个节点在计算自己记账权的时候，通过计算自己的股权或权益来评估，如果发现自己权益最大，则将自己的区块广播给其它节点，当然必须保证该区块的有效性
• 

优点

• 1.将算力竞争转变成权益竞争。与 PoW 相比，PoS 不需要消耗大量的电力就能够保证区块链网络的安全性
• 2.不需要在每个区块中创建新的货币来激励记账者参与当前网络的运行，这也就在一定程度上缩短了达成共识所需要的时间

缺点

• PoS 算法中持币越多或持币越久，币龄就会越高，持币人就越容易挖到区块并得到激 励，而持币少的人基本没有机会
• 整个系统的安全性实际上会被持币数量较大的一部分 人掌握，容易出现垄断现象

DPoS

DPoS(委托权益证明法)是什么

• 由被社区选举的可信账户（受托人，比如得票数排行前 101 位）来拥有记账权
• 为了成为正式受托人，用户要去社区拉票，获得足够多的信任。用户根据自己持有的货币数量占总量的百分比来投票
• 根据自己拥有的权益，投票选出可代表自己的受托节点，受托节点之间竞争记账权
• 
• 通常会选出k(如101)个受托结点，它们的权利是完全相等的。受托节点之间争取记账权也是根据算力进行竞争的。只要受托节点提供的算力不稳定，计算机宕机或者利用手中的权力作恶，随时可以被握着货币的普通节点投票踢出整个系统，而后备的受托节点可以随时顶上去

优点

• 1.由投票选举出的若干信誉度更高的受托人记账，解决了所有节点均参与竞争导致消息量大、达成一致的周期长的问题。DPoS 能耗更低，具有更快的交易速度
• 2.每隔一定周期会调整受托人，避免受托人造假和独权

缺点

• 1.由于大多数持币人通过受托人参与投票，投票的积极性并不高
• 2.一旦出现故障节点，DPoS 无法及时做出应对，导致安全隐患

PoW、PoS和DPoS三种共识算法的对比图

• 

参考

• 分布式协议与算法实战-极客时间
• 分布式技术原理与算法解析-极客时间