2018-04-30 | 김흥록 기자

[比特币概论]<3>破解计算机科学难题“拜占庭帝国问题”

本页标题和正文均由AI机器翻译,未经人工审校。准确内容请以韩文原文为准。

“所有人都知道X这一事实本身还不够。所有人都必须知道‘所有人都知道X’这一事实,而且全员还必须知道‘我们所有人都知道所有人都知道X’这一事实。这就像拜占庭将军问题一样,是分布式数据系统中一个古老的难题。”

这段咬文嚼字、如同密文的文字,出自一位名叫詹姆斯·A·唐纳德的人物在2008年11月13日早上7时左右发给中本聪的电子邮件。据悉,自2008年中本聪宣布开发比特币的消息之后,詹姆斯·A·唐纳德就围绕此事多次与中本聪往来邮件,并与其共同开展工作。

唐纳德在邮件中谈到的内容,源自计算机网络领域主要探讨的“两将军问题(Two Generals Problem)”。两将军问题此后扩展为“拜占庭将军问题(Bizantine Generals Problem)”。这正是比特币之前多种电子货币系统曾试图解决、却未能完全解决的问题。

分布式账本体系要正常运转,需要跨越的门槛很多。如何保证共享账本的参与者会诚实行事?即便有人试图作弊,是否有办法让所有人持有的账本保持相同内容?这类难题就是比特币中的拜占庭将军问题。

中本聪是用什么方法解决拜占庭将军问题的?

两将军问题是1972年出现的一种假想实验(思想实验)。设想两支友军部队的将军A和B驻扎在敌军占领的一座城市两侧。要攻占敌军,两支部队必须在同一天同一时刻发起进攻,但要互通消息,传令兵就必须亲自穿过敌军的城市。也就是说,消息始终面临被敌军中途截获的风险。

A向B发送了载有进攻日期和时间的消息,但无法确信是否顺利送达。于是B若收到消息,就应向A回复确认,但B同样无法确信这条消息是否安全送达A。为了让B放心并共同发起进攻,A必须再回复说自己已收到回信,但这同样无法保证顺利送达B。结果,A和B两位将军陷入永远无法确信自己最后发出的消息是否送达的境地。这意味着两位将军无法达成同等水平的共识,而这种不确定性最终意味着无法共同进攻敌城。此后,这一问题被证明实际上无法解决。用比特币来说,只要混有潜在的背叛者,参与者就永远无法达到持有相同交易记录的状态。

假设将军不是两名而是多名的情形,就是拜占庭将军问题。正如詹姆斯·唐纳德在邮件中亲自提到的,自1982年莱斯利·兰波特、罗伯特·肖斯塔克和马歇尔·皮斯共同撰写的论文介绍该问题以来,它被视为计算机工程的经典难题。比特币的参与者可能不是两名而是数万名,因此比起两将军问题,有多名参与者的拜占庭将军问题对中本聪而言是更直接需要跨越的障碍。

它与两将军问题相似,但情形略有不同。拜占庭帝国在辽阔疆域的各个地区都由将军统治。要成功进攻邻国,必须在同一天同一时刻集中所有将军率领的兵力,而如果相距遥远的各位将军无法正确传达准确的进攻时间、进攻地点和是否参战,兵力就会分散,进攻随之失败。将军之中可能有间谍,会把进攻命令伪装成撤退命令,而即便是失误,也始终存在传错消息的可能。有没有办法让各位将军之间传递的信息与司令官传达的内容完全一致?或者说,至少在收到错误消息时能否辨别出来?有没有办法让所有人始终保持持有相同答案的状态?寻找这样的答案正是拜占庭将军问题的核心。

唐纳德提出的“全员还必须知道‘我们所有人都知道所有人都知道X’这一事实”,归根结底是在追问:比特币参与者不仅能够无限制地互相交换余额、汇款交易明细等全部信息,是否还有办法确信整个网络持有同一本账簿?这也是在追问:从比特币的所有权到汇款状态、汇款的有效性、账簿的生成过程,整个网络是否有办法不受背叛者影响地对这些信息作出相同的更新。

在比特币出现之前,尤其在计算机工程领域,克服拜占庭将军问题的方法是朝着即便有将军发送错误消息、整个系统仍能运转的方向推进。不妨想想飞机。要让导航装置正确运转,各处安装的传感器必须始终发送相同的高度和位置信息。若哪怕一个传感器给出不同信息,就必须迅速与其他传感器给出的数值比较,决定采用哪个数值。这就是拜占庭将军问题。

重要的是,不能因为某一个传感器给出错误信号,就在飞行中让导航装置停止工作。即便发生拜占庭将军问题,也必须设计成把错误消息就当作错误放在一边、系统继续运转。在计算机工程中,这被称为拜占庭容错(BFT·Bizantine Fault Tolerance)。

学者们查明,BFT最基本的前提是全体参与者中至少三分之二必须是正常工作的善意参与者。当有三个传感器、其中两个正常工作时,即便忽略一个信号,乘客也能安全抵达目的地。实际飞机上至少装有3台以上高度测量设备,还配有以防某个传感器故障的备用传感器。掌握位置信息的惯性导航装置通常也安装3台,此外还会利用从卫星接收位置信息的GPS接收装置或地面飞机位置校正装置的信号。

据称,波音777和787的自动导航装置尤其直接应用了拜占庭容错技术。来听听国内唯一运营波音787机型的Korean Air Lines维修技术部/Avionics技术团队的说明。

“最新的787等飞机所采用的、与拜占庭将军问题相关的容错方法,是在一个传感器上生成多份内容相同的数据,并通过多条线路将其发送到需要数据的设备。自动导航装置被设计为,对通过多条线路收到的相同数据检查是否出现异常信号,并通过相互比较确保完整性。”

归根结底,可以理解为同时增加数据的数量和传输路径,从而用一个传感器取得与安装多个传感器相同的效果。这看起来并不是在数学上保证拜占庭故障不会发生,而是在现实中降低问题发生概率的做法。中本聪采取了与此不同的路径。他让参与者全体能够在数学上被保证持有完全相同的最新账本。

比特币引入了名为POW的共识结构。这正是亚当·贝克和哈尔·芬尼提出的那个概念。POW是为达成某一目标而要求投入一定运算量的方式。(参见比特币概论第1篇)

先看比特币的结构。比特币是把参与者生成的汇款交易数十笔汇集起来,生成最新账本并不断接续下去的结构。用家庭账簿来比喻,账簿的一页在区块链中就是一个区块。

比特币被设计为:把参与者从收到钱到发出钱期间必须遵守的基本规则用特定数字来表示。中本聪让人们在生成新区块时,汇集这些数字,并以此为基础去寻找新区块的唯一编号,这是一种解谜游戏。解谜的过程就是POW,因为要投入运算力。数学谜题被解开后区块就生成,这被称为挖矿。

若执行POW并解开谜题,就意味着这个区块是汇集了遵守各种防作弊规则的正常交易、以正常方式生成的账本。如果最后得出的区块唯一数值是正常的,那么进入计算过程的所有数字也都是正确数值,因此在数学上也能证明可以接受该数值。比特币归根结底具备接受经过POW的区块这一共识结构。通过实时共享经过POW的区块,参与者无需担心其他将军是否作弊,最终所有人始终处于相同的账本状态。银行的角色就这样在比特币系统内消失了。困扰众多P2P电子货币开发者的拜占庭将军问题,随着比特币的诞生找到了解决之道。

举例来说,如果某个参与者制造并散布两笔相互矛盾的交易,会怎样?在比特币中,任何愿意的人都可以执行POW生成区块,因此若相互矛盾的交易各自被装入区块,就会成为问题。相当于将军们各自收到了不同的进攻时间。因此比特币系统要求参与者在执行POW之前,先对收到广播的交易是否存在矛盾进行一次验证。此外,比特币处理矛盾交易的原则是接受先经过POW的交易。也就是说,当将军们收到两笔矛盾交易时,若有任何人执行POW并率先成功把其中一笔放入区块,那么进入该区块的交易就获得认可。载有该交易的区块向整个网络广播后,其他参与者会在验证该区块后予以接受。随后参与者会废弃与该区块内交易相矛盾的交易。

中本聪在其发出的邮件中这样解释:“他们(将军们)并不特别在意进攻时间是什么时候,重要的是所有人都同意。任何人都可以告知时间,先听到的时间就成为正式的进攻时间。”

《精通比特币》的作者安德烈亚斯·安东诺普洛斯在其书中这样记述解决了拜占庭将军问题的比特币的功绩:“这一(利用工作量证明概念的)解决方案在分布式计算科学中取得了划时代的成就,不仅可用于货币,还可应用于其他领域。在选举、彩票、资产登记、数字公证等需要证明公正性的领域,它可用于就分布式网络达成一致。”

/金兴禄记者 rok

阅读韩文原文