深入理解区块链共识算法

区块链的概念：

• 区块链是一种去中心化、不可篡改、可追溯的分布式数据库系统[3]。区块链系统中底层网络采用对等式网络(P2P 网络)组织各个独立的网络节点。P2P网络是扁平式的拓扑结构, 网络中的每个节点地位对等, 不存在任何中心化的特殊节点和层级结构。因此区块链具备去中心化的特点, 系统中各节点相互独立, 具备相同的功能, 存储同样的信息, 相互监督;
• 与传统分布式数据库不同,  各个节点独立存储完整的数据,  任何组织或个人无法完全控制所有数据, 只拥有本地数据的控制权,  任何单个节点对本地数据的修改不会对整个区块链产生影响,  因此区块链具备难以篡改性;  区块链把数据分成不同的区块, 每一个区块头都包含前一个区块的哈希摘要信息；
• 如图 1 所示,  前后顺连形成一条链,  因此区块链具备可溯性。总体来说,  区块链融合了经济学的博弈论、计算机科学等多种技术,  比如P2P 网络协议, 块链结构、共识算法、非对称加密、激励机制等, 解决了数据可信问题。在无需借助可信第三方的情况下,  实现互不信任的多方对等可信的价值传输。 

共识算法：

共识算法汇总：

共识算法的共识过程

算法的共识过程总体上分为三个阶段, 创建区块、验证区块,  提交区块。根据共识协议,  从参与共识过程的节点中选择主节点创建新区块(定义主节点为每轮共识过程中产生有效区块的节点);  然后新区块交由其他参与共识的节点进行独立验证;  通过验证的新区块会被节点提交到本地区块链中,  达成对最新高度区块的共识;  至此完成共识, 开启下一轮共识过程。

共识算法分类

共识算法的分类方式有很多,  比如在性能层面: 从数据一致性的角度将共识算法分为强一致性共识算法、弱一致性(最终一致性)共识算法;  从拜占庭容错的角度将共识算法分为拜占庭容错共识算法、非拜占庭容错共识算法。在应用层面:  可以将共识算法分为适用于公链、联盟链、私链的共识算法。从共识过程出发,  按照主节点的产生方式将共识算法分为竞争类、选举类、随机类以及其他类型。

竞争类

竞争类大概有这几种 PoW (Proof of Work)、PoS (Proof of Stake)、PoSpace (Proof of Sapce) 

• PoW 共识算法中,  所有参与共识的节点通过消耗算力解决数学难题来竞争成为主节点,  由最先解决数学难题的节点成为主节点。
• PoS 将算力竞争转化为权益竞争,  不仅节约算力,  权益的引入也能够防止节点发动恶意攻击;  同时促使所有节点有责任维护区块链的安全稳定运行以保障自身权益;  PoS 虽然降低了算力资源的消耗, 但是没有解决中心化程度增强的问题,  新区块的生成趋向于权益高的节点。
• PoSpace 共识算法使用存储空间代替计算,  节约电力资源;  同时该共识协议下,  节点初次接入网络时确定存储空间大小,  之后不能扩容,  防止了 PoW共识算法中“矿池”(将不同节点的算力集合成一个大的算力节点)的出现,  一定程度上避免了中心化程度增强的问题,  同时降低了安全风险。

     竞争类算法共识过程：

选举类

选举类算法共识过程

授权股份证明算法(DPoS)、实用拜占庭容错算法(PBFT)、授权拜占庭容错算法(DBFT)

DPoS 共识算法，在PoS 中引入选举机制。DPoS 将节点分为普通节点和信任节点两种角色。普通节点可以投票选择信任节点或者被投票成为信任节点。每个信任节点依次被赋予固定的期限(比如 2 秒)成为主节点, 授权时间结束后,创建权依次交由下一个信任节点。

PBFT 共识算法。该共识算法从全网节点选择一个主节点负责创建区块, 然后经过三阶段投票达成共识:  预准备阶段,  准备阶段,  提交阶段。

1. 预准备阶段:  从全网选择一个主节点;  每个节点把客户端发来的交易信息向全网广播,  主节点收集所有交易信息,  创建新区块并向全网广播;    
2. 准备阶段:  每个节点在收到主节点发送的区块信息后,  从预准备阶段进入到准备阶段,  节点对区块进行验证,  验证通过后向其他节点广播一条准备消息;    
3. 提交阶段:  节点在向全网广播准备消息之后进入提交阶段,  如果节点收到超过 2/3 节点的准备消息, 就向全网广播一条提交消息;  如果一个节点收到超过2/3 节点的提交消息,  即可提交新区块到本地区块链,  达成对最新高度区块的共识。

PBFT 中无权益的抵押或竞争资源的消耗,  使得恶意节点的成本降低,  PBFT 通过三阶段的投票机制排除恶意节点对共识的影响,  提供不超过1/3 总节点数量的容错能力,  但 2( ) O N   的通信复杂度使得系统性能随着网络规模的增加而下降。

PBFT 三阶段示意图

 DBFT算法

DBFT 改进自PBFT 算法,  PBFT 算法共识过程需要全部节点的参与,  且需要通过3 轮网络请求确认来达成共识,  网络通信复杂度为 o(n²) , N 为全网节点的数量,  可扩展性差,  随着网络规模增加,  难以快速达成一致。NEO 的解决方案是投票选取出部分节点参与共识, 由此减少网络通信消耗、提高可扩展性、同时提升交易处理速度。

随机类

除竞争、选举外, 也可以通过随机方式选择主节点。对于随机方式, 可以设计随机函数使得每个节点成为主节点的概率与节点所持有的某种资源成比例,也可以设计随机函数使得每个节点成为主节的概率相等。

• Ouroboros 共识算法的核心思想是根据节点权益大小,  随机地选出主节点,  节点权益越大被选中的概率越大。
• PoET 共识算法将信任依托于硬件,  使得区块链系统不必耗费大量算力,  实现了“一CPU 一票”的公平性。每个节点成为主节点的概率相等,  但不能排除用户通过增加CPU 资源提高出块概率,  从而使中心化程度增强。PoET 面临硬件安全造成的单点故障风险,  恶意节点只需攻破一台SGX 就可以控制出块权。

 解释 SGX：SGX（Software Guard Extensions），是 Intel CPU 提供的可信执行环境，可以为云上数据代码的完整性和保密性提供芯片级的安全保障。

其他类型

Ripple

Ripple联盟链项目中提出并实现了 RPCA 共识算法。RPCA 中引入了一个新的概念:  独立节点列表(Unique Node List, UNL)。这是一份“信任”列表, 这里的“信任”指的是节点相信这个列表里的节点不会联合起来作恶,  不需要相信这个列表里的每一个节点。每个节点维护自己的UNL,  各个节点的UNL相互独立,  可能相同也可能不同。 
共识过程如下:    

1. 共识开始之前,  每个节点接受所有的交易, 放到本地的“交易候选集”;    
2. 每个节点把自己UNL 列表中的节点各自维护的“交易候选集”合并到自己本地,  然后以 UNL 为单位对每笔交易进行投票;    
3. 当UNL 中超过一定数量比例的节点都认为某笔交易正确的时候,  这笔交易进入第4 步;  没有达到要求的交易要么被丢弃,  要么继续被留在“交易候选集”中等待下一轮共识过程开始后重新被投票;    
4. 共识过程的最后一步,  对于第 3 步中通过的交易,  如果在这一步 UNL 中超过 80%的节点都认为该笔交易正确,  则这笔交易满足共识要求。所有满足这一要求的交易被添加进账本。 

分片共识算法
当前区块链面临的一大问题是交易性能低。竞争类和随机类共识算法中系统性能等价于单节点性能,  选举类共识算法由于 2( ) O n 的通信复杂度会使得随着节点数量的增加整体的交易性能下降。分片技术中,  全网节点划分为不同的分组(委员会),  每个分组并行处理不同的交易集。其关键技术在于设计合理的分片方式以及解决分片交易的原子性问题。
DAG 共识算法
DAG中的每个单元代表用户发起的一笔交易,  每一条从子单元指向父单元的有向边代表一种验证关系,  即用户创建交易的时候需要对先前的交易单元进行验证,  将验证有效的交易单元的哈希值包含到自己的交易数据结构中,  则当前的交易单元称为子交易,  被验证的交易称为当前交易的父交易,  每笔交易可以有多个父交易,  每个交易也可以有多个子交易,  这样交易单元构成有向无环图的结构：

文章参考了 《区块链共识算法研究综述》 这本书。需要书的可以私信。