共识算法学习记录

包括POW,POS,DPOS,PBFT,RAFT

学习资料

区块链共识算法综述

拜占庭将军问题

「拜占庭将军问题」来源于这样一个场景：拜占庭帝国的军队正在围攻一座城市。这支军队被分成了多支小分队，驻扎在城市周围的不同方位，每支小分队由一个将军领导。这些将军们彼此之间只能依靠信使传递消息（无法聚在一起开个会）。每个将军在观察自己方位的敌情以后，会给出一个各自的行动建议（比如进攻、撤退或按兵不动），但最终的需要将军们达成一致的作战计划并共同执行，否则就会被敌人各个击破。但是，这些将军中可能有叛徒，他们会尝试阻止其他忠诚的将军达成一致的作战计划。

这就是拜占庭将军的「问题」：只能依靠通信相互交流，又不知道谁是叛徒，怎么能不受叛徒们的影响，让这些忠诚的将军快速的达到一致的作战计划呢？

很显然，将这一场景套用到计算机系统中也是非常适用的：在一个分布式系统中，针对每个运算，每台独立的机器也需要最终达成一致的结果。但每台计算机之间也只能依靠网络通信（显然它们无法聚在一起开会），每台计算机都有出错的可能（被攻击，或故障），从而变成「叛徒」干扰正常的计算机达成一致。

这一问题是由 Leslie·Lamport 等人在这篇论文中提出的，并在论文中给出了理论可行的解决方案和证明。事实上, 拜占庭将军问题是分布式系统领域最复杂的容错模型, 它描述了如何在存在恶意行为(如消息篡改或伪造)的情况下使分布式系统达成一致。 是我们理解分布式一致性协议和算法的重要基础。

论文中给出了一个结论: 如果存在m个叛将, 那么至少需要3m+1个将军, 才能最终达到一致的行动方案。

Leslie Lamport在论文中给出了两种拜占庭将军问题的解决方案, 即口信消息型解决方案(A solution with oral message)和签名消息型解决方案(A solution with signed message).

口信消息型解决方案

首先, 所谓口头消息，是指内容完全由发送者或转发者控制的消息。需要对消息传递系统作如下的限制：

• A1. 任何已经发送的消息都将被正确传达
• A2. 消息的接收者知道是谁发送了消息
• A3. 消息的缺席可以被检测

A1 和 A2 可以防止叛徒干扰两个将军之间的通信：A1 让叛徒无法在通信过程中修改信息；A2 让叛徒无法冒充其它将军发送消息。A3 可以防止叛徒通过不发消息的方式影响一致共识的达成。并且如果将军们发现缺少某个消息，他们可以使用统一的默认值（比如RETREAT）来替代缺失的消息。

签名消息型解决方案

口头消息的解决方案之所以复杂，就是因为叛徒可以随意改更忠诚将军的消息，而别人无法发现消息被改。如果我们让忠诚将军的消息无法篡改，那么问题就变得简单多了。这就是签名消息的解决方案。所以, 签名消息的限制是在口信消息定义的基础上增加了如下两条:

• A4. 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现
• A5. 任何人都能验证将军签名的真伪

这里通过消息不可篡改这一特性，让所有忠诚将军成为「一体」，就像同一个人一样。

签名消息型解决方案可以处理任何数量叛将的场景.

POW

干的越多，获得越多。

介绍

工作量证明（PoW，Proof of Work）

代表项目：BTC

PoW是是首个共识算法。它是由中本聪在他的论文中提出的，用于建立分布式无信任共识并识别“双重支付”（double spend）问题。PoW并非一个新理念，但是中本聪将Pow与加密签名、Merkle链和P2P网络等已有理念结合，形成一种可用的分布式共识系统。

由于不同的节点接受数据有所区别，为了保证数据一致性，每个区块数据只能由一个节点进行记录。BTC通过POW来确认记账节点。每个节点如果想生成一个新的区块并写入区块链，必须解出比特币网络出的PoW问题。其关键的要素是工作量证明函数、区块信息及难度值。工作量证明函数是这道题的计算方式，区块决定了这道题的输入数据，难度值决定了这道题所需要的计算量。可以简单理解成就是将不同的nonce值作为输入，尝试进行SHA256哈希运算，找出满足给定数量前导0的哈希值的过程。而要求的前导0的个数越多，代表难度越大。

新难度值=旧难度值×（过去2016个区块花费时长/20160分钟）

目标值=最大目标值/难度值

其中最大目标值为一个恒定值，难度为1时的目标值，即2^224：0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

比特币工作量证明的达成就是矿工计算出来的区块哈希值必须小于目标值

比特币节点求解工作量证明问题的步骤大致归纳如下：

1. 生成铸币交易，并与其他所有准备打包进区块的交易组成交易列表，通过Merkle树算法生成Merkle根哈希；
2. 把Merkle根哈希及其他相关字段组装成区块头，将区块头的80字节数据作为工作量证明的输入；
3. 不停地变更区块头中的随机数，即nonce的数值，并对每次变更后的区块头做双重SHA256运算（即SHA256（SHA256（Block_Header））），将结果值与当前网络的目标值做对比，如果小于目标值，则解题成功，工作量证明完成。

优缺点

优点：

1）去中心化，将记账权公平的分派到其他节点。你能够获得的币的数量，取决于你挖矿贡献的有效工作，也就是说，你用于挖矿的矿机的性能越好，分给你的收益就会越多，这就是根据你的工作证明来执行币的分配方式。

2）安全性高，破坏系统需要投入极大的成本，如果想作弊，要有压倒大多数人的算力（51%攻击）。因为作弊要付出一定成本，作弊者就会谨慎对待了。在比特币的 PoW 机制中，由于获得计算结果的概率趋近于所占算力比例，因此在不掌握51%以上算力的前提下，矿工欺诈的成本要显著高于诚实挖矿，甚至不可能完成欺诈(由于概率过低)。

缺点：

1）挖矿造成大量的资源浪费，目前bitcoin已经吸引全球大部分的算力，其它再用Pow共识机制的区块链应用很难获得相同的算力来保障自身的安全。这让依据算力公平分配奖励的机制，演变为了对矿机算力的大举投入，扭曲了中本聪的设计初衷。

2）网络性能太低，需要等待多个确认，容易产生分叉，区块的确认共识达成的周期较长（10分钟），现在每秒交易量上限是7笔（visa的平均每秒交易量上万，支付宝峰值接近9万），不适合商业应用。

3）PoW共识算法算力集中化，慢慢的偏离了原来的去中心化轨道。从比特币扩容之争可以看到，算力高的大型矿池是主人，而持币的人没有参与决定的权利，比特币分叉出很多儿子，即将失去“去中心化”的标签。

POS

持有越多，获得越多。

介绍

权益证明（PoS，Proof of Stake）

以太坊正在由POW转为POS

PoS 试图解决 PoW 机制中大量资源被浪费的情况。

在 POW 工作量证明中，主要是根据算力来决定哪个节点可以进行生产新区块，算力越大有越大的概率获得打包新区块的机会; 而在 POS 权益证明中主要就是根据股权，拥有的股权高即有越高的概率获得生产新区块的机会。

在 POS 权益证明共识机制里有个专有名次叫做币龄。在 POS 权益证明共识系统中的每个货币每天都会产生 1 币龄，若你在权益证明机制中拥有 100 枚货币并存放了 10 天，你的币龄就为 1,000。若你成功被系统挑选出挖掘新区块，你的币龄会归 0 并重新开始累积计算，你会获得的奖励公式如下：

奖励 = 币龄 * 年利率 / 365

意味你每被清空 365 币龄即会从区块中会得 N% 年利率的货币奖励。假使在一个当前年利率为 5% 的系统中，你每成功帮忙打包一个新区块会获得的奖励为 1,000 * 5% / 365 = 0.137 个系统货币。

优缺点

优点：

1）在一定程度上缩短了共识达成的时间。

2）不再需要大量消耗能源挖矿。

3）Pos 当然也能防作弊，因为如果一名持有 51%以上股权的人作弊，相当于他坑了自己，因为一个人自己不会杀死自己的钱。

缺点：

1）还是需要挖矿，本质上没有解决商业应用的痛点；

2）POS面临的最严重的一个问题就是无成本利益问题，在PoS系统中做任何事几乎没有成本，比如在PoS系统上挖矿几乎没有成本，这也就意味着分叉非常方便。

3）极端的情况下会带来中心化的结果。PoS 机制由股东自己保证安全，工作原理是利益捆绑。在这个模式下，不持有 PoS 的人无法对 PoS 构成威胁。PoS 的安全取决于持有者，和其他任何因素无关。在POS机制里，拥有币和币龄越高的节点拥有着越高产生新区块的权力。简单来说，就是你拥有越多的币，并且你拥有的币的币龄越久，就有可能获得记账权的概率越大。POS虽然解决了POW的能耗的问题，但全节点确认会让区块确认的效率提不起来，且时间越长，也越容易产生马太效应，即持有币越多的人会获得更多的币奖励，从而加大贫富差距，最终产生超过50%的中心化节点，被动演化为非预期的中心化的结果。

4）币龄其实就是时间，一旦挖矿者囤积一定的币，很久很久之后发起攻击，这样将很容易拿到记账权。并且，矿工可以囤积代币从而导致货币流通困难。

DPOS

带中心化思路的共识机制

人民代表大会制度

介绍

委任权益证明（DPOS，Delegated Proof-of-Stake）

DPoS算法是根据当时PoW、PoS的不足而改进的共识算法，它的目的就是为了提高性能，也就是交易确认时间短。

跟PoS不同的是，持有少数股份（权益）的节点也能行使他们的共识权了，只不过是以一种间接的方式。类似于股东代表大会，每当要决策公司大事（记什么账，谁来记账）的时候，全体股民（节点）依法行使投票权，选出自己心中的股东代表（可信账户），谁得票高谁当选。候选人可以去公开演讲拉票，获得足够多股民（节点）的信任，然后股东代表（被选中的可信节点）代表股民决策公司大事，股东代表的人数由系统决定，比如Bitshares为101个、Asch为51个，EOS为21个。

比特股（Bitshare）是一类采用DPoS机制的密码货币，它期望通过引入一个技术民主层来减少中心化的负面影响。

它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。

比特股引入了见证人这个概念，见证人可以生成区块，每一个持有比特股的人都可以投票选举见证人。见证人会因为生成区块而获得一笔支付费用。该费用是由权益持有者设立的 。得到总同意票数中的前N个（N通常定义为101）候选者可以当选为见证人，当选见证人的个数（N）需满足：至少一半的参与投票者相信N已经充分地去中心化。见证人的候选名单每个维护周期（1天）更新一次。见证人然后随机排列，每个见证人按序有2秒的权限时间生成区块，若见证人在给定的时间片不能生成区块，区块生成权限交给下一个时间片对应的见证人。DPoS的这种设计使得区块的生成更为快速，也更加节能。

DPoS充分利用了持股人的投票，以公平民主的方式达成共识，他们投票选出的N个见证人，可以视为N个矿池，而这N个矿池彼此的权利是完全相等的。持股人可以随时通过投票更换这些见证人（矿池），只要他们提供的算力不稳定，计算机宕机，或者试图利用手中的权力作恶。

在 DPoS 中，矿工可以合作生成块，而不是像在 PoW 和 PoS 中那样竞争生成。通过区块生成的部分中心化，DPoS 的运行可以比其它共识算法呈数量级快。

注意

1）DPoS机制中的股民（节点）根据自己持有的加密货币数量占总量的百分比（占股比例）来投票，不是一人一票；

2）选举出的股东代表（可信节点）完全对等，可理解为具有同等算力的101个矿池；

3）股东代表一旦无能、不作为、胡作为（提供的算力不稳定，计算机宕机、或者试图利用手中的权力作恶），将立刻被股民踢出整个系统，然后由其他后备代表顶上去；

4）决策完公司大事（记完账、出完块）有钱分，根据占股比例。

优缺点

优点：

节能、快速、高流量博客网站Steemit就使用了它。EOS 的块时间是 0.5 秒。

1）记账节点减少，交易速度更快，EOS号称可达百万TPS；

2）更加安全，一般不不会发生链分叉并不可逆，确保最终一致性；

3）相对PoW，解决了资源消耗问题；

缺点：

1）略为中心化、拥有高权益的参与者可投票使自己成为一名验证者。DPoS机制的设计并不能保证一定有足额的真实的区块生产者，因为一个人或一个实体，可能控制着多个节点。这是近期已在 EOS 中出现的问题。

2）对于坏节点的处理存在诸多困难。社区选举不能及时有效的阻止一些破坏节点的出现，给网络造成安全隐患，同时在网络节点数量少的场景，选举的BP代表性不强。

PBFT

介绍

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

PBFT算法的核心理论是N>=3F+1，其中N是总节点数，F是故障节点（故障包括叛徒或不响应）。假如有F个故障节点，至少有3F+1个节点才能保证整个系统正确运行。

Practical Byzantine Fault Tolerance（原论文）

参考

算法流程：

PBFT基于拜占庭将军问题，一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)

其中C为发送请求端，0123为服务端，3为宕机的服务端（即作恶节点），具体步骤如下：

1.Request：请求端C发送请求到任意一节点，这里是0

2.Pre-Prepare：服务端0收到C的请求后进行广播，扩散至123

3.Prepare：123,收到后记录并再次广播，1->023，2->013，3因为宕机无法广播 。在一定时间范围内，如果收到超过 2f +1个不同节点（包括自己）的 prepare 消息，就代表 prepare 阶段已经完成。

4.Commit：0123节点在Prepare阶段，若收到超过一定数量的相同请求，则进入Commit阶段，广播Commit请求； 当收到 2f+1 个 commit 消息后（包括自己），代表大多数节点已经进入 commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。

5.Reply：0123节点在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈；c收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。

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

某副本收到f+1个相同的反馈确认，如果这f+1个反馈中包含faulty节点发过来的消息，是不能作数的，因为faulty节点是墙头草，给副本i发送的消息和副本j发送的消息不一致(类⽐一下一个汉奸跟游击队说⾃己是爱国的，跟⻤子说⾃己是忠⼼的)。必须要2f+1个相同的反馈确认才能保证f+1个non-faulty节点正常，这时候即便f个faulty节点给不同⼈发不同消息也没关系，f+1个non-faulty节点已经形成了统一战线，他们在⼈数上已经多于那些墙头草了，可以达成⼀致了。

因此，如果顺利的话，一个节点收到1个pre-prepare消息和2f个和prepare消息进入commit阶段，2f+1个commit消息后可以reply给client，client收到f+1个回复就可以确认提交成功。

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就能保证他拿到的是整个系统内“大多数正常节点“的意见，从而达到一致性。

优缺点

优点：

1）适用于permissioned systems (联盟链/私有链)，能容纳故障节点，也能容纳作恶节点。要求所有节点数量至少为3f+1（f为作恶/故障不回应节点的数量），这样才能保证在异步系统中提供安全性和活性。

2）解决了原始拜占庭容错(BFT)算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

缺点：

1）仅仅适用于permissioned systems (联盟链/私有链)。

2）通信复杂度过高，可拓展性比较低，一般的系统在达到100左右的节点个数时，性能下降非常快。

3）PBFT在网络不稳定的情况下延迟很高。

RAFT

介绍

参考

Raft协议是一种分布式一致性协议。一个节点有3种状态：

1. Follower state.
2. Candidate state.
3. Leader state.

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout：

（1）收到选举的请求

（2）收到 Leader 的 Heartbeat

在 Raft 运行过程中，最主要进行两个活动：

（1）选主 Leader Election

（2）复制日志 Log Replication：leader接受来自客户端的命令，记录为日志，并复制给集群中的其他服务器，并强制其他节点的日志与leader保持一致

优缺点

优点：

模型比Paxos更简单，但提供了同等的安全性。有多种语言的实现可用。

缺点：

1）通常用于私有网络和许可网络

2）顺序投票，只能串行apply，因此高并发场景下性能差。