1、共识简史 回顾现状未来区块链技术的发展历史区块链共识简史目录目录1. 回顾2. 现状3. 未来4. 小结区块链共识简史2018Lamport 发表发表“拜拜 占庭将军占庭将军” 论文论文Liskov 发表发表ViewStampedLamport发发 表表PAXOS论论文文Castro和和Replication 论文论文 PBFT论文论文Jakobsson 和和Juels发表发表PoW论文论文ZooKeeper1.0 发布发布中本聪实现中本聪实现 比特币比特币 POWLiteCoin Scrypt PoWPeerCoin PoSRipple UNLNXT PoSBitShares DPoSPri
2、meCoin PoWOngaro 和和 Ousterhout 发表发表RAFT 论文论文Stellar SCPLiu 和和 Caching 发表发表XFT论论 文文Ethereum Ethash PoWIBM Fabric0.6 PBFTIntel发布锯发布锯 齿湖项目齿湖项目PoET共识共识OnChain dBFTR3CEVCordaTendermintIBM Fabric1.0 Kafka ZooKeeperEthereum MetropolisEthereum Casper PoSMikeKotla 发发Liskov发表发表 Burrrows 表表发表发表ZyzzyvaChubby论论
3、论文论文 文文Martin 和和 Alvisis 发发 表表 FaB Paxos论文论文Fischer 和和Lynch 发表发表FLP分分 布共识容错不可行布共识容错不可行 论文论文1982 1985 1988198919981999200620072008 2009 201120122013 2014 2015 20162017Eric Brewer 发表发表 CAP 理理 论论共识算法的起源 解决集中式计算向分布式计算 转型的首当其冲的一致性挑战 分布式系统 分布式是一种计算模式，指在一个网络中，各节点通 过相互传送消息来通信和协调行动，以求达到一个共 同目标 一致性的问题 分布式系统由于
4、各节点独立运行，相互通信也会出故 障，因此要保证整个系统状态的一致性，需要有共识 协议分布式系统如何保证一致性？分布式系统如何保证一致性？分布式系统一致性问题的形象比喻-拜占庭 将军问题（Lamport）l拜占庭将军问拜占庭将军问题题ll所有忠诚的将军决定一致的 计划；少数叛徒不能使忠诚将军采 用错误的计划。l简化版拜占庭问题简化版拜占庭问题l一个指挥官要发一个命令给 n-1个副官，希望：ll所有忠诚的副官都执行同一 命令；如果指挥官是忠诚的，每个 忠诚的副官都执行该命令。共识问题的特征和属性l 共识问题共识问题（Consensus Problem）l 特征特征l 所有进程都有一个初始值（al
5、l processes have an initial value ）l 属性属性l 一致协议（Agreement）l所有的非缺陷进程都必须同意同一个值。l 正确性（Validity）l如果所有的非缺陷的进程有相同的初始值，那么所有非l缺陷的进程所同意的值必须是同个初始值。可结束性（Termination）l每个非缺陷的进程必须最终确定一个值。分布式系统与拜占庭将军问题l分布式系统节点类型分布式系统节点类型ll正常系统 忠诚的拜占庭将军任意故障系统 叛变的Byzantine将军l拜占庭缺陷拜占庭缺陷 （Byzantine Fault）l任何从不同观察者角度看表现出不同症状的缺陷l拜占庭故障拜占
6、庭故障（Byzantine Failure）l由于拜占庭缺陷导致的节点故障l故障的分类故障的分类宕机、停 机故障丢消息任意故障 认证消息任意故障关于拜占庭将军问题的理论证明lLamport （1982）ll当叛徒多于将军总数的三分之一时，同时通信采用同步非防篡改方式， 拜占庭将军问题无解。如果通信采用同步、认证和不可篡改方式，拜占庭将军问题可以在任 意多叛徒情况下有解 （如果将军总数少于叛徒数+2，问题就没有意 义）lFischer-Lynch-Paterson （1985）l在一个多进程异步系统中，只要有一个进程不可靠，那么就不存在一 个协议，此协议能保证有限时间内使所有进程达成一致。关于拜
7、占庭将军问题实际情况假设l分布式系统假分布式系统假设设l故障模型非拜占庭故障l l拜占庭故障l通信类型同步l l异步l通信网络连接l节点间直连数l信息发送者身份实名l l匿名ll通信通道稳定性 消息认证性l l认证消息 非认证消息强一致性（Strong Consistency）共识算法l 强一致性共识算强一致性共识算法法l 宕机故障（Crash Failure）l主副本, 2PC, 3PC提交l 宕机-恢复故障 （Crash Recovery Failures）l Paxos, Chubby，ZooKeeper，etcdl RAFT，ViewStamped Replicationl 拜占庭故障
8、 （Byzantine Failures）l PBFT（实用拜占庭容错）， Zyzzyva，Fab Paxos故障容错办法 状态机复制 （SMR） 状态机复制（State Machine Replication) 采用把系统状态复制到各冗余副本节点以及协调客户端 对服务器节点访问的通用容错方法如何保证在故障情况下的一致性？ - 交易的原子性 2PC 两阶段提交 2PC 缺点 当Coordinator和其它一个节点发生故障，其它节点无法知道 是应该提交还是回滚3PC提交可以避免多个节点故障情况 3PC提交 把第二阶段再划分，从协议上使得第一阶段状态完全确定; 其它节点第二阶段只能确认收到消息，不
9、能提出回滚要求; 第三阶最后交易提交。 3PC的局限 过于依赖协调节点，如果部分节点认为协调节点故障，将比较复杂 如果一个Coordinator故障节点恢复上线, 如何处理？13Paxos 避免对Coordinator的依赖，处理多节点 Crash-Recovery 故障Paxos 多数集 任意两个多数集之间的交集不是空集 三种角色 Proposer 提议一个被希望接受的值 Accepter 接受提议或拒绝提议 Learner 不参与决策 但必须知道最后结果 两阶段 Prepare Prepare(x, n) / acc(y, m) | acc (,0) Propose Propose(y,
10、n) / ack(y, n)Paxos 优点和局限 Paxos 优点 Paxos是一个可以容忍 fn/2 Crash-Recovery 故障的 异步强一致性协议 Paxos能保证协议性（Agreement）和正确性（Validity） 局限 不能保证可终止性（Termination） Paxos 只能保证如果一个值被选择，其它节点只能选择同意一 个值 但它不能保证一个值能被选择到。PBFT 实用拜占庭容错 PBFT 需要5轮通信步骤 第一轮 客户端发命令 op 给主节点 第二轮 Pre-prepare 第三轮 Prepare 第四轮 Commit 第五轮 客户端接收服务端的回复 如果 f+1
11、回复一样，这个结果被接受。 因为只有 f 个拜占庭服务器，至少有一个正确的服务器支持这个结果。PBFT 强一致性共识算法 PBFT 特性 PBFT在一个异步系统中能达成共识，容忍fn/3拜占庭 故障 PBFT的异步通信是一个有固定延迟限制的异步通信系统（接近同步通信） 采用认证的消息 可以验证服务器是否发过一个消息 在最坏情况下，PBFT需要用f轮才能达到共识。17区块链共识简史目录目录1. 回顾2. 现状3. 未来4. 小结首个区块链共识公有链比特币PoW机制生成铸币交易，并与其他所有准备打包进区块的交易组成交易列表，通过Merkle树算法生成 Merkle 根哈希；把Merkle根哈希及其
12、他相关字段组装成区块头，将区块头的80字节数据作为工作量证明的输入；不停的变更区块头中的随机数即nonce的数值，并对每次变更后的区块头做双重SHA256运算（即SHA256(SHA256(Block_Header)）将结果值与当前网络的难度目标值做对比，如果小于目标值，工作量证明完成 难度调整难度调整由于矿工数量动态变化，比特币系统动态调整挖矿难度，使得大约每10分钟产生一个区块 共识区块链共识区块链最长区块链为共识区块链，代表具有最大工作量的区块链 概率性拜占庭概率性拜占庭 （Probabilistic BA）协议（协议（Agreement）在不诚实节点总算力小于50%的情况下，同时每轮同
13、步区块生成的几率很少的情况下，诚 实的节点具有相同的区块的概率很高。正确性正确性（Validity）大多数的区块必须由诚实节点提供（严格的说，当不诚实算力非常小的时候，才能使大多数区块由诚实节点提供）可终止性（可终止性（Termination）约每10分钟完成一次共识比特币PoW 最终一致性共识 挖矿过程挖矿过程公有链其它PoW共识算法其它其它PoW共识算法共识算法 LiteCoin PoW采用scrypt算法，不但需要计算能力，还需要内存，可以防止暴力破解，对ASIC挖矿也有 一定的抵抗力 PrimeCoin PoW工作量证明不像比特币那样做无用功，而是寻找质数，具有科学价值，可称为“有用工
14、作 量证明”（Proof of Useful Work”） Ethereum Ethash PoW比特币PoW基础上引入GHOST（Greedy Heavest-Observed Sub-Tree), 在共识区块链 计入叔区块挖矿不但需要计算能力，还需要内存，对ASIC挖矿和算力中心化有一定抵抗力 Intel SawtoothLake PoET采用新的CPU安全指令，通过可信任运行环境（TEE）如 Intel Software Guard Extensions (SGX) ，根据验证者等待时间来确定Leader，实现公平、随机选取共识 Leader每个验证者向一个enclave (信任函数）请
15、求一个等待时间，具有对一个区块最短等 待时间的验证者会被选成Leader.实现“一个CPU一票”权益证明共识算法 POS、DPOS 权益证明权益证明Proof-of-Stake (PoS)共识算法共识算法 PeerCoin POS权益证明机制结合了随机化与币龄的概念，未使用至少三十天的币可以参与竞争下一区块， 越久和越大的币集有更大的可能去签名下一区块。 NXT、Blackcoin POS采用随机方法预测下一合法区块，使用公式查找与权益大小结合的最小哈希值， 由于权益 公开，每个节点都可以以合理地准确度预计哪个帐户有权建立区块。 BitShares DPOS引入了见证人这个概念，见证人可以生成
16、区块，每一个持有比特股的人都可以投票选举见 证人。 Tendermint验证者将押金锁定，投票权力和押金相等。验证者如果作弊，押金会被销毁。投票步骤：Propose, Prevote, Precommit， Commit, NewHeightPrecommit和Commit需超过2/3投票 Ethereum PoS (Casper)权益持有者通过用押金方式来赌下一个区块，赌中有奖，不中会扣掉一部分押金21其它共识算法 Ripple 高扩展性BFT算法 Ripple共识 假设拜占庭节点数少于所有节点数的20% （f 80 UNL2：21红21个节点，其中18个投No共识结果是No 80% UNL
17、 1和 UNL2 共识结果分叉Ripple用子网共识提升共识效率，但能保证一致性吗用子网共识提升共识效率，但能保证一致性吗？*source: Ripple Forum: https:/ Stellar联邦式BFT SCP共识 特点 分散控制、低延迟、灵活信任、渐近 安全开放成员，每个节点可以决定信任对象 （quorum slices) 共识条件Quorum达成一致的多数集Quorum SliceQuorum中的子集，能说服一个节点达成一致Quorum Intersection 条件任意一个节点的Quorum Slices函数必须满足任意两Stellar联邦式联邦式BFT共识算法共识算法个Quo
18、rum之间必须有一个共同的节点的条件删除破坏节点后还能达到Quorum Intersection SCP协议 提名协议（Nomination Protocol）生成候选值 SCP协议 投票协议 （Ballot Protocol)Prepare （准备）Confirm （确认）Externalize （外部化）*source：Stellar White Paper and Technical Summary区块链共识现状 多数单一场景，受限于FLP，CAP公有链公有链联盟联盟/私有链私有链拜占庭故障拜占庭故障非拜占庭故障非拜占庭故障高扩展性，开放高扩展性，开放安安 全全 性性高性能高性能, 许可
19、，确定性许可，确定性XFT PBFTZyzzyva FaB Pax TendosRippStellarBitCoin PoW Ethereum Ethash PoWermintLiteCoin PoW lePeercoin PoSPaxosNXTChubbyBBitZookeeperIntel P ViewStamped ReplicationetcdRAFTl PoS oin PoSackcShares DPoS oET私有链上共识算法存在问题l私有链多数采用状态机复制技术（私有链多数采用状态机复制技术（SMR）lPaxos-basedlChubby, Zookeeper, etcd, RA
20、FTlBFT-basedllPBFTZyzzyvalSMR技术扩展性不好技术扩展性不好lll成员固定一般记账节点10-20个 多轮消息往返lPBFT：五阶段， 节点平方级的消息量l节点增加，性能降低公有链上共识算法存在问题l比特币比特币 POW机制机制ll能源消耗大，工作量没有实际价值 交易速度慢l1秒钟最多7笔交易ll缺少最终确定性（Finality） 算力集中l矿池lASIC矿机lPOS 机制机制破坏者攻击成本小，安全性成疑ll公平性有问题l有用工作量机制有用工作量机制 Proof-of-useful WorkllPrimecoin如何满足容易验证，难度可调，几率和贡献工作量成正比（Pro
21、gress-free）区块链共识简史目录目录1. 回顾2. 现状3. 未来4. 小结区块链共识算法发展趋势 未来区块链平台支持可插拔共识模块 Hyperledger Fabric, Ethereum， Hyperledger SawtoothLake 根据不同场景，选择合适的共识算法 Fabric1.0， 提升交易吞吐率，采用Kafka 未来更多的融合，取长补短 多链，侧链，闪电网络 公有链/联盟链融合 去信任 + 信任 Ripple, Stellar 行业区块链 R3CEV Corda -专注于金融行业，（不是区块链的区块链DLT） 数据只在相关方共享，不交给无关第三方 交易正确性共识通过合
22、约运行和签名校验来验证 交易唯一性共识需要事先设置的独立公证发展趋势发展趋势 融合融合区块链共识简史目录目录1. 回顾2. 现状3. 未来4. 小结区块链共识算法分类 按共识机制分类 PoW, PoS, PoET, BFT, Paxos 按区块链部署模式 公有链共识算法 联盟链/私有链共识算法 按容错类型分类 宕机容错共识算法 拜占庭容错共识算法 按一致性类型分类 强一致共识算法 最终一致性共识算法 按副本复制方式分类 Primary-backup 主从备份 State Machine Replication 状态机复制分类方式区块链共识算法的选择考虑 公有链 最终一致性（Eventually
23、 Consistency） 故障类型: 拜占庭故障 共识成本 POW vs POS 共识效率 安全性 联盟链 / 私有链 强一致性（Strong Consistency） 故障类型 非拜占庭故障 拜占庭故障 共识效率区块链主要技术核心 共识机制 共识算法属性共识算法属性 一致性（Agreement） 正确性 （Validity） 活性（Liveness） 性能 （Performance） 扩展性（Scalability） 公平性（Fairness） 安全性 （Security） 共识算法的理论限制共识算法的理论限制 Fischer-Lynch-Paterson定律 在一个多进程异步系统中，只要
24、有一个进程不可靠，那么就不存在一个协议， 此协议能保证有限时间内使所有进程达成一致。 实用共识算法实用共识算法 实际情况下假设不同的条件 同步/异步 身份认证/匿名 宕机-恢复故障 / 拜占庭故障 故障节点占比32小结 区块链是信任机器区块链是信任机器 信任由共识产生 共识算法有强一致性和最终一致性共识算法共识算法有强一致性和最终一致性共识算法 强一致性 Paxos，PBFT, RAFT 等 最终一致性 PoW， PoS，DPoS 区块链共识算法因公有链、联盟链、私有链不同区块链共识算法因公有链、联盟链、私有链不同而而 有所不同有所不同 公有链：最终一致性共识算法 联盟链，私有链 强一致性共识算法33
