区块链入门系列之共识算法

区块链入门系列文章

区块链基本概念和名词解释
P2P

共识算法

梅克尔-帕特里夏树
从零开始搭建区块链

这里写自定义目录标题

前言

前文已经说过，区块链从本质上来说就是基于P2P网络的分布式系统，而对于分布式系统来说，如何维护各节点之间的状态尤其重要，需要所有节点步调一致，这就需要设计相应的算法或者协议来进行管理。对于一个分布式系统来说，一定是遵从CAP定理的

• C: Consistency即一致性，全部节点在同一时间下数据是一致的
• A: Availability即可用性，整个分布式系统总是可用能提供正常服务的
• P: Partition tolerance即分隔容错性，系统中某些节点故障时不影响整体的运行 对于目前大部分的公链系统来看，他们都牺牲掉哪个特性了？明显是一致性，它不要求数据实时一致，但最终都会一致，实现的是最终一致性。虽然牺牲了强一致性，但是AP两块板就被加到非常非常长，因为其节点数量可能比其他任何分布式系统的都要多，所以公链系统的可用性和容错性是非常之高的。总之，数据是否一致对于区块链来讲不是最重要的，重要的是数据必须要按照固定的增量内容和顺序去一步步实现更改。 这里还有个小问题，我觉得有必要再补充说明下。在接触区块链之前，如果有小伙伴对分布式系统已经比较熟悉了的，肯定是知道一个名词叫一致性算法，和区块链中的共识算法有什么区别呢？我个人认为是要实现一致性，必然需要经历共识的过程，所以共识算法可以简单看作是一致性算法的一个步骤。 本文就针对核心的共识部分，通过列举一些常用的共识算法思想来帮助大家理解。

POW

全称是Proof Of Work，即工作量证明。前文我们已经讲过了POW简单来说就是解数学题，通过不断地计算，最终得出正确答案的过程。

输入数据是 “自增数+该区块的Hash”，由于没办法预测输出结果，且区块的Hash是定值，所以只能不断的用自增数去试，直到试出这个答案来

仅仅是这样就能实现POW算法了吗？其实上面计算nonce只是算法的一部分，该算法还约定了所有节点总是倾向于选择更长链，即使用更长链的hash作为previousHash的区块，以及只要这几个条件都满足了要无条件接受。只有以上几点同时满足，POW算法才能正常工作。
接下来再针对几个维度看看POW算法的表现如何

• 安全性 假设存在攻击者且如果攻击者节点的总算力是大于忠实节点的总算力，则攻击者总会攻击成功。为什么呢？不论忠实节点怎么出块，都赶不上攻击节点的篡改速度，因为攻击节点算力高，算出nonce的速度更快，这也是常说的51%算力攻击。攻击者可能达到全网51%的算力吗？不能说不可能，但绝对可以说很难，退一万步看即便真达到51%算力了，那是多么恐怖的资源，攻击区块链带来的收益恐怕无法填补收集这些资源带来的损益。所以也从经济层面上制约了该情况的产生，而这也正是比特币能稳定运行十多年的原因。 还有说POW算法不抗量子攻击，因为量子计算机在做hash运算时效率非常高，所以传统计算机要算很久的nonce对于量子计算机分分钟就算出来了，所以不安全。论据没错，但是结论错了，因为POW算法只是一种思想，并没有非要绑定hash算法，如果量子计算真普及了，完全可以设计一种抗量子的数学模型来替代计算hash。
• 环保性 不知道当时中本聪选用该算法时有没有预料到，若干年后竟然滋生出专门的“矿产业链”，当中涉及了挖矿机房、矿卡、挖矿能源、矿机、挖矿木马等，非常的em…。在越来越提倡环保的现代社会下，还存在消耗大量能源去挖矿的事情，怎么看都是很魔幻的。所以监管的利剑也是可预见地挥了下来，大力整治挖矿这种白白消耗能源地投机活动。所以POW算法在这个维度上看，算是饱受诟病的，这也为后来的更加环保的算法催生提供了前提条件。
• 稳定性 在谈安全性的时候说了算法简单，攻击困难是比特币能够稳定运行的前提，及必要条件，那要达到稳定运行的效果是不是仅满足安全性就好了呢？答案当然是否定的。根据摩尔定律集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。也就说，处理器的性能大约每两年翻一倍，算力提升速度非常之快。十年前的计算机算力和十年后的相比就更是天差地别了，所以算hash的速度也是不一样的，这就需要一定的规则去控制解题时间。比特币的做法是动态调参计算位数，如果普遍计算时间大于10min则减少位数，反之则增加位数，使用让计算时间保持在10min上下小范围波动。这也是其能稳定运行的重要原因。

POS

正如上面提到POW算法由于非常的不环保，催生了很多更加环保的共识算法，其中就有POS，Proof Of Stake，即权益证明算法。这个算法也没有过多的数学论证，更多的是一种设计思想上的创新。既然POW是率先算出答案的才有绝对话语权，会让参与区块链的用户陷入无尽的算力之争，那就让你直接不用算了，而是通过 “购买股份” 的方式来决定你的相对话语权。
可以想象成现实生活中我们使用金钱去购买某家公司的股权，占的股比越高在股东大会上的话语权也就越高。而放在区块链的世界中，其典型的实践就是通过质押代币来实现购买股份的目的，谁购买的代币越多谁的话语权就更高，也就更容易被推选出来作为记账者。如果被选举成为记账者，但是被发现作恶时，则会按照其行为扣除其质押的代币，来一定程度上遏制作恶行为的产生。
正是这样简单的机制，就避免了前面提到的能源浪费问题。但是POS也有一些缺点，比如在区块链运行前期少数人才能挖矿，因为代币都集中在少数人手里。还有很容易造成矿工囤积代币，以期获得更多的记账权，进而造成代币越来越向更多持有者集中（有点像现实生活中的马太效应，钱越来越向少数富人集中）。

PBFT

前面提到的算法都是有效适用于海量节点的，也就是公链很适合使用的，但是忽略了一个使用场景就是联盟链和私链。这种场景的节点数一般较少，且一般需要进行身份验证，所以对于共识算法来说就可以不依赖现实生活中的资源（如算力、代币）作为因素来进行，可以通过节点间纯通信来实现强一致性。这种类型的算法往往需要全节点协商参与共识，就必然涉及到节点间的通信，在通信过程中如果节点数过多通信的次数过多，则很容易出现网络风暴进而造成整个网络瘫痪。
PBFT即Practical Byzantine Fault Tolerance，意为实用拜占庭容错算法，在将这个算法前有必要先说一下什么是拜占庭容错，而这就是为了解决著名的拜占庭将军问题

拜占庭是一个地名，位于如今的土耳其的伊斯坦布尔，在古代是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。

而拜占庭容错，是由Leslie Lamport在其论文中提出的分布式对等网络通信容错问题。在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。
首先来看一看PBFT算法的几个步骤示意图

简单解释下，C代表客户端，0、1、2、3代表服务节点（其中0表示主节点）。整个算法执行过程中共产生5个状态跃迁，request -> pre-prepare -> prepare -> commit -> reply，有点类似于分布式事务中的二阶段提交。接下来分别对每个阶段展开说明：

• request : 即客户端向服务集群发送请求
• pre-prepare : 主节点收到请求后，会对本次请求生成一个唯一的编号n，然后把请求和编号n组合生成pre-prepare报文并广播给所有成员节点（图中表示3就是拜占庭节点，收到广播后不响应）
• prepare : 所有成员节点在收到pre-prepare报文后，首先需要验证消息的正确性，即是否由主节点签发，如果正确无误，则将编号n由本节点签名后生成prepare报文，再广播给其他所有节点（包括主节点）
• commit : 所有节点收到prepare报文，首先校验签名是否由对应节点签发。然后统计收到的正确报文数量，若超过全部节点数量的2/3-1，则认为请求是达成一致了的，即对所有节点广播签名后的commit报文
• reply : 所有节点收到commit报文，首先还是得校验签名是否由对应节点签发。其次统计收到的正确报文数量是否超过全部节点的2/3，是则说明请求已完成，构建reply报文响应给客户端。客户端则是判断是否收到超过1/3+1的正确回复来判断请求是否完成。

这里面涉及几个问题：

• 为什么在判断prepare报文的条件为是否超过2/3-1？ 因为PBFT算法规定在拜占庭节点（即非正常节点）不能超过所有节点的三分之一，否则无法完成共识。假设所有拜占庭节点在该阶段均不正确响应，也最多影响三分之一的数量，所以超过三分之二时则表示所有正常节点均已正常响应。之所以还要减一是因为主节点在prepare阶段没有进行广播，所以减去主节点即可。
• 为什么客户端是根据是否收到1/3+1个正确回复来判断请求是否完成？ 因为客户端对于服务端内部的共识过程完全不关心也无法感知到，所以只需要考虑最坏情况，所有拜占庭节点都响应了虚假的reply报文，只要有一个正常节点响应了也说明请求是真的成功了。
• [灵魂拷问]为什么规定拜占庭节点不能超过总节点的1/3？ 设总结点数为n，拜占庭节点数为f，也就说至少n-f个节点在每个阶段会正常广播，而收到n-f个报文时无法判断这里面是否含有拜占庭节点发的，最坏情况是其中有f个都来自拜占庭节点也不能影响共识，所以能列出不等式n-f-f>f => n≧3f+1
• 上述步骤中很关键的一步是主节点需要发出pre-prepare报文才能继续下面的操作，那主节点就是拜占庭节点，故意不发送怎么办？ PBFT中有一个视图轮换机制，设视图编号为v，节点数为n，则当前的主节点是 v mod n = i即节点i，而v始终是自增的，所以主节点是轮换着的。那何时轮换呢？答案是当操作没有正确处理时。就拿该问题的场景来举例，主节点作恶故意不发送pre-prepare报文，势必造成客户端一直收不到响应。而客户端在一定时间内未收到正确响应会向其他节点发出请求，其他节点收到后会将v自增构建出view-change报文进行广播，共识成功后，视图轮换成功。另外所有从节点本身也维护了一个timeout计时器，如果长时间未收到主节点的报文也会发起视图轮换。

Raft

上面介绍的PBFT算法在消息复杂度上比较高，因为其设计的是三阶段共识，那有没有复杂度相对低一点的共识算法呢，就是本节的主角Raft。对于Raft大家应该都熟悉，因为它常常被用作各大中间件的一致性算法，如Zookeeper、Elasticsearch、Redis等。
Raft将节点分为三种状态，分别是Follower、Candidate、Leader

• Follower：只能被动的接受来自Leader的指令，当超时未收到Leader的消息时则自动切换为Candidate
• Candidate：只能向其他节点广播选举自己成为Leader的消息，如果获取到超过半数的投票则切换为Leader
• Leader：负责处理请求，以及定时广播心跳信息，防止Follower认为自己挂掉了，进而被替代掉

设想一个场景，Leader所在的主机网络突然故障了，导致心跳包没能及时广播到Follower节点，所以Follower节点们纷纷超时后切换为Candidate节点发起了竞选Leader的投票并成功选出了一个新Leader，此时原Leader的网络恢复了，会发生怎样的后果呢？Raft中有个Term的概念即任期，每一个Leader都有属于自己的任期，而任期又始终是自增的。所以回到这个场景中，原Leader的任期肯定是小于新Leader的任期的，所以当原Leader收到新Leader的广播消息后会自动把自己降级为Follower，有效避免了冲突。

Raft的处理过程并没有引入二阶段提交，甚至是三阶段提交的机制，因为Raft是“一言堂”所有的事儿只需要听大哥安排就好。具体的事务在Raft中被视为一个个的“日志”，它是通过日志复制来进行一致性处理的。
每条日志都包含有索引号以及产生时的任期号，是按顺序排列的，一旦某条日志以及被复制到超过半数的节点上，则表示该日志已经被提交，即可以对客户端进行响应了。分布式系统中突然的网络中断是不可避免地，在出现频繁的复制失败、Leader选举之后，节点之间的日志存储情况可能天差地别，如下图所示。

每一个方块表示一个日志条目，里面的数字表示任期号，按照日志索引号顺序排列着的，这里面就包含了如下异常情况：

• 存在缺少一些日志的节点（a-b）
• 存在有未提交日志的节点（c-d）
• 两种情况均有的节点（e-f）

这种情况下，Raft会怎么处理呢？Leader节点会根据自身的最大索引日志向其他所有节点进行AppendEntry RPC操作，内容包含最大日志的索引号，而收到的节点如果发现和前一日志索引号存在断层或不匹配则拒绝响应，Leader只要收到任意拒绝响应则将索引号前移一位后再次重试。所以针对上述情况是按照如下逻辑进行处理的。

• 对于缺少日志就很好处理了，在不断地重试过后总能找到最早地日志块然后一个一个地向后补齐，如a的10，b的5-10
• 对于比Leader多的部分日志会被直接丢弃，如c的11，d的11-12，f的11
• 对于和Leader冲突部分的日志会被直接覆盖，如e的6-7，f的4-10

那么问题又来了，按照上图的情况，假如当选的Leader是b，那岂不是很多日志都要被丢弃了？ 还记得前面说过有个日志提交的概念吗，只要被复制到超过半数的节点上，该日志就属于提交状态的，是不会被覆盖的，现在可以讲Raft是如何实现这一机制的。在新Leader选举时还会有一个额外的条件，即拉票节点是否包含有最大已提交日志块，只有是的情况下才给其投票。可以看到任期6索引9就是被提交的最大日志块，所以这种情况下能当选Leader的，只有a、c、d以及当前Leader这四个几点可能会当选Leader，所以此情况下b不可能当选为Leader。
总来地说，Raft相对于PBFT高效且相对简单，但缺点是并不能容忍作恶节点。

其他共识算法

随着区块链的热度越来越高，对于共识算法的研究也是越来越广泛深入，发明出的共识算法种类也是种类繁多。上文提到了，PBFT、Raft等强一致性算法无法适应海量节点数量，甚至上百个节点数性能就已严重受到影响，所以绝大部分还是围绕POX方向进行展开，因为区块链最大的应用场景还是公链，其节点数都是非常庞大的。目前已知的大致有：

• POC：Proof Of Capacity，容量证明，为了改进POW能耗高的问题，方法仍然是算题，但这些题可以通过存储一系列的中间值来简化，存储的越多运算速度越快，所以最终是拼容量
• POA：Proof Of Authority，权威证明，其实和权益证明差不多，改进了因为质押代币而造成的一系列问题，但是引入权威的概念可能会使去中心化程度不那么高。还有诸如POWeight、POR、POET都是这个范畴。
• POR：Proof Of Weight，权重证明，这个是在POS的基础上引入了权重的概念，
• …

算法种类还有很多就不一一列举了，如果有兴趣进一步了解的，可以跳转这篇文章进行查看。