海阔 山遥 2019-05-13 13:42:52 浏览 149 评论 0
分布式
分布式系统与计算
阿里技术协会
分布式系统
区块链
共识机制
分布式一致性
摘要: 本文将从传统的分布式一致性问题说起, 再次重温我们需要面对的问题挑战, 已有的理论研究, 以及相应的一致性算法, 并简要分析这些一致性算法的适用性与局限性, 以及这些传统一致性算法与崭新的区块链技术的结合. 另外, 将从区块链中一致性问题的全新视角 "人的可信" 出发, 重点阐述公有链领域中的共识算法与机制.
分布式一致性是一个很 "古典" 的话题, 即在分布式系统中, 如何保证系统内的各个节点之间数据的一致性或能够就某个提案达成一致. 这个问题想必对于很多技术同学而言并不陌生, 几乎在所有的分布式系统中都会遇到, 比如 hdfs,mq,zookeeper,kafka,Redis,Elasticsearch 等. 然而这个问题却历久弥新, 随着分布式网络的蓬勃发展与复杂化, 对于该问题解法的探索也一直在进行中.
而近年来, 随着区块链技术的兴起, 特别是开放网络中的公有链与有权限网络中的联盟链的蓬勃发展, 一致性问题再次得到关注, 并从新的视角来审视该问题.
本文将从传统的分布式一致性问题说起, 再次重温我们需要面对的问题挑战, 已有的理论研究, 以及相应的一致性算法, 并简要分析这些一致性算法的适用性与局限性, 以及这些传统一致性算法与崭新的区块链技术的结合. 另外, 将从区块链中一致性问题的全新视角 "人的可信" 出发, 重点阐述公有链领域中的共识算法与机制. 因此, 本文围绕 "一致性" 技术问题, 重点从技术视角阐述传统计算机科学中的分布式一致性算法与区块链中的共识机制的关联, 以及公有链对于一致性问题的重新思考.
分布式一致性问题的挑战
要清楚理解分布式一致性, 首先需要对分布式网络的特性有清晰的认识. 那么分布式网络具有哪些特点呢? 或者通俗理解, 在分布式网络中, 可能遇到哪些问题呢?
Crash Fault
故障错误 (Crash Fault) 很好理解, 就是说分布式网络中:
节点或副本可能随时宕机, 可能暂停运行但随后又恢复;
网络可能随时中断;
发送的消息可能在传递的过程中丢失, 对方一直收不到;
发送的消息可能出现延迟, 过了很久对方才能收到;
消息在传递的过程中可能出现乱序;
网络可能出现分化, 如中美集群因通信不畅, 而导致整体网络分化为中美两个子网络;
这些问题, 其实就是我们在分布式环境中最常实际遇到的问题, 这些问题实质上都是由于分布式系统中的物理硬件的不可靠, 不稳定所带来的必然风险, 比如: 网络 (信道) 不可能是永远稳定可靠的, 物理机磁盘或 CPU 等不可能是永远良好的. 故障错误可以说是分布式系统中必须考虑并解决的最基本, 最常见的一类错误.
Byzantine Fault
上文的故障错误, 仍然基于一个很简单的假设: 节点要么不正常工作或响应, 要么能正常工作或响应, 但不能口是心非, 阳奉阴违, 表里不一, 即可以不干事, 但不能干坏事. 一旦网络中存在作恶节点, 可能会随意篡改或伪造数据, 那么一致性问题的难度就大幅增加. 我们常把这类存在 "捣乱者", 可能会篡改或伪造数据或响应信息的错误, 称之为拜占庭错误(Byzantine Fault), 而前面所说的故障类错误也称之为非拜占庭错误.
拜占庭这一称呼, 源于 Lamport 最初的论文, 可以说是分布式领域最复杂, 最严格的容错模型. 简而言之, n 个将军准备一起进攻某个城堡, 每个将军都可以选择进攻或是撤退, 但所有将军必须行动一致才能成功. 各个将军之间相隔很远, 不能直接通讯, 必须通过信使来传递消息. 但是信使并不可靠, 信使可能过了很久才送到消息, 可能一直也没有把消息送到, 甚至可能会故意篡改消息; 而将军也并不可靠, 里面可能存在叛徒, 并不按照提案来行动. 显然, 这个故事中的信使用来代表分布式网络中的不可靠信道, 而将军就是各个不可靠的节点.
拜占庭问题示意图()
应对风险 - Fault Tolerance
如何在充满风险与不确定的分布式网络中, 寻找到某种确定性与一致性, 使得整个分布式网络输出稳定可靠的一致性结果, 就是分布式一致性算法要解决的核心问题. 显而易见, 解决故障类错误更容易一些, 通常把这类一致性算法叫做故障容错算法 (Crash Fault Tolerance) 或者非拜占庭容错算法. 而拜占庭类错误, 因为有恶意篡改的可能性存在, 复杂性更高, 解决难度更大, 通常把解决这类问题的算法称作拜占庭容错算法(Byzantine Fault Tolerance).
那么我们忍不住要问, 两类容错算法的界限在哪里? 或者说两类错误都在什么样的场景下出现? 恶意篡改这种情况真的需要考虑吗? 问题的答案可能取决于我们所处的网络环境与业务场景.
CFT
通常而言, 如果系统处于可信的内部网络环境中, 只需要考虑故障容错 (CFT) 可能就足够了. 比如我们经常见到的公司内的分布式存储, 消息队列, 分布式服务等各种分布式组件, 其实只需要考虑故障容错就足够了. 因为公司内整个网络是封闭的, 又有多重防火墙的保护, 外界很难接入或攻击; 各个节点是由公司统一部署的, 机器或运行的软件遭到篡改的可能性极小; 此时的分布式网络环境相对 "单纯", 我们唯一的敌人只是: 通信网络与机器硬件. 我们需要考虑的是网络的延迟, 不稳定, 以及机器随时可能出现的宕机, 故障.
BFT
而拜占庭类错误(BFT), 是把整个分布式网络放到了更大的环境中去看, 除了物理硬件之外, 还考虑了一些 "人" 的因素. 毕竟, 机器是不会作恶的, 作恶的只有人. 假如我们所处的分布式网络是较为开放的网络, 比如行业内几十上百家公司组成的联盟网络; 或者是完全开放的网络, 比如任何人都可以随意接入到网络中; 而节点机器和上面部署的软件也是由各个公司或个人自己提供和部署的, 那么如果利益足够大, 很可能会有人对网络中的某个节点发起 DDoS 攻击, 故意篡改软件代码改变其执行逻辑, 甚至可能故意篡改磁盘上持久化的数据. 显然, 我们此时面临的挑战更大了, 我们除了要考虑通信网络和机器硬件的不可靠之外, 还必须要考虑和应对系统中的 "捣乱者".
不可能三角
这些实践中遇到的问题, 也引发了诸多计算科学家进行了非常多的理论研究. 这些理论研究对于工程技术人员而言或许过于抽象繁琐, 有些甚至是无趣的数学问题, 但这些理论对于指导我们解决这些问题意义重大. 这些理论相当于是告诉了我们这类问题解法的理论极限, 以及哪些方向可以探索, 哪些方向是死路一条. 站在前人的肩膀上, 才不至于花毕生精力去研制 "永动机". 这些理论大家应该都有所了解, 这里只简单回顾.
FLP impossibility
早在 1985 年, Fisher,Lynch,Paterson 三位科学家就发表了关于分布式一致性问题的不可能定理: 在完全异步的分布式网络中, 故障容错问题无法被解决.( We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation. )说得更直白点: 在异步网络中, 不可能存在能够容忍节点故障的一致性算法, 哪怕只有一个节点故障. 并且这里并没有考虑拜占庭错误, 而是假设网络非常稳定, 所有的消息都能被正确传递, 并且仅被传递一次, 即便如此都不可能找到能容忍哪怕只有一个节点失效的一致性协议, 可见该结论有多强.( In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once. )
当然了, 这只是理论上的. 它的意义在于告诉我们此类问题的理论极限, 并不意味着此类问题在实践中也不可能被 "解决". 如果我们愿意放宽限制, 做出牺牲, 在工程上是可以找到切实可行的解法的.
FLP 不可能定理的最大适用前提是异步网络模型. 何为同步, 异步模型呢?
所谓异步模型, 是说从一个节点到另一个节点的消息延迟是有限的, 但可能是无界的(finite but can be unbounded). 这就意味着如果一个节点没有收到消息, 它无法判断消息到底是丢失了, 还是只是延迟了. 也就是说, 我们无法通过超时时间来判断某个节点是否故障.
所谓同步模型, 是说消息传递的延迟是有限的, 且是有界的. 这就意味着我们可以通过经验或采样精确估算消息的最大可能延迟, 从而可以通过超时时间来确定消息是否丢失, 节点是否故障.
所幸的是, 我们所处于的真实的网络世界更接近同步模型, 在很多场景上, 我们都可以通过经验或采样确定最大超时时间. 举个通俗点的例子: 你给朋友快递了一本书, 朋友过了 3 天还没收到, 此时朋友很难判断到底是快递延迟了, 还是快递出问题送丢了. 但是如果过了一个月, 朋友仍没收到书, 基本就可以断定快递送丢了. 而背后的推论就是基于经验或统计: 通常快递都能在 1-2 周内送达. 显然, 异步模型其实是反映了节点间通讯的最差情况, 极端情况, 异步模型包含了同步模型, 即能在异步模型上有效的一致性协议, 在同步模型上也同样有效. 而同步模型是对异步模型做了修正和约束, 从而使得更接近真实世界, 也使得在实践中一致性问题有可能得到有效解.
另外, 即便是在异步网络模型下, FLP 也并不意味着一致性永远无法达成, 只是说无法保证在有界的时间 (in bounded time) 内达成. 在实践上, 如果放宽对 bounded time 的限制, 仍然是有可能找到实践中的解法的.
而根据 DLS 的研究( ), 一致性算法按照网络模型可以分为三大类:
部分同步网络模型 (partially synchronous model) 中的一致性协议可以容忍最多 1/3 的任意错误. 这里的部分同步模型是指网络延迟是有界的, 但是我们无法提前得知. 这里的容错也包含了拜占庭类错误.
异步网络模型 (asynchronous model) 中的确定性协议无法容忍错误. 这里的异步模型即是前文所说的网络延迟是无界的. 该结论其实就是 FLP 不可能定理的含义, 在完全异步网络中的确定性协议不能容忍哪怕只有一个节点的错误.
同步网络模型 (synchronous model) 可以达到惊人的 100% 容错, 虽然对错误节点超过 1/2 时的节点行为有限制. 这里的同步模型是指网络延迟一定是有界的, 即小于某个已知的常数.
从另一个角度来理解, FLP 实际上考虑了分布式系统的 3 个属性: 安全(safety), 活性(liveness), 容错:
安全是说系统内各个节点达成的值是一致的, 有效的. safety 其实是保证系统一致性运行的最低要求, 其核心是 cannot do something bad, 即不能干坏事, 不能做错事.
活性是说系统内各个节点最终 (在有限时间内) 必须能够达成一致, 即系统必须能够向前推进, 不能永远处于达不成一致的状态. liveness 其实是更高要求, 意味着不能只是不干坏事, 也不能一直不干事, you must do something good, 即必须使得整个系统能良好运转下去.
容错是说该协议在有节点故障的情况下也必须能有效.
FLP 不可能定理其实意味着在异步网络中, 不可能存在同时满足这三者的分布式一致性协议. 因为分布式环境中, 节点故障几乎是必然的, 因此容错是必须要考虑的因素, 所以 FLP 不可能定理就意味着一致性协议在能做到容错的情况下, 没办法同时做到安全性与系统活性. 通常在实践中, 我们可以做出部分牺牲, 比如牺牲一部分安全性, 意味着系统总能很快达成结论, 但结论的可靠性不足; 或者牺牲一部分系统活性, 意味着系统达成的结论非常可靠, 但可能长时间, 甚至永远都在争论中, 无法达成结论. 所幸的是, 很多时候现实世界的鲁棒性很强, 使一致性协议失效的倒霉事件发生的概率也很可能极低.
FLP 不可能定理示意图()
另外, FLP 并未排除 Las Vegas 类随机算法, 许多一致性算法采用了这种随机性来规避 FLP 不可能定理对于确定性异步网络的限制. 此类非确定性一致性算法涉及 Las Vegas 规则: 网络最终一定能达成一致, 但是达成一致所需要的时间可能是无界的. 此类算法每轮共识决策都有一定的概率, 并且系统在 T 秒内能够达成一致的概率 P 随着时间 T 的增加而指数增长并趋近于 1. 事实上, 该方法被许多成功的一致性算法所采用, 是在 FLP 不可能定理笼罩下的安全地带(escape hatch), 后面将会讲到比特币的共识机制就是采用了这样的方法.
CAP theorem
众所周知, 大名鼎鼎的 CAP 原理, 从另一个维度, 简单明了, 直截了当地告诉我们: 可用性, 一致性与网络分区容错性这三者不可能同时实现, 而只能实现任意其中的两个.( "Of three properties of shared-data systems (data consistency, system availability and tolerance to network partitions) one can only achieve two at any given time".) CAP 与 FLP 看起来有相似之处, 其实二者并不尽相同, 二者是从不同的维度思考问题, 另外即使是很相似的概念, 内涵也并不完全一样. 比如:
FLP 面对的是分布式一致性问题, 而 CAP 面对的是分布式网络中的数据同步与复制.
FLP 是说在异步网络模型中, 三者不可能同时实现; 而 CAP 是说在所有场景下, 三者都不可能同时实现.
FLP 中的 liveness 强调的是一致性算法的内在属性; 而 CAP 中的 availability 强调的是一致性算法对外呈现的外在属性.
理论上, 只能从 CAP 三者中选择两者, 然而, 这种选择的边界并非是非此即彼的(not binary), 很多时候混合考虑不同程度的各个因素, 结果可能是更好的.( The whole spectrum in between is useful; mixing different levels of Availability and Consistency usually yields a better result.)
CAP 理论示意图()
在实践中, 我们通常需要根据实际业务场景做折中权衡. 比如:
传统的关系型数据库如 MySQL 等多采用 ACID(atomicity, consistency, isolation and durability)理论, 通过同步事务操作保证了强一致性; 因节点较少(一般只有主从), 可用性也比较一般; 网络拓扑较为简单, 而弱化了分区容错性.
NoSQL 存储系统如 hbase 等多采用 BASE(Basically Available,Soft state,Eventually consistent)理论, 通过多节点多副本保证了较高的可用性; 另外因节点数增多, 网络环境也更复杂, 也考虑了网络分区容错性; 但一致性较弱, 只能保证最终一致性.
ACID 与 BASE 对比()
当然, 这些并不是定论, 各个系统都在各自不断的进化完善中, 今天的结论明天可能就会被打破. 更好的系统一定是不断探索适合自己的场景, 找到更佳的平衡点.
分布式一致性算法
面对分布式环境中各种真实, 复杂的问题与挑战, 基于理论上的指引, 各种应对现实问题的解法也被提出. 我们这里不探究各类算法的实现细节与具体差异, 仅做大体介绍, 以便放到更大的维度, 从整体上做比较.
Paxos
最大名鼎鼎的分布式一致性算法当属 Lamport 提出的 paxos 算法, 虽然其复杂性也同样 "臭名昭著".Lamport 开创性地提出了一种在工程实践上切实可行的, 能够最大程度地保证分布式系统一致性的机制. paxos 被广泛应用在诸多分布式系统中, 如 Chubby,Zookeeper 等. 在 basic paxos(单一法令, 即每次仅对一个值进行决策)中有两种角色: proposer 可以处理客户端请求, 主动提出某个议案值; acceptor 被动响应 proposer 发出的信息, 对提案进行投票, 持久化存储决策过程中的值和状态.(为简化模型, 可以忽略 learner 角色, 不影响模型决策.)
如图所示, 共识决策过程采用了两阶段提交:
第 1 阶段, 广播 Prepare RPC 命令, 即找出协议决定的最终值, 阻断尚未完成的旧提案;
第 2 阶段, 广播 Accept RPC 命令, 即要求 acceptor 接受共识协商出的特定值. 而 multi-paxos 是由多个 basic paxos 实例组成, 可以对一系列的值进行决议.
Paxos 之所以在实践中可行, 其实也做了诸多假设和约束. 从处理的问题上来看, Paxos 仅能处理故障容错, 并不难处理拜占庭错误, 所以属于非拜占庭容错算法. 从 FLP 的视角, Paxos 做到了故障容错和安全性, 但放弃了 liveness(safe but not live), 也就是说该算法可能永远无法结束, 或者说永远无法达成共识, 虽然这种可能性极小. 从 CAP 的视角, Paxos 只保证了 CP, 即做到了分区容错性和一致性, 但弱化了可用性. 有时为了增强 paxos 系统的可用性, 可以考虑增加 learner 角色的数目.
即便并不完美, Paxos 在实践中仍然是可靠, 有效且久经考验的. Paxos 本质上是异步系统的分布式一致性协议, 并且在该领域具有支配地位. Chubby 之父甚至声称世界上只有一种一致性算法, 那就是 paxos( there is only one consensus protocol, and that's Paxos), 其他一致性算法都是 paxos 的 broken version.Paxos 之所以在实践中有效是因为可能影响 paxos 系统 liveness 和可用性的条件并不容易被触发, 即便真的出现, 所带来的代价也可能并非是难以接受的.
Basic Paxos RPC 通信与决策过程()
Raft
有感于 Paxos 的晦涩难懂, Ongaro 在 2014 年提出了更容易理解的 Raft 算法. Raft 把易于理解, 易于工程实现提到了很高的重要级别, 甚至是 raft 的初心和存在理由, 因而在不影响功能性的前提下, 尽可能多地做了易于理解的精细设计.
Raft 算法是 leader-based 的非对称模型, 系统中的任意一个节点在任意时刻, 只能处于 leader,follower,candidate 这 3 种状态之一. 初始状态所有节点都是 follower 状态, follower 想变成 leader 必须先成为 candidate, 然后发起选举投票; 如果投票不足, 则回到 follower 状态; 如果投票过半, 则成为 leader; 成为 leader 后出现故障, 若故障恢复后已有新 leader, 则自动下台, 回归 follower 状态.
Raft 还引入了 term 的概念用于及时识别过期信息, 类似于 zookeeper 中的 epoch;term 值单向递增, 每个 term 内至多一个 leader; 若不同 term 的信息出现冲突, 则以 term 值较大的信息为准.
Raft 还采用了心跳包和超时时间, leader 为了保持自己的权威, 必须不停地向集群中的其他节点发送心跳包; 一旦某个 follow 在超过了指定时间 (election timeout) 仍没有收到心跳包, 则就认为 leader 已经挂掉, 自己进入 candidate 状态, 开始竞选 leader.
不难发现, raft 的 leader 选举是通过 heartbeat 和随机 timeout 时间来实现的; 而日志复制 (log replication) 阶段是以强 leadership 来实现的: leader 接收 client 的 command,append 到自身 log 中, 并将 log 复制到其他 follower; 而 raft 对安全性的保证是通过只有 leader 可以决定是否 commit 来实现的.
详细的竞选, 复制等过程, 这里不再赘述, 有兴趣的同学可以参考笔者之前的文章(https://yq.aliyun.com/articles/675031 ). 值得一提的是, raft 中的 leader 选举过程和 leader 任期内的正常运作过程都比较简单, 复杂的其实是 leader 的变更过程.
然而, 虽然 raft 的原理机制与 paxos 不尽相同, 但二者所解决的问题, 以及所采取的折中权衡策略, 可以认为是类似的. 也就是说 raft 仍然只能解决故障错误, 仍然强调了故障容错与安全性, 一致性, 弱化了 liveness 和可用性.
Raft 协议概览()
PBFT
自从 1982 年 Lamport 提出拜占庭将军问题之后, 虽然有诸多关于拜占庭容错解决方案的讨论, 但长期以来, 此类问题的解决方案都效率低下, 运行缓慢, 复杂度过高, 直到 1999 年 Castro 和 Liskov 提出实用拜占庭容错算法(Practical Byzantine Fault Tolerance), 首次将此类算法的复杂度从指数级降到了多项式级, TPS 可以达到几千, 也使得节点故意作恶类问题在实践中找到了可行的解法. 可以证明, 如果系统内作恶节点数目不超过总节点数目的 1/3,PBFT 算法就能生效.
在 PBFT 中, 所有的节点被顺序编号, 其中 1 个是 leader, 其余的都是 backup. 系统内的所有节点间都互相通讯, 依据多数原则达成一致. PBFT 中的每轮共识都被称为一个 view, 而在不同的 view 之间, leader 都会发生变化; 如果超过给定的时间, leader 没有广播出消息, 则 leader 就会通过 view change 协议被替换掉. 通过这种 replica timeout 机制, 保证了 crashed 或 malicious leader 会被检测出来, 从而通过重新选举新的 leader, 而进入到新的 view 中.
如图所示, 从客户端发起请求到收到回复结果, 可以分为 5 个阶段, 而共识过程采用了 3 阶段协议. 下面简要叙述 5 个阶段的大致过程:
发起: 客户端 (client c) 向集群发起服务请求 m;
pre-prepare 阶段: leader 节点 (replica 0) 验证请求消息 m 的有效性, 并在其 view 内为该请求 m 分配序列号 n, 并向所有 backup 节点 (replica 1-3) 广播关于该分配的 pre-prepare 消息;
prepare 阶段: backup 节点验证请求消息 m 的有效性, 并接受序列号 n. 若该节点同意该分配方案, 则向其他所有节点广播出相应的 prepare 消息; 这一阶段其实是要求所有 replica 达成全局一致的顺序.
commit 阶段: 所有节点 (包含主备) 一旦收到来自集群的同意分配消息, 则向其他所有节点广播出 commit 消息; 这一阶段, 所有 replica 已经对顺序达成一致, 并对收到请求已做确认.
执行并返回: 节点收到来自集群的 commit 消息后, 执行请求 m, 并返回消息给客户端; 客户端等到接收到来自 f+1 个不同节点的相同回复, 则认为请求已成功执行; 其中 f 表示集群中潜在故障节点的最大数目. 这里所有节点都向 client 直接返回消息也是为了避免主节点在请求期间出问题.
PBFT 算法正常运作过程( http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf )
PBFT 基于异步网络模型做到了安全性, 但需要依赖消息超时时间来做周期性的同步. 因为采用了 leader-based 方案, 消息同步过程很快, 也做到了完全的顺序写入. 但是 leader 的重新选举过程很困难, 某些恶意 leader 可以在临近 timeout 窗口期时才发送消息, 这样会导致系统严重缓慢. 而利用这一不利特点, 可以攻击网络使正确的 leader 看起来也出问题, 从而导致无穷无尽的 leader 选举过程.
PBFT 与 Paxos,Raft 相比, 所能处理应对的问题更为完备, 除了能应对故障崩溃类错误之外, 还能处理存在 "捣乱者" 的恶意篡改类拜占庭错误. 然而, 从所采取的折中权衡策略来看, PBFT 仍然与 Paxos,Raft 很类似. 从 FLP 的视角来看, PBFT 同样更关注容错性和安全性, 而弱化了 liveness. 从 CAP 的角度, PBFT 同样强调网络分区容错与一致性, 而弱化了可用性.
即便如此, 只要故障或作恶节点不超过总节点数的 1/3,PBFT 在实践中还是有效可行的. 而拜占庭容错算法 (BFT) 也不止 PBFT 一种, BFT 类算法也在不断进化, 如 Lamport 就提出过改进版的 Paxos 算法 BFT Paxos 以处理拜占庭错误, 近来也有人结合 PBFT 与 Raft 提出了 BFT Raft 算法. 但从问题领域与原理机制上来说, 仍然与原有的思路和框架较为类似, 不再一一赘述.
适用场景
从 Paxos,Raft 到 PBFT, 再到目前层出不穷的 Paxos 变种, Raft 变种, BFT 类混合新算法, 分布式一致性算法在不断发展, 完善, 进化. 甚至各大公司也在结合自己的业务实际, 研发各种适合自己场景的分布式一致性算法. 这些算法虽然并不完美, 但都在适合自己场景的业务实践中发挥着重大作用. 那么这些算法的适用场景到底是什么? 自身又有哪些局限性呢?
对于 Paxos,Raft 这类非 BFT 算法而言, 只能处理机器硬件故障, 而无法处理存在作恶节点的情况. 显然, 这类非 BFT 算法只能运行在非常可信的网络环境中, 比如公司内部网络中, 在这样的较为封闭的网络中, 访问需要严格授权, 从而保证各个节点的身份是已知的, 可信的, 基本排除了节点作恶的可能性, 这类算法才能有效运行.
而 BFT 类算法, 对于网络环境的要求不再那么苛刻, 即使存在作恶节点, 只要作恶节点数目不超过总节点数的 1/3, 整个系统依然是安全的. 但问题就在于, 你怎么知道网络中到底有多少作恶节点? 作恶节点占总节点的比例到底有多高? 显然, 如果网络的接入是需要权限控制的, 那么这个问题就相对容易解决. 比如 10 家业务关联公司组成的联盟网络, 只有这 10 家授权的公司才能访问, 即便里面有个别公司 (少于 3 家) 蓄意作恶, 妄图篡改数据, 整个系统仍然是安全可靠的. 在这种 permissoned 网络中, 隐含着对于网络中可能作恶节点数目的预估, 即便真的作恶了, 也能方便快速地定位出其真实身份, 间接提高了网络的安全性.
局限性
然而, 在 permissonless(开放权限, 无权限控制)的公有网络中, BFT 类算法很可能会有问题. 因为, 如果分布式网络是开放的, 谁都能进进出出, 而接入网络系统的成本又很低, 那么没人知道网络中到底可能有多少作恶节点, 即便真有作恶, 也很难定位出真实身份. 比如, 一种比较典型的女巫攻击 (Sybil attack) 场景, 作恶者可以通过大量伪造身份来控制集群中的大量节点, 从而控制整个分布式网络.
另外, BFT 类算法最大的局限性还在于仅能协调少量的节点, 如几个到几十个, 若节点数目成千上万, 整个系统的性能将会非常低下, 甚至可能无法达成共识, 从而影响系统的 liveness 和可用性. 想必大家已经注意到, 在 PBFT 的三阶段协议中, 都需要多点广播(multicast): 在 pre-prepare 阶段, 主节点向所有备节点广播; 在 prepare 节点, 备节点向其他所有节点广播; 在 commit 阶段, 各个节点向其他所有节点广播. 由此可见, 通讯次数的数量级是节点数目的平方, 当节点数目庞大时, 这种两两广播的机制将会是灾难, 系统几乎不可能在较短时间内达成一致.
综上可知, 这些传统的分布式一致性算法, 无论是 Paxos,Raft, 还是 PBFT, 通常适用于存在权限控制的, 节点数目较少的, 较为可信的分布式网络环境中.
在联盟链中的应用
事实上, 这些传统的一致性算法在区块链时代也焕发了新的活力, 得到了进一步的认识和使用. 在网络环境较为可信的联盟链场景中, 这些一致性算法得到了大量的应用. 联盟链因如下特点而被业内看好其应用前景:
接入需授权: 联盟链并不完全对外开放, 一般只有几家或几十家企业组成, 只有经过授权的公司或组织才能加入到网络中, 并且一般是实名认证参与.
数据保护: 联盟链信息数据并不完全对外开放, 而只有授权方可见. 这对于保护行业或公司的数据安全比较重要, 如跨境转账中的交易信息等对于银行业至关重要, 链上税务系统中的税务信息也很敏感.
可监管: 联盟链中一般可以设立监管观察节点, 对于敏感信息进行审计与监管, 满足合法性要求.
在当前阶段, 联盟链不失为快速落地, 解决行业痛点的不错选择, 也是对区块链后续发展的积极探索. 因为联盟链需要授权才能参与, 这其实相当于已经提前建立了相当程度的信任, 网络环境较为可信, 网络中的恶意行为和攻击行为发生的可能性都非常低, 并且即便发生也很容易快速追责. 因此在这样的场景下, 传统的一致性算法也可以得到应用. 比如:
HyperLedger Fabric( https://www.hyperledger.org/projects/fabric ) 在 v1.0 中可以使用 Solo 和 Kafka pubsub 系统来实现 ordering; 在 v1.4 版本也引入了 Raft 算法( ); 目前这些均是 CFT 类算法, 而 raft 的引入主要也是为后期支持 BFT 类算法铺平道路( Raft is the first step toward Fabric's development of a byzantine fault tolerant (BFT) ordering service. As we'll see, some decisions in the development of Raft were driven by this. ).
R3 Corda( https://www.r3.com/corda-platform/ )也采用了可插拔式的共识算法设计, 不仅可以选择高速度, 高可信环境的 Raft 算法, 也可以选择低速度, 低可信环境的 BFT 类算法( https://docs.corda.net/key-concepts-notaries.html ).
以太坊企业联盟 EEA( https://entethalliance.org/ )也支持 BFT 类算法, Raft 算法, 以及 PoET 算法( ).
蚂蚁区块链 BaaS 平台 ( https://tech.antfin.com/blockchain ) 也采用了 PBFT 算法.
Permissionless 网络的挑战
那么我们忍不住要问, 如果网络是完全开放的, 无需权限许可的(permissionless), 谁都可以随时进出, 那么整个系统还能在有限的时间内达成一致吗? 如果网络中的节点数目不再是几十个, 而是一万个, 那么又该如何协调这些数量庞大的节点呢?
在回答这些问题之前, 其实更应该反问: 为什么需要网络是完全开放, 无需许可的? 什么场景会需要一万个节点? 这到底是伪需求, 还是真实存在的场景? 这个问题的答案直接关系到区块链中公有链的存在意义, 而要回答这个问题, 我们需要回到分布式系统的初心和目的.
去中心化的意义
我们为什么需要分布式系统? 显然, 这个问题不难回答, 通常的理解, 分布式系统可以增强容错能力(Fault tolerance), 毕竟系统依赖众多不同的节点, 而众多节点同时失败的可能性远低于一个节点发生故障的可能性; 另外, 分布式系统还可以抵御攻击(Attack resistance), 毕竟攻击或摧毁众多节点的难度远大于攻击单点的难度.
然而, 以上这些依然是局限在物理硬件的维度, 都是用来降低机器物理硬件发生故障的可能性, 而没有考虑 "人" 的因素. 如果一个系统足够重要, 比如电子货币系统等, 除了考虑机器故障之外, 更多需要考虑的是人的因素. 部署节点的人会不会故意作恶呢? 如何防止系统内不同节点间的腐败串通呢?
如下图所示, 以太坊创始人 Vitalik Buterin 曾经深入地探讨过去中心化的含义. 如果说传统的分布式系统做到了 architectural decentralization(系统有多少物理机器构成? 系统能够容忍最多多少台机器同时故障?), 考虑的是 fault tolerance 和 attack resistance; 那么现在我们需要考虑的是如何做到 political decentralization, 如何能够 collusion resistance? 到底有多少人或组织最终控制了系统内的节点? 如何防止这些人之间的腐败串通? 如果说传统的分布式系统考虑的问题是网络或机器硬件的可信, 那现在我们想考虑的是 "人的可信": 是否存在这样的技术手段来防范人的作恶? 如何确保重要网络中的大部分节点不被一个人或一个组织恶意控制?
去中心化的三个维度()
值得一提的是, 这个问题的必要性依然充满争议, 很多人根本不曾想过, 或者认为根本没有必要考虑人的腐败串通, 也可能认为对于这个问题技术也无能为力, 毕竟这与我们生活的真实世界相去甚远. 我们生活在一个中心化平台拥有极高声誉, 提供信用背书, 控制一切规则流程的世界, 比如极少有人担心银行会故意做假账, 侵吞你在银行的资产, 毕竟大家普遍认为银行是值得信赖的. 如果认为银行都不可信, 那很可能一切商业活动都无法开展.
然而, 我们只是 "假设" 银行是可信的, 在 "信任" 与 "怀疑" 之间, 我们只是被迫选择了信任, 毕竟不信任银行, 商业活动无法开展, 经济也将停滞. 然而实际上, 并没有切实可行的措施来向所有人 "证明" 银行是可信的.
如果你认为这个问题是必要的, 有意义的, 那么能否找到一种解决方案, 可以让这个世界变得更可信, 让你不再需要 "被迫相信" 某个陌生人, 而是提供一种 "证明", 足以确保与你交易的某个陌生人是可信的? Don't Trust, Please Verify. 你不需要相信我, 你也不必相信我, 你只需要去验证我.
如果要解决这个问题, 所有人的身份应该是对等的, 每个人都可以平等, 自由地参与决策过程, 每个人都可以自由地进出 "议会", 这事实上是一种技术上的 democracy, 隐含的技术要素是: 网络必须是 permissonless 的, 谁都可以随时加入随时离开; 节点之间必须是对等的, 可以直接通讯; 无任何中间人, 无任何中心权威存在, 完全的点对点(peer to peer); 每个节点都有希望成为记账者.
因为网络无权限控制, 完全的开放, 透明, 民主, 所以参与的节点数目很可能非常众多, 节点作恶的可能性也很高. 那如何在这种 permissionless 的, 节点数目众多, 存在较大作恶可能的分布式网络环境中, 通过某种机制协调节点间的行为, 保证整个系统的一致性呢? 显然, 如前所述的一致性算法并不能做到这一点, 我们需要寻求新的解法.
另外, 去中心化可能是区块链领域最充满争议的词汇. 一些人认为去中心化是区块链的价值观和公有链的灵魂与存在前提, 应该尽可能地保证系统的去中心化程度; 而另一些人认为完全的去中心化过于理想, 不太可能实现, 应该结合实际场景, 在兼顾效率的情况下考虑弱中心化或多中心化. 这里抛开价值判断, 单纯从技术角度理性分析, 去中心化程度越高确实系统的安全性会越高, 所以在公有链的系统设计中确实应该尽可能地保证系统的去中心化程度. 不过, 结合 Vitalik Buterin 对于去中心化含义的诠释, 在追求去中心化的过程中, 我们不应该停留在单纯的表面上看起来的去中心化, 而应该综合考虑去中心化的各个维度, 结合实际情况, 做出必要的 trade-off.
PoW
对开放网络中的分布式一致性问题比较创新的解法当属比特币中的 Proof-of-work(PoW, 工作量证明)机制.
不得不提的 Bitcoin
2008 年 10 月 31 日, 中本聪发表了比特币白皮书《Bitcoin: A Peer-to-Peer Electronic Cash System》, 天才般地为此类问题提供了创造性的解决思路, 使得协调复杂网络环境中的成千上万节点成为可能. 事实上, 中本聪并不是为了解决这个技术问题而发表了比特币白皮书. 相反, 中本聪想象的更加宏大, 他创造性地发明了比特币这种完全点对点的电子现金系统, 以消除传统支付中需要依赖的可信第三方中间人, 而在实现的过程中恰好依赖并解决了开放网络中众多节点间的一致性问题. 也可以说, 比特币所解决的最核心问题是点对点网络中电子货币的双花问题. 然而, 比特币的实现机制绝不仅仅是分布式网络技术问题, 还结合了密码学, 经济学, 博弈论等思想, 并以一种非确定性的概率方式实现了节点间的一致性. 因此, 单纯地称为算法已不太能准确表达其含义, 可能叫作共识机制 (consensus mechanism) 更为恰当, 因为其实现的确依赖了一整套的完整策略与制度. 这里我们不过多阐述比特币的思想意义与实现细节, 而仅聚焦在其共识机制的实现上.
比特币实际上是电子签名链, 币的 owner 可以通过对前一个交易的哈希值和下一个 owner 的公钥进行签名, 并将签名添加到币的末尾, 从而实现转账. 接受者通过校验签名来验证币的 owner 构成的链. 然而, 问题是币的接受者没有办法确保币的 owner 没有进行双花(double-spend), 即有可能某个币的 owner 将同一个币先后转给了两个人. 因此我们需要一种机制来让接收者确保币的前一个 owner 并没有在此之前将币转给其他人, 为了确保这一点, 唯一的办法就是让所有人知晓所有的交易. 而在无可信第三方的情况下, 想实现这一点, 所有的交易必须广播给所有人. 因此我们需要一个系统, 其中的所有参与者对他们接收币的顺序达成一致, 形成唯一的顺序记录历史. 不难发现, 这其实就是分布式一致性问题.
而比特币提供的方案就是需要一个由所有节点组成的时间戳服务器(timestamp server), 时间戳服务器可以对交易区块的哈希加盖时间戳, 并将该哈希广播出去. 每一个时间戳都在其哈希中包含了前一个时间戳, 从而形成一条链, 而每一个新的时间戳都是对其之前所有时间戳的确保与强化. 为了在点对点的网络中实现分布式的时间戳服务器, 比特币采用了工作量证明机制(proof-of-work,PoW).PoW 涉及在做哈希运算时, 需要寻找某个值, 使得总体哈希值的开头前几位都为零, 而所需要的平均工作量随着零位数目的增多而指数增加. 另外, 该哈希没有任何规律, 为了保证开头前几位为零, 只能通过暴力的方法不断地随机试错. 一旦消耗了足够的 CPU 的算力, 找到了符合条件的哈希值, 则该区块就无法变更, 除非再耗费 CPU 重做一遍.
另外, PoW 也解决了大多数决策问题. 在比特币中, 最长的那条链就代表了大多数的决策. 因为如果诚实的节点控制了大部分的算力, 则诚实的链就会快速增长并超过其他链. 如果想篡改某个过去的区块, 攻击者必须重做相应的区块和其后面所有区块的 PoW 任务, 然后追赶并赶超诚实的节点. 这种难度是非常巨大的, 从数学上不难证明, 随着后续节点数目的增多, 较慢的攻击者想追赶上来的概率指数下降, 一般认为经过 6 个区块之后, 想追赶上来几乎是不可能的. 另外, PoW 任务的难度并不是固定的, 而是用移动平均的方法动态调整的, 这主要是考虑到硬件运算速率的提高和挖矿人数的增减变化, 算的快就加大难度, 算的慢就减小难度, 通过动态调节难度使得比特币的出块时间大致稳定在 10 分钟左右.
整个网络的运行过程如下:
新交易广播到所有节点.
每个节点都将收到的交易打包到一个区块内.
每个节点都为该区块不断尝试改变 nonce, 做 PoW 任务, 以使得该区块的哈希符合指定条件.
一旦某个节点完成了 PoW 任务, 则它将该区块广播给其他所有节点.
其他节点收到该区块后, 验证区块内交易的有效性, 验证通过则接受该区块.
节点如何表达自己接受了该区块呢? 那就在添加下一个区块的时候, 将该已接受区块的哈希值作为下一个区块的前一个哈希值(previous hash).
比特币交易过程( https://www.giottus.com/Bitcoin )
关于交易, 挖矿等细节, 这里不过多阐述, 有兴趣的同学可以参考笔者之前的入门介绍文章( https://www.atatech.org/articles/126343 ). 简而言之, 在比特币中总是以最长链的信息为准, 若某个节点发现了比自己更长的链会自动切换到最长的链工作.
我们忍不住要问, 既然 PoW 成本如此之高, 那如何激励大家贡献算力, 成为节点, 以保证整个比特币网络的安全呢? 比特币中提供了两种激励策略:
挖出某个区块的节点会得到一定量的比特币, 这其实也是比特币唯一的发行机制(一级市场), 所有的比特币都只能通过挖矿的形式被挖出然后进入流通领域;
矿工处理交易信息可以得到一定量的手续费, 这其实是存量比特币的流通(二级市场), 而当比特币的 2100 万枚被完全挖出后, 激励策略就只能依靠手续费这种方式了.
这些激励策略也隐含地鼓励了节点保持诚实, 若某个贪婪的攻击者真的拥有了过半的 CPU 算力, 他不得不做出选择: 到底是篡改交易记录, 把他已经花出去的比特币再转回来呢? 还是老老实实地挖矿赚钱新币和手续费呢? 很可能, 老老实实地挖矿是更有利的, 毕竟能赚到的币比其他所有节点加起来都要多; 而破坏比特币体系也将会破坏自身财富的有效性, 毕竟若比特币不再可靠, 其价值也会迅速崩溃. 这里多提一点, 攻击者并不像一般人想象的那样可以为所欲为, 任意篡改或伪造交易记录, 他能做的只可能是将其最近花出去的比特币偷回来.
PoW 为什么有效?
比特币在没有任何组织或团体维护的情况下, 仅仅依靠社区志愿者自发维护, 稳定运行了 10 年之久, 期间从未发生过重大问题, 这不能不说是个奇迹, 也足以证明了比特币背后共识机制的有效性. 我们忍不住要问, 为什么比特币能够做到? 为什么比特币背后的共识机制能够如此有效? bitnodes 数据显示目前比特币节点数目超过 1 万(比特币节点类型较多, 不同口径数量可能不一致, 这里仅考虑全节点). 为什么比特币能够在 permissionless 的网络环境中, 协调上万的节点保持一致性?
笔者粗浅的认为, 可能有以下几个原因:
有效的激励策略: 通过激励策略有效地激励了更多节点参与到比特币的点对点网络中, 节点越多比特币网络越安全.
PoW: 挖矿出块需要消耗 CPU 算力, 人为地制造障碍, 增加成本, 提高了攻击者的作恶成本.
博弈论思想: 激励策略也考虑了博弈平衡, 理性节点保持诚实的收益更大.
通讯效率: 比特币节点间的通讯效率并不低效, 大家可能注意到其中也涉及到了交易和区块的广播, 不过这种广播并非是两两广播, 而是由某个节点 (发生交易或算出 PoW 的节点) 将信息广播到其他所有节点. 另外, 交易广播并不要求触达所有节点, 只要有许多节点接受, 不久之后就会被打包. 2014 年也有 Miller 等人 (Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin) 严格证明, 消息复杂度并不随网络大小而增大, 而是一个常数. 另外, 区块广播也容许消息丢失, 若某个节点未收到某个区块, 则当它接收到下个区块时, 会意识到自己遗漏了上个区块, 而主动向其他节点请求该区块.
概率性的一致性: 相比其他一致性算法, 比特币的共识机制最特别的是不再追求确定性的一致性, 而是追求概率性的一致性. 当某个区块刚被挖出的时候, 其包含的交易信息并非被所有节点最终确认, 其包含的数据并非是最终一致性的结果, 还是有可能被攻击者篡改的; 但是随着后续节点数目的增多, 这种被篡改的可能性指数下降, 最终一致性的概率显著增大; 一旦后续节点超过 6 个(也就是经过约 60 分钟), 这种一致性就可以被认为是确定的, 最终的.
显然, 比特币的共识机制不再拘泥于分布式算法层面, 而是包含了更多经济学, 博弈论, 概率论等思想, 因此可能叫作共识机制更为恰当. 不过, 我们仍然可以将比特币的 PoW 共识机制放到一致性问题的框架内来思考, 从 FLP 和 CAP 的角度来看:
比特币最大程度地考虑了故障容错和网络分区容错, 这也是对网络 openness 的必要要求, 因为开放网络环境极其复杂, 谁都可以随时进出, 节点遍布全球各地, 机器故障, 网络分化, 系统攻击随时可能发生, 容错是必须需要考虑应对的. 而利用 PoW 机制, 比特币不仅做到了故障容错, 而且结合密码学非对称加密技术, 也可以做到拜占庭容错, 抵御恶意篡改与攻击.
比特币尽可能地保证了 liveness 和 availability, 比特币的出块时间总是在 10 分钟左右, 这也就意味着系统总可以在 10 分钟内达成一致; 比特币网络十年来不曾瘫痪, 从这个角度来讲确实将可用性做到了极致. 然而, 我们必须指出, 比特币的可用性与我们通常理解的互联网领域的可用性是有很大差异的. 互联网领域的系统可用性, 不仅要求系统稳定运行不宕机, 还对服务体验如响应时间有明确要求. 如果你用支付宝转账, 不是随时可转, 3 秒到账, 而是告诉你系统繁忙, 需要等待 10 分钟, 甚至 30 分钟, 这显然会被认为服务不可用. 然而, 这一现象在比特币中一直在发生, 比特币每 10 分钟一个区块, 而区块大小只有 1M, 装不下太多交易, 若同一时间交易过多, 只能一直等待, 直到能被下一个区块打包进去, 所以经常可能需要等待 20 分钟, 30 分钟, 甚至更久. 从这一角度对比来看, 其实比特币网络放宽了对响应时间的要求, 做到了比较基本的可用性: 读的可用性极高, 而写的可用性很低.
比特币对于 safety 和 consistency, 不再追求确定性, 而是采用了概率性的保障, 基本可以认为保证了最终安全性和最终一致性, 只不过这里的 "最终" 依然是有时间条件的, 基于概率的. 比如, 如果我刚刚给你转账了一个比特币, 没人敢说这个结果是确定的, 最终的, 但是随着时间的推移, 不断有新的区块被挖出, 我转账的交易信息也会被更多的节点确认, 被更多的后续区块强化, 这一结果确定性的概率不断增大, 一旦过了足够的时间(如 1 个小时), 我们从概率角度可以认为结果被篡改的可能性极低, 系统达成最终一致性的概率极高, 从实践上就可以认为系统保证了最终的一致性.
综合来看, 不难看出, 比特币的 PoW 共识机制在 FLP 和 CAP 的限制下, 做到了比较好的折中权衡, 在实践中确实提供了开放复杂网络中分布式一致性问题的可行解法, 比特币近十年来的稳定可靠运行也有力地证明了这一点.
另外, 比特币的 PoW 算法也被 Miller 等人 ( :Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin) 严谨地分析并证明:
比特币网络可以看作是由近似无穷节点组成的, 每个节点贡献一小部分算力, 并且相应地每个节点都有较小概率可以创造区块.
PoW 算法依赖于同步网络模型. 在该模型中, 若网络延迟为 0, 则算法可以容忍 50% 错误; 而以目前真实观测的网络延迟来看, 比特币可以容忍 49.5% 的错误; 若网络延迟等于区块时间(即 10 分钟), 则只能容忍 33% 的错误; 若网络延迟接近无穷, 则算法的容错也趋近于 0.
比特币 PoW 算法具有扩展性 (scalable), 这是因为共识时间和消息复杂度都与网络大小(网络中的节点数目) 无关, 而只与错误节点的相应算力有关, 可以认为是一个无量纲常数.
可见, PoW 算法不仅在实践中可靠, 在理论上也能经受考验. PoW 算法采用了同步模型与随机概率来规避 FLP 的确定性异步模型不可能定理. 而 PoW 独立于网络大小的可扩展性, 与 PBFT 算法 O(n2)复杂度相比优势巨大: 节点越多, 系统效率并未降低, 而系统却更安全.
PoW 到底是什么?
我们忍不住要问, PoW 机制到底有何神奇之处呢?
其实, 大家可能也意识到了, PoW 的思想并不高深, 事实上也并非是中本聪首创. 早在 1993 年这一思想就被提出用于对抗垃圾邮件 (Pricing via Processing or Combatting Junk Mail), 但直到中本聪创造比特币之前, 这一思想都尚未得到广泛应用. PoW 思想的精髓就在于故意制造障碍, 增加参与者的成本, 以尽量降低参与者的恶意企图. 比如要求请求者做些额外的工作以检测 DDoS 攻击, 垃圾邮件等, 也比如最常见的登录网站需要输入验证码, 也是为了增加登录成本, 防止网站被攻击. 这类任务最核心的特征是非对称: 对于服务请求者来说, 完成任务必须有一定难度; 而对服务提供者来说, 验证任务必须很简单快速. 对于比特币 PoW 而言, 显然符合非对称性: 不断试错, 寻找使哈希符合条件的 nonce(随机数) 需要消耗大量算力, 而验证寻找到的 nonce 是否符合条件只需要做一次简单的哈希运算验证即可.
比特币的 PoW 本质上是 one-CPU-one-vote, 一个 CPU 投一票. 为什么选择 CPU, 而不是 IP 地址呢? 这仍然是基于任务难度考虑, 若是 one-IP-one-vote, 则系统可以被拥有大量 IP 地址的人 (如 ip 供应商) 轻易控制. 相对而言, 至少在当时 (尚未出现 ASIC 和 FPGA)CPU 仍然是比较昂贵的硬件, 想拥有大量的算力(CPU + 电力) 并不容易. 当然, 这其实也隐含地为比特币的价值提供了现实锚定: 虚拟的货币体系通过算力找到了现实物理世界的价值锚定, 虽然在很多人看来这种算力的消耗是毫无意义, 浪费能源的.
也有很多人提出如何降低比特币的挖矿成本, 当然这种思考尝试有其积极意义, 这种工作量证明的成本需要适宜: 难度过大, 成本过高确实浪费能源较多, 不过比特币网络的安全性也得到了提高; 难度过小, 成本过低则会起不到防攻击的目的, 进而也会降低比特币网络的安全性. 这其实是一个需要做 tradeoff 的问题, 也是一个偏主观的价值判断, 取决于大众对比特币的认识和定位. 价值判断总是充满了主观偏见, 目前对于比特币的争论如此之大, 其实也正是因为社会大众尚未达成共识, 尚未构建出对于比特币未来共同一致的想象.
简言之, 比特币的 PoW 是一整套的机制, 包含了技术上的权衡, 经济和博弈的考量, 这一整套的策略和机制共同保障了比特币网络的安全可靠.
PoW 机制的局限性
凡事没有完美, PoW 机制也不可例外地存在局限, 其实从大家对比特币的诸多批评也可见一二, 通常地大家认为 PoW 机制存在以下局限性:
成本过高, 浪费能源: 大家对比特币浪费能源的批评声不绝于耳, digiconomist 数据显示, 比特币的全年电力消耗基本与新西兰相当, 也相当于澳大利亚用电量的 1/5; 而每笔比特币转账交易的成本是每 10 万笔 visa 转账交易的 3 倍. 虽然有时候这种对比有失公允(比特币交易即清算, 而 visa 除交易成本之外还有额外的清算成本), 也有不少人并不以为然. 前文也提到这其实也是一种主观价值判断, 但这毕竟是一种声音, 有时候也是切实的痛点, 比如恐怕没人愿意用比特币买杯咖啡, 毕竟手续费可能会比咖啡还贵. 而罪魁祸首当然是 PoW 机制所需要的 CPU 算力消耗, 因此不断有人尝试改进, 甚至提出新的解决思路.
效率低下: 大家习惯了互联网的便捷, 习惯了秒级到账和百万级别的 TPS, 对于比特币交易动辄需要等待几十分钟, 每秒钟仅能支持 7 笔交易, 显然不太满意. 虽然这种对比也并不公正, 毕竟银行系统后台只有几个机房, 最多百台机器, 并且交易只进入到了其中某台机器, 事后的清算环节才保证了最终一致性; 而比特币无任何单点, 协调的是上万台机器, 并且交易即清算. 不过这种效率的低下也确实是事实, 也不断有人尝试改进, 如把比特币每个区块的 size limit 调大, 让其每个区块能打包更多的交易, bitcoin cash 就是这么干的; 再如把比特币的出块时间改小, 让其更快出块, litecoin 就是这么干的. 但即便如此, PoW 为了保证网络安全性而要求的巨大的工作量证明成本, 也注定了网络的效率很难有质的提升.
中心化风险: 随着 ASIC 和 FPGA 等特制挖矿芯片的出现, 普通个人 PC 想挖出比特币几乎是天方夜谭. 挖矿越来越集中到有实力研发芯片的巨头企业上, 而矿池 (为了平滑收益大量节点组成联盟共同挖矿, 平分收益) 的出现也加剧了这一趋势. 另外, 对比特币 block size limit 的调大, 也会导致运行比特币全节点需要庞大的存储空间, 以至于无法在普通 PC 上运行, 而只能运行在特制的大型计算机上. 这些中心化的倾向无疑都会损害比特币网络的安全性, 毕竟由全世界各个角落的普通 PC 构成的比特币网络的安全性远远高于由几个巨头公司直接或间接控制的比特币网络. 虽然这一问题的争议更大, 仁者见仁, 但仍然有很多人在尝试寻求新的解决思路.
PoS
在这些新的解决思路中, 无疑最引人注目的就是 Proof-of-stake(PoS, 权益证明), 同样面对开放复杂网络中的一致性问题, 提出了全新的解决方案.
基本思想
2011 年在 bitcointalk 论坛一个名为 QuantumMechanic 的用户率先提出了 proof-of-stake 的思想( https://bitcointalk.org/index.php?topic=27787.0 ), 而后不断发展完善, 得到越来越多人的信赖.
PoS 的基本思想大致如下:
所有节点不再同时竞争挖矿, 而是每次仅有 1 个节点做验证者: 在比特币网络中, 所有节点都需要做 PoW 任务, 也就是说都需要做复杂的哈希运算而消耗大量 CPU 算力, 而只有最先找到答案的节点才能获得奖励. 这种所有节点间的同时竞争挖矿无疑需要消耗大量资源, 那么是否可以每次只有一个节点工作呢? 如果可以, 那怎么选定这个幸运儿呢? PoS 中不再需要挖矿, 不再有 miner, 而是每次只需要选出一个节点作为 validator 去验证区块的有效性. 如果某个节点被选为 validator 来验证下一个区块, 它将验证该区块内的所有交易是否有效. 如果所有交易都验证有效, 则该节点对该区块进行签名, 并添加到区块链上. 作为回报, 该 validator 将会收到这些交易相关的交易费用. 显然, 在 PoS 中每次共识只有一个节点付出了劳动, 且该劳动非常轻松, 从而达到了节约资源的目的.
想成为 validator 必须提供保证金: 为了防止 validator 作恶, 想成为 validator 必须提前往指定账户存入代币作为保证金或抵押担保金, 一旦被发现作恶, 则保证金即会被罚没, 而诚实工作将会得到激励. 显然, 只要作恶带来的收益不超过保证金额度, 节点就会老老实实地保持诚实.
被选为 validator 并不是完全随机的, 而是被选定概率与提供的保证金金额成正比: 例如 Alice 提供 100 个币的保证金, 而 Bob 提供 500 个币的保证金, 则 Bob 被随机选为 validator 从而产出下一个区块的概率是 Alice 的 5 倍. 这其实就类似于股份制公司, 按照出资比例来划分发言权, 最终受益权等, 大股东出资多, 承担责任大, 相应的回报也大.
PoW 与 PoS 对比图()
不难发现, PoS 也是采用了经济和博弈的思想, 通过激励策略和惩罚机制来确保了网络的安全可靠.
PoS 为什么有效?
PoS 协议仍然符合传统的拜占庭容错算法研究的结论. 目前围绕 PoS 的研究可以分为两条主线: 一条围绕同步网络模型, 一条围绕部分异步网络模型. 而基于链的 PoS 算法几乎总是依赖于同步网络模型, 并且其有效性与安全性可以像 PoW 算法一样被严格证明( ).
另外, 从 CAP 的角度来看, 基于链的 PoS 算法与 PoW 算法类似, 也是尽可能地做到了容错性, 另外在可用性与一致性之间, 更多地保证了可用性.
如果说传统的一致性算法 (Paxos,Raft 和 PBFT) 实现的是确定性的最终性 (finality) 或一致性, 那么 PoS 与 PoW 类似, 转而寻求概率性的最终一致性. 从传统 CAP 的视角, 这其实是对一致性的弱化, 然而从实践可行性的视角来看, 也是一种全新的思维和突破.
而从 PoS 的设计策略来看, 也可以分为两大阵营( https://arxiv.org/pdf/1710.09437.pdf ):
一类是如前所述的 chain-based PoS, 主要是模仿 PoW 机制, 通过伪随机地把区块创造权分配给 stakeholders 来模拟挖矿过程, 典型代表如 PeerCoin,Blackcoin 等. 其安全性与有效性可以参考类比 pow 来看.
另一类是 BFT based PoS, 基于近 30 年来的 BFT 类一致性算法研究. 基于 BFT 算法来设计 PoS 的思想最初在 Tendermint 中提出, 以太坊 2.0 中的 Casper 也遵从了这一传统并做了一些修改完善. 这类 PoS 的安全性与有效性可以参考 BFT 类算法来看, 如可以从数学上证明, 只要协议参与者的 2/3 以上节点都诚实地遵照协议, 不管网络延迟有多大, 算法都能保证最终状态不会出现冲突区块. 不过此类算法也并不完美, 特别是针对 51% 攻击问题, 也尚未完全解决, 目前该领域仍然处于开放探索阶段.
PoS 的争论
PoS 的思想并不复杂, 而其中比较容易被诟病的恰恰就是这种与现实世界类似的按出资比例获取收益的制度. 大家对现实世界的马太效应已经非常警惕, 这种制度显然容易带来富者越富, 穷者越穷的结果: 拥有更多代币的人, 将会有更多机会成为 validator, 从而参与网络并获得更多收益.
然而, 对这一问题的看法争议很大, 很多人提出了完全不同的看法, 认为 PoS 相比 PoW 更公平, 更有助于对抗中心化趋势. 理由主要是: PoW 挖矿依赖现实世界的物理硬件和电力资源, 而这很容易带来规模经济 (Economies of scale) 优势. 购买 10000 台矿机的公司相比购买 1 台矿机的个人更有议价权, 甚至可以自主研发成本更低的矿机; 而拥有 10000 台矿机的矿场, 对电费的议价权也更高, 甚至可以搬迁到电费便宜的国家和地区的电站旁边, 甚至可以自建成本更低的电站. 由此带来的后果就是越庞大的组织的综合挖矿成本越低, 而这正是现实世界真实已经发生的事实. 相比之下, PoS 不需要依赖现实硬件, 不存在规模经济优势, 在不考虑价格操纵的情况下, 买 1 个币的价格和买 10000 个币的价格是线性增加的, 从这个角度理解, PoS 可能更公平, 更有助于去中心化.
对 PoS 的另一个担忧是其安全性, 毕竟 PoS 不再像 PoW 那样做复杂的 CPU 运算以证明自己. 在 PoW 中, 若想发动攻击, 需要控制 51% 的算力(近来也有研究发现只需 25% 算力即有可能攻击成功), 这也就意味着需要拥有大部分的矿机和算力资源. 而在 PoS 中, 若想控制整个体系, 需要拥有 51% 的代币. 究竟哪个更安全? 其实也不太好讲, 不过可以从现实世界的例子来看, 如果比特币算法切换为 PoS, 则控制比特币体系需要大约比特币市值的一半, 大概是 400~1600 亿美金(比特币价格区间 5000~20000 美金), 显然这一数字远远高于矿机成本, 想拥有这么大资金量发动攻击几乎是不可能的, 从这个角度来讲, PoS 可能更安全.
除此之外, PoS 因为部署成本很低 (对硬件要求很低), 在真实世界中会导致代币非常容易分叉, 从而产生一堆山寨币, 而 PoW 不存在这个问题. 因为 PoW 依赖硬件挖矿, 若想把比特币的某个参数改改, 这很容易; 但真想跑起来, 则需要大量算力的支持, 需要争取大量 miner 的支持, 比如 bitcoin cash 从 bitcoin 中分叉出来就历经波折. 而 PoS 完全没这个顾虑, 随便某个人都可以下载开源代码, 随意改下, 拉几个节点就可以声称自己创造了一种全新的代币, 比如从 EOS(代币名) 中可以轻易分叉出几十上百个山寨兄弟币, 每个都声称自己很独特. 这确实是事实, 不过也不太容易说孰好孰坏.
PoS 的改进优化
PoS 机制中最关键的当属下一个区块 validator 或 creator 的选择机制, 究竟谁来做这个幸运儿? 前文所说的根据账户资金按比例按概率选择其实是最简单的一种方式, 这种方式确实容易导致有钱人获得一劳永逸的收益, 从而损害网络中其他参与者的积极性. 目前有很多种思路来改善这一问题, 其中比较有意思的是 coin age-based 方法, 在选择 creator 的时候, 除了考虑资金量, 还会考虑 coin age(币龄). 所谓的 coin age 指的是币在某个账户上的停留时间, 比如 1 个币转入指定账户经过 10 天, 可以认为币龄是 10, 而每次币发生变动币龄都会从 0 开始重新计算. 通过这样, 可以限制大资金量节点频繁成为 creator, 比如可以设定币龄达到 30 才有机会成为 creator, 而成为 creator 之后币龄立即清零. 这其实是限制了大参与者的利益, 为其他中小参与者提供了更多的参与机会.
基于 PoS 改进的比较有名的方案当属 Delegated Proof-of-Stake(DPoS), 其中采用了代理人委托机制. 在 DPoS 中不再是所有节点都有可能成为 creator, 而是节点间相互投票, 只有得票最高的一些节点才可能参与区块创造过程. 具体如下:
代理人的职责包含保证自身节点持续运行, 收集交易信息并打包到区块中, 签名验证并广播区块, 解决网络中可能存在的一致性问题.
对于大多数 DPoS 链来说, 网络中的所有持币人 (token holders) 都可以向代理人投票, 且投票权与持币数量成正比. 用户也可以不直接投票, 而把投票权委托给其他人来代表他们投票.
投票是动态的, 可变的, 意味着某个代理人随时可能被选进来或选出去. 而一旦某个代理人被发现作恶或欺诈, 就将失去收入和名誉, 这就起到了激励代理人保持诚实, 保证网络安全的目的. 代理人可以将收到的区块奖励按比例分给向他投票的用户(这其实相当于贿选, 在有些方案中不被允许).
不像传统的 PoS, 代理人不再需要持有大量的代币, 而是必须相互竞争从持币者那里争取投票.
DPoS 限制了交易区块的验证者人数, 这相当于牺牲了一定程度的去中心化, 但却带来了效率的提升, 因为网络达成共识所需的工作量大幅降低.
DPoS 选举 validator/witness 过程()
不难发现, DPoS 通过引入投票机制, 尽可能地保证了节点的广泛参与; 而对 validator 数目的限制(一般是 21-101 个), 尽可能地提高了系统的运行效率. 虽然充满很大争议, DPoS 仍然不失为一种可行的解法, 越来越多的区块链系统也在尝试对其进行改进和探索.
在公有链中的应用
在公有链中, 众多项目都采用了 PoS 机制, 比较有名的有:
以太坊(Ethereum: https://www.ethereum.org/ ): 目前阶段以太坊仍然采用的是 PoW 挖矿机制, 不过作为以太坊的创始人和公有链领域的领军人物 Vitalik Buterin 对于 PoS 机制显然更为青睐, 也多次阐述过 PoS 的设计哲学( ), 以及 PoS 相比 PoW 的优势( ). 目前以太坊正在开发基于 PoS 的 Casper 协议( https://arxiv.org/pdf/1710.09437.pdf ), 预计将于今年下半年发布, 这种从 PoW 到 PoS 的转变也标志着以太坊进入 2.0 时代. 如下图所示, 在以太坊 2.0 phase0 阶段, 将会发布采用 Casper 协议的 PoS beacon chain, 作为 coordination layer( ).
以太坊 2.0 layers 和 phases(
EOS( https://eos.io/ ): 作为 DPoS 思想的提出者 Daniel Larimer 发起了 EOS 公有链项目, 其中众多节点会一起竞争, 期望成为拥有记账权的 21 个 Supernodes 中的其中一员. 这种类似现实世界议会制度的设计引起了非常大的争议, 而超级节点的竞选也可能蕴含着巨大的商业利益, 这些都已经超越了技术讨论的范畴, 在此不做过多讨论.
Proof of X?
其实, PoS 机制的兴起除了其本身具备的低成本, 高效率, 去中心化等特点之外, 还在于它打开了一扇新的大门 -- 基于博弈论机制来设计如何降低中心化风险的一系列技术, 如何预防中心化垄断巨头的形成, 以及在已有巨头的情况下如何防范它们损害网络( Proof of stake opens the door to a wider array of techniques that use game-theoretic mechanism design in order to better discourage centralized cartels from forming and, if they do form, from acting in ways that are harmful to the network).
而随着近年来区块链 (特别是公有链) 的蓬勃发展, 其他各种 Proof of 机制也层出不穷. 从这里面的诸多机制中都可以看到 PoS 思想的影子, 即如何从经济角度和博弈视角来设计制度尽可能地保证去中心化, 安全性与高效率. 下面对这些机制做简要说明:
Leased Proof of Stake: 持币量非常低的众多节点可以将代币出租给其他节点, 从而形成合力, 增加成为 validator 的几率; 而一旦选举胜出得到奖励, 则按比例分配手续费, 其实与矿池的思想比较类似.
Proof of Elapsed Time: 所有节点都必须等待一定的时间才能成为记账者, 而等待时间是完全随机的. 而要想保证公平, 核心的两个问题是: 如何保证等待时间确实是完全随机的? 如何保证某个节点真的等待了指定的时间? 目前的解法依赖于 Intel 的特殊 CPU 硬件 Intel SGX 系统, 目前通常也仅能应用在 permissioned 网络环境中, 如前所述的以太坊企业联盟 EEA 中.
Proof of Activity:PoA 同时结合了 PoW 和 PoS 的思想. 在 PoA 中, 起始过程与 PoW 类似, 仍然是 miners 间竞争解题挖矿, 只不过所挖的区块仅仅包含头信息和矿工地址. 而一旦区块被挖出, 则系统自动切换成 PoS 模式, 区块头信息指向一个随机的持币者(stakeholder), 由该持币者来验证该 pre-mined 区块.
Proof of Importance: 有感于 PoS 机制倾向于鼓励人持币而不是流通, 也容易导致富者越富的问题, PoI 在计算节点对系统的重要性上吸纳了更多的维度: 除了考虑币的数量, 币在账户上的停留时间之外, 还考虑了交易对手 (与其他账户的净交易越多分数越高) 以及最近 30 天交易数目和大小(交易越频繁, 数额越大分数越高).
Proof of Capacity: 也称作 Proof of Space, 思想与 PoW 类似, 只是不再以 CPU 算力为衡量标准, 而是以存储空间来衡量.
Proof of Burn: 矿工必须烧毁一定量的代币, 即将一定量的代币转入 eater address(黑洞地址, 只进不出, 即私钥未知的地址), 以此来证明自己. 本质上与 PoW 的思想接近, 只是工作量证明消耗了算力资源, 而 PoB 直接消耗了代币本身.
Proof of Weight:PoWeight 是在 PoS 考虑代币量的基础之上, 增加考虑了更多的权重因子. 比如 FileCoin(IPFS 分布式文件系统上的代币)考虑了你拥有的 IPFS 数据大小; 其他的一些权重因子也包含但不限于 Proof-of-Spacetime,Proof-of-Reputation 等.
一致性算法概览()
不难发现, 虽然这些 Proof-of 机制层出不穷, 不尽相同, 但其要解决的核心本质问题是相同的, 即: 让谁来成为能够记账的幸运儿? 这些 Proof-of 机制只不过是采取了各种不同的策略来制定游戏规则, 让各个节点尽可能公平地证明自己, 从中公平地选出幸运儿. 所有这些策略, 包括基于 CPU 算力, 持有代币数量, 存储空间大小, 随机等待时间, 销毁代币数量, 节点活跃度, 节点贡献度等, 都是在特定的场景下对于开放网络中一致性问题的探索.
一切关乎信任
从 PoW 到 PoS, 再到 Proof of "Everything you can think", 对于 permissionless 网络中的一致性问题一直在探索中."一致性" 的内涵也在发生变化, 从传统的如何防范网络与机器硬件的故障, 保证网络节点间的数据一致性, 到开放网络中, 如何防范网络中人的作恶, 保证网络中节点数据间的真实一致. 可以说是从硬件的可信, 迈进了 "人的可信", 公有链技术也被视为 "信任的机器". 不过显然, 人的可信问题过于复杂, 甚至也超越了单纯的技术范畴. 目前阶段所能做到的也远远未能保证 "人的可信", 更多的仍停留在人对于机器的信任, 人对于 "协议" 的信任. 不过可喜的是, 我们终于迈出了这一步, 开始直面这个棘手的问题, 探索创新性的解法.
信任的机器()
总结
这个世界充满了不确定性, 计算机科学也一样. 从计算机出现开始, 我们就不得不面对机器硬件的不确定性: 意外故障可能带来的问题. 从互联网兴起开始, 我们就不得不面对网络的不确定性: 通讯消息可能的延迟, 乱序, 丢失. 而应对不确定性问题最自然的解法就是冗余, 通过大量节点来实现系统整体的安全性, 避免单点故障, 增强容错能力和抵御攻击的能力. 正是基于此, 才带来了大型分布式网络的蓬勃发展, 而如何在不确定的网络和节点间寻找到某种确定性, 协调众多节点间的一致性, 正是分布式一致性算法需要解决的问题. 能够应对故障类错误的 CFT 算法包括最经典的 Paxos 算法和更简单的 Raft 算法, 可以在网络中正常节点超过一半的情况下保证算法的有效性. 这类算法通常应用在环境可信的封闭网络中, 协调几个到几十个节点间的一致性, 如公司内部的分布式存储, 分布式服务协议, 分布式消息系统等. 另外, 也可以应用于由少数机构组成的需要授权才能访问的联盟链网络中.
然而, 不确定的不止是网络与机器本身, 还有控制网络中各个节点的人的行为. 如何在可能存在捣乱者恶意篡改数据或攻击网络的情况下, 保证分布式网络的一致性, 正是拜占庭容错类算法 BFT 需要考虑的问题. BFT 类算法中最常见的就是 PBFT 算法, 可以在网络中正常节点超过 1/3 的情况下保证算法的有效性. 即便如此, PBFT 对于网络中恶意行为的应对能力仍然是有限的, 另外其性能也会随着网络中节点数目的增多而显著下降. 这些局限性也导致 PBFT 算法仅能用于环境较为可信的, 有权限控制的网络中, 协调几个到几十个节点间的一致性, 比如联盟链场景中.
而在无权限控制的 permissionless 开放网络中, 不确定性更加严峻, 特别是网络节点背后的人的行为的不确定性. 如何防止网络中的控制人之间通过腐败串通组成寡头, 从而控制网络中的过半节点, 达到控制, 损害, 攻击网络的目的, 即是开放网络需要考虑的问题. 从这一角度看, 开放网络中的一致性还隐含了安全性的前提: 即不仅要求节点间能够达成共识, 还要求该共识确实是由节点众多控制人真实表达而形成的. 而为了达到这种一致性与安全性, 不仅需要实现物理硬件节点在结构上的 decentralization, 还需要尽可能地保证节点背后实际控制人的 decentralization. 为了实现这一点, 需要保证任何人都可以随时部署运行网络协议而成为网络中的节点, 可以随时进出网络; 节点之间点对点通讯, 无任何中心化控制节点; 节点的角色是完全对等的, 按照规则有公平的可能性参与记账. 而如何协调开放网络中数量庞大的上万个节点间的行为, 保证网络的一致性与安全性, 即是公有链共识机制要解决的问题. 其中, 最典型的当属比特币首创的基于工作量证明的 PoW 共识机制, 以及随后兴起的基于权益证明的 PoS 共识机制. 这些共识机制不再局限于技术上的一致性本身, 而是更多地引入了经济学和博弈论的思想, 从经济和博弈的角度尽可能保证网络的一致性与安全性.
从传统的封闭分布式网络环境中的一致性, 到有权限控制的联盟链场景中的一致性, 再到无权限控制的公有链开放网络环境中的共识机制, 面对的问题越来越复杂, 应对的挑战也越来越严峻. 从单纯的技术视角来看, 其中对于 consensus 的研究是一脉相承的, 这些一致性算法或共识机制同样也都受到传统分布式一致性理论研究中 FLP impossibility 和 CAP theorem 的制约. Paxos,Raft 和 PBFT 都强调了 fault tolerance 与 safety/consistency, 而弱化了 liveness 与 availability. 而 PoW 与 PoS 则采用了全新的视角来考虑该问题, 尽可能地保证了 fault tolerance, 以及 liveness 与 availability, 放弃了对于安全性与一致性确定性的追求, 而仅仅以概率性的方式追求最终的 safety 与 consistency.
另外, 对于 consensus 的思考, 也在不断深入, 从单纯的节点间的数据一致性, 到强调节点背后的人之间的共识与认同; 从保证网络与硬件的可信, 到尽可能地确保组成网络的节点背后的人的可信. 虽然人与人之间的可信非常复杂, 也超越了单纯的技术范畴, 可喜的是我们已经走在路上, 而目前在该领域正在进行的创新性的积极探索, 也必将让世界变得更加可信.
注: 本文篇幅较长, 写作时间跨度较长, 本人水平也有限, 所参考资料可能有疏漏或个人理解偏差, 欢迎大家指正, 讨论, 交流, 建议, 后续将进行更新.
参考资料
- An Overview of Blockchain Technology: Architecture, Consensus, and Future Trends
- Comparative Analysis of Blockchain Consensus Algorithms
- https://draveness.me/consensus
- http://ug93tad.github.io/flpcap/
- http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf
- https://www.youtube.com/watch?v=M4RW6GAwryc
- https://bitcoin.org/bitcoin.pdf
- https://en.wikipedia.org/wiki/Proof-of-work_system
- https://bitnodes.earn.com/
- Data Consistency and Blockchain
- https://www.youtube.com/watch?v=M3EFi_POhps
- https://bitcointalk.org/index.php?topic=27787.0
- https://www.youtube.com/watch?v=Qfm26MX-Kdo
- https://www.giottus.com/Bitcoin
- https://en.bitcoinwiki.org/wiki/DPoS
- https://www.mycryptopedia.com/proof-of-importance/
- https://en.wikipedia.org/wiki/Proof-of-space
- https://en.bitcoin.it/wiki/Proof_of_burn
- https://en.wikipedia.org/wiki/Las_Vegas_algorithm
- https://arxiv.org/pdf/1710.09437.pdf
- https://arxiv.org/pdf/1607.01341.pdf
- https://en.bitcoinwiki.org/wiki/DPoS
来源: https://yq.aliyun.com/articles/702243