作者: 郑翊
目录
什么是共识机制
拜占庭将军问题
CAP 原理
定义
应用
拜占庭问题的常规解法
口头协议
书面协议
PBFT
比特币中对于拜占庭问题的解法
- PoW
- Bitcoin
- Ethereum
- PoS
- Peercoin PoS v1
- Blackcoin PoS v2
- Blackcoin & Qtum PoS v3
- Ethereum Casper
- Delegated Methods
- EOS DPOS
- NEO DBFT
非拜占庭问题下的解法
Paxos
Raft
总结
参考资料
什么是共识机制
区块链从本质上而言是一种分布式账本技术传统的账本, 通常会以数据库的形式, 集中存储在银行或公司的服务器节点上而在区块链的网络中, 每个节点都会保有一份完整的账本, 且所有节点的账本内容完全一致每个节点都可以根据自己本地的账本去查找交易, 也可以往账本中添加交易
这样就带来了一个问题, 如果所有节点同时一起写入账本数据, 那么肯定数据会不一致因此需要一种机制来保证区块链中的每一区块只能由一个节点来负责写入, 并且让所有其他节点一致认同这次写入如何选出写入账本数据的节点, 这就是共识机制
拜占庭将军问题
拜占庭将军问题 [1][2](Byzantine Generals Problem) 是对上述场景的一种建模拜占庭将军问题是一个共识问题: 首先由 Leslie Lamport 与另外两人在 1982 年提出, 被称为 The Byzantine Generals Problem 或者 Byzantine Failure 核心描述是军中可能有叛徒, 却要保证进攻一致, 由此引申到计算领域, 发展成了一种容错理论, 即拜占庭容错(BFT,Byzantine Fault Tolerance)
拜占庭将军问题可以描述如下:
拜占庭帝国想要进攻一个强大的敌人, 为此派出了 10 支军队去包围这个敌人这个敌人虽不比拜占庭帝国, 但也足以抵御 5 支常规拜占庭军队的同时袭击基于一些原因, 这 10 支军队不能集合在一起单点突破, 必须在分开的包围状态下同时攻击他们任一支军队单独进攻都毫无胜算, 除非有至少 6 支军队同时袭击才能攻下敌国他们分散在敌国的四周, 依靠通信兵相互通信来协商进攻意向及进攻时间困扰这些将军的问题是, 他们不确定他们中是否有叛徒, 叛徒可能擅自变更进攻意向或者进攻时间在这种状态下, 拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商, 从而赢取战斗? 这就是著名的拜占庭将军问题
解决问题的难点在于, 将军中可能出现叛徒, 叛徒可以通过选择性地发送消息, 从而达到混淆进攻决策的目的假设有 9 位将军投票, 其中 1 名叛徒 8 名忠诚的将军中出现了 4 人投进攻, 4 人投撤离的情况这时候叛徒可能故意给 4 名投进攻的将领送信表示投票进攻, 而给 4 名投撤离的将领送信表示投撤离这样一来在 4 名投进攻的将领看来, 投票结果是 5 人投进攻, 从而发起进攻; 而在 4 名投撤离的将军看来则是 5 人投撤离这样各支军队的一致协同就遭到了破坏
拜占庭将军问题对应到分布式系统中, 可以表述为分布式的节点间需要对某一个 message 达成共识 (只要过半数节点认同这个 message 即可) 节点之间可以交换信息, 但是由于恶意节点的存在, 恶意节点会发布错误的消息, 或是给不同的节点发送不同的消息在这样的场景下, 怎样设计一种机制去让节点能够达成共识的问题
拜占庭问题的传统解法
口头协议
首先明确口头协议的定义我们将满足以下三个条件的方式称为口头协议:
每个被发送的消息都能够被正确的投递
信息接收者知道是谁发送的消息
能够知道缺少的消息
Lamport 论证得出结论: 将军之间采用口头协议进行通信, 若叛徒数少于 1/3, 则拜占庭将军问题可解也就是说, 若叛徒数为 m, 当将军总数 n 至少为 3m+1 时, 问题可解本文中不再详细介绍通信机制和论证过程, 有兴趣的读者可以查阅文章 [1] 中口头协议一节和 [2] 中的 Early solutions 下的第一种
书面协议
在口头协议上加上一个条件, 使之成为书面协议
发送者对消息加上签名, 签名不可伪造, 一旦被篡改即可发现, 而叛徒的签名可被其他叛徒伪造;
任何人都可以验证签名的可靠性
可以论证, 在将军之间使用书面协议通信的基础上, 不管将军总数 n 和叛徒数量 m, 忠诚的将军总能达到一致书面协议的本质就是引入了签名系统, 这使得所有消息都可以追溯到底有谁认同了它这一优势, 大大节省了成本, 他化解了口头协议中 1/3 要求, 只要采用了书面协议, 忠诚的将军就可以达到一致即恶意的节点不超过半数, 分布式系统就能达成共识对推导细节感兴趣的读者可以同样参照[1][2]
PBFT
实用拜占庭容错协议 (PBFT,Practical Byzantine Fault Tolerance) 是 Miguel Castro (卡斯特罗)和 Barbara Liskov(利斯科夫)在 1999 年提出来的, 解决了原始拜占庭容错算法 (即上文中的口头协议) 效率不高的问题, 将算法复杂度由指数级降低到多项式级, 使得拜占庭容错算法在实际系统应用中变得可行
PBFT 算法的结论是 n>=3f+1 n 是系统中的总节点数, f 是允许出现故障的节点数换句话说, 如果这个系统允许出现 f 个故障, 那么这个系统必须包括 n 个节点, 才能解决故障这和上文口头协议的结论一样, 或者这么说, PBFT 是优化了口头协议机制的效率, 但是结论并未改变
PBFT 算法的步骤, 详见[1][3]
取一个副本作为主节点(图中 0), 其他的副本作为备份;
用户 (图中 C) 向主节点发送消息请求;
主节点通过广播将请求发送给其他节点(图中 123);
所有节点执行请求并将结果发回用户端;
用户端需要等待 f+1 个不同副本节点发回相同的结果, 即可作为整个操作的最终结果
CAP 原理
为了便于理解比特币中对于拜占庭问题的解法(PoWPoS 等), 先看一下著名的 CAP 原理[4], 对于共识算法的设计有指导意义 CAP 原理最早由 Eric Brewer 在 2000 年, ACM 组织的一个研讨会上提出猜想, 后来 Lynch 等人进行了证明该原理被认为是分布式系统领域的重要原理
定义
分布式计算系统不可能同时确保一致性 (Consistency) 可用性 (Availability) 和分区容忍性(Partition), 设计中往往需要弱化对某个特性的保证
数据一致性(Consistency): 如果系统对一个写操作返回成功, 那么之后的读请求都必须读到这个新数据; 如果返回失败, 那么所有读操作都不能读到这个数据, 对调用者而言数据具有强一致性(strong consistency) (又叫原子性 atomic 线性一致性 linearizable consistency)
服务可用性(Availability): 所有读写请求在一定时间内得到响应, 可终止不会一直等待
分区容错性(Partition-tolerance): 在网络分区的情况下, 被分隔的节点仍能正常对外服务
在某时刻如果满足 AP, 分隔的节点同时对外服务但不能相互通信, 将导致状态不一致, 即不能满足 C; 如果满足 CP, 网络分区的情况下为达成 C, 请求只能一直等待, 即不满足 A; 如果要满足 CA, 在一定时间内要达到节点状态一致, 要求不能出现网络分区, 则不能满足 PCAP 三者最多只能满足其中两个
分区容错性
这里重点讲一下对分区容错性的理解, 便于大家理解 CAPPartition 字面意思是网络分区, 即因网络因素将系统分隔为多个单独的部分, 有人可能会说, 网络分区的情况发生概率非常小啊, 是不是不用考虑 P, 保证 CA 就好要理解 P, 我们看回 CAP 证明中 P 的定义:
In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.
网络分区的情况符合该定义, 网络丢包的情况也符合以上定义, 另外节点宕机, 其他节点发往宕机节点的包也将丢失, 这种情况同样符合定义现实情况下我们面对的是一个不可靠的网络有一定概率宕机的设备, 这两个因素都会导致 Partition, 因而分布式系统实现中 P 是一个必须项, 而不是可选项
弱化一致性
对结果一致性不敏感的应用, 可以允许在新版本上线后过一段时间才更新成功, 期间不保证一致性
例如网站的 CSSJS 等, 通常都设置了一定的缓存时间超过缓存时间才会重新去服务器获取最新的版本
弱化可用性
对结果一致性很敏感的应用, 特别是交易相关的应用场景, 通常会用到锁事务等概念
例如银行取款机, 当系统故障时候会拒绝服务 PaxosRaft 等算法, 主要处理这种情况
弱化分区容忍性
现实中, 网络分区出现概率减小, 但较难避免某些关系型数据库 ZooKeeper 即为此设计一旦有部分节点网络通信出现故障, 则暂停这部分节点, 不再提供对外服务
比特币中对于拜占庭问题的解法
拜占庭问题之所以难解, 在于任何时候系统中都可能存在多个提案(因为提案成本很低), 并且要完成最终的一致性确认过程十分困难, 容易受干扰但是一旦确认, 即为最终确认
比特币的区块链网络在设计时提出了创新的 PoW(Proof of Work) 算法思路一个是限制一段时间内整个网络中出现提案的个数(增加提案成本), 另外一个是放宽对一致性确认的需求, 约定好大家都确认并沿着已知最长的链进行拓宽系统的最终确认是概率意义上的存在这样, 即便有人试图恶意破坏, 也会付出很大的经济代价(付出超过系统一半的算力)
或者通俗来说, 比特币的 PoW 共识弱化了拜占庭问题中对于一致性的要求, 在同一时刻访问不同比特币的节点, 所得到的共识并不一致, 且一致性还会随着时间改变 (分叉的情况) 但是可用性和分支容错性都得到了提升
后来的各种 PoX 系列算法, 也都是沿着这个思路进行改进, 采用经济上的惩罚来制约破坏者
PoW
Bitcoin
Bitcoin 的共识协议, 可以参照 Mastering Bitcoin[5]中有详细的描述其步骤如下:
本地维持所有未被确认的交易, 称之为交易池, 每新接收到一笔交易就加入到交易池中
本地维持整个区块链, 每新接收到一个 block, 则加入到区块链中, 并根据最长链原则确定主链
当新接收到的 block 加入到区块链的时候, 开始挖矿
构建一个空的 block, 选取交易池中费率最高的交易填充 block, 费率的定义为 交易费 / 交易大小
根据主链, 填充 block header 中的 previous block hash 字段
根据 block 中所有交易的交易费和挖矿奖励, 构建 coin base 交易挖矿奖励大约 每四年 (或准确说是每 210,000 个块) 减少一半, 开始时为 2009 年 1 月每个区块奖励 50 个比特币
修改 block header 中的 nonce, timestamp, merkle root(通过修改 coinbase data), 让 hash(block header) <difficulty, 其中 difficulty 是根据近期 block 的产出时间来计算的, 保证每个 block 产出的时间大致是 10 分钟左右
由于满足 hash 要求的 block head 只能通过大量遍历获得, 所以挖矿的过程需要消耗大量的算力, 直到得到合适的字段取值为止
发布得到的 block, 其他节点验证通过后加入区块链中
2010 年左右, 挖矿还是一个很有前途的行业但是现在, 建议还是不要考虑了, 因为从概率上说, 由于当前参与挖矿的计算力实在过于庞大(已经超出了大部分的超算中心), 获得比特币的收益已经眼看要 cover 不住电费了
从普通的 CPU(2009 年)到后来的 GPU(2010 年) 和 FPGA(2011 年末)到后来的 ASIC 矿机 (2013 年初, 目前单片算力已达每秒数百亿次 Hash 计算) 再到现在众多矿机联合组成矿池短短数年间, 比特币矿机的技术走完了过去几十年的集成电路技术进化历程, 并且还颇有创新之处
Ethereum
由于 ASIC 矿机被大量运用在比特币的挖矿过程中, 所以如果出现其他基于 hash 运算达到共识的区块链, 则很容易受到原本服务于比特币的 ASIC 矿机攻击因此 Ethereum 在设计其 PoW 共识算法的时候, 就意识到应该让算法在普通的个人电脑上运行更有优势, 从而避免被 ASIC 进行攻击
Ethash 设计时就明确两大目标:
抵御矿机性能(ASIC-resistance), 团队希望 CPU 也能参与挖矿获得收益
轻客户端可快速验证(Light client verifiability)
基于以上两个目标, 开发团队最后倒腾出来的 Ethash 挖矿时基本与 CPU 性能无关, 却和内存大小和内存带宽成正相关不过在实现上还是借鉴了 SHA3 的设计思路, 但是使用的 SHA3_256 ,SHA3_512 与标准实现很不同
Ethash 基本流程是这样的 [6]: 对于每一个块, 首先计算一个种子(seed), 该种子只和当前块的信息有关; 然后根据种子生成一个 32M 的随机数据集(Cache); 紧接着根据 Cache 生成一个 1GB 大小的数据集合(DAG),DAG 可以理解为一个完整的搜索空间, 挖矿的过程就是从 DAG 中随机选择元素(类似于比特币挖矿中查找合适 Nonce) 再进行哈希运算可以从 Cache 快速计算 DAG 指定位置的元素, 进而哈希验证此外还要求对 Cache 和 DAG 进行周期性更新, 每 1000 个块更新一次, 并且规定 DAG 的大小随着时间推移线性增长, 从 1G 开始, 每年大约增长 7G 左右
PoS
可以看到, PoW 会存在两点问题:
费电无论是比特币的共识还是以太坊的 Ethash, 挖矿的过程中都带来了巨大的电力消耗网上有报道称, 现在每挖一个比特币的成本在 6000-8000 美元之间; 比特币现在每天消耗的电量相当于一个小国家的耗电量
矿池的优势随着算力的不断提升, 单个矿机挖出一枚币的概率降到了极低因此, 很多矿机的拥有者联合在了一起形成矿池矿池中的矿机并行地分担计算量, 当挖出新的 block 获得奖励后, 再根据计算量的贡献分享奖励矿池的出现导致了比特币的中心化从下图中可以看出, 65% 的算力集中在了 5 大矿池的手里如果这些矿池对比特币网络进行攻击, 则网络会面临较大的风险
因此, 业内提出了 PoS(Proof of Stake)[7]的思想:
把生产 block 的工作交给拥有更多 token 的人, 拥有的越多, 作为 block producer 的概率越高
生产 block 的过程中得到 token 奖励, 可以理解为持有 token 带来的利息
拥有大量 token 的人如果攻击网络, 则会造成 token 价格的下降, 对这些人是不利的, 所以这些 block producer 攻击网络的意愿较低
生产 block 只需证明自己持有的 token 即可, 不需要消耗多少算力, 节约能源
围绕以上 PoS 的思想, 各个区块链系统有不同的 PoS 实现, 以下将依次介绍
Peercoin PoS v1
最初的一版 PoS 由 Peercoin 设计实现 [8] 其中, 用户要产出 block 必须满足以下条件
hash(stake_modifier, current_time, UTXO) < coin(UTXO) * age(UTXO) * difficulty
具体解释如下
用户在每一秒时间(current_time), 遍历自己所有的 UTXO, 代入上述公式中, 看是否能满足不等式条件; 如果满足, 就把相应的 UTXO 记录在 block 中, 并发布 block(见 4)
stake_modifier 是对前一个 block 中部分字段 hash 后的值, 加入这一项是为了防止用户提前预知自己何时有权挖矿
difficulty 会根据近期的 block 产出时间动态调整, 保证 block 产出时间间隔稳定
由于每秒只需要完成和自己 UTXO 数量相等的 hash 计算, 所以需要的算力较低
从不等式可以看出, 持有的 UTXO 越多 UTXO 中 token 数额越大(coin(UTXO))UTXO 持有时间越长(age(UTXO), 或称之为币龄), 不等式越容易成立, 越容易进行挖矿
生成 block 的奖励设置为了 coin(UTXO) * age(UTXO), 即 UTXO 数额越大持有时间越长, 奖励越高
为了将符合条件的 UTXO 记录进 block, 并且兼容原本的 PoW 模式, Peercoin 设计了 coinstake 的逻辑
保留原本第一个 transaction 为 coinbase, 但要求输入数量必须等于 1, 且输入的 prevout 字段必须置空值, 输出数量必须大于等于 1
令第二个 transaction 为 coinstake, 要求输入数量大于等于 1, 且第一个输入为满足条件的 UTXO, 输出数量大于等于 2, 且第一个输出必须置空值, 第二个输出为 block 奖励
该版本的 PoS 面临着如下的问题
因为构造新的 block 没有算力成本, 所以当区块链出现 fork 的时候, 用户有可能会倾向于同时在多个 branch 一起挖矿来获得潜在更高的收益, 这样制造了大量的分支, 破坏了一致性这个问题多次被以太坊团队提及, 并称之为 nothing at stake 问题[12], 以太坊在其 PoS 方案 CASPER 中致力于解决该问题, 下文 Ethereum Casper 一节中将详细描述
出现了攒币龄的现象, 即关闭节点, 直到 age(UTXO)足够大的时候再启动节点挖矿, 从而节省电力, 这样引起了在线节点数太少系统脆弱的问题
可以攒够足够的币龄后, 保证自己有足够的 UTXO 能够连续生产 block, 从而发动 double-spend 攻击
Blackcoin PoS v2
Blackcoin 在 Peercoin 的基础上进行了修改, 从而缓解了上述问题, 主要改动如下, 全部改动参见[9]
去掉了不等式公式右边的 age(UTXO), 从而解决了问题 3 中攒币龄然后进行 double-spend 的现象; 但是 block 奖励还是使用了币龄, 因此并不能完全解决问题 2 中节点关闭的现象
优化了 stake_modifier 的计算逻辑, 让用户提前预知自己有权挖矿时间的难度更大了
Blackcoin & Qtum PoS v3
Blackcoin 又在 v2 的基础上改进得到了 v3[10], 然后 Qtum 对 v3 又进行了修改并应用 [11] 主要改动点描述如下, 全部改动请参照[10][11]
把 block 奖励改成固定值, 解决了问题 2
规定 500 个 block 之前的 UTXO 才能参与挖矿, 缓解挖矿过于频繁带来的潜在风险
Ethereum Casper
Ethereum 在其白皮书中承诺最终将从 PoW 过渡到 PoC, 并且其 PoC 的方案, 名叫 CASPER[12], 正在积极开发中 CASPER 一个主要改进点是其将致力于解决 nothing at stake 问题, 主要的方式是惩罚在多个分支上同时进行挖矿的用户, 甚至让这些用户失去用于 stake 的那部分 token 其方案描述如下:
用户质押自己的一部分 token 进入智能合约, 然后开始挖矿
如果成功挖到 block 并被网络接受, 则用户获得奖励
如果用户被系统发现试图进行 nothing at stake 行为, 则其质押的 token 将被销毁
但对于 nothing at stake 问题, 业界一直是有争议的 [13] 主要观点就是执行这种攻击的代价太高, 而且对攻击者是毫无收益的这和 PoW 的前提假设一样, 拥有大量矿机的人可以对比特币发动 double-spend 等攻击, 但是这样的攻击对其并无收益, 且会损失大量算力, 所以这种攻击并没有大量发生
Delegated Methods
以上的 PoW 和 PoS 的挖矿过程, 是全网所有节点共同参与的, 每一时刻都有成千上万个节点同时去争取产出下一个 block, 因此会时有发生区块链分叉 (fork) 的问题即同一时刻, 两个节点同时产出了 next block, 但由于网络时延的问题, block 产出的时候两个节点并不知道有其他节点已经产出了另一个 block, 因此这两个 block 都被发布到了网络中 [5] 中对分叉的问题有详细的描述, 可以进行参考
正是由于分叉的存在, block 的产出时间间隔不能太短各区块链通过动态调整的挖矿难度, 将 block 时间间隔稳定在自己期望的水平例如最初比特币的间隔是 10 分钟, 后续的以太坊是 15 秒左右如果时间间隔进一步调短(即降低挖矿难度), 分叉问题就会大量显现, 不利于共识的达成和系统的稳定
block 产出时间过长导致了两个问题:
交易确认所需的时间过长通常来说, 一笔交易进入区块链后, 都建议经过 6 个 block 之后才真正确认交易, 因为 6 个 block 之后想要再分叉并且追赶主链的难度已经超乎想象了因此, 在区块链上确认交易需要分钟级别的时间
TPS (Transactions Per Second) 受到制约 TPS 受到了 block generation time 和 max block size 的共同制约其中 max block size 的存在是为了防止 DOS 攻击等因素[14], 有一定的天花板, 因而缩减 block generation time 至关重要
为了缩短 block 产出时间, delegated 开头命名的系列方法被提了出来其基本思想就是, 选出少量的代表来负责生产 block 这样即使缩短 block 的时间间隔, 也不会有严重的分叉发生甚至可以使用 PBFT 这种没有分叉的方法来达成代表之间的一致共识
EOS DPOS
EOS 提出的 DPOS 方案[15], 其步骤简述如下
持有 token 的用户可以对候选的 block producer 进行投票; 虽然没有看到对投票过程的详细设计, 但是相关文章中提到了一种可选的方法, 即用户在生成交易的时候, 把自己的投票包含在交易中
得票最高的 n 个用户被选为代表, 在下一个周期中负责产出 block, 目前 n=21
打乱代表的顺序后, 各代表开始依次生产 block 每个代表都有自己固定的时间区间, 需要在自己的区间中完成 block 的生产发布目前这个区间是 3 秒, 即在正常情况下每 3 秒产出一个 block
每个代表在生产 block 的时候, 需要找当时唯一的最长链进行生产, 不能在其他分支上进行生产
EOS 论证了在这种机制下, 只要 n>=3f+1(n 是系统中的总节点数, f 是允许出现的恶意节点数), 则共识能够达成
通过上述方法, EOS 保证了较短的 block 生产时间(3 秒), 且因为给每个生产者设置了固定的时间区间, 则 block 的产出不会因为某个候选节点的延迟而延迟 EOS 的文章中详细论述了各种节点异常情况下的共识达成, 有兴趣可以参考
NEO DBFT
NEO 的共识机制也是先选代表, 和 EOS 的不同之处在于, 代表之间是按照 PBFT 的方式达成共识的由于上文中已经描述了 PBFT 算法, 所以这里就不再解释 DBFT 的原理了, 有兴趣的读者可以参照[16]
非拜占庭问题下的解法
以上的算法都是在拜占庭问题建模下的共识算法, 以下将介绍非拜占庭问题在拜占庭问题中, 我们认为每个节点是可以进行恶意的攻击的, 即节点在传递消息的过程中, 可以给不同节点传递不同的消息, 从而破坏共识这种场景是符合开放的网络环境的
而在较为封闭的网络环境中, 比如我们常说的私有链, 或是公司内部的一些分布式系统中, 每个节点是可信的, 不会存在恶意的攻击者节点在传递消息的过程中, 只会因为网络不稳定或是节点挂掉出现漏传重传消息的情形因此, 有一类算法是用于解决在这种场景下的共识问题, 因此我们称这种场景建模为非拜占庭问题
Paxos
早在 1990 年, Leslie Lamport(即 LaTeX 中的 "La", 微软研究院科学家, 获得 2013 年图灵奖)向 ACM Transactions on Computer Systems (TOCS)提交了关于 Paxos 算法的论文 The Part-Time Parliament 几位审阅人表示, 虽然论文没什么特别的用处, 但还是有点意思, 只是要把 Paxos 相关的故事背景全部删掉 Leslie Lamport 心高气傲, 觉得审阅人没有丝毫的幽默感, 于是撤回文章不再发表直到 1998 年, 用户开始支持 Paxos,Leslie Lamport 重新发表文章, 但相比 1990 年的版本, 文章没有太大的修改, 所以还是不好理解于是在 2001 年, 为了通俗性, Leslie Lamport 简化文章发表了 Paxos Made Simple, 这次文中没有一个公式
但事实如何? 大家不妨读一读 Paxos Made SimpleLeslie Lamport 在文中渐进式地从零开始推导出了 Paxos 协议, 中间用数学归纳法进行了证明可能是因为表述顺序的问题, 导致这篇文章似乎还是不好理解所以这里我摘录了一篇对 Paxos 描述的中文文档[17], 供参考
想要看懂 Paxos 中共识达成的机制较为简单, 其基本来说就是一个二次确认的过程
首先由用户向网络中所有节点发出提议 n,n 是提议的编号
节点收到提议 n 后
若编号 n 比之前接受的提议请求都要大, 则承诺将不会接收提议编号比 n 小的提议, 并且带上之前接受的提议中编号小于 n 的最大的提议{n0, v0},n0 是编号, v0 是内容(如果之前没接受过提议则返回空的消息)
否则不予理会
用户得到了多数节点的承诺后
如果发现承诺的节点返回的都是空, 则向所有节点发送自己本次提议的{n, v}, 让大家接受
否则, 从所有节点返回中选择 n0 最大的 v0, 作为提议的值, 提议编号仍然为 n, 即向所有节点发送 {n, v0} 让大家接受
节点接收到提议后, 如果该提议编号不违反自己做过的承诺, 则接受该提议
Paxos 证明了在这种机制下, 只要挂掉的节点小于半数, 则能实现系统的共识
Raft
Paxos 协议是第一个被证明的一致性算法, 但是 Paxos 的论文非常难懂, 导致基于 Paxos 的工程实践和教学都十分头疼, 于是 Raft 在设计的过程中, 就从可理解性出发, 使用算法分解和减少状态等手段, 目前已经应用非常广泛可以这么理解, Raft 改进了 Paxos 的机制, 便于理解和在实际场景中编程实现
Raft 的详细描述可以参照[18], 由于篇幅所限本文就不详细介绍了
总结
本文的目的是列举目前区块链系统中, 已经应用的主流共识机制, 并附带介绍了 Paxos 和 Raft 这两种非拜占庭问题下的共识算法, 便于对所有共识算法有更好的理解由于所涉及的算法较多, 所以本文并未对算法的细节进行特别详细的描述, 而是罗列了相关的参考文献, 便于读者更加详细地去了解算法细节
本文的主要贡献是描述了各个算法的设计思路使用场景, 也许可以使读者了解每个算法是怎么想出来的以及怎么使用另外, 本文还对比了算法之间的优缺点, 便于读者去了解算法的不同
还有一些正在测试中或是开发中的共识机制, 将在后续文章中进一步阐述
参考资料
[1] 拜占庭共识机制 https://www.jianshu.com/p/5fea30b25f0a
[2] Byzantine fault tolerance https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
[3] 实用拜占庭容错算法 PBFT https://www.jianshu.com/p/1e2acd3cbd9f
[4] 分布式系统理论基础 - CAP https://www.cnblogs.com/bangerlee/p/5328888.html
[5] 精通比特币 (第二版) 挖矿和共识 http://book.8btc.com/books/6/masterbitcoin2cn/_book/ch10.html
- [6] https://github.com/ethereum/wiki/wiki/Ethash
- [7] Cryptocurrencies without Proof of Work https://arxiv.org/pdf/1406.5694.pdf
[8] PPC: 一种 P2P(点对点)的权益证明 (Proof of Stake) 密码学货币 https://peercoin.net/assets/paper/peercoin-paper-cn.pdf
- [9] BlackCoin's Proof-of-Stake Protocol v2 https://blackcoin.co/blackcoin-pos-protocol-v2-whitepaper.pdf
- [10] Security Analysis of Proof-of-Stake Protocol v3.0 https://bravenewcoin.com/assets/Whitepapers/Blackcoin-POS-3.pdf
- [11] The missing explanation of Proof of Stake Version 3 http://earlz.net/view/2017/07/27/1904/the-missing-explanation-of-proof-of-stake-version
- [12] Proof of Stake FAQ https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ
- [13] Qtum's PoS vs CASPER (and the nothing-at-stake problem) https://www.reddit.com/r/Qtum/comments/788oa5/qtums_pos_vs_casper_and_the_nothingatstake_problem/
- [14] Block size limit controversy https://en.bitcoin.it/wiki/Block_size_limit_controversy
- [15] EOS.IO Technical White Paper https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md
[16] NEO 共识机制 http://docs.neo.org/zh-cn/node/consensus/consensus.html
[17] 微信 PaxosStore: 深入浅出 Paxos 算法协议 http://www.infoq.com/cn/articles/wechat-paxosstore-paxos-algorithm-protocol
[18] Raft 一致性算法笔记 https://www.jianshu.com/p/096ae57d1fe0
来源: https://juejin.im/post/5ac1e9adf265da23906c2dc8