共识算法简介

Blockchain Comments

1. 主要内容

  • 拜占庭将军问题概述
  • 共识算法定义(作用)
  • 共识算法种类
  • 共识算法优缺点对比以及应用

2. 拜占庭将军问题

莱斯利·兰波特在其论文中描述了如下问题：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。

上述的故事映射到计算机系统里便是：

在分布式系统中存在恶意的计算机节点，这些节点会选择性响应某些请求或篡改系统中的数据。 那么在上述不可靠的信道上，系统中所有非恶意节点如何通过消息传递达成共识？

3. 共识算法

3.1 定义(作用)

共识算法使高度分散且彼此不信任的网络环境中的节点就某个事务达成一致且不分叉

按拜占庭容错性分类：

  1. 容忍非拜占庭错误（CTF）：容忍网络环境中存在故障节点但不存在恶意节点

  2. 容忍拜占庭错误（BFT）：容忍网络环境中同时存在故障节点和恶意节点

3.2 算法需满足的条件

FLP不可能问题：在异步网络中，哪怕只有一个节点故障也不可能存在能够容忍节点故障的一致性算法。

需满足的约束条件：

  1. 消息安全：节点件必须采用非对称加密对消息进行签名保证消息可传递（不可用对称加密，因为信道不安全）
  2. 处理FLP不可能问题：设置消息最大时延
  3. 共识结论合法：结论必须是一个节点的提案

3.3 算法详情

3.3.1 Paxos（CTF）

  1. 概念

    Paxos原理基于“两阶段提交”算法并进行泛化和扩展，通过消息传递来逐步消除系统中的不确定状态，是Raft、ZAB设计的基础

    Paxos角色：

    • 提案者（Proposer）：提出一个提案等待大家批准为结案（value）
    • 接受者（Acceptor）：对提案进行投票，接受提案
    • 学习者（Learner）：获取批准结果，不参与投票

  2. 共识过程

    pok：收到提议请求； aok：收到提交请求；最大提案编号：MaxN；AcceptN：接收到的提案编号； AcceptV：接收到的提案值；

  3. 举例说明 假设集群中有2个Proposer、3个Acceptor、1个Learner

    • 有两个Proposer，两个都提出 prepare request。来自 Proposer A的 request 先于Proposer B 的 request 到达 Acceptor X和 Acceptor Y， 但来自Proposer B的 request 首先到达 Proposer Z.
      img.png
    • 如果接收（accept）prepare request 的 Acceptor 之前没有看到其他的提议，则 Acceptor 以 prepare response 作出响应， 该 prepare response承诺永远不接受具有较低提议编号的另一提议。
      img.png
    • Acceptor Z收到了 Proposer A 的 request ，Acceptor X和 Acceptor Y收到了 Proposer B的 request 。 如果 Proposer 之前已经看到具有更高提议号的request ，则忽略晚到的 request，如Acceptor Z将忽略 Proposer A的 request（因为2<4）。 如果 Proposer 之前没有看到更高编号的 request，它再次承诺忽略具有较低提议编号的任何请求，并发回其已接受的编号最高的提议以及该提议的值。 如 Acceptor X和Y 对Proposer B的 request 的做法。
      img.png
    • 一旦 Proposer 收到大多数 Acceptor 的准备响应，它就可以发出接受请求
      • 对于Proposer A：由于 Proposer A仅收到表明没有先前提案的答复， 因此它向每个具有与其初始提案相同的提议编号和值的 Acceptor 发送 accept request（n = 2，v = 8）。然而，这些 request 都将被忽略，因为目标 Acceptor 都承诺不接受的提议编号低于4 的 request（这是对 Proposer B 的承诺）
      • 对于Proposer B：Proposer B 向每个 Acceptor 发送 accept request ， 该 request 包含先前使用的提议号（n = 4）以及与其接收的准备响应消息中的最高提议号相关联的值（v = 8）。 请注意，这不是 Proposer B 最初提出的值，而是它看到的 prepare response 消息中的最高值。
        img.png
    • 如果 Acceptor accept 的 accept request 的 编号 比其已经看到的更高或相等，则它会 accept 并向每个 Learner 节点发送通知。 当 Learner 发现大多数 Acceptor已接受某个值时，Paxos算法会选择该值
      img.png
    • 一旦Paxos选择了一个值，与其他 Proposer 的进一步沟通就无法改变这个值。 如果另一个 Proposer（如 Proposer C）发送的 request 的 提案号比之前看到的提案号更高，并且具有不同的值（例如，n= 6，v = 7）， 则每个接受者都会使用之前的最高提案进行响应（n = 4，v = 8）。这要求提议者C发送包含[n = 6，v = 8] 的接受请求，该请求仅确认已经选择的值。此外，如果一些少数接受者还没有选择一个价值，这个过程可以确保他们最终就同一价值达成共识。 （批注，这个过程总是成立的，具体论证过程见上）

3.3.2 Raft（CTF）

  1. 概念

    Raft相比Paxos是一种旨在易于理解的共识算法。

    Raft角色：

    • 领导者（Leader）
    • 候选领导者（Candidate）
    • 跟随者（Follower）

  2. 共识过程

    Raft演示地址

    主要阶段：

    • Leader选举
    • 同步日志

3.3.3 PoW（BFT）

  1. 概念

    POW 工作量证明共识机制，系统通过让所有节点公平地去计算一个随机数，最先寻找到随机数的节点即拥有记账权

  2. 比特币共识过程

    • 客户端发起交易广播到网络中等待确认
    • 网络中的用户将所有等待确认的交易打包到一个区块链中
    • 不断修改区块头中的Nonce值以使该区块头的hash值小于一个特定的目标值
    • 计算出Nonce后向全网广播
    • 网络中收到提案区块的节点对Nonce进行验证，验证合法交易被确认，该块加入链

3.3.4 PoS（BFT）

权益证明机制，是为解决PoW算法大量浪费资源问题而提出的一种替代算法，该算法中区块的记账权由权益最高的节点获得

3.3.5 DPoS（BFT）

  1. 概念

    股份授权证明机制，是PoS的一种衍生算法，算法的思想是系统中持有权益的节点投票选举出一部分代表，再由这些代表轮流获取区块链记账权，类似于股份制公司的“董事会”

  2. 共识过程

    • 每个节点将自己持有的权益转换为选票投给自己信任的节点
    • 选票最多的N个节点当选为见证人（Witness），即代表
    • 见证人在一个规定时间内随机排列并轮流对交易打包，生成新区块连接到最长链，见证人收获m％的交易手续费

3.3.6 PBFT（BFT）

  1. 概念

    PBFT在保证可用性和安全性的前提下，提供了(n-1)/3的容错性，意思就是如果系统内有n个节点，那么系统最多能容忍的作恶/故障节点为(n-1)/3个。（作恶节点可以不响应或者回应错误的信息）

  2. 共识过程

    共识算法系列：PBFT算法关键点综述、优缺点总结

    定义：

    • f：恶意节点

    • Digest(m)：消息摘要

    过程：

    • 预准备阶段：发送原本的消息m，让每个节点都获取原始消息
    • 准备阶段：用Digest(m)去发送，如果一个节点收到2f+1个prepare消息，就认为准备阶段结束，说明已经有大部分节点认同了这个m
    • 提交阶段：用Digest(m)去发送，如果一个节点收到2f+1个commit，那么就可以认为，就说明已经有大多数节点“执行”了这些m，这个阶段主要是为了View Change服务
    • 回执阶段：提交结束后将结果返回给客户端，客户端收到至少f+1个消息即可确认

3.3.7 DBFT（BFT）

  1. 概念

    授权拜占庭容错，系统中的代币持有者通过投票选举出自己所支持的共识节点，这些选出来的共识节点再通过BFT来达成共识并生成区块

  2. 共识过程

    image-20220108234438067

    过程：

    • 节点投票选出一定数量的共识节点
    • 议长设置视图并广播提案<PrepareRequest>消息
    • 议员收到提案对其验证，验证通过后议员向全网发送<PrepareResponse>消息
    • 当收到n-f条<PrepareResponse>消息时，议员们发布一个新的区块，对区块签名，发送给其他节点进行同步<Synchronization>
    • 其他节点收到完整区块后达到相同的区块高度，清除本地内存中所存储的当前视图交易数据，准备下一次共识

3.4 算法优缺点与应用

算法 优点 缺点 应用
Paxos - 容忍非拜占庭错误节点能力高
- 性能高		 - 算法难以理解
- 不能容忍拜占庭错误节点		 ZooKeeper、GoogleChubby
Raft - 算法容忍非拜占庭错误节点能力高
- 性能高
- 易于理解和实现		 - 不能容忍拜占庭错误节点 IPFS Private Cluster、R3 CodaQuorum
Pow - 算法逻辑简单
- 安全性高
- 容错性高		 - 资源消耗过高
- 系统吞吐量低		 Bitcoin、Ethereum、Dogcoin、Litecoin、Zcash
PoS - 缓解PoW资源浪费问题
- 相对PoW提高了出块速度		 - 易出现持币人屯币现象，造成寡头优势 Blackcoin、ADA、Peercoin、Casper、Nxt
DPoS - 解决了PoW资源浪费问题
- 性能较高
- 出块速度较快		 - 相比其他算法该算法趋于中心化
- 投票无门槛，权益余额大票数越大，易造成联合选举行为		 EOS、Bitshares、Steemit、Lisk、Ark、GXChain、ASCH
PBFT - 无代币
- 性能效率高
- 安全性高		 - 通信复杂度O(n2)，可扩展性低
- 视图转换时间复杂度O(n3)，视图转换期间只能接收view-change和new-view消息，不能对外提供服务
- 无法避免恶意节点担任主节点
- 节点不可进行动态增删
- 无法承受大规模节点		 Fabric
DBFT - 借鉴DPoS，参与共识节点数量较少，因此提高了性能 - 相比其他算法该算法趋于中心化 NEO

4. 引发思考

  1. PBFT在节点数超过100后性能继续下降，如何缓解？

    • 方法一：带宽优化：

      • 客户端将请求发给任意节点，而不是只发给主节点，然后节点直接将请求广播给所有节点
      • 设计共享交易池，预先进行交易的广播，仅共识交易哈希值主节点打包交易hash，广播包含hash的提案消息，而不是广播交易数据
      • 从节点在提交之前主动向主节点获取可能缺失的交易，最终提交之前确认交易合法性

      image-20220109102820146

    • 方法二：BFT问题转换成CFT问题，即规避拜占庭行为

      image-20220109104150146

    • 方法三：点对点网络转换为星型网络

      image-20220109104400275

  2. PBFT无法动态增删节点，如何解决？

    先请求分布式CA，再通过配置交易的方式，准入与删除共识节点

    image-20220109103818671

  3. PBFT中prepare和commit阶段为何都要2f+1个节点反馈确认?（这2f+1节点反馈的结果并不一定是相同的）

    对于prepare和commit来说，节点需要在2f+1个状态复制机的沟通内就要做出决定，这是刚好可以保证一致性的，考虑最坏的情况：我们假设收到的有f个是正常节点发过来的，也有f个是恶意节点发过来的，那么，第2f+1个只可能是正常节点发过来的。（因为我们限制了最多只有f个恶意节点）由此可知，“大多数”正常的节点还是可以让系统工作下去的。所以2f+1这个参数和n>=3f+1的要求是逻辑自洽的。

  4. PBFT中client为何只需要f+1个相同的回复就可确认？

    之前我们说，prepare和commit阶段为何都要2f+1个节点反馈，才能确认。client只需要f+1个相同的reply就可以了呢？我们还是来考虑最坏的情况，我们假设这f+1个相同的reply中，有f个都是恶意节点。

    所以至少有一个rely是正常节点发出来的，因为在prepare阶段，这个正常的节点已经可以保证prepared(m,v,n,i)为真，所以已经能代表大多数的意见，所以，client只需要f+1个相同的reply就能保证他拿到的是整个系统内“大多数正常节点“的意见，从而达到一致性。

  5. PBFT中如果primary是恶意节点呢？

    对于一致性，我们可以这么看：如果prepared(m，v，n，i)为真，那么prepared(m’，v，n，j)一定是错误的，因为对于同一个提案我们不可能有两种结果，从而保证整个系统的一致性。

    假设primary节点是恶意的，那么意味着在replicas节点中⾄多有f-1个恶意的节点，prepared(m，v，n，i)为真，则证明有f+1个善意节点达成了了⼀致，prepared(m’，v，n，j)为真，意味着另外f+1个善意节点达成了一致，因为系统中只有2f+1个善意节点，因此最少有⼀个善意节点发送了两个冲突的prepare消息，这是不可能的。所以prepared(m，v，n，i)为真，那么prepared(m’，v，n，j)是错误的。

  6. PBFT中为什么要求N>=3f+1?

    • 两次读写请求都需要N-f个节点返回响应后完成共识，这两次操作响应的节点交集至少有N-2f个
    image-20220814221555557
    • 为了保证不让f个拜占庭节点成功作恶，对外提供一致的应答，需要让交集满足N-2f>f，即N>3f，也即N>=3f+1

5. 参考资料

  1. 李永乐老师讲解拜占庭将军问题
  2. 维基百科对拜占庭将军问题的解释
  3. Paxos学习笔记及图解
  4. PBFT提出者论文《Practical Byzantine Fault Tolerance》
  5. 共识算法系列：PBFT算法关键点综述、优缺点总结
  6. 区块链共识算法对比研究
  7. 联盟区块链共识算法的实践与挑战 - 端豪 杭州趣链科技架构师
  8. Paxos论文
  9. 长安链共识算法介绍

Yang YangJava Development Engineer

Keep looking, don't settle.