请选择 进入手机版 | 继续访问电脑版

Hi,Tokens

 找回密码
 立即注册
查看: 410|回复: 2

区块链基本原理文章汇编

  [复制链接]

594

主题

957

帖子

3399

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3399
发表于 2018-4-22 15:39:36 | 显示全部楼层 |阅读模式
拜占庭容错

区块链本质上是分布式系统,其中包含不同的参与者,基于各自动机和可用信息行动。
每当一笔新交易在网络中广播出来,节点有权选择将该交易纳入其持有的账本副本之中,或者将其忽略。当网络中的大部分参与者选定某一状态之时,就能达成共识
分布式计算多智能体系统的一个基本问题是如何在一些错误流程存在的情况下实现总体系统的可靠性。这通常需要各个流程就计算中所需的某些数据值达成一致意见。¹
这些过程被称为共识。
  • 当某个参与者决定不遵守规则并篡改其账本状态之时会发生什么状况?
  • 当这些参与者构成网络中的一大部分且总数不过半之时会发生什么状况?
要创建一种安全的共识协议,必须实现容错性
首先,我们将简要谈谈无法解决的“两军问题(Two Generals' Problem)”。之后我们会延伸至拜占庭将军问题并讨论在分布式和去中心化系统中的拜占庭容错。最后,我们会探讨上述内容与区块链领域有何关联。

两军问题
这一问题(最早于1975年[url=https://ethfans.org/posts/%5Bhttp://hydra.infosys.tuwien.ac.a ... load/1975_Akkoyunlu,%20Ekanadham,%20Huber_Some%20constraints%20and%20tradeoffs%20in%20the%20design%20of%20network%20communications.pdf%5D(http://hydra.infosys.tuwien.ac.a ... load/1975_Akkoyunlu,%20Ekanadham,%20Huber_Some%20constraints%20and%20tradeoffs%20in%20the%20design%20of%20network%20communications.pdf)]提出[/url],并于1978年得名)描述了一个两军共同抗敌的场景。将军1是领导者,而将军2是跟随者。两位将军各自的军队不足以击败敌军,因此他们需要联手同时进攻。虽然这看似是一个简单的场景,却内含警示之意:
为了双方能够交流并选定时间,将军1需要派遣一名通信兵穿越敌军阵营通知将军2进攻时间。然而,通信兵有可能被敌方捕获,致使消息传递失败。结果导致将军1在发动进攻之时将军2仍驻守原地。
即便第一次传信成功了,将军2必须承认(即ACK(acknowledge),注意这与[url=https://ethfans.org/posts/%5Bhttps://en.wikipedia.org/wiki/Transmission_Control_Protocol%5D(https://en.wikipedia.org/wiki/Transmission_Control_Protocol)]TCP[/url]协议的“三次握手”相似)已收到消息,于是他派遣了一名通信兵回信,因此又会出现之前通信兵被捕获的情况。这就会引起无数次地重传 ACK 确认符,导致两位将军无法达成共识。
要实现这两位将军都确认对方同意作战方案的第二点要求是不可能的。两位将军总是会心存疑惑,想知道他们的最后一名通信兵是否成功穿越了敌方阵营。
-因为消息传递失败的可能性始终大于0,两位将军永远不可能在100%的信任下达成共识。-
两军问题已经[url=https://ethfans.org/posts/%5Bhttps://en.wikipedia.org/wiki/Two_Generals%27_Problem#Proof%5D(https://en.wikipedia.org/wiki/Two_Generals%27_Problem#Proof)]被证明[/url]无解的

拜占庭将军问题
[url=https://ethfans.org/posts/%5Bhttp://citeseerx.ist.psu.edu/vie ... ep1&type=pdf%5D(http://citeseerx.ist.psu.edu/vie ... p=rep1&type=pdf)]Lamport、Shostak和Pease在1982年[/url]发表的一篇著名文章中描述了拜占庭将军问题,它是改编后的两军问题的广义版本。该问题描述了一个相同的场景,只不过需要由两位以上共同抗敌的将军就进攻时间达成一致。其复杂性更强,因为一位或多位将军可能叛变,此即表明他(们)可能会在做出选择时撒谎(例如,他们会假意同意在9点发起攻击但并不行动)。
两军问题中描述的领导者-跟随者模式转变成了指挥官-副官模式。在拜占庭将军问题中,为了达成共识,指挥官和每位副官必须就同一决定达成一致意见(简单来说就是攻击撤退)。
-拜占庭将军问题,第三页-
此外,上图中的条件 IC2 还可能出现一种有趣的情况,如果指挥官叛变了,依然要达成共识。结果,所有副官取得了多数票。
在这种情况下,达成共识的算法依据的是由副官观察到的大多数成员决定的值。
原理:取任意值m,如果将军人数为3m以上,叛徒的人数不超过m,算法OM(m)则达成共识。
这表明只要有 2/3 的参与者是忠诚的,该算法就能达成共识。如果叛徒的人数超过 1/3 ,则无法达成共识,同盟军无法协调进攻,敌方获胜。
- m = 0 →没有叛徒,所有副官选择一致 m > 0 →每位副官的最终选择取决于绝大多数副官的选择 -
从副官2的视角图示举例会更加直观清楚——以C代指指挥官,L{i}代指副官i:
- OM(1) :副官3是叛徒——副官2的视角-
步骤:
  • 指挥官将v发送给所有副官
  • L1将v发送给L2 | L3将x发送给L2
  • L2计算收集到的消息可知:v是大多数,L2 ←majority(v,v,x) == v
最终决定取决于L1, L2, L3中的多数票,因此达成了共识。
要记住的重要一点是该算法旨在让多数副官选择相同的决定,而非某一决定。
让我们探究一下指挥官叛变的情况:
- OM(1) :指挥官是叛徒-
步骤:
  • 指挥官分别向L1, L2, L3发送 x, y, z
  • L1 向L2, L3 发送x | L2向L1, L3发送y | L3向L1, L2发送z
  • L1 ← majority(x,y,z) | L2 ← majority(x,y,z) | L3 ← majority(x,y,z)
因为三位副官得到的值相同,因此达成了共识。此处请略微思考一下,即使x, y, z均不相同,对于三位副官来说majority(x, y, z)得出的值也是一样的。在这种情况下,x,y,z是完全不同的指令,我们可以假定他们采取了默认选项撤退
如果你想了解更具体实际的方法以及7位将军两位叛徒这样更复杂的例子,我建议你阅读[url=https://ethfans.org/posts/%5Bhttp://marknelson.us/2007/07/23/byzantine/%5D(http://marknelson.us/2007/07/23/byzantine/)]这篇文章[/url]

拜占庭容错
拜占庭容错定义了一类系统的特征,即允许出现属于拜占庭将军问题的错误。拜占庭容错是最难的一类[url=https://ethfans.org/posts/%5Bhttps://en.wikipedia.org/wiki/Failure_cause%5D(https://en.wikipedia.org/wiki/Failure_cause)]容错模式[/url]。它没有限制条件,也没有对节点可能做出的行为进行假设(例如,一个节点在充当一个诚实的参与者之时可以生成任意数据)。
拜占庭容错是最难解决的。航空发动机系统、核能工厂,以及几乎所有依靠大量传感器的结果决定行动的系统都需要拜占庭容错。甚至连 SpaceX 都[url=https://ethfans.org/posts/%5Bhttps://lwn.net/Articles/540368/%5D(https://lwn.net/Articles/540368/)]认为其系统对此有着潜在需求[/url]
上一节提到的算法是拜占庭容错以及叛徒人数不超过将军人数的 1/3 的情况。此外还存在其它能使该问题更容易解决的方案,其中包括使用数字签名或在网络中设置节点之间的交流限制。

这些都跟区块链有什么关系?
从定义上来看,区块链是不受任一中心主体控制的分布式账本。由于这些账本内蕴藏的价值,不良参与者有着极大的经济激励来试图引发错误。此即表明,区块链很需要拜占庭容错,即解决拜占庭将军问题的方案。
在没有拜占庭容错的情况下,一个节点能够发送并发布错误交易,极大地破坏区块链可靠性。更糟糕的是,没有中心主体能够掌握控制权并且修复损伤。
正如中本聪在这封邮件中深入描述的那样,比特币的问世带来了一项重大突破,即使用工作量证明作为拜占庭将军问题的概率解决方案。

结论
在本文中,我们讨论了分布式系统共识的几个基本概念。
在下一篇文章中,我们将讨论和比较一些用于区块链、实现拜占庭容错的算法。
谢谢James Martin Duffy。
如果你喜欢本文:
请访问Loom Network的网站
Github | Medium| Twitter
联系我们:team@loomx.io

原文链接: https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
作者: Georgios Konstantopoulos
翻译&校对: 闵敏 & Elisa


本帖被以下淘专辑推荐:

回复

使用道具 举报

594

主题

957

帖子

3399

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
3399
 楼主| 发表于 2018-4-22 15:40:12 | 显示全部楼层
工作量证明和权益证明
第一节(编者注:中译本见文末)中,我们探讨了拜占庭将军问题的概念,如何实现拜占庭容错,以及二者与区块链之间的关系。
上一篇文章中提到的算法实际上是实现拜占庭容错的一种解决方案。然而,该方案还不够有效,其变化方案又存在局限性,网络中的叛徒人数不能超过将军人数的1/3。
-通过由 Lamport、Shostak和Pease 提出的算法解决拜占庭问题的运行时间(n=参与者人数,m=叛徒人数)-
这将我们引向了计算机科学的一个经典问题:
我们能做得更好吗?
本文的主题是讨论实现拜占庭容错的替代性算法。
注意:请原谅我对部分内容有所简化。这些算法背后有很多复杂的研究。我会在论述过程中提供链接,以便感兴趣的读者进一步研究。
区块链使用共识算法选择一名领导者,以决定下一个区块内容。
该领导者还负责将该区块在网络中广播出来,以便其他节点能够核实其内容的有效性。

工作量证明(PoW)
对于比特币和以太坊等各有特点的虚拟货币来说,工作量证明是目前最流行的算法,应用于各种加密货币如比特币和以太坊,每个版本有各自的区别。
在继续论述之前,先为非技术类读者介绍一下:
哈希函数是可以用来将任意长度的数据映射为固定长度的数据的函数¹
如果一个哈稀函数是安全的话,其输出值与随机数无异。
示例:keccak256("hello") = 1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8keccak256("hello1") = 57c65f1718e8297f4048beff2419e134656b7a856872b27ad77846e395f13ffe
工作量证明中,为了选出一位参与者成为领导者并选择下一个加入区块链的区块,参与者必须解决一个特定的数学问题。
这个数学问题可能是:
已知数据X,找到一个数字 n,使得n附加到 X的结果的哈希值是一个小于 Y的数字。
示例——hash即一个假定的哈希函数,其输出值如下Y = 10, X = 'test'hash(X) = hash('test') = 0x0f = 15 > 10hash(X+1) = hash('test1') = 0xff = 255 > 10hash(X+2) = hash('test2') = 0x09 = 9 < 10  问题解决
由于上述示例使用的哈希函数具备加密安全性[1,2],要想解决该问题只能依靠蛮力(即尝试所有组合)。换言之,从概率上来说,在大多数时候第一个解决上述问题的参与者是拥有最多算力的人。这些参与者也被称为矿工
哈希函数之所以取得了广泛的成功主要是因为其具备以下特性:
  • 对于给定问题很难找到解决方法
  • 一旦找到问题的答案,很容易就能证实它是对的
挖出一个新的区块,矿工就会得到一些代币奖励(区块奖励、交易费),以此激励他们继续挖矿。在工作量证明中,其它节点通过检验该区块数据的哈希值是否小于预设值来验证该区块的有效性。
由于算力的供给有限,抑制了矿工的作弊行为。攻击网络的成本很高,因为除了要投入高昂的硬件和电力成本,还会造成潜在挖矿利润的流失。
该图片很好地显示了比特币等代币是如何使用工作量证明来抵挡恶意攻击的。
如果有读者对链分裂(即分叉或链重组)是如何在有争议的情况下发生感兴趣的话,建议阅读这篇文章
工作量证明提供了所需安全性,并且迄今为止已被证明很有效。但是这[url=https://ethfans.org/posts/%5Bhttps://thenextweb.com/hardfork/ ... ctricity-africa/%5D(https://thenextweb.com/hardfork/ ... electricity-africa/)]非常耗电[/url]
几乎所有非洲国家(各自)的耗电量都比不上比特币矿业。
权益证明(PoS)
在继续阐述之前,先让我将领导者选举(即选择下一个区块的参与者)类比成彩票:
就彩票而言,从概率上来说,如果Bob买的彩票比Alice多,他赢的可能性就会更高。
同理可得:
就工作量证明而言,如果Bob拥有的算力和电力都比Alice多——因此能够计算出更多的输出值——他赢(挖出下一个区块)的可能性就会更高。
同理又可得:
就权益证明而言,如果Bob的权益比Alice多,他赢(“挖出”下一个区块)的可能性就会更高。
权益证明用权益替代了工作量证明在电力和算力方面的要求。权益指的是参与者在一段时间内愿意锁定的代币量。作为回报,他们成为下一个领导者并选择下一个区块的可能性是与他们所下的赌注成正比的。目前有几种代币使用纯权益证明,如Nxt和Blackcoin等。
权益证明的主要问题是所谓的“无利害关系(nothing at stake)”问题。从本质上来说,该问题主要是,在出现分叉的情况下,权益持有者有动机在由分叉形成的两条链上都下赌注,更有可能出现双重支付问题。欲知详情,请点击此处
为了避免上述问题,混合共识算法出现了,例如Decred就使用了工作量证明和权益证明的结合算法。以太坊基金会通过 Casper The Friendly GhostCasper The Friendly Finality Gadget对安全的分布式权益证明协议进行了积极的研究。

结语
在本文中,我们讨论了工作量证明和权益证明的概念。目前,它们都是实现拜占庭容错的共识算法,实际运用于如今的区块链系统之中。
其他共识算法还包括实用拜占庭容错(即PBFT,Practical Byzantine Fault Tolerance,用于Tendermint)和分布式拜占庭容错(即Distributed Byzantine Fault Tolerance,用于NEO)等。PBFT和Casper之间的比较可见此处
谢谢James Martin Duffy。


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|Hi,Tokens  |网站地图 | Swtc行情

GMT+8, 2019-6-18 03:22 , Processed in 0.150047 second(s), 5 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表