关于区块链:区块链常见共识算法概述

共识的含意

对于事实世界，共识就是一群人对一件或者多件事件达成统一的认识或者协定，在计算机世界，多个节点对某个数据达成统一共识，多个节点对多个数据的程序达成统一共识。

共识算法的三大分类

• 私链：私链的共识算法即区块链这个概念还没遍及时的传统分布式系统里的共识算法，私链的实用环境个别是不思考集群中存在作恶节点，只思考因为零碎或者网络起因导致的故障节点，常见算法包含raft,paxos
• 联盟链：联盟链的实用环境除了须要思考集群中存在故障节点，还须要思考集群中存在作恶节点，对于联盟链，每个新退出的节点都是须要验证和审核的，常见算法包含pbft,dbft
• 公链：公链一直须要思考网络中存在故障节点，还须要思考作恶节点，这一点和联盟链是相似的，和联盟链最大的区别就是，公链中的节点能够很自在的退出或者退出，不须要严格的验证和审核，常见算法包含pow,pos,dpos,ripple

Pow(Proof of Work)

概述

• 用一份证实来确认做过一定量的工作，工作方须要破费很长时间去得出一个后果，验证方能够很容易应用该后果来验证工作方的工作量
• 通过暴力破解办法解决一个数学难题，在哈希计算后失去一个小于目标值的哈希值

举例

给定一个字符串 Hello, world!，当初要求在该字符串前面加上一个nonce 的整数值，采纳 SHA256 哈希运算之后，哈希后果合乎前 4 位是 0，即后果是0000*，则验证通过

能够采纳 python 代码实现如下

import hashlib

msg = "Hello, world!"
for i in range(1000_000_000):
    result = hashlib.sha256(f'{msg}{i}'.encode()).hexdigest()
    if result.startswith('0000'):
        print(f'nonce: {i}, result: {result}')
        break

下面的输入后果是

nonce: 4250, result: 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

下面为了计算出一个符合条件的哈希值，运算了 4251 次，失去了 nonce 的值为 4250，这样验证方就能够拿着一个 Hello, world! 的信息，加上一个 nonce 为 4250 的值，运算一次，得出的哈希后果就能够验证符合要求，证实了工作量

哈希函数次要阐明与特色

• 输出 x 的长度任意，输入 H(x) 的长度固定，计算 H(x) 的过程是高效的
• 免碰撞，哈希函数的输入须要足够随机，即不会呈现输出 x≠y，然而H(x)=H(y)。比特币采纳的SHA256 算法，输入长度是 256，输入可能性就是 2^256，所以当输出 2^256+ 1 次，则必然产生一次碰撞，然而事实中，运算 2^32 大略是 40 亿次，运算 2^256 次是压根就没法计算完的。
• 不可逆性，即依据一个输入H(x)，不能倒推回输出x

利用

PoW是比特币的共识机制，在目前的公链共识算法外面占据主导地位，矿工以计算机计算工作，获取相应的比特币处分或者手续费，将一些列的交易打包造成块，矿工采纳 SHA-256 算法，计算其块的 hash 值进行验证，

安全性剖析

一个破坏者领有比特币全网算力的 51%，即能够改写区块链进行坑骗，然而新区块的产生同时也会有新币处分以及交易费的收取，这在肯定水平上爱护了比特币网络的平安，即攻击者会在应用昂扬的算力进行坑骗以及应用算力生产新区块获取新币以及交易费之间做出抉择。（然而也不排除事实中会存在一种人，就是不在乎利益的，就像功夫外面的火云邪神一样，只是想找个对手，最经典的就是对着杨过与小龙女所说的经典台词，我只是想 …）

长处

• 造假老本比拟高

毛病

• 资源节约，挖矿须要大量的哈希运算，耗费大量资源，找到的哈希值的惟一意义就是满足了挖矿胜利的定义，即该哈希的有多少个间断的 0 作为结尾，除了使歹意攻击者不能轻易地伪装成几百万个节点和打垮比特币网络，并没有更多理论或迷信价值
• 网络性能低，因为 PoW 共识算法限度比特币出块的工夫是 10 分钟，所以交易确认至多须要 10 分钟，而且目前仅反对每秒 7 笔的交易速度，不适宜高并发的商业利用
• PoW共识算法算力集中化，目前挖矿矿池是主力，集体矿工根本不可能生存上来，算力高的矿池有选择权，进而导致算力的集中化
• 随着比特币产量的一直升高，矿工人数也会越来越少，这样就会导致整个比特币网络的稳定性呈现问题，矿工数量变少的时候，比特币被 51% 算力攻打就越容易

算法矛盾点

区块大小与出块距离。减少区块容量能够进步吞吐量，然而区块过大会造成网络拥塞，减少节点间共识的工夫和效率，反而可能升高区块效率；减小出块距离也能减少吞吐量，但出块距离的缩短会造成更频繁的链分叉，也会减少双花等平安问题

Pos(Proof of Stake)

概述

基于随机抉择的验证者来生产并批准区块，验证者通过在区块链内锁定代币来“质押”原生网络代币，验证者依据本人的权利质押总额取得处分，此举能够用投资回报 (ROI) 来激励节点验证网络，相似现实生活中的股东机制，领有股份越多的人越容易获取记账权，同时越偏向于保护网络的失常工作，是更加环保和更加可扩大的共识算法

区块生产过程

• 被选出的验证者依据本人的权利质押状况产出下一个区块
• 权利质押数额较大的验证者生成下个区块的机会更大
• 区块先由局部验证者提交，而后向其余验证者广播，由这些验证者核实后将取得批准的区块增加到区块链

实现逻辑

• 通过保证金（代币、资产、名声等具备价值属性的物品）来对赌一个非法的块成为新的区块，收益为抵押资本的利息和交易服务费
• 提供证实的保证金，例如通过转账货币记录越多，则取得记账权的概率就越大
• 歹意参与者的歹意操作并生成虚伪区块，为了生成区块而依照锁定机制所质押的权利就会面临着受到削减或被剥夺控制权的威逼（保证金被罚没，即损失经济利益），对于 PoS 来说，须要把握超过全网 1/3 的资源，才有可能左右最终的后果
• 在 POS 模式下，有一个概念叫币龄，每个币每天产生 1 币龄，例如，你持有 100 个币，总共持有了 30 天，那么，此时你的币龄就为 3000，这个时候，如果你发现了一个 PoS 区块，你的币龄就会被清空为 0。你每被清空 365 币龄，你将会从区块中取得 0.05 个币的利息（能够了解为年利率 5%），那么在这个案例中，利息 =3000×5%/365=0.41 个币

加密货币所有者取得的益处

• 持有处分：用户只需让加密货币在本人的钱包里放上一段时间，即可赚取处分
• 参加 / 委托处分：用户将本人的局部权利委托给负责爱护网络的验证者。验证者与委托权利给本人的用户分享局部权利质押支出，由此产生处分

长处

• 省资源：不须要挖矿，不须要大量消耗电力和能源
• 更加去中心化：绝对于比特币等 PoW 类型的加密货币，更加去中心化，相比 PoW 算法的 51% 算力攻打，PoS须要购买 51% 的货币，老本更高，没有攻打意义
• 防止通货膨胀：PoS机制的加密货币按肯定的年利率新增货币，能够无效防止压缩呈现，放弃根本稳固

毛病

• POS会面临发币的问题，起初只有创世块上有币，意味着只有这个节点能够挖矿，所以让币扩散进来能力让网络壮大，所以晚期采取的是 POW+POS，即第一阶段POW 挖矿，第二阶段 POS 挖矿，起初 ERC20 合约代币呈现后，能够只存在 POS 的挖矿模式
• 开发者作恶，纯 PoS 机制的加密货币，只能通过 IPO 的形式发行，这就导致“多数人”（通常是开发者）取得大量老本极低的加密货币，很有可能造成大面积的抛售
• 币龄其实就是工夫，一旦挖矿者囤积肯定的币，很久很久之后发动攻打，这样将很容易拿到记账权
• 矿工能够囤积代币从而导致货币流通艰难
• POS面临的最重大的一个问题就是无老本利益问题，在 PoS 零碎中做任何事简直没有老本，比方在 PoS 零碎上挖矿简直没有老本，这也就意味着分叉十分不便
• 首富账户的势力过大，可能摆布记账权

Dpos(Delegated Proof of Stake)

概述

DPO S 是一种基于投票选举的共识算法，有点像专制大会，持币人选出几个代表节点来经营网络，用业余运行的网络服务器来保障区块链网络的平安和性能，DPOS机制中，不须要算力解决数学难题，而是由持币者选出谁说生产者，如果生产者不称职，就有随时有可能被投票出局，这也就解决了 POS 的性能问题

受托人，代理人 (Delegates) 的主要职责

• 保障节点的失常运行
• 收集网络里的交易
• 节点验证交易，把交易打包到区块
• 节点播送区块，其余节点验证后把区块增加到本人的数据库
• 率领并促成区块链我的项目的倒退

实现逻辑

• 受托人的节点服务器相当于比特币网络里的矿机，在实现本职工作的同时能够支付区块处分和交易的手续费
• 一个区块链我的项目的受托人个数由我的项目发起方决定
• 任何一个持币用户都能够参加到投票和竞选受托人这两个过程中，用户能够随时投票、撤票，每个用户投票的权重和本人的持币量成正比
• 投票和撤票能够随时进行，在每一轮选举完结后，得票率最高的 n(区块链我的项目方决定) 个用户则成为该项目标受托人，负责打包区块、维持零碎的运行并取得相应的处分
• 每名代表都有一份相等的投票权，并且，如果以后记账节点不记账则由下一个记账人记账

DPOS机制的准则

• 持股人根据所持股份行使表决权，而不是依赖挖矿竞争记账权
• 最大化持股人的盈利
• 最小化保护网络安全的费用
• 最大化网络的效力
• 最小化运行网络的老本

PBFT(Practical Byzantine Fault Tolerance)

背景

拜占庭罗马帝国疆土辽阔，为了达到进攻目标，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递音讯。在和平的时候，拜占庭军队内所有将军必须达成统一的共识，决定是否有赢的机会才去攻打敌人的营垒。然而，在军队内有可能存有叛徒和敌军的特务，左右将军们的决定影响将军们达成统一共识。在已知有将军是叛徒的状况下，其余虔诚的将军如何达成统一协定的问题，这就是拜占庭将军问题。

必要前提

信道必须是牢靠的，如果信道不能保障牢靠，在一个不牢靠的通信链路上试图通过通信以达成统一是根本不可能或者十分困难的

算法根本解释

将军总数大于 3f ，背叛者为 f 或者更少时，虔诚的将军能够达成命令上的统一，即 3f+1<=n，即网络中全副节点总数是大于3f, 歹意节点以及故障节点总数是小于等于f, 那么整个集群还是能够达成一个正确的共识，该算法最大容错节点数量是(n -1)/3，算法须要反对容错故障节点，也须要反对容错作恶节点

最好极其状况

如果 f 个节点是故障节点，也是作恶节点，那么依据多数遵从少数的准则，集群外面存在 f+1 个失常节点，那么集群就可能达成共识，这种状况反对的最大容错节点数量是 (n-1)/2

最坏极其状况

故障节点和作恶节点全是不同节点，有 f 个作恶节点，有 f 个故障节点，当发现节点是作恶节点之后，集群排除节点，剩下 f 个故障节点，依据多数遵从少数准则，须要 f+1 个失常节点大于 f 个故障节点，集群就能达到共识，所以最大容错节点是(n-1)/3

长处

• 通信复杂度 O(n^2)，解决了原始拜占庭容错(BFT) 算法效率不高的问题，将算法复杂度由指数级升高到多项式级，使得拜占庭容错算法在理论零碎利用中变得可行
• 首次提出在 异步网络环境下应用状态机正本复制协定，该算法能够工作在异步环境中，并且通过优化在晚期算法的根底上把响应性能晋升了一个数量级以上。作者应用这个算法实现了拜占庭容错的网络文件系NFS，性能测试证实了该零碎仅比无正本复制的规范 NFS 慢了 3%
• 应用了加密技术来避免坑骗攻打和重播攻打，以及检测被毁坏的音讯。音讯蕴含了公钥签名（RSA算法）、音讯验证编码 MAC 和无碰撞哈希函数生成的音讯摘要

毛病

• 仅仅实用于联盟链 / 公有链
• 通信简单度过高，可拓展性比拟低，个别的零碎在达到 100 左右的节点个数时，性能降落十分快
• 在网络不稳固的状况下提早很高

Raft

概述

将一致性问题看成零碎中过程间在不同机器上一个状态机同步问题，为保障每个机器上的过程具备一致性，Raft共识算法来保障在每个过程初始状态雷同的状况下，每个过程的下一个操作，状态扭转操作雷同，这样就能保障所有过程的状态机的扭转过程是一样的，即零碎中的过程最终会达成数据统一状态

raft集群节点状态

• leader领导者，负责整个集群状态的同步和对外部事件的解决，整个集群只有一个leader
• follower跟随者，是被动的，不会被动收回音讯，只是响应 leader 或candidate的音讯，或者转发客户端的申请给leader
• candidate候选者，是一种长期的状态

领导人选举

• 每个节点在退出集群的时候都会初始化为follower
• 以后集群没有 leader 的时候，follower会进行选举试图成为leader，将本人的状态转变为candidate
• 向集群内的其余成员发动投票申请，若该 candidate 收到了大多数人的赞成票
• 变成 leader 之后，集群内播送心跳音讯，接到心跳音讯的 follower 或其余 candidate 就会意识到此时已有leader，会进行本人的竞选行为而从新变为follower，稳固的集群状态就造成了

发动竞选条件

每个节点外部都有一个被称之为选举时停的属性，当在此时间段内，没有收到来自 leader 的心跳音讯，就能够认为以后没有 leader 存在，能够发动竞选

任期 term 概念

• 任期 Term 是一个全局可见递增的数字
• 简直每个在集群间流传的音讯都会携带者发送者所属的Term
• 示意一个 Leader 施展其影响力的一段期间的序号
• Term的减少产生在一个 follower 成为 candidate 时，一个 follower 长时间未收到 leader 的心跳，它就认为新的时代要到来了，因而它自增此 Term，成为候选者发动竞选，同时将此更新后的Term 发送给其余节点以彰显本人的竞选资格

日志序号 Index 概念

• 纪录了节点日志 entry 的序号

follower投票给 candidate 的条件

• 投票的准则是先来先投票
• 在一个 Term 内只能投一次赞成票，如若下一个来申请投票的 candidate 的Term更大（示意可能进入到了下一轮的选举），那么投票者会重置本人的 Term 为最新而后从新投票
• candidate的日志 index 大于本人的日志index
• candidate的 term 大于本身的term

选举失败后续流程

candidate的选举流动有一个最大时限，超过该时限还没有胜利胜出，就会被发表为失败，从新变为 follower 而后从新开始选举时停的计时，为了保障选票瓜分的状况不会频繁呈现，每一个节点的选举时停都是随机的

日志复制阶段

• 提案阶段：是一个初始阶段，当 leader 收到来自客户端的一条申请后，会将申请打包成为一个 entry，该entry 便处于此阶段，它是不稳固的，也就是说集群没有方法保障此 entry 会被集群承受还是摈弃（网络、机器起因），须要 raft 共识算法施展其作用来确定
• 达成共识阶段 / 可提交阶段：一旦某一 entry 被集群内大多数节点所持有，该 entry 就曾经处于达成共识阶段，它曾经可能确定将会被集群承受（提交），但具体何时写入状态机，内部客户端何时可能验证此命令曾经失效，则是没有方法保障的
• 被提交阶段：可认为是显式的达成共识阶段。当 leader 意识到某一个 entry 曾经进入了达成共识阶段，则 leader 将会将它标记为被提交状态。并将此信息播送给集群中的其余节点申明该 entry 曾经被集群承受，能够将其利用进状态机了
• 被利用状态：当集群中的任意节点意识到某一个 entry 曾经被标记为已提交，而且本身也持有这个 entry，就会将其利用进状态机，对于KV 数据库可能是写、删除操作等，此时一个申请才真正被实现，能够被内部验证其已被执行

参考浏览

区块链 pow 算法介绍

死磕共识算法 |POS算法

详解 DPoS 共识算法

区块链共识算法 -POW- 简书

共识算法系列之一：raft和 pbft 算法

PBFT共识算法详解

分布式共识算法 Raft（可用性和一致性）详解