区块链共识算法研究_区块链共识算法推导与仿真

分布式集群设计中不可逃避的一个问题就是一致性问题，即在分布式场景中，经过一系列的写数据后，多个节点如何达成相同的数据状态？

共识算法就是解决一致性问题的算法，即针对某一提案，大家达成一致意见的过程。

在这个过程中，会出现以下场景：

1. 节点间通信不可靠，网络丢包，延迟等；

2. 节点的处理可能出错，甚至宕机；

3. 节点作恶（拜占庭类错误）

以上场景都会导致多个节点的数据状态不一致

常见的共识算法有Solo、Raft、TBFT、PoW、DPoS等

根据容忍类型不同，可以分为

另外，公链因为节点众多，性能要求不高，所以常用的是PoW和PoS

联盟链对性能的要求比较高而节点数量稳定，所以常用的是Raft和PBFT

拜占庭容错原理

拜占庭是东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点作恶），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。

假如将军总数为 N，叛变将军数为 F，则当N>=3F+1 时，问题才有解，即叛变的将军不超过1/3时，则存在有效的算法，如BFT，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。

每个将军需要收集其他所有将军的消息，然后做出判断，在已知F个叛军的前提下，当他收到N-F条消息时，就要在这N-F条消息中做出判断，极端情况是，剩下F条消息都是忠诚的，只是由于网络等等问题，收不到剩下的F条消息，这种最坏情况下，N-F中有F条假消息，N-2F条真消息，当N-2F>F时，才可以做出正确判断，即N>3f，即N>=3F+1

一、Solo共识

solo实际上不算是一种共识算法，因为只有一个节点，不涉及分布式，无共识投票过程。

solo用于快速部署区块链网络，降低使用门槛，供开发人员调试除网络和共识以外的区块链功能的

二、工作量证明PoW

1.定义

工作量证明（proof-of-work）是一种确认你完成了某件事的证明方式。

生活中常见的就是毕业证，因为毕业证可以证明你完成了阶段性的学习，通过了考试，但过程对验证方来说不重要，验证方只看到你的毕业证就行了

2.基本原理

工作量证明涉及到两方，一个是工作方，一个是验证方。

工作方需要完成一定难度的工作并得出一个结果，验证方验证这个结果是否通过。其中，工作方完成工作是有难度的，而验证方的验证是及其容易的

举个例子：
（1）

老师：给一个数学题，你们把它解出来并告诉我答案（必须解出来，不是蒙的）

学生需要完成求解的动作，告诉老师答案是什么，老师来验证答案对不对，验证通过，证明该学生完成了一定的工作量。

（2）

验证方给一个字符串“Hello,world!”，要求在这串字符串后加一个随机数，不限定位数，使得加上这个随机数后的字符串的hash值以0000开头

那么，工作方就要一个一个随机数去尝试：

"Hello,world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello,world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello,world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello,world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello,world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello,world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

得出了需要加个随机数4250，才能满足条件

验证方验证结果确实是0000开头的，说明工作方完成了这项工作，即工作量证明。

3.比特币的PoW（挖矿）

上述例2的思想就是来自于比特币，只不过比特币给定的是一个区块，当需要往链上新增一个区块时，旷工需要对指定区块增加一个随机数nounce，算出这个数据的hash，并且这个hash要满足有N个前导0

N是由挖矿难度决定的，N=目标值=最大目标值/难度，最大目标值为0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

比特币会控制难度，保证每10分钟出一个块

所以，挖矿就是对每一个新区块，通过不断的尝试，得出一个随机数来满足要求，并获得一定的奖励

4.为什么是一种共识算法

有这么两种情况：

a.每个旷工都是自私自利的；

b.不是每个交易都是有效的，即便是有效交易，由于旷工的自私自利，他可能不同意这笔交易，则这笔交易无效

例如，A给B转钱，交易成功了，但是B可以操作区块链，那么B不同意这笔交易落块，而他又获得了这笔钱，这就导致了作恶。

事实上，不同的区块对不同的人有不同的好处，谁都想挖到矿，也就是谁都想自己提议的区块被别人同意，那如何让旷工们达成共识，避免旷工私自操作区块链呢？

比特币的解决办法是增加背叛成本。如果区块是通过困难的计算随机生成的，那么一次只会有一个提议的新区块。一旦有一个新区块被提议了，矿工就要选择是继续寻找对自己更有利的替代区块（冒险，需要足够多的旷工都同意他的提议），还是接受新的提议并寻找下一个区块（找到有奖励）。

一般情况是，第一个算出来的区块都不是对自己有利的，因为你无法保证你是第一个算出来区块的人，只能靠运气，这时，你必须选择继续算这个，还是接受这个，算下一个。

正常都会继续下一个，那对该区块即达成了共识。

三、权益证明PoS

1.概念

与竞争挖矿不同的是，权益证明（proof-of-stake）通过选举的方式，选举出一些节点做为“验证者”来“铸造（mint）”新区块，而不是挖区块

2.机制

挖矿是非常耗费电力资源的，而在权益证明，每个节点都有一定的概率被选中来验证区块。

每个节点都要在网络中存入一定数量的货币作为权益，称为保证金。存的越多，被选中的概率就越大。例如A存了1000美元进网络，B存了100美元，那么A被选中的概率是B的十倍。

那就是越有钱越能操作区块链？

其实不是的，它甚至比工作量证明更公平，在工作量证明中，有钱人可以购买更多的设备来挖矿，并将资源聚合起来，一旦超过51%，就可以随意操作区块链。

每当有一个新区块产生，每个验证者都会对其进行验证，并投票通过还是不通过，一旦这个区块有超过51%的验证者同意通过，这个区块将会被写入账本，同意的验证者可以获得一定的奖励，而不同意的验证者，会失去他的全部权益，一旦比他能获得的奖励还多，那肯定得不偿失，所以网络更信任有钱人。

3.优缺点

四、委任权益证明DPOS

1.原理

委托权益证明（Delegated proof of stake）需要每个网络的参与人都投票，选出一些见证人（超级节点）来验证和共识，而这些见证人的权利是相等的，他们轮流产生区块（对区块签名），一旦有某个见证人作恶或放弃对区块签名，则会被踢出见证人队伍，网络的参与人会重新投票决定谁加入这个队伍。

类比：中国的人民代表大会制度，每个公民都有选举权，选举出的代表代表全国公民参与国家决策

2.优点

相比于PoS，大幅缩小了见证人的数量，大大提高了效率，可以达到秒级的出块速度。

3.缺点

属于弱中心化，因为出块的权利还是掌握在部分人的手中，是一种精英制度，参考人民代表大会制度。

但实际上，去中心化、安全、速度，这三个指标不可能同时保证， 最多只能选其二

4.DPOS在相当长一段时间内不会被超越

（1）比较：

PoW耗费资源，还可以聚集资源，形成矿池，一旦矿池联合起来，整个区块链会被掌握在他们手中。

PoS中，越有钱的人，越可能称为验证者，获得奖励，最终的钱都掌握在他们的手中，容易产生垄断。

而DPOS既不用耗费资源，又不会形成垄断，是一种“民主”的机制，虽然最终产生区块的是部分人，但这些人是网络中所有人选举出来的，他们代表了整个网络中的所有人。不随机选择见证者的原因是：不是每个节点都长时间在线；在POS中，攻击者可以使用其权益控制网络

（2）虽然DPOS是弱中心化的，但是我们所说的“去中心化”，只是手段，而不是目的，况且，这种制度的先进性，不是来源于技术，而是来源于人类社会。

（3）越来越多的项目使用DPOS：比特股、steem、EOS

五、拜占庭容错PBFT

1.原理

前面提到，系统总规模N要大于3倍的作恶节点的数量F，最少是3F+1，所以PBFT要求最少有4个节点，只允许最多一个作恶节点。

算法流程：
（1）客户端向主节点发起请求；

（2）主节点向其他所有副节点广播该请求；

（3）所有副本执行请求，并将结果返回客户端

（4）客户端需要等待至少2F+1个结果后，才能做出决定。

2.三阶段和两个状态

三个阶段：pre-prepare、prepare、commit，两个状态：prepared、committed-local

（1）预准备阶段pre-prepare

主节点向其他节点发送预准备消息，这个消息不包括请求，而是包括消息序号、视图编号、消息摘要。这样的好处在于压缩消息大小，提升传播速率，并且解耦了消息排序和消息传输。

副节点收到预准备消息后，验证消息签名、视图编号是否一致、消息序号是否满足水线要求（即h<n<H，意义在于防止一个失效节点称为主节点后，使用一个很大的序号浪费序号空间，对于区块链，请求就是区块，天然有区块号，所以水线要求无效）

（2）准备阶段prepare

每个副节点都向其他节点发送包含自己ID的准备消息，同时也接收别的节点的准备消息，收到别人的消息后，同样也要校验消息的合法性。

来自其他节点的准备消息验证通过后，写入自己的消息日志，一个节点集齐2F+1（含自己）条消息后进入prepared状态。

当前只有自己完成共识，并不表明其他人都完成共识。

（3）提交阶段commit

每个节点既发送，也接收commit消息，当收集到了2F+1条消息后，说明大家都完成共识，进入committed-local状态。

客户端一旦收集到了F+1条commit消息后，说明其发起的请求通过。

为什么是F+1而不是2F+1呢？

因为F+1中至少有一个诚信节点已经完成了3阶段的共识，说明其他诚信节点也可以完成共识，所以其实只需要一个诚信节点的结果就可以了，即一共只需F+1个节点的结果。

F+1个确实得不出共识结果，但对于客户端来说，他只要知道共识完成了就行，不用关心共识的结果。

为什么是三个阶段不是两个阶段？

一般问出这种问题，砍掉的都是最后一个阶段，那当commit阶段不存在时会发生什么呢？一旦节点A进入prepared状态，它认为已经完成了共识，开始执行下一个请求Q，但是其他节点并未按时完成共识，于是发起了view change，即更换主节点重新共识本轮消息（不包含Q的pre-prepare消息），而Q的pre-prepare消息已经发送给A了，所以Q不会再被共识。

如果有第三个commit阶段，那么即便发生view change，也不会漏掉任何一条请求。

 六、分布式一致性协议RAFT

1.概念

raft是一种非拜占庭场景下使用的共识机制。系统只要有多数节点存活，即可完成共识，允许消息延迟，丢弃

2.节点类型

（1）leader节点：负责与客户端交互，由follower节点选举出来，在每次共识过程中有且仅有一个leader节点，全权负责打包交易出块；

（2）follower节点：同步leader节点的消息，并在leader节点挂了时，重新选举产生leader节点，系统刚启动时，都是follower节点；

（3）candidate节点：follower节点在竞选leader时的临时身份。

3.任期

每个Term（任期）时间不同，但序号连续，以选举开始，以出块结束。未选出leader会继续下一term

4.消息类型

（1）voteReq：投票请求，由candidate节点主动发出，用于向网络中其他节点请求投票以竞选Leader；

（2）voteResp：投票响应，在节点收到投票请求后，用于对投票请求进行响应，响应内容为同意或拒绝该投票请求；

（3）heartbeat：心跳，由leader节点周期性的主动发出，作用：①告知follower节点自己存活性，只要leader一直存活，就不会开始下一轮term；②广播区块信息，leader会在心跳中带上区块信息，follower节点接收到信息后，解析区块存入自己的缓冲区；

（4）heartbeatResp：心跳响应，即follower节点响应心跳信息。当心跳中包含区块时，心跳响应中会包含区块hash

5.流程

5.1 状态转换

5.1.1 选举

系统刚启动时，节点均为follower，term=0

一段时间内没有收到来自leader的心跳消息或来自candidate的voteReq消息，则term++，follower自动转换为candidate，开始新一轮选举。

如果监听到有心跳或voteReq，则保持为follower

选举流程如下：

1. Follower增加当前的Term，转换为Candidate；

2. Candidate将票投给自己，并广播RequestVote到其他节点请求投票；

3. Candidate节点保持在Candidate状态，直到下面三种情况中的一种发生：(1)该节点赢得选举；(2) 在等待选举期间，Candidate收到了其他节点的Heartbeat；(3) 经过Election Timeout后，没有Leader被选出。Raft算法采用随机定时器的方法来避免节点选票出现平均瓜分的情况以保证大多数时候只会有一个节点超时进入Candidate状态并获得大部分节点的投票成为Leader。

5.1.2 投票

节点收到voteReq后有几种响应策略：

1. voteReq的term小于等于自己的term：

如果节点是leader，则拒绝本次请求，candidate会自动转为follower，投票超时

如果节点不是leader：

       如果VoteReq的Term小于自己的Term，则拒绝该投票请求，如果Candidate收到超过半数的该种响应则表明其已经过时，此时Candidate会放弃选举转变为Follower，投票超时

       如果VoteReq的Term等于自己的Term，则拒绝该投票请求，对于该投票请求不作任何处理。对于每个节点而言，只能按照先到先得的原则投票给一个Candidate，从而保证每轮选举中至多只有一个Candidate被选为Leader。（重复收到同一轮的来自不同candidate的投票请求，因为term相等，说明已经接受了其他节点的投票请求，不再接收本次请求）

2. VoteReq的lastLeaderTerm小于自己的lastLeaderTerm：

lastLeaderTerm表示自己见过的最后一个leader的term，lastLeaderTerm只能由心跳更新，如果VoteReq的lastLeaderTerm小于自己的lastLeaderTerm，说明消息来源的节点落后了，拒绝请求

3. VoteReq的lastBlockNumber小于自己的lastBlockNumber

说明消息来源的节点记录的区块落后了，为了使系统一致，应该把票投给有最新区块的节点，让他称为leader并出块，所以拒绝请求

4. 节点是第一次投票

为了避免出现Follower因为网络抖动导致重新发起选举，规定如果节点是第一次投票，直接拒绝该投票请求，同时会将自己的firstVote字段置为该Candidate的节点索引

5.没有上述情况，则同意

5.2 区块复制

当leader产生区块后，区块状态记为未提交uncommitted，通过心跳将区块信息广播给其他节点，其他节点将区块放入本地缓冲区，并返回心跳响应，其中包括区块hash，leader收到超过半数的心跳响应时，再将区块写入数据库，区块状态记为提交committed，再通过sync模块广播其他节点存储区块。