PalletOne架构师曾毅：共识机制的演进。

4-12号PalletOne架构师曾毅在北京市朝阳区瀚海文化大厦一层创客空间路演厅发表演讲：共识机制的演进。

议程：分布式和共识的几个概念，CFT & BFT，POW，POS，DPOS，其他改进的共识算法

PalletOne 架构师/交付总监

毕业于电子科技大学，从事IT行业10余年。 先后服务于微软、中金公司、硅谷公司和区块链创业公司。 参与开发并带领团队完成了大量项目，涉及企业管理、财务数据处理、商业智能、移动互联网、供应链金融等。专注于数据库、数据仓库、大数据和区块链技术。

Agenda：分配和共识的几个概念

1. FLP不可能&CAP原理

FLP不可能性原则（FLP impossibility）：在一个可靠的网络中，存在节点故障的最小异步模型系统（即使只有一个），不存在可以解决一致性问题的确定性算法。

分布式计算系统不可能同时保证Consistency、Availability和Partition，设计时往往需要弱化对某个特性的保证。

* 一致性：任何操作都应该是原子的，后面发生的事件可以看到前面事件的结果。 注意这里指的是强一致性；

*可用性：在限定时间内，任何非故障节点都可以响应请求；

*分区容忍度（Partition）：网络可能被分区，即无法保证节点间的通信。

2. 什么是共识？

*什么是共识共识？ 当多台主机通过异步通信组成一个网络集群时，这个异步网络默认是不可靠的，因此需要一种机制来复制这些不可靠主机之间的状态，以保证每台主机的状态最终达到一致的状态，达到一个共识。

*为什么默认情况下异步网络被认为是不可靠的？ 这是基于 FLP 原理。 文章 Impossibility of Distributed Consensus with One Faulty Process 提出：在异步系统中，我们不可能准确知道任何一台主机是否死了，因为我们无法区分主机或网络性能下降与崩溃之间的区别主机的，也就是说我们无法可靠地检测到故障错误。 但是，我们也必须确保安全。

3. 共识特征

达成共识的过程越去中心化，效率越低，但满意度越高，因此越稳定； 反之，达成共识的过程越集中，效率越高，也越容易出现独裁和腐败。

*一种常用的达成共识的方法是通过物质激励对某一事件达成共识； 但这种共识的问题在于，它很容易被来自外部的其他更大的物质激励所破坏。

*还有一种群体，群体中的个体自发地就某一事件朝着符合自身利益或整个群体利益的方向达成共识； 当然，形成这种以维护群体利益因素为核心的自发共识过程需要时间和环境，但一旦形成这样的共识趋势，共识结果就会更加稳定，更不容易被破坏。

议程：CFT 和 BFT

1. Paxos 和 Raft

*Paxos问题是指在存在故障但没有恶意节点（即消息可能丢失或重复，但没有错误消息）的分布式系统中达成共识的问题。 因1990年Leslie Lamport首次以Paxon Island的故事模型描述而得名。

*Paxos过于晦涩难懂，此后出现了各种改进算法：Egalitarian Paxos、Hydra、Fast Paxos、Ios、VRR（Viewstamped Replication Revisited）、Multi-Paxos、Raft等。

*Raft算法是2013年问世的Paxos算法的简化实现。

*Paxos是无领导算法，Raft算法是强领导算法。

2. 两军问题和拜占庭将军问题

*拜占庭将军问题是一个共识问题：由Leslie Lamport等人于1982年首先提出，称为拜占庭将军问题或拜占庭失败。 核心描述是军队中可能有叛徒，但攻击必须一致。 这扩展到计算领域，发展成为容错理论。

*白军驻扎在沟里，蓝军分散在沟的两边。 白军比蓝军都强，但蓝军同时进攻也能打败白军。 他们无法远程通讯，只能通过壕沟派出信号兵，通知对方蓝军协商进攻时间。 有没有能让蓝军获胜的通信协议，是两军的问题。

3.PBFT

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用的拜占庭容错算法。 该算法由Miguel Castro（卡斯特罗）和Barbara Liskov（里斯科夫）于1999年提出，解决了原始拜占庭容错算法效率低下的问题，将算法的复杂度从指数级降低为多项式级。 ，使得拜占庭容错算法在实际系统应用中具有可行性。

该算法在保证活跃性和安全性的前提下提供(n-1)/3容错，即节点数需要达到3f+1个节点才能容错f个节点。

4. CFT 和 BFT

*Crash Fault Tolerant 无恶意节点的容错Paxos和Raft

*Byzantine Fault Tolerant 恶意节点情况下的容错PBFT和POW

议程：战俘

一、POW共识

Proof of Work，工作量证明的概念最早由 Cynthia Dwork 和 Moni Naor 于 1993 年提出。在随后的几年里，这个概念在是否能有效抵抗拒绝服务攻击的争论中越来越为人所知。 PoW机制的核心是迫使攻击者做一定的工作量才能进行下一步的交互操作，无形中增加了攻击者的攻击成本。 自然地，攻击者需要完成的工作可以根据消耗的计算机资源类型分为以下三类：

* 消耗CPU资源

* 消耗内存资源

*消耗网络资源

1998年在B-money设计中提出POW作为一种共识机制。

2. 比特币 POW 共识

*2008年，中本聪发表了比特币白皮书。 比特币采用POW共识通过计算猜测一个值（nonce），并解决规定的Hash问题（两个SHA256）。 保证在一段时间内系统中只会出现少数合法提案。

*同时，这些少量的合法提案将在网络中广播比特币挖矿难度的历史演进，接收用户将根据其认为持续困难的最长链来验证计算。 因此，系统中可能存在链分叉（Fork），但最终一条链会成为最长链。

*哈希问题是不可逆的。 因此，除了暴力计算外，没有有效的算法可以解决。 反之，如果获得了满足要求的nonce，则意味着相应的算力已经按概率支付了。 谁的算力大，谁先解决问题的概率就大。

*当掌握了全网一半以上的算力时，可以从概率的角度控制链在网络中的走向。 这也是所谓51%攻击的由来。

3. POW共识ASIC的问题

4. 抗ASIC化

莱特币：刚性内存哈希函数 Scrypt 取代 SHA256

Dash：X11，11 个哈希函数的混合

以太坊：Ethash，大内存DAG搜索

5. POW资源浪费

六：消除浪费——有效工作量的证明

Prime 硬币：Twin Prime 搜索。

治疗硬币：用于发现新药的蛋白质折叠计算。

比原链：一种有利于人工智能的POW机制。

议程：POS

1. 收款机

*2011年，一位名叫Quantum Mechanic的数字货币爱好者在Bitcointalk论坛提出Proof-of-Stake（POS）证明机制比特币挖矿难度的历史演进，经过充分讨论证明是可行的。 如果说POW主要是比拼算力，算力越大，挖到区块的概率就越大，而POS则是比拼平衡。 通俗地说，手里的硬币越多，挖到区块的概率就越大。

2.POS共识

PoS 中存在内部 Nothing-at-Stake 攻击。

假设系统中有两条支链，那么对于持币的“矿工”来说，最好的操作策略是同时在两条支链上“挖矿”，这样无论哪条支链获胜，最远对持币者而言，他会得到属于他的收益，即不会有收益损失。 并且由于不需要算力，所以在 PoS 的两个分支上挖矿是可行的。

由此带来的问题是，只要系统中存在分叉，“矿工”就会同时在这些分叉上挖矿； 因此，在某种情况下，发起攻击的分叉链极有可能得逞，因为他们也对这条分叉链达成了共识； 甚至不持有51%的币，也能成功发起分叉攻击。

3.点点币

Peercoin（PPC）于2012年8月发布，最大的创新在于其挖矿方式混合了POW工作量证明和POS权益证明。 其中POW主要用于发行货币。 未来预计随着挖矿难度的增加，产量减少，系统安全主要由POS维护。 目前区块链中有两种类型的区块，POW 区块和 POS 区块。 PPC的作者是Sunny King，一位同样不愿透露身份的加密货币极客，同时也是素数币的发明者。

4.Nextcoin未来币

2013年9月，一位名叫BCNext的用户在Bitcointalk论坛发帖，宣布将发行一种新的纯POS币种，后命名为Nextcoin，简称NXT。

Nxt 是第一个具有 100% 权益证明 (PoS) 机制的电子货币。 Nxt不再消耗大量资源“挖矿”产生新的货币，而是通过已有账户的余额来“锻造”区块，并奖励成功“锻造”区块的账户的交易手续费

议程：DPOS

一、DPOS共识

比特股（Bitshares）项目于2013年8月启动，比特股的核心账本采用石墨烯技术，对交易容量和出块速度有着极高的要求。 显然，无论是 POW 还是 POS 都不能满足要求，因此 Bitshares 发明了一种新的共识机制——Delegated Proof-Of-Stake (DPOS)，即 Proxy Proof of Stake。

DPOS 很容易理解，类似于现代的公司董事会制度，比特股制度将代币持有者称为股东，由股东选出 101 名代表，然后由这些代表负责出块。

2. EOS的共识——BFT+DPOS

EOS通过投票选出21个超级节点作为记账节点，每个节点有3秒的时间片轮流记账。 如果轮到一个节点记账但没有产生区块，则该节点可能被投票出局并被其他备选节点取代。 出块速度0.5秒！

拜占庭容错算法（BFT）被添加到传统的 DPOS 中，允许所有生产者签署所有块，只要没有生产者用相同的时间戳或相同的块高度标记两个块。 一旦 15 个生产者签署了一个区块，该区块就被认为是不可逆的。 在这种模式下，不可逆共识应该在1秒内完成。

各种共识战

V神和BM关于pow和dpos的相互交锋。 POW和DPOS，谁更中心化？

议程：其他改进的共识算法

1. 传统共识算法存在的问题

2.其他改进的共识算法

*NEO 的 DBFT

*以太坊下一代POS共识：Casper

*DAG及IOTA和Byteball的相关共识

*HyperLedger Fabric 下一代共识：SBFT

3. PalletOne陪审团共识

“我们都有责任。我一直认为这就是民主的伟大之处。我们在邮件中被告知，我们大老远跑到这里来决定我们从未见过的人是否有罪。不管怎样结论是，我们一无所获，也没有什么可失去的。这是我们国家强大的原因之一。我们不能把它放在心上。”

4. PalletOne 多陪审团并行共识

总结

*现在越来越多的区块链数字资产应用来自现实世界或金融资产，对交易的最终确认有很高的要求，需要不同的共识机制。

* 共识机制是区块链的核心技术。 各种区块链共识机制的选择被认为是目前为止最好的选择； 当未来区块链技术越来越多地应用到现实中时，未来会不断做出改进以满足实际需求。

*共识算法的选择与应用场景高度相关。 可信环境使用Paxos或Raft，许可联盟可以使用PBFT，非许可链可以是POW、POS、DPOS共识等。

加入“托盘”

让我们一起见证跨链时代的到来！

欢迎大家加入“托盘”微信群