[大数据]区块链主流共识算法简介

简介

本文主要是参考网上资料自己对区块链共识算法做的一个汇总和简介
主要参考文章一文读懂11个主流共识算法, 彻底搞懂PoS,PoW,dPoW,PBFT,dBFT这些究竟是什么鬼

何为共识算法

所谓共识，简单理解就是指大家都达成一致的意思。其实在现实生活中，有很多需要达成共识的场景，比如开会讨论，双方或多方签订一份合作协议等。

而在区块链系统中，每个节点必须要做的事情就是让自己的账本跟其他节点的账本保持一致如果是在传统的软件结构中，这几乎就不是问题，因为有一个中心服务器存在，也就是所谓的主库，其他的从库向主库看齐就行了。

在现实生活中，很多事情人们也都是按照这种思路来的，比如企业老板发布一个通知，员工照着做。但是区块链是一个分布式的对等网络结构，在这个结构中没有哪个节点是“老大”，一切都要商量着来。

所以在区块链系统中，如何让每个节点通过一个规则将各自的数据保持一致是一个很核心的问题，这个问题的解决方案就是制定一套共识算法。

拜占庭将军问题是什么？

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

图1：三个将军均为忠诚的场景 （2：1 进攻）

当三个将军中存在一个叛徒时，将可能扰乱正常的作战计划。图2展示了General C为叛徒的一种场景，他给General A和General B发送了不同的消息，在这种场景下General A通过投票得到进攻：撤退=1:2，最终将作出撤退的行动计划；General B通过投票得到进攻：撤退=2:1，最终将作出进攻的行动计划。结果只有General B发起了进攻并战败。

图二：两忠一叛（A：1：2撤退；B：2：1进攻）（作战失败）**

事实上，对于三个将军中存在一个叛徒的场景，想要总能达到一致的行动方案是不可能的。详细的证明可参看Leslie Lamport的论文。此外，论文中给出了一个更加普适的结论：如果存在m个叛将，那么至少需要3m+1个将军，才能最终达到一致的行动方案。

两种解决方案：

1、口信消息型解决方案

首先, 对于口信消息(Oral message)的定义如下：

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

基于口信消息的定义，我们可以知， 口信消息不能被篡改但是可以被伪造。即使出现了伪造或错误的讯息。只要有问题的将军的数量不到三分之一，仍可以达到“拜占庭容错”。

原因是把同样的标准下放到“军官与士官的问题”时，在背叛的军士官不足三分之一的情况下，有问题的军士官可以很容易的被纠出来。

结论：以函式来表示，将军的总数为n，n里面背叛者的数量为t，则只要n > 3t就可以容错。

2、签名消息型解决方案

**
同样，对签名消息的定义是在口信消息定义的基础上增加了如下两条：

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

基于签名消息的定义，我们可以知道，签名消息无法被伪造或者篡改。为了深入理解签名消息型解决方案，我们同样以3三将军问题为例进行推导。 图3是忠将率先发起作战协商的场景，General A率先向General B、C发送了进攻消息，一旦叛将General C篡改了来自General A的消息，那么General B将将发现作战信息被General C篡改，General B将执行General A发送的消息。

图3. 忠将率先发起作战协商

图4是叛将率先发起作战协商的场景，叛将General C率先发送了误导的作战信息，那么General A、B将发现General C发送的作战信息不一致，因此判定其为叛将。可对其进行处理后再进行作战信息协商。

图4. 叛将率先发起作战协商

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

主流共识算法

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

优点：自 2009 年以来得到了广泛测试，目前依然得到广泛的使用。

缺点：速度慢；耗能巨大，对环境不好；易受“规模经济”（economies of scale）的影响。

使用者：Bitcoin、Ethereum、Litecoin、Dogecoin等。

类型：有竞争共识（Competitive consensus）。

简单来说就是要求使用者进行一些耗时适当的复杂运算，并且答案能被服务方快速验算，以此耗用的时间、设备与能源做为担保成本，以确保服务与资源是被真正的需求所使用。

货币上应用（bitcoin）:

由分散在各处的计算机，竞赛谁能最早找出，搭配原本要打包的资料的穷举猜测值，谁就等同获得该区块的打包权（记帐权）。此猜测值被找出后，与资料、杂凑值一起打包成块后广播，经多数节点确认与承认，打包者就能获得打包该区块所提供的奖励。一般采用工作量证明的加密货币，好比比特币，会设定成随著参与竞赛的算力增减，而调整找寻猜测值的难度，以维持合理的运作速度。

工作量证明和安全性:

矿工会因挖矿而收到回报。 对于所有矿工的一个子集而言，他们几乎没有动机去开辟一条属于自己的新链——因为这破坏了系统。 区块链依赖于唯一状态来作为其真实性的来源。 同时使用者要始终选择最长的或者最重的链。

工作量证明机制是为扩展链的长度。 最长的链是最可信的，因为它完成了最多的计算工作。 在 PoW 系统中，几乎不可能创建一个新区块去擦除交易信息、创建假区块或者维持第二个链。 这是因为恶意矿工需要比其他所有人更快地计算出区块。

要一直创建恶意但有效的区块，你需要有超过 51% 的全网采矿能力去打败其他人。 这样你就需要大量的计算算力才能完成这样一个“工作”。 而能源支出可能甚至超出你做这样一次攻击所取得的成果。

2. 权益证明（PoS，Proof of Stake）

优点：节能；攻击者代价更大；不易受“规模经济”的影响。

缺点：「无利害关系」(Nothing at stake)攻击问题。

使用者：Ethereum（即将推出）、Peercoin、Nxt。

类型：有竞争共识。

正是因为PoW算法在挖矿过程中对环境和电力的浪费极大，PoS才作为一种代替算法。

POS也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。让获得担任验证者工作的人获得奖励以吸引更多的人参与。此奖励通常会依照验证者持有的货币数量来计算，当持有的量越多获得的奖励也越高。

3. 延迟工作量证明（dPoW，Delayed Proof-of-Work）

PoB（Proof of Burn）叫做焚烧证明机制，是一种通过焚烧自己手中的代币来表决谁拥有对网络的领导地位的承诺。焚烧代币的数量越多，能获得网络领导地位的概率越高。PoB是分布式共识的一种方法，也是工作量证明机制的替代方法。它也可以用来引导一种加密货币。

在基于DPoW的区块链中，矿工挖矿所获得的不再是奖励的代币，而是可以焚烧的“wood”——燃木。矿工使用自己的算力，通过哈希算法，最终证明自己的工作量之后，获取对应的wood，wood不可交易。当wood积攒到一定量之后，可以前往燃烧场地燃烧wood。

通过一组算法计算后，燃烧较多wood的人或者BP或者一组BP可以获取下个事件段出块的权利，成功出块后获取奖励（代币）。由于一个时间段内可能会有多人燃烧wood，下一个时间段出块的概率由自己燃烧wood数量决定。焚烧的越多，下一段时间可以获得出块权利的概率越高。

4. 授权 PoS（DPoS，Delegated Proof-of-Stake）

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

缺点：略为中心化；拥有高权益的参与者可投票使自己成为一名验证者（这是近期已在 EOS 中出现的问题）。

采用者：BitShares、Steemit、EOS、Lisk、Ark。

类型：协同型共识

它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。

类似人民代表大会制度。

除了以上介绍的4种共识算法还有一些主流的共识算法如：

实用拜占庭容错算法（PBFT：Practical Byzantine Fault Tolerance）

授权拜占庭容错算法（dBFT，Delegated Byzantine Fault Tolerance）

权威证明（PoA，Proof-of-Authority）

所用时间证明（PoET，Proof of Elapsed Time）

权益流通证明（PoSV，Proof of Stake Velocity）

恒星共识（Stellar Consensus）

活动证明（PoActivity，Proof Of Activity）

具体可以参考资料【1】

参考资料及链接：

1. 一文读懂11个主流共识算法, 彻底搞懂PoS,PoW,dPoW,PBFT,dBFT这些究竟是什么鬼
2. 拜占庭将军问题 维基百科，自由的百科全书
3. 拜占庭将军问题是什么？区块链如何防范恶意节点？
4. 拜占庭将军问题论文《The Byzantine Generals Problem 》
5. 一文读懂拜占庭将军问题

一些论坛及网站：

1. 鸵鸟区块链
2. 巴比特
3. Ethfans