区块链中常用的共识算法

本文是对区块链技术涉及的共识算法的总结。 其中PBFT和Raft是联盟链和私有链常用的共识算法，而PoW（比特币使用）和PoS是公链常用的共识算法。 区块链的学习建议分公链或者联盟链。 这两条链还是有很大区别的。 比如这篇博文要讨论的共识算法和P2P网络也有很大的不同。

大家可以想想为什么传统的共识算法不适合公链，但是在一定程度上适合联盟链。 同时，对于P2P网络，当节点数nn巨大时，广播信息为O(n)O(n)...

1、实用的拜占庭容错系统PBFT（常用于联盟链）

拜占庭容错（BFT）是分布式计算领域的一种容错技术，是解决分布式系统容错问题的通用方案。 实用拜占庭容错（PBFT）将拜占庭协议的运算复杂度从指数级降低到多项式级，使得拜占庭协议在分布式系统中的应用成为可能。

1.1 拜占庭将军问题

拜占庭将军问题是 Leslie Lamport 于 1982 年提出的用于解释一致性问题的虚构模型。 拜占庭是古东罗马帝国的首都。 由于地域辽阔，守卫边境的多个将军（系统中的多个节点）需要通过使者传递消息并达成一些一致的决定。

但是，由于将军之间可能存在叛徒（系统中的节点出错），这些叛徒会试图向不同的将军发送不同的消息，试图干扰共识。 拜占庭问题就是在这种情况下如何让忠诚的将军们达成行动的共识。

1.2 拜占庭容错系统

一个拜占庭容错系统是指：在一个有n个节点的系统中，整个系统对每个请求都满足以下条件：

同时，在拜占庭系统的实际运行中，一般假设系统中的拜占庭节点数不超过mm，且每个请求满足两个指标：

安全——任何已完成的请求都不会被改变，它可以被未来的请求看到；

Liveness——可以接受并执行来自非拜占庭客户端的请求，不会受到任何导致非拜占庭客户端请求无法执行的因素的影响。

目前拜占庭系统常用的假设包括：

（故障节点称为拜占庭节点；正常节点为非拜占庭节点。）

1.3 状态机拜占庭系统

状态机拜占庭系统的特点

状态机拜占庭系统的特点是整个系统共同维护一个状态，所有节点采取一致的动作，一般包括三种协议：共识协议、检查点协议和视图替换协议。 系统通常在一致性协议和检查点协议下运行。 视图替换协议只会在主节点出现故障或运行缓慢时启动，负责维护系统继续执行客户端请求的能力。

状态机拜占庭系统的核心协议

1.一致性协议

共识协议的目标是使来自客户端的请求在每个服务器上以确定的顺序执行。 在协议中，一般有一个服务器称为主节点，负责对客户端的请求进行排序； 其余的服务器称为从节点，按照主节点提供的顺序执行请求。 所有服务器都在相同的配置信息下工作。 此配置信息称为视图。 每次更换master节点，view都会随之改变。

共识协议至少包含3个阶段：发送请求、分配序列号和返回结果。 根据协议的设计，它可能包括相互交互和序列号确认等阶段。

一致性协议解决一致性的主要方法有：

1）服务器之间二对二交互，服务器将自己获得的信息传递给其他服务器；

2) 客户端收集服务器的信息，将收集到的信息制作成证书发送给服务器。 对于包含3m+13m+1台服务器的拜占庭系统，需要收集2m+12m+1台服务器发送的一致信息，保证达成一致的非拜占庭服务器数大于拜占庭服务器数。

延伸思考：可以这样想：

1. 使用PBFT共识算法部署区块链需要多少个节点？

2、PBFT共识算法的区块链，最优节点数，使用PBFT共识算法的区块链系统节点数的下限和上限？

3、可靠性、安全性，与节点数量的关系？

4、节点数不能超过100个？

2.检查点协议

拜占庭系统每执行一次请求，服务器都需要记录日志。 如果不及时清除日志，系统资源将被大量日志占用，影响系统性能和可用性。 另一方面，由于拜占庭服务器的存在，共识协议无法保证每个服务器执行相同的请求，因此不同服务器的状态可能不一致。

比如有些服务器可能因为网络延迟，从某个序号开始，后面的请求就不会执行了。 因此，拜占庭系统中设置了一个周期性的检查点协议，使系统中的服务器同步到某种相同的状态。 因此，周期检查点协议可以定时处理日志，节省资源，及时纠正服务器状态。

处理日志主要解决的问题是区分哪些日志可以清理，哪些日志还需要保留。 如果一个请求已经被 m+1m+1 个非拜占庭服务器执行过，并且一个服务器 ii 可以向其他服务器证明这一点，那么 ii 可以删除关于这个请求的日志。

目前该协议常用的做法是，服务器每执行一定数量的请求，就将自己的状态发送给所有服务器，执行该协议。 如果一个服务器接收到2m+12m+1台服务器的状态，那么它一致的部分就是至少m+1m+1台非拜占庭服务器经历过的状态。 因此，可以删除这部分日志，同时只更新较新的状态。

3.查看替换

在共识协议中，已知主节点具有整个系统的序号分配、请求转发等核心能力，支配着系统的运行行为。 但是，一旦主节点自身出现错误，可能会导致从节点接收到同一个序号的不同请求，或者同一个请求分配了多个序号等，这将直接导致请求无法执行正确。 视图替换协议的作用是当主节点无法继续履行职责时，将主节点替换为从节点，并保证已经被非拜占庭服务器执行过的请求不会被篡改。

触发视图替换协议一般有两种方式：

1) 仅由服务器触发。 在这种触发方式下，服务端自己负责判断是否达到服务端的一致性，客户端无法从请求的整个执行过程中获取到服务端运行状态的信息；

2）客户端触发。 在这类触发方式中，一般由客户端负责判断服务端是否达成一致。 如果没有达成一致，那么可以判断是服务器运行有问题。 如果是主节点的问题，服务器会要求更换主节点。 .

视图替换协议需要解决的问题是如何保证已经被非拜占庭服务器执行过的请求不被改变。 由于系统达成共识后至少有m+1m+1台非拜占庭服务器执行过请求，目前的做法是：新的主节点收集至少2m+12m+1台服务器的状态信息，其中必须包含所有已执行的请求； 然后，新的主节点将这些状态信息发送给所有的服务器，服务器按照同样的原则同步上一个主节点完成的请求。 同步后，所有节点都处于相同的状态，此时可以执行新的请求。

1.4 实用拜占庭容错系统PBFT详解

实用拜占庭容错（PBFT）是一种状态机拜占庭系统。

PBFT的一致性协议如下：PBFT系统通常假设故障节点数为mm，服务节点数为3m+13m+1。 每个client的请求需要经过5个stage，通过两次pairwise交互，在server达成一致后执行client的请求。 由于客户端无法从服务器获取任何服务器运行状态信息，因此PBFT中主节点是否出现错误只能由服务器进行监控。 如果服务端不能在一定时间内完成客户端的请求，就会触发视图替换协议。

上图展示了一个简化的PBFT协议通信模式，其中CC为客户端，N0N0~N3N3代表服务节点，其中N0N0为主节点，N3N3为故障节点。 整个协议的基本流程如下：

1）客户端发送请求激活主节点的服务运行；

2）当主节点收到请求后，启动三阶段协议，将请求广播给各个从节点；

序号分配阶段：主节点为请求分配一个序号nn，广播序号分配消息和客户端的请求消息mm，并构造一个pre-prepare消息给各个从节点；

交互阶段：接收来自节点的pre-prepare消息，并向其他服务节点广播prepare消息；

序列号确认阶段：每个节点在视图中验证请求和序列后，广播提交消息，执行收到的客户端请求并响应客户端。

3) 客户端等待来自不同节点的响应。 如果m+1m+1个响应相同，则响应为运算结果；

2. 筏协议

Raft 是一种在非拜占庭故障下达成共识的强共识协议。 在区块链系统中，使用Raft实现记账共识的过程可以描述为：首先选举出一个leader，然后赋予leader完全的记账管理权。 领导者收到客户端的记账请求，完成记账操作，生成区块，复制到其他记账节点。 拥有领导者可以简化会计业务的管理。 如果领导者失败或与其他节点失去联系，系统将选举新的领导者。

2.1 筏板基础

一个 Raft 集群通常包含 5 个服务器，允许系统有 2 个故障服务器。 每个服务器都处于 3 种状态之一：领导者、追随者或候选者。 正常运行时，只有一个leader，其他服务器都是follower。 follower是被动的，不响应自己的请求，而是响应leader和candidate的请求。 领导者处理所有客户端请求（如果客户端联系追随者，追随者会将其转发给领导者）。 候选状态用于选举领导者。

Raft阶段主要分为两个阶段。 首先是leader选举过程，然后在选出的leader的基础上进行一些正常的操作，比如日志复制、计费等。

2.2 领导人选举

当follower在选举超时时间内没有收到leader的心跳消息，就​​会切换到candidate状态。 为了避免选举冲突比特币使用的共识算法是，这个超时时间是一个介于 150 和 300 毫秒之间的随机数。

一般来说，在 Raft 系统中：

任何一个server都可以成为candidate candidate，它向其他server follower发送请求，让其选举自己。

另一台服务器同意，发出 OK。 如果在这个过程中，一个follower宕机，没有收到选举请求，此时候选人可以选择自己，只要达到N/2+1N/2+1的多数票，候选人就可以仍然成为追随者。 领导者。

这样candidate就变成了leader，它可以给follower下达指令，比如记账。

以后可以通过心跳进行计费的通知。

一旦领导者崩溃，其中一名追随者成为候选人并邀请投票选举。

Follower同意后，成为Leader，继续承担记账等指导工作。

2.3 会计处理

Raft的记账过程分以下几个步骤完成：

假设已经选出leader，客户端发出添加日志的请求；

leader 要求 follower 按照他的指示将这个新的日志内容追加到各自的日志中；

大多数follower server将交易记录写入账本后，确认添加成功并发送确认消息；

在下一个心跳中，领导者通知所有追随者更新已确认的项目。

对于每条新的交易记录，重复上述过程。

如果在这个过程中，出现了网络通信故障，导致leader无法访问大部分follower，那么leader只能更新那些自己可以正常访问的follower服务器。 大多数server follower会因为没有leader重新选举一个候选人作为leader，然后由leader作为代表与外界打交道。 如果外界要求它增加一条新的交易记录，新的leader会按照上面的步骤通知大家 对于大多数follower，如果此时网络故障修复，原leader将成为follower。 在断开连接阶段，旧领导者的任何更新都不能被视为已确认，它们将被回滚以接收来自新领导者的新更新。

如果你想更直观的了解Raft协议，可以观看这个动画演示。

3. 工作量证明

PoW的数学原理可以参考本博文哈希函数谜题的友好性部分：理解了谜题的友好性，就基本了解了PoW机制的原理。

结合比特币理解 PoW。 比特币PoW的过程是使用不同的nonce值作为输入，尝试进行SHA256哈希运算，找出满足给定个数前导0的哈希值。 需要的前导 0 越多，难度就越大。 比特币节点解决工作量证明问题的步骤总结如下：

生成铸币交易并与所有其他交易组成交易列表打包进区块，通过Merkle树算法生成Merkle和hash；

将Merkle根哈希和其他相关字段组装成一个区块头，并将区块头的80字节数据作为工作量证明的输入；

不断改变区块头中的随机数nonce，对每一个改变的区块头进行两次SHA256运算，并将结果值与当前网络的目标难度进行比较。 如果满足困难条件，则求解成功，完成工作 量化证明。

4.权益证明

Pos了解其提案的背景，并提供了另一种共识思路。

更多信息请参考：二跳区块链：安全地结合工作量证明和权益证明

PoW 有以下缺点：

1）矿池的出现在一定程度上违背了去中心化的初衷，也使得51%攻击成为可能，影响其安全性。

2）PoW算力浪费巨大，看矿池耗电多少就知道了。

PoS（Proof of Stake）的出现很大程度上是由于PoW的缺陷。 PoS币中不同币种的PoS并不完全相同。 Proof of Stake要求用户证明自己拥有一定数量的币（即币的权益）。 下面我们以点点币为例来理解PoS的思想。

Peercoin的哈希运算难度在SHA-256中方便引入了币龄的概念，使得难度与交易输入的币龄成反比。 在 Peercoin 中，币龄定义为币的数量与币拥有天数的乘积。 Peercoin 的权益证明机制结合了随机化和币龄的概念。 至少 30 天未使用的币可以参与下一个区块的竞争。 币组越老越大，签署下一个区块的可能性就越大。 一旦币种权益被用于签署一个区块，币龄将被清零，因此您必须至少等待30天才能签署另一个区块。 同时，为了防止非常老或非常大的权益控制区块链，找到下一个区块的最大概率在 90 天后达到最大值。 这个过程保护了网络比特币使用的共识算法是，并随着时间的推移逐渐成为一种新的货币，而不需要消耗大量的计算能力。

5.DPoS

PoS 机制虽然考虑到了 PoW 的不足，但它也有缺点：根据股权余额进行选择，会导致首富的账户拥有更大的权力，并可能控制记账权。

由于缺乏 PoW 和 PoS，因此提出了委托权益证明（DPoS）。 我们以比特股为例来理解DPoS的思想。

比特股引入了见证人的概念，见证人可以生成区块，每个持有比特股的人都可以投票给见证人。 The first NN (NN is usually defined as 101) candidates among the total number of consent votes can be elected as witnesses, and the number of elected witnesses needs to meet: at least half of the participating voters believe that NN has been fully decentralized. 见证人名单在每个维护期（1 天）更新一次。 然后随机排列见证人，每个见证人有2秒的授权时间依次生成区块。 如果见证人不能在给定的时间片内生成区块，则将出块权授予下一个时间片对应的见证人。 如果见证人提供的算力不稳定或者电脑宕机等情况，股东可以随时投票更换这些见证人。

可见其核心思想是通过减少参与核心共识过程的节点数量来提高共识效率。 （这里选举见证人的过程可视为非核心共识过程，而见证人有序出块可视为核心共识过程）

排序系列文章