关于区块链:读懂区块链共识机制-PoWPoSPAXOSRAFTPBFT

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

百度百科

Consensus

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

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

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

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

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

• 放弃账本（区块链）中的数据的有序性、安全性
• 在区块链网络中的节点之间达成协议，即提供拜占庭协定（即便呈现拜占庭式的失败，也不会造成太大影响）

拜占庭协定（Byzantine Agreement）采纳的办法是确保能够通过分布式的办法达成共识，即便呈现了拜占庭式的失败也不会影响。“拜占庭失败”能够了解为歹意节点造成的故障。

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

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）》
如有侵权请与咱们分割删除。