所谓“共识机制”，是通过非凡节点的投票，在很短的工夫内实现对交易的验证和确认；对一笔交易，如果利益不相干的若干个节点可能达成共识，咱们就能够认为全网对此也可能达成共识。再艰深一点来讲，如果中国一名微博大V、美国一名虚构币玩家、一名非洲留学生和一名欧洲旅行者互不相识，但他们都统一认为你是个坏蛋，那么基本上就能够判定你这人还不坏。

百度百科

Consensus

当谈及分布式环境中的共识时，个别波及到两种类型的节点：

  • Legitimate nodes：诚恳节点，感觉你是坏蛋，就投票你为坏蛋
  • Malicious nodes：歹意节点，行为“顽劣”，颠倒是非

此外，即便产生任何故障，咱们的零碎也必须失常运行。有两种类型的故障会产生：

  • Crash failure：诚恳节点产生的故障（音讯提早、不可送达）
  • Byzantine failure：歹意节点造成的故障（篡改音讯、不按套路执行协定）

因而，区块链共识协定的次要责任有：

  • 放弃账本（区块链）中的数据的有序性、安全性
  • 在区块链网络中的节点之间达成协议，即提供拜占庭协定（即便呈现拜占庭式的失败，也不会造成太大影响）
拜占庭协定（Byzantine Agreement）采纳的办法是确保能够通过分布式的办法达成共识，即便呈现了拜占庭式的失败也不会影响。“拜占庭失败”能够了解为歹意节点造成的故障。

上面列出一些驰名的DLT（分布式账本）以及它们所应用的共识算法：

DLTConsensus Algorithm UsedDescription
BitcoinPoW利用 PoW 来生产新的货币
EthereumPoW首次收到传入操作的账户
HyperledgerPBFT如果 2/3 的成员对新的区块达成共识，那么该区块就成为区块链的一部分
ParityPoS要求矿工提供肯定数量加密货币的所有权，而不要求其算力
HashgraphVirtual voting-based consensus algorithm
TezosPoS

Proof of Work（PoW)

比特币区块链的共识机制，PoW是为公共区块链设计的。在PoW中，共识是否最终达成是不被保障的。在PoW中，矿工既是leader node又是validator node。

节点通过计算随机哈希散列的数值解抢夺记账权，求得正确的数值解以生成区块的能力是节点算力的具体表现，算力越高，就越有可能解得数值。计算出哈希值的节点才可能向区块链中增加区块，并取得处分。某个节点获胜的概率为

其中，i代表每个参加节点，N是节点的总数量，i代表节点i的算力。

PoW存在的问题：

  • 如果某两个矿工同时解出了PoW puzzle，就会造成所谓的fork
  • 达成共识所需周期长
  • 消耗大量计算资源
  • 双花问题（double spending）
如果咱们微信钱包里有 100 块钱的宏大资产，咱们先去饭店吃了顿饭，后果微信出了 bug，这一笔钱并没有被银行同步，还留在钱包里，于是咱们又能拿着同样的 100 块钱去看场电影，这就属于双花问题。在区块链零碎中，因为共识机制导致区块确认工夫长，用一个数字货币去进行一次交易，能够在这笔交易还未被确认实现前，进行第二笔交易，这就会造成双花问题。

PoW的容错能力：

  • PoW可能会受到51%算力攻打。当零碎中有单干关系的歹意节点所管制的算力，超过诚恳节点所管制的算力，零碎就有被攻打的危险。
  • 能够容忍拜占庭失败
  • 能够无效抵挡“女巫攻打”（Sybil Attack），即多数歹意节点结构多个虚伪身份，并利用这些身份管制或影响网络的大量失常节点。

Proof of Stake（PoS）

在权利证实（PoS）类共识协定中，矿工的抉择取决于每个节点携带的“权利”（如加密货币）数量，而不是其计算能力。

PoS 相比 PoW 会耗费更少的资源，缩短达成共识所需的工夫。当然，PoS 也存在本人的一些问题，例如，在 PoS 中，处分的授予形式应该是使所有节点都有平等的机会参加到采矿过程中。否则，每次获胜的都为权利较高的矿工，每次失去处分的也是它。而且如果有任何提早或链接的连贯问题，节点可能没有账本的最新正本，因而会导致同步问题。

上面这张图总结了PoS相比PoW的一些区别：

PAXOS

最根本的分布式共识（一致性）算法，容许在不牢靠的通信条件下（信息能够提早、失落或者反复，但没有出错）对一个值达成共识。

PAXOS的外围idea是，如果有一半以上的过程抉择了一个值，那么根据少数人代表整体的准则，这个值就是共识。

PAXOS中的节点：

  • Proposer：提出要达成统一的值。某个选取的Proposer作为一个单的的 leader，提出一个新的决定，它解决客户的申请。
  • Acceptor：Acceptor依据若干规定和条件对决定进行评估，并决定承受还是回绝Proposer提出的倡议。
  • Learner：获取Acceptor达成统一的值

Phases in PAXOS

Prepare Phase

  1. Proposer收到客户提出的就某个值达成共识的申请；
  2. Proposer向大多数或所有接受者发送一个音讯prepare(n)；
  3. Acceptor接管到prepare(n) 音讯，并进行回应。

在第二步中，n代表proposal number，它必须是全局惟一的，且要大于该Proposer之前应用过的proposal number。如果Proposer没有收到来自大多数Acceptor的响应，那么它须要增大n，从新发送。

在第三步中，如果Acceptor之前没有做出过任何响应，那么它会回复 promise(n) 音讯，并承诺会疏忽之后任何小于n的proposal number。而如果Acceptor之前有做出过回应，即对某个小于n的proposal number回复了promise(n) 音讯，那么进一步可分为两种状况：

  • 如果它还没有收到来自之前Proposer的accept音讯，那么它会存储当初更高的proposal number n，回复promise(n) 音讯；
  • 如果它曾经收到了来自之前Proposer的accept音讯，那么它肯定曾经相应的回复了accepted音讯，在这种状况下，它会把之前这个full proposal连同 promise(n) 音讯一起回复，表明我之前曾经接管过值了。

Accept Phase

  1. Proposer期待，直到失去大多数Acceptor对该proposal number n的回应；
  2. 评估应该在accept音讯中发送什么v值；
  3. 给Acceptor发送accept(n, v) 音讯，v值是理论要达成统一的值；
  4. Acceptor接管到accept(n, v) 音讯后，要么回复accepted(n, v) 音讯并将该音讯发给所有learners，要么间接疏忽；
  5. 如果大多数Acceptor都承受了v值这个提议，那么就达成共识了。

第二步细节：如果Proposer收到的promise音讯中有带有full proposal 的，那么它会将v值增大，如果都没有full proposal的话，v值能够轻易选取。

第四步细节：Acceptor接管到accept(n, v) 音讯后：

  • 如果它之前曾经承诺过不承受这个proposal number，它就会疏忽这个音讯；
  • 如果它之前回复过promise(n) 了，那么它就回复accepted(n, v) 音讯并将该音讯发给所有learners。

Replicated And Fault Tolerant（RAFT）

RAFT容许集群的重新配置，这使得集群成员的扭转不须要中断服务。它还容许日志压缩，以缓解节点解体后迟缓重建的问题并缩小耗费的存储。

一个RAFT集群中的节点可分为以下三种：

  • Leader：接管客户申请，组织日志复制给其它节点，并治理与Follower的通信
  • Follower：节点在实质上是被动的，只对近程过程调用（RPC）做出响应。它们从不被动发动任何通信，只会承受leader的复制日志，对leader我行我素
  • Candidate：尝试成为leader的节点，会发动投票申请

RAFT次要包含两个阶段：

  • leader election
  • log replication

这里先将三个节点之间的状态转换图给出，具体过程能够往下看。

Leader Election

Leader Election会基于一个心跳（heartbeat）机制来触发leader的选举过程：

  1. 所有的节点一开始都是Follower；
  2. 如果Follower继续收到来自leader或者candidate的近程过程调用，那么它们只会放弃本人Follower的身份；
  3. 如果特定工夫内某个Follower没有收到来自leader的心跳包，表明leader可能曾经生效了，那么该Follower就会变为Candidate，发动新的选举，尝试变为leader。
  4. 如果Candidate 收到了大多数的选票，那么它就“竞选”胜利，成为leader。但如果多个Follower同时变为Candidate，且它们的选票并驾齐驱，那么此时就无奈决出胜者，RAFT为每轮选举都设置了超时工夫，如果在这段时间内还没有选出新的leader（election timeout），那么就会开启新一轮的选举过程。

不论是在Follower变为Candidate时的等待时间，还是选举时的timeout工夫，都可能会发送这样的状况：不同Follower设置的等待时间或者不同Candidate的timeout工夫雷同，那么这一轮选举超时了，下一轮同样的Follower又变为了Candidate，雷同的timeout工夫内还是没有从这些Candidate中还是没有选出leader，又进入下一轮…

因而咱们在理论中会将Candidate的timeout工夫以及Follower的等待时间随机化，每轮选举后，每个Candidate都会让本人的任期号+= 1，这样咱们每轮就能够抉择任期号最大的那个Candidate，减小抵触的概率。此外，发生冲突的选举后，Candidate距离下一次选举的工夫也要随机化。

上图中还短少一点，如果candidate收到了来自leader的心跳包，那么阐明选举完结了，它会变为follower。

Log Replication

  1. 客户给leader发送申请；
  2. leader会给该申请增加一个任期号（term）以及索引（index），使得该申请或命令在日志中可能被惟一辨认，而后将该申请增加到本人的日志中；
  3. 并行地给follower发送AppendEntries RPC，将新的日志项传递给follower。
  4. 当集群中的大多数follower都追加了该申请后，leader会提交该日志, 并执行指令扭转状态机的状态，并返回后果给客户。它也会通过AppendEntries RPC通知follower日志曾经被提交，以便让follower也开始执行指令扭转它们本人状态机的状态

上述过程的日志追加可看下图：

Practical Byzantine Fault Tolerance (PBFT)

从名字中也能够看出，PBFT被设计用来在有拜占庭谬误的状况下提供共识。

PBFT蕴含三个子协定：

  • normal operation：该协定在一切正常，无错产生的状况下运行
  • view change：在leader节点出错的状况下运行
  • checkpointing：抛弃零碎中的旧数据

PBFT同样也有三种节点：

  • replicas：每个PBFT协定中的参与者（包含leader和backup）
  • leader：也叫primary，每个轮次都会有一个leader来与客户通信，leader不变，则始终为同一个view
  • backup：除去leader外的其它所有节点

如果想要容忍拜占庭谬误，那么节点的最小数量应为n=3f+1，也就是说，如果要容忍f个故障，那么这个零碎必须要有n个节点。只有零碎中的节点数量放弃n≥3f+1，PBFT就能够提供拜占庭容错。

PBFT协定的执行分为3个阶段：

  • Pre-prepare
  • Prepare
  • Commit

Pre-prepare Phases

  1. leader从客户端接管一个申请；
  2. 为该申请调配对应的序列号，序列号代表着申请被执行的程序；
  3. 将该申请信息（pre-prepare message）播送到所有backups备份。

Prepare Phase

  1. backups只会接管之前未接管过的序列号或者不同view对应的pre-prepare音讯；
  2. 将prepare音讯发给所有节点。

Commit Phases

  1. 收到prepare音讯的replica对音讯进行验证（是否为雷同的申请、view以及序列号），直到集齐2f+1个验证好的音讯；
  2. 播送commit音讯给所有replica；
  3. 如果集齐2f+1个达到的无效commit音讯，阐明决定通过；
  4. 执行该申请/决定
  5. 返回给客户reply音讯，蕴含处理结果

下图为一个在normal operation协定下运行的PBFT根本过程，这是最简略过程，因为为了达到n≥3f+1的要求，零碎中至多须要4个节点。

对于RAFT算法的最大容错节点数量是（n-1）/2，而PBFT算法的最大容错节点数量是（n-1）/3 的补充阐明：（《深刻分析区块链的共识算法Raft&PBFT》）

对于RAFT算法，它只反对容错故障节点，不反对容错作恶节点。故障节点就是节点因为零碎忙碌、宕机或者网络问题等其它异常情况导致的无响应，呈现这种状况的节点就是故障节点（也就是咱们结尾提到过的诚恳节点的故障，Crash failure）。作恶节点除了能够成心对集群的其它节点的申请无响应之外，还能够成心发送谬误的数据，或者给不同的其它节点发送不同的数据，使整个集群的节点最终无奈达成共识，这种节点就是作恶节点（也就是咱们结尾提到过的歹意节点造成的故障，Byzantine failure）。

RAFT算法只反对容错故障节点，假如集群总节点数为n，故障节点数为f，依据小数遵从少数的准则，集群里失常节点只须要比f个节点再多一个节点，即f+1个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识。因而RAFT算法反对的最大容错节点数量是（n-1）/2。

对于PBFT算法，因为PBFT算法的除了须要反对容错故障节点之外，还须要反对容错作恶节点。假如集群节点数为n，有问题的节点为f。有问题的节点中，能够既是故障节点，也能够是作恶节点，或者只是故障节点或者只是作恶节点。如果故障节点和作恶节点都是不同的节点，那么就会有f个作恶节点和f个故障节点。当发现节点是作恶节点后，会被集群排除在外，剩下f个故障节点，那么依据小数遵从少数的准则，集群里失常节点只须要比f个节点再多一个节点，即f+1个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是f+1个正确节点，f个故障节点和f个问题节点，即至多须要3f+1个节点。

Metrics of Consensus

IT零碎的性能和可扩展性始终是用来掂量区块链共识算法的要害非功能性指标。

Performance

Transaction Throughput：

交易吞吐量被定义为区块链网络每秒钟能够解决的交易（Tx）数量。它能够通过如下公式进行计算：

其中，Block Time为将一个区块增加到区块链中所破费的均匀工夫。

显然，区块尺寸越大，吞吐量就越高，而Block Time或者交易规模越大，吞吐量就越小。（固定其余两个量）

当交易大小为500 Bytes，Block Time为10s时，吞吐量随区块大小变动如下图所示：

版权申明：本文为CSDN博主「如松茂矣」的原创文章，遵循CC 4.0 BY-SA版权协定，转载请附上原文出处链接及本申明。

原文链接：

https://blog.csdn.net/myDarli...

文章起源：CSDN博主「如松茂矣」
文章原题目：《区块链共识机制 (Consensus)（PoW，PoS，PAXOS，RAFT，PBFT）》
如有侵权请与咱们分割删除。