“区块链研习”是雷锋网推出的区块链技术研习系列,本系列将收罗学界与业界大咖技术研究与应用实践中的真知灼见,以飨读者。本文作者为中国信息通信研究院(工信部电信研究院)专家敖萌博士,记者独家特约文章,撰写网站与信通院联合首发。未来,敖萌博士原创的区块链系列文章还将继续刊出,撰写网站与信通院相关平台同步更新,敬请关注!

区块链11

上一篇我们简单提到了拜占庭将军问题:拜占庭的n个将军围攻一个敌人,n个将军包围着这个敌人,所以他们是在不同的地方。忠诚的将军希望通过某种协议达成某个命令的一致(比如约定某个时间一起进攻)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。如果同时发起进攻的将军数量少于m个,那么不足以歼灭敌人反而容易被敌人全部歼灭。怎样做才能保证有多于m个将军在同一时间一起发起进攻?

“拜占庭将军问题”模型中,对于将军们(节点)有两个默认的假设:

所有忠诚的将军收到相同的命令后,执行这条命令得到的结果一定是相同的;

如果命令是正确的,那么所有忠诚的将军必须执行这条命令。

假设1的含义是:所有节点对命令的解析和执行是一样的,这个命令必须是一个确定性的命令,不能存在随机性,也不能依赖节点自身的状态。(这个命令不能是心情好就攻击敌人,心情不好就原地休息。)

假设2的含义是:忠诚的将军需要判断接收到的命令是不是正确的。这个判断命令的方法是整个拜占庭容错技术的核心。

对于将军们的通信过程,在“拜占庭将军问题”中也是有默认假设的:点对点通信是没问题的。也就是说,在这里,我们假设A将军要给B将军一条命令X,那么派出去的传令兵一定会准确的把命令X传递给B将军。

有了上述假设,我们来看看将军们面临的核心问题是什么。

我们考虑4个将军的情况,同时假设4个将军中最多只有1个背叛者。当4个将军A、B、C、D把敌人包围了之后,必须协商一个统一的时间去发起进攻。这时,A将军派出了3个传令兵,分别告诉B、C、D将军,下午1点准时发起进攻。到了下午1点,A、C、D三个将军发起了进攻,歼灭了敌人,同时他们三个发现B是背叛的。虽然B背叛了,但是对最终任务没有影响。

拜占庭

但如果A是背叛的,会发生什么情况?A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。于是,到了下午1点,B将军去攻击敌人,由于寡不敌众,全军覆没;2点,C将军全军覆没;3点,D将军全军覆没。

因为对于忠诚的将军来说,他不知道谁是背叛者,所以,他不能完全相信接收到的命令,他必须对命令做出判断。在1999年,著名的PBFT算法出现了。这个算法说起来也不难理解,他的核心思想是:对于每一个收到命令的将军,都要去询问其他人,他们收到的命令是什么。

拜占庭1

回到刚才的第二种情况(A是背叛者),A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。B将军派出传令兵去告诉C和D两位将军,B收到的命令是下午1点进攻。C也同样派出了传令兵分别告诉B和D两位将军,C收到的命令是下午2点进攻。D也同样告诉B和C两位将军,D收到的命令是下午3点进攻。于是,B得到了3条指令:A命令B下午1点进攻,A命令C下午2点进攻,A命令D下午3点进攻。B很容易判断出来,A是背叛者(因为B知道最多只有一个背叛者)。C和D也能做出同样的判断。因此这次进攻时间的协商是无效的。

A

采用了这种办法以后,另一种情况又会怎样?当B是背叛者,A将军派出了3个传令兵,分别告诉B、C、D将军,下午1点准时发起进攻。B告诉C说B收到的命令是下午2点,B告诉D说收到的命令是下午2点,C和D分别告诉另外2个将军,A告诉他们的命令是下午1点。

B

C

于是,C、D收到的消息都是两个1点,一个2点。对于C、D而言,不需要判断是A和B谁是背叛者——他们只需要执行收到多的那个命令就可以了。

如果A是忠诚的,那么B是背叛的,这种情况下对于A来说,他知道自己是忠诚的,他发出的命令,至少有2个将军会执行,所以下午1点,A、C、D三个将军一起去进攻,有3个将军一起发起攻击,敌人被歼灭了。如果B是忠诚的,那么B会收到两个1点一个2点,B也会执行收到多的命令,于是B、C、D三个将军一起去进攻,有3个将军一起发起攻击,敌人被歼灭了。不管怎样,按照这种方式执行,结果是没问题的。

D

采用PBFT方法,本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息,通信代价是非常高的。通常采用PBFT算法,节点间的通信复杂度是节点数的平方级的。

注意,上面所讨论的所有情况里,还有一个假设:所有传递的消息都是口头消息。意思就是,A告诉B下午1点进攻,B可能告诉C说“A命令我下午2点进攻”。如果采用了书写的消息,那么情况是不一样的。A派传令兵给B一张纸,A将军用自己独特的笔迹写的“下午1点进攻”,然后要求B把这张纸传给C,B在纸上用自己独特的笔迹签名表示同意,然后B传给C,C也签名表示同意,然后D也同意,最后签过所有名的纸再给每个人看一眼,就可以让所有节点一致了。这种采用书面签名消息的情况,对算法要求简单得多。但是,采用书面消息的前提是:每个将军都知道其他将军的笔迹是什么样的,并且无法模仿其他将军的笔迹。

在PBFT的基础上,又出现了很多变种算法,这些算法往往都带有一些额外的假设。例如:认为发起请求的客户端一定是忠诚的,由客户端去验证节点是否忠诚;认为绝大部分时候将军都是忠诚的,所以降低两两交互核验消息的次数;通过对节点进行分工,来提高整个系统的处理速度;等。这些变种算法由于增加了额外的假设,导致了整个系统的去中心化程度的降低(关于区块链系统去中心化程度的理解,可以参见本系列的第6篇文章)。

但是,对于不同类型的应用场景,有些假设是合理的,有些假设则是不合理的。例如,在类似比特币的代币转账系统中,不能认为客户端是忠诚的,因为客户端很可能会发起双花交易。因此,当企业希望使用区块链技术改进自己的业务或者开展新业务的时候,一定要选择适合自己业务的区块链技术和系统。

关注中国IDC圈官方微信:idc-quan或微信号:821496803 我们将定期推送IDC产业最新资讯

扫描二维码,将会有专人将您拉进“大数据交流群”“云计算交流群”“区块链交流群”“物联网交流群”

查看心情排行你看到此篇文章的感受是:


  • 支持

  • 高兴

  • 震惊

  • 愤怒

  • 无聊

  • 无奈

  • 谎言

  • 枪稿

  • 不解

  • 标题党
2017-09-13 11:58:00
区块链 国土安全局期待初创企业带来区块链解决方案
尽管联邦与州级机构以及当地社区都正在探索区块链应用,但仍需进行更多的工作来解决技术上的一些关键问题。美国国土安全局的科学技术专门委员会(S&T,Science and Technol <详情>
2017-09-13 10:32:00
区块链 区块链技术:下一代技术革命的希望
今天的区块链技术就像20世纪90年代的互联网,那时候人们尚不知互联网为何物,如今中国的网民早已超过5亿,互联网已经极大的改变了人们的生活。 <详情>
2017-09-13 10:20:00
公众号 区块链考前总复习——来来来,划重点了!
扪心自问,在追区块链的过程中,你真的明白它作为全新“信任机器”背后的内在逻辑吗?真的读懂了其在金融、能源等领域的行业应用吗?在技术专家之外,普通爱好者要想全面了 <详情>
2017-09-12 15:28:00
云资讯 微软Azure区块链委员会有了新进展
微软收到客户对于区块链服务的请求的推动,这家软件巨头目前希望它在特定行业的合作伙伴对区块链服务进行竞标。目前,微软正在为创业公司寻求获取收益的机会,同时帮助现有 <详情>
2017-09-12 13:22:00
大数据应用 网信办:要对人工智能安全、区块链安全加大研究力度
中央网信办副主任杨小伟在发言时指出,维护网络安全要加强技术创新和前瞻布局。网络安全是动态的,而不是静态的,互联网领域发展变化非常快,新技术、新应用带来的新问题、 <详情>