区块链共识算法的发展现状与展望

ゞ浴缸里的玫瑰 2022-03-15 05:28 615阅读 0赞

### 区块链共识算法的发展现状与展望-袁勇等 ###

*  1.传统分布式一致性算法
 *  2 主流区块链共识算法
 *  3 共识算法的模型与分类
 *  4 区块链共识算法的新进展
 *   *  4.1 主线 1: PoW 与 PoS 算法的有机结合
     *  4.2 主线 2: 原生 PoS 算法的改进
     *  4.3 主线 3: 原生 PoW 共识算法的改进
     *  4.4 主线 4: 传统分布式一致性算法的改进及其他

# 1.传统分布式一致性算法 #

最早的一致性算法是“两军问题” ，两军 问题表明, 在不可靠的通信链路上试图通过通信达 成一致共识是不可能的, 这被认为是计算机通信研 究中第一个被证明无解的问题. 两军问题对计算机 通信研究产生了重要的影响, 互联网时代最重要的 TCP/IP 协议中的 “三次握手” 过程即是为解决两 军问题不存在理论解而诞生的简单易行、成本可控 的 “工程解”. 分布式计算领域的共识问题主要研究在一组可能存在故障 节点、通过点对点消息通信的独立处理器网络中, 非 故障节点如何能够针对特定值达成一致共识. 这就是后来著名的“拜占 庭将军问题”，提出了基于口头消息和基于签名消 息的两种算法来解决该问题. 分布式共识算法可以分为两 类, 即拜占庭容错和非拜占庭容错类共识. 早期共识 算法一般为非拜占庭容错算法, 例如广泛应用于分 布式数据库的 VR 和 Paxos, 目前主要应用于联盟 链和私有链; 2008 年末, 比特币等公有链诞生后, 拜 占庭容错类共识算法才逐渐获得实际应用. 1985 年, 迈克尔 · 费舍尔 (Michael Fisher)、 南希 · 林奇 (Nancy Lynch) 和迈克尔 · 帕特森 (Michael Paterson) 共同发表了论文 “Impossibility of distributed consensus with one faulty process”\[11\]. 这篇文章证明: 在含有多个确定性进程的 异步系统中, 只要有一个进程可能发生故障, 那么就 不存在协议能保证有限时间内使所有进程达成一致. 按照作者姓氏的首字母, 该定理被命名为 FLP 不可 能定理, 是分布式系统领域的经典结论之一, 并由此 获得了 Dijkstra 奖. 需要说明的是, VR 和 Paxos 算法均假 设系统中不存在拜占庭故障节点, 因而是非拜占庭 容错的共识算法.

# 2 主流区块链共识算法 #

首次提出了工作量 证明思想是用来解决垃圾邮件问题. 该机制要求 邮件发送者必须算出某个数学难题的答案来证明其 确实执行了一定程度的计算工作, 从而提高垃圾邮 件发送者的成本.用拜占 庭容错算法 (Practical Byzantine fault tolerance, PBFT)\[18\], 解决了原始拜占庭容错算法效率不高 的问题, 将算法复杂度由指数级降低到多项式级, 使得拜占庭容错算法在实际系统应用中变得可 行. PBFT 实际上是 Paxos 算法的变种, 通过改 进 Paxos 算法使其可以处理拜占庭错误, 因而也称 为 Byzantine paxos 算法, 可以在保证活性 (Liveness) 和安全性 (Safety) 的前提下提供 (n−1)/3 的 容错性, 其中 n 为节点总数. 分布式系统无法同时满足一 致性 (Consistency)、可用性 (Availability) 和分区 容错性 (Partition tolerance), 最多只能同时满足其 中两个. 其中, 一致性是指分布式系统中的所有数据 备份在同一时刻保持同样的值; 可用性是指集群中 部分节点出现故障时, 集群整体是否还能处理客户 端的更新请求; 分区容忍性则是指是否允许数据分 区, 不同分区的集群节点之间无法互相通信. POS最早应用在点点币。瑞波 协议共识算法 (Ripple Protocol Consensus Algorithm, RPCA)\[21\], 该共识算法解决了异步网络节点 通讯时的高延迟问题, 通过使用集体信任的子网络 (Collectively-trusted subnetworks), 在只需最小化 信任和最小连通性的网络环境中实现了低延迟、高 鲁棒性的拜占庭容错共识算法. 目前, Ripple 已经 发展为基于区块链技术的全球金融结算网络. DPoS 共识的基本思路 类似于 “董事会决策”, 即系统中每个节点可以将其 持有的股份权益作为选票授予一个代表, 获得票数 最多且愿意成为代表的前 N 个节点将进入 “董事 会”, 按照既定的时间表轮流对交易进行打包结算、 并且签署 (即生产) 新区块。 Raft 的初衷是为设计一种比 Paxos 更易于理解 和实现的共识算法.

# 3 共识算法的模型与分类 #

区块链共识算法可以根据其容错类型、部署方 式和一致性程度等多个维度加以分类. 例如, 根据容 错类型, 可以将区块链共识算法分为拜占庭容错和 非拜占庭容错两类; 根据部署方式, 可以将区块链共 识算法分为公有链共识、联盟链共识和私有链共识 三类; 根据一致性程度, 还可以将区块链共识算法分 为强一致性共识和弱 (最终) 一致性共识等. 本文提 出一种按照共识过程的选主策略的新分类方法, 其 优点在于便于刻画共识算法的核心机理. 具体来说, 可根据选主策略 (即函数 f 的具体实现方式) 将区 块链共识算法分为选举类、证明类、随机类、联盟类 和混合类共 5 种类型: 选举类共识: 即矿工节点在每一轮共识过程中 通过 “投票选举” 的方式选出当前轮次的记账节点, 首先获得半数以上选票的矿工节点将会获得记账权; 多见于传统分布式一致性算法, 例如 Paxos 和 Raft 等. 证明类共识: 也可称为 “Proof of X” 类共识, 即矿工节点在每一轮共识过程中必须证明自己具有 某种特定的能力, 证明方式通常是竞争性地完成某 项难以解决但易于验证的任务, 在竞争中胜出的矿 工节点将获得记账权; 例如 PoW 和 PoS 等共识算 法是基于矿工的算力或者权益来完成随机数搜索任 务, 以此竞争记账权. 随机类共识: 即矿工节点根据某种随机方式 直接确定每一轮的记账节点, 例如下文将要提到的 Algorand 和 PoET 共识算法等. 联盟类共识: 即矿工节点基于某种特定方式首先选举出一组代表节点, 而后由代表节点以轮流或 者选举的方式依次取得记账权. 这是一种以 “代议 制” 为特点的共识算法, 例如 DPoS 等. 混合类共识: 即矿工节点采取多种共识算法的 混合体来选择记账节点, 例如 PoW + PoS 混合共 识、DPoS+BFT 共识等.

# 4 区块链共识算法的新进展 #

## 4.1 主线 1: PoW 与 PoS 算法的有机结合 ##

研究者基于 PoW 和 PoS 算法的有机结合, 相 继提出了权益–速度证明 (Proof of stake velocity, PoSV)\[25\]、燃烧证明(Proof of burn, PoB)、行动 证明 (Proof of activity, PoA) 和二跳 (2-hop) 共识算法, 致力于取长补短、解决 PoW 与 PoS 存 在的能源消耗与安全风险问题. PoSV 共识算法, 针对 PoS 中币龄是时间的线 性函数这一问题进行改进, 致力于消除持币人的屯 币现象. PoSV 算法前期使用 PoW 实现代币分配, 后期使用 PoSV 维护网络长期安全. PoSV 将 PoS 中币龄和时间的线性函数修改为指数式衰减函数, 即币龄的增长率随时间减少最后趋于零. 因此新币 的币龄比老币增长地更快, 直到达到上限阈值, 这在 一定程度上缓和了持币者的屯币现象.基 于 PoW 和 PoS 首创提出了 PoB 共识算法. 其中, PoW 共识被用来产生初始的代币供应, 随着时间增 长, 区块链网络累积了足够的代币时, 系统将依赖 PoB 和 PoS 共识来共同维护. PoB 共识的特色是 矿工通过将其持有的 Slimcoin 发送至特定的无法找 回的地址 (燃烧) 来竞争新区块的记账权, 燃烧的币 越多则挖到新区块的概率越高.PoA 共识也是基于 PoW 和 PoS, 其中采用 PoW 挖出的部分代币以抽奖的方式分发给所有活跃节点, 而节点拥有的权益与抽奖券的数量即抽中概率成正比。二跳共识解决 PoW 潜在的 51% 算力攻击问题, 解决思路是 在 PoW 算力的基础上引入 PoS 权益, 使得区块链 安全建立在诚实节点占有大多数联合资源 (算力 + 权益) 的基础上. 换句话说, 拜占庭节点必须同时控 制 51% 以上的算力和 51% 以上的权益, 才能成功 实施 51% 攻击, 这无疑极大地提高了区块链的安全 性.

## 4.2 主线 2: 原生 PoS 算法的改进 ##

原生 PoS 共识算法的改进目标主要是解决 其固有的 “无利害关系 (Nothing at stake)” 问 题, 形成了 Tendermint\[29\] 以及由其衍生出的 Casper\[30\]、Ouroboros\[31\]、Tezos\[32\] 和 Honeybadger\[33\] 等新共识算法. 原生 PoS 共识一般假设系统 中的对等节点都是静态和长期稳定的, 这在区块链 环境中并不现实. 2014 年提出的 Tendermint 的重 大突破是使用区块、哈希链接、动态验证器集合和循 环的领导者选举, 实现了第一个基于 PBFT 的 PoS 共识算法. 为解决无利害关系问题, Tendermint 节 点需要缴纳保证金, 如果作恶则保证金就会被没收. Tendermint 是一种拜占庭容错的共识算法, 具有抵 御双花攻击的鲁棒性, 并且可以抵御网络中至多三 分之一的破坏者的攻击. 2016 年提出的 HoneyBadger 共识是首个实用 的异步拜占庭容错共识协议, 可以在没有任何网络 时间假设的前提下保证区块链系统的活性 (Liveness). 该共识基于一种可实现渐近有效性的原子广 播协议, 能够在广域网的上百个节点上处理每秒上 万笔交易. 2017 年 8 月提出的 Ouroboros 共识是 首个基于 PoS 并且具有严格安全性保障的区块链协 议, 其特色是提出了一种新的奖励机制来驱动 PoS 共识过程, 使得诚实节点的行为构成一个近似纳什 均衡, 可以有效地抵御区块截留和自私挖矿等由于 矿工的策略性行为而导致的安全攻击.

## 4.3 主线 3: 原生 PoW 共识算法的改进 ##

原生 PoW 共识算法的改进目标主要是实现比 特币扩容或者降低其能耗. Elastico 是第一个拜占庭容错的安 全分片协议. OmniLedger 通过并行 跨分片交易处理优化区块链性能, 是第一种能够提 供水平扩展性而不必牺牲长期安全性和去中心性的 分布式账本架构.

## 4.4 主线 4: 传统分布式一致性算法的改进及其他 ##

Tangaroa 继承了Raft 简洁和容易理解的优势, 同时在拜占庭错误环境下 也能够维持安全性、容错性和活性. 受 Tangaroa 共 识启发, 2016 年 Github 平台的 Juno 项目提出一 种拜占庭容错的 Raft 算法, 此后该算法演变为一种 称为 ScalableBFT\[45\] 的专用拜占庭容错协议, 能够 实现比 Tangaroa 和 Juno 更好的性能. SCP 在联邦拜占庭协议 和 Ripple 协议的基础上演化而来的, 是第一个可证 明安全的共识机制, 具有分散控制、低延迟、灵活信 任和渐近安全 4 个关键属性. 同年, 超级账本的锯 齿湖项目将 Ripple 和 SCP 共识相结合, 提出了法 定人数投票 (Quorum voting) 共识算法, 以应对那 些需要即时交易最终性的应用场景. 2016 年, 中国 区块链社区 NEO (原名小蚁) 提出一种改进的拜占 庭容错算法 dBFT, 该算法在 PBFT 的基础上借鉴 了 PoS 设计思路, 首先按照节点的权益来选出记账 人, 然后记账人之间通过拜占庭容错算法来达成共 识. 该算法改进了 PoW 和 PoS 缺乏最终一致性的 问题, 使得区块链能够适用于金融场景.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3FpbmdzaHVhbmc_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3FpbmdzaHVhbmc_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3FpbmdzaHVhbmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190301102909657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3FpbmdzaHVhbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3FpbmdzaHVhbmc_size_16_color_FFFFFF_t_70 1]: /images/20220315/95b496cfa947433dbf60e386b31c226c.png