区块链共识算法学习笔记

一、选举类共识

       选举类共识是指在完成区块生成过程中，通过“ 投票选举”的方式选出获得半数以上选票的节点作为记账权节点；多见于传统分布式一致性算法, 例如 Paxos 和 Raft[7]。 Paxos 和 RAFT 共识机制旨在解决 Paxos 问题。

        具体而言，Paxos 问题常常出 现在分布式系统中，即存在非恶意节点(即可能消息丢失或重复，但无错误消息)下， 如何达成共识。

1、Paxos算法

在 Paxos 算法中存在三种类型的逻辑节点，分别是：

① Proposer: 提出提案 (Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
② Acceptor：参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受 提案，若 Proposal 获得多数 Acceptors 的接受，则称该 Proposal 被批准。
③ Learner：不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案 （Value）。

       基本原理类似于两阶段提交：首先提案者需要得到多数接收者的支持以获得提 案的权利；然后提案者提供提案，并接受投票，若提案得到大部分人认可，则可获 得记账权。

2、Raft 算法

       Raft 算法从工程实践性角度改进 Paxos 算法得到的。类似与 Paxos 算法，同样 拥有三类逻辑节点，领导者(leader)、候选者(candidate)和跟随者(follower) 。每个 区块完成期间选举一个全局的领导者，获得提交日志(log)权利，并向跟随者单向传 播。

二、证明类共识

       证明类共识的英文名称常以“ Proof of X ” 出现，即在完成区块生成过程中， 每一个节点必须证明自己拥有记账的权利，常见的共识算法有 PoW 和 PoS。

1、工作量证明（PoW，Proof of Work），本质上讲，该共识机制需要矿工需要进 行复杂而又无用的计算，以证明节点进行了一定的工作量。这样确保节点不会恶意 损害区块链系统，因为对系统的损害也将会导致投资的损失，进而损害自身。一般 情况下，会有多个节点同时进行问题解决，在此情况下每位矿工从中选取一个区块 链，并以选取最长链者为获胜者。

Pow有两个角色，一个是工作者，一个是验证者！

对于工作者

• 需要完成的工作必须有一定的量，这个量由工作验证者给出。
• 工作者无法自己“创造工作”，必须由验证者发布工作。
• 工作者没有办法快速完成工作，要完成工作必须消耗一定代价。
  对于验证者
• 可以迅速的检验工作量是否达标。

从流程图中看出，pow工作量证明的流程主要经历三步：

① 生成Merkle根哈希
生成Merkle根哈希在第二章节中的第2要素中已经有讲解，即节点自己生成一笔筹币交易，并且与其他所有即将打包的交易通过Merkle树算法生成Merkle根哈希，所以为什么说区块是工作量证明的三要素之一。

② 组装区块头
区块头将被作为计算出工作量证明输出的一个输入参数，因此第一步计算出来的Merkle根哈希和区块头的其他组成部分组装成区块头，这也就是为什么我们在前言中大费周章的去提前讲解比特币的区块头。

③ 计算出工作量证明的输出
下面我们直接通过公式和一些伪代码去理解工作量证明的输出：

i. 工作量证明的输出=SHA256(SHA256(区块头))

ii. if（工作量证明的输出<目标值），证明工作量完成

iii.if（工作量证明的输出>=目标值）,变更随机数，递归i的逻辑，继续与目标值比对。
注：目标值的计算见第二章节的要素3的难度值。

上面的流程图及解析即pow工作量证明的整个过程。

2、权益证明（PoS，Proof of Stake），PoS 为解决 Pow 技术存在的一些内在问题 而被提出，例如电量消耗问题。在 PoS 算法中，矿工需要拥有系统中的一些权益， 拥有的权益代表了矿工下一步生成新区块的概率。此外PoS 系统比 PoW 系统具有更高的安全性。由于 POS 的机制问题，每次进行恶意行为，需要花费已经获 得的权益而不是算力，增加了恶意行为的成本，提高了系统的安全性。

DPoS算法是BM根据当时PoW、PoS的不足而改进的共识算法，它的目的就是为了提高性能，也就是交易确认时间短。注意一点，在DPoS中，记账节点不叫做矿工，而是改称为见证人，Witness。

三、拜占庭类共识

拜占庭容错（Byzantine Fault Tolerance） 正如前文所言，拜占庭将军问题是分布式计算中的一个经典问题。

在实践过程 中一般采用以下两种算法：

① 实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）

       PBFT 是一种关键联盟币的共识算法。具有 3f + 1 的容错性（拜占庭将军问题也只在节点数 N > 3f 时可解），并同时保证一定的性能。简而言之，在恶意节点数 f = 1，节点数 N = 3f = 3 时，恶意节点的出现将会导致系统无法作出决定。而当节点数 N>3f（如 4 个） 时，即使恶意节点出现，在少数服从多数的原则下系统也将达成共识。【重点考察】

② 联邦拜占庭协议（FBA，Federated Byzantine Agreement）

       FBA 的通用理念是每个拜占庭将军负责自身的链，消息 一旦到来，通过排序建立事实。该共识算法在不同加密货币中选择将军的情况下存 在不同，有以机构名义进行选定的，例如 Ripple；有用户选定的，例如 Stellar。此 外该共识算法具有很高的吞吐量、低交易开销和网络扩展性。【了解即可】

四、混合类共识

       PoW+BFT 将经典共识机制与非授权共识机制进行了结合, 利用工作量证明, 提 出混合共识机制, 实现非授权环境中的状态机复制。【了解即可】

五、随机类共识

Algorand 算法是从减轻 PoW、PoS 安全性问题提出的。

Algorand 算法采用了 VRF 函数（可验证随机函数）， 并结合矿工持有权益比例，通过随机确定区块生成以及投票人角色选择记账权利人。 这样保证了记账权利人不能被操控，也不能被预测，大大减轻了恶意节点操控长链 的可能性，避免了双花攻击。【了解即可】

六、波卡共识

总结：

共识算法的选择与应用场景高度相关，可信环境使用Paxos或者Raft，带许可的联盟可使用PBFT，非许可链可以是 POW 、POS 、DPOS 共识等

查看详细讲解：https://blog.csdn.net/qq_38491875/article/details/109029306