区块链不可能三角为什么不可突破

技术文章黄连金,向文波2019-02-25 18:59:58  阅读 -评论 0  阅读原文

摘要

在1985年,由Fischer、Lynch和Patterson三位科学家发表的论文中,提出了FLP理论。FLP理论证明了,在一个完全异步的分布式系统中,如果有一个节点出现故障,没有任何一种共识协议,能够实现完全的一致性。

在2002年,Lynch和Gilbert发表的论文中,提出了CAP理论。CAP理论证明了,在一个分布式系统中,最多只能同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance)这三项中的两项。

区块链作为典型的分布式系统,FLP和CAP同样适用于区块链。本文将基于FLP理论和CAP理论,分析一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance)与区块链不可能三角间的逻辑关系,从而解释为什么区块链不可能三角不可突破。

1.FLP理论概要

1985年4月,Fischer,Lynch和Patterson证明的FLP理论,是最重要的分布式系统理论之一,他们也凭借论证FLP理论的论文,获得了分布式计算中最具影响力的Dijkstra论文奖。

FLP理论证明了,在异步通信系统中,存在节点失效(即便只有一个),不存在一个可以解决一致性问题的确定性算法。

在同步的系统中,达成共识是可以被解决的。因为在同步系统中,当有进程出现故障,或者响应超时,我们可以认定它已经崩溃。

在异步的系统中,当一个进程出现故障,或者响应丢失时,是无法检测到的。在这样的条件下,如果其中有任意一个进程出现问题,没有任何一个分布式算法,可以让所有的非故障进程,达成一致性共识。

因为有FLP不可能性的限制,大部分区块链项目的共识算法都把大部分节点是诚实的和满足一定的同步性作为前提。POW认为51% 的节点是诚实的,并且有一定的同步性。POS和PBFT也认为大部分节点(66%)是诚实的。

2.CAP理论概要

在2000年的分布式计算原则研讨会(PODC)上,计算机科学家埃里克.布鲁尔针对分布式计算系统的一致性(Consistency)、可用性(Availability)、分区容错性(Partition-tolerant)提出了猜想。在2002年,他的猜想得到了来自麻省理工学院的两位教授Nancy Lynch 和 Seth Gilbert的证明,并被称为CAP定理。

CAP定理证明了:当网络存在分区时,提供可靠的原子一致性数据是不可能的,但是想要实现一致性、可用性、分区容错性,三个属性中的两个是可行的。在异步通信系统中,当没有锁提供时,如果出现消息丢失,即使允许过时的数据返回,提供一致性数据也是不可能的。在同步通信系统中,可以在一致性和可用性间取得一定的平衡。

2.1.一致性(Consistency)

CAP理论的论证中,把一致性定义限定在原子数据对象上,这和其他大多数正式定义一致性服务的方法相同。满足一致性条件的系统,对所有操作都有统一记录,这些操作记录看起来像是一个单独的实例完成的。这要求分布式系统的所有请求必须进行同步,然后才能执行操作。最终呈现的结果,像是同一个节点在同一时间响应,然后执行的一样。

这是提供给用户理解的,最简单的一致性保障模型,也是给设计分布式客户端应用的人理解的最简单的模型。

2.2.可用性(Availability)

为了能让分布式系统持续可用,每个请求会被发送给一个系统中的正常节点,并收到响应。这是任何分布式服务使用的算法必须要满足的。

CAP理论的论证中,将可用性定义为两种:

  • 弱可用性:在终止之前,算法运行的多久是没有边界的,因此允许没有边界的计算。
  • 强可用性:当服务网络发生错误时,每个请求也必须被响应。

在弱可用性条件下,系统对响应时间可以不做保证,但是必须做出响应,当系统出现错误时,并不保证对请求做出响应。而在强可用性条件下,即使系统出现错误,请求也必须得到响应。

2.3.分区容错性(Partition-tolerant)

CAP理论的论证中,分区指的是,网络中允许丢失从一个节点发送到另一个节点的任意数量的消息。这意味着当网络中出现分区时,从一个分区中的节点发送给另外一个分区的节点的消息将会全部丢失。

分区容错指的是,在出现分区时,系统依然能够满足以上定义中的一致性和可用性。原子性要求意味着每一个响应将会是原子性的,尽管任意作为算法的一部分的消息可能不会被传递。可用性要求意味着,每个节点收到的客户端请求必须被响应,尽管任意的消息都可能丢失。

3.用CAP理论来解锁区块链不可能三角为什么不可突破

在区块链领域中,安全性、可扩展性、去中心化,三者被称作区块链的"不可能三角",意思是说,在同一个区块链系统中,想要同时做到三者,并且都达到足够高的要求,是不可能做到的。

我们的基本论证思路是,CAP理论在分布式系统中成立,区块链属于分布式系统,区块链必然遵守CAP理论,只要能证明CAP理论中的一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance),与区块链的不可能三角存在相应的逻辑关系,即可证明区块链不可能三角不可突破。

3.1.一致性与安全性

在CAP理论的证明过程中,证明了在异步网络模型中,实现一个读/写数据对象同时具备可用性和一致性是不可能的。我们将该结论和证明过程,对应到区块链系统中。

在CAP理论限定的网络环境中,我们假设一个区块链系统中,存在A和B两个节点,其中A和B同时记录了一个地址H的加密货币余额为X1,此时A和B出现了分区。

当用户在A节点所在的分区发起一笔交易时,地址H中的余额将会发生变化,成为X2。当用户在B节点所在的分区发起一次余额查询操作时,地址H中的余额依然是X1。由此我们说区块链系统中,出现了账本不一致的情况。

当区块链系统中出现不一致状态时,我们认定这样的区块链系统是不安全的。在这样的定义下,一致性是区块链系统安全的基本前提。或者说区块链的安全性是比分布式系统的一致性更加严格的需求。安全性>一致性。

3.2.可用性与可扩展性

在CAP理论的可用性定义中,分为弱可用性和强可用性,但是这两种可用性都要求,系统可以对所有正常请求做出响应。从技术的角度来讲,即是可以实现正常的可读可写。

在区块链系统中,可扩展性指的是,每秒可以处理的交易量。从技术的角度来讲,高可扩展性即是实现每秒钟高频次的可读可写操作。

从逻辑上,我们可以看出,可用性是比可扩展性更基础的网络要求,不能实现可用性的区块链系统,是不能实现可扩展性的,即是可用性是可扩展性的前提。或者说区块链的可扩展性是比分布式系统的可用性更加严格。可扩展性>可用性。

3.3.分区容错性与去中心化

在CAP理论中,分区被认为是分布式系统必然存在的。事实也的确如此,在真实分布式环境中,不可能保证系统中的每个节点,都不会出现任何故障。

去中心化作为区块链的基本特征,意味着区块链系统必然是分布式的,也就是说去中心化必定导致发生分区的可能,由此也意味着分区容错性是实现去中心化的前提。

3.4.现有共识算法对CAP的平衡

在CAP理论中,分区被认为是分布式系统必然存在的,所以讨论没有分区情况的分布式系统是没有意义的。区块链作为典型的分布式系统,其不同的共识算法在满足分区的前提下,对系统的一致性(Consistency)和可用性(Availability)做出了一定的平衡。

Tendermint: Tendermint是POS类型的共识算法,主要包括NewHeight -> Propose ->Prevote -> Precommit -> Commit五个阶段。其中Propose-> Prevote -> Precommit属于共识阶段,是算法的核心,被称作一个Round。在进行区块的提交确认时,一个区块可能需要多个Round。在多个Round中,区块的高度并不会增加,只是向系统提交空块,并且一个区块一旦被确认,是不可能被修改的。所以Tendermint理论上有可能被卡住,区块高度永远不会增加。 这意味着Tendermint在出现分区时,更加侧重于一致性(Consistency)。

Casper FFG: Casper FFG是POS类型的共识算法。在Casper FFG的设计中, 优先考虑一致性,因为它不允许在没有绝大多数验证者同意的情况下完成checkpoint,这样区块也就不会达到最终的确认状态。

Algorand: Algorand是POS类型的共识算法。Algorand与Tendermint的设计中有类似的地方,当出现一致性和可用性冲突时,系统会更倾向于产生空块,不会产生真正意义的区块。所以Algorand更优先考虑一致性。

Dfinity: Dfinity是POS类型的共识算法。当网络出现分区时,它会自动使随机信标暂停,不允许网络中的任何分区继续。所以Dfinity更优先考虑一致性。

POW:当使用POW的网络出现分区时,所有的分区都可以正常的进行出块,等到网络恢复,分区结束时,会遵循最长链原则,不同分区的链将会进行合并,最终成为一条链。因此POW优先考虑可用性。

POC:POC的全称是Proof of Credit ,是全球开源社区项目NULS,创新使用的共识算法。当使用POC的网络出现分区时,所有分区都可以正常进行出块。等到网络恢复时,与POW类似,将会遵循最长链原则,进行区块链的合并。因此NULS创新使用的POC优先考虑的是可用性。

注:A<C代表该共识算法更优先考虑Consistency;

C<A代表该共识算法更优先考虑Availability;

4.结论

通过以上对一致性(Consistency)与安全性、可用性(Availability)与可扩展性、分区容错性(Partition-tolerant)与去中心化的逻辑关系推导,我们可以得出以下结论:

  • 一致性(Consistency)是安全性的必要条件
  • 可用性(Availability)是可扩展性的必要条件
  • 分区容错性是去中心化的必要条件

又通过CAP理论可以知道一致性、可用性、分区容错性是不能同时满足的,所以我们可以得出:在CAP理论限定的条件下,安全性、可扩展性、去中心化不能同时满足,即是区块链的不可能三角不可突破。

作者简介:

黄连金

著名区块链专家,核聚链首席科学家、美国 DistributedApps CEO、中国电子学会区块链分会专家委员、NULS技术顾问。

向文波

Java软件工程师,Cryptotech-Writer,NULS Core Team成员。专注于区块链技术研究和区块链解决方案。

参考文献:

Brewer's conjecture and the feasibility ofconsistent, available, partition-tolerant web services Seth Gilbert,Nancy Lynch

Impossibility of Distributed Consensus withOne Faulty Process MICHAEL J. FISCHER,NANCY A. LYNCH,MICHAEL S. PATERSON

分布式系统的CAP理论:https://www.hollischuang.com/archives/666

比较各种共识算法的Finality和Liveness:

https://www.odaily.com/post/5134107

Finality in Blockchain Consensus:

https://medium.com/mechanism-labs/finality-in-blockchain-consensus-d1f83c120a9a

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们100@7234.cn

    参与讨论 (0 人参与讨论)

    相关推荐

    比特币有什么缺点?

    1.交易平台的脆弱性。比特币网络很健壮,但比特币交易平台很脆弱。交易平台通常是一个网站,而网站会遭到黑客攻击,或者遭到主管部门的关闭。2.交易确认时间长。比特币钱包初次安装时,会消耗大量时间下载历史交易数据块。而比特币交易时,为了确认数据准确性,会消耗一些时间,与p2p网络进行交互,得到全网确认后,交易才算完成。3.价格波动极大。由于大量炒家介入,导致比特币兑换现金的价格如过山车一般起伏。使得比

    业务中使用区块链的四种方式

    业务中使用区块链的四种方式

    暴走时评:区块链是一种支持像比特币这样的数字货币的公共分类帐本,并且正改变着我们的业务方式。一旦那些对匿名交易,甚至是秘密交易感兴趣的人接纳了这样一种鲜为人知的工具,加密货币就会日趋成为主流。 区块链是一种支持像比特币这样的数字货币的公共分类帐本,并且正改变着我们的业务方式。一旦那些对匿名交易,甚至是秘密交易感兴趣的人接纳了这样一种鲜为人知的工具,加密货币就会日趋成为主流。越来越多的个人和企

    区块链:法定数字货币技术路线的必然选择

    区块链:法定数字货币技术路线的必然选择

    在人类发展史上,货币的进化从未停止。从物物交换,到金属铸币,再到纸质货币,以及当前正在发展的数字货币正在向着越来越便捷的方向进化。 比特币的出世起初并未带来轰动,但是最近几年其价格惊人的爬高创造出了一个个造富神话,引起各国政府及监管机构的关注。虽然金融专家普遍认为它只是一种资产,而非货币,但是,其背后的区块链(Blockchain)技术引起了包括各大金融机构、政府、企业及学术界的浓厚兴趣,未

    用区块链记录证书,证明真伪,墨尔本大学迈出了第一步

    用区块链记录证书,证明真伪,墨尔本大学迈出了第一步

    墨尔本大学宣布发起区块链认证和审核计划,允许通过一种隐私、安全且持久的方式验证学生的证书。 墨尔本大学正在试验一个区块链记录维护项目,允许接收者(即学生)存储他们的证书,出于核验目的,第三方也能访问这个系统。Learning Machine是这个发布系统的开发者,他们采用的是麻省理工媒体实验室(MIT Media Lab)在2016年提交的Blockcerts开源代码。 墨尔本大学副校长格雷

    日本IT巨头富士通联合日本“三大行”开发区块链p2p资金转移系统

    日本IT巨头富士通(Fujitsu)与三家大型银行已经宣布计划试点一项基于区块链创建的点对点资金转移系统。 通过与日本三大行——瑞穗金融集团,三井住友金融集团和三菱UFJ金融集团——的合作,富士通将现场试验一种基于云的区块链平台,用于在个体之间发送资金,并开发一款智能手机APP来提高这个系统的可用性。 从理论上讲,这个平台将把三大行的客户法定货币账户与这个区块链系统相连接。客户然后将能够使用这

    动画科普:什么是比特币?

    动画科普:什么是比特币?

    比特币(Bitcoin,简写BTC)概念由中本聪(化名)提出,是一种点对点、去中心化的数字资产;2009年,中本聪打包了第一个区块,并获得50枚比特币的挖矿奖励,挖矿奖励每4年减半一次,按此计算,比特币预计2140年发行完毕,总量为2100万枚。 随着比特币的发展,比特币逐渐受到认可:德国为全球首个接受比特币支付的国家;微软、戴尔等知名企业也纷纷接受比特币支付。 举个栗子,你能直接用比特币买到

    3分钟理解什么是公有链、私有链、联盟链、许可链

    不同的区块链有着不同的内涵和功能,在区块链领域经常出现的公有链、私有链、联盟链、许可链,这些又都代表什么意思呢? 公有链 公有链是指全世界任何人都可以随时进入系统中读取数据、发送可确认交易、竞争记账的区块链。公有链通常被认为是完全去中心化的,因为没有任何人或机构可以控制或篡改其中数据的读写。公有链一般会通过代币机制鼓励参与者竞争记账,来确保数据的安全性。比特币、以太坊都是典型的公有链。 私

    区块链是比特币的底层技术,但似乎两者已走上不同的道路

    区块链是比特币的底层技术,但似乎两者已走上不同的道路

    比特币的出现带来了一项新的技术——区块链,不过区块链和比特币似乎已走上了两条不一样道路,作为技术的区块链被越来越多的人所看好,而性质偏向于投资的比特币似乎被更多人看衰。 成也萧何败也萧何 比特币火爆的原因是其拥有去中心化、全世界流通、专属所有权、低交易费用、无隐藏成本、跨平台挖掘的特性,这些特性促使比特币成为了很多人关注的焦点。之后众多庄家的入局让比特币一瞬间成为了热门投资产业,但这几大特

    麦妖榜
    更新日期 2019-07-22
    排名用户贡献值
    1BitettFan24106
    2等待的宿命23810
    3牛市来了22238
    4六叶树20309
    5区块大康19383
    6linjm122717663
    7天下无双16192
    8lizhen00215252
    9让时间淡忘14484
    10冷风大q11188
    返回顶部 ↑