如何理解拜占庭将军问题

如何理解拜占庭将军问题

拜占庭将军问题（以下简称“共识问题”）的正式表述是：如何在一个不基于信任的分布式网络中就信息达成共识？这个表述听起来有些晦涩，但其本质并不复杂，下面的例子与共识问题虽然并不完全一致，但却有助于我们的理解[9]。 想象一下在遥远的拜占庭时代，有一个富饶的城邦，金银珠宝绫罗绸缎应有尽有，它的领主哆啦A梦独享着这一切奢华与荣耀。而在城邦的外围，四位拜占庭将军大雄、胖虎、小夫和静香都觊觎着哆啦A梦的财富，于是他们决定联手攻占哆啦A梦的城邦。根据双方的实力对比，必须有超过半数的将军同时发起进攻方能克敌制胜，因此获胜条件就是四人中至少三个人可以就进攻时间达成一致。那么四位将军的胜算有多少呢？ 这个问题的答案就要取决于四个人的合作方式了，如果是集中式系统，有一个盟主，比如胖虎（相当于中央服务器），那么他们的胜利是毫无悬念的，因为就进攻时间达成一致非常简单，只要胖虎召集大雄、小夫和静香开个会讨论一下就可以了，即使大家意见有分歧胖虎也可以在最后予以定夺。下面让我们回到拜占庭将军问题的假设里，在不基于信任的分布式网络中，四位将军的胜算又如何呢？ ? 首先由于四位将军之间缺乏信任，因此聚到小黑屋里开个密...拜占庭将军问题（以下简称“共识问题”）的正式表述是：如何在一个不基于信任的分布式网络中就信息达成共识？这个表述听起来有些晦涩，但其本质并不复杂，下面的例子与共识问题虽然并不完全一致，但却有助于我们的理解[9]。 想象一下在遥远的拜占庭时代，有一个富饶的城邦，金银珠宝绫罗绸缎应有尽有，它的领主哆啦A梦独享着这一切奢华与荣耀。而在城邦的外围，四位拜占庭将军大雄、胖虎、小夫和静香都觊觎着哆啦A梦的财富，于是他们决定联手攻占哆啦A梦的城邦。根据双方的实力对比，必须有超过半数的将军同时发起进攻方能克敌制胜，因此获胜条件就是四人中至少三个人可以就进攻时间达成一致。那么四位将军的胜算有多少呢？ 这个问题的答案就要取决于四个人的合作方式了，如果是集中式系统，有一个盟主，比如胖虎（相当于中央服务器），那么他们的胜利是毫无悬念的，因为就进攻时间达成一致非常简单，只要胖虎召集大雄、小夫和静香开个会讨论一下就可以了，即使大家意见有分歧胖虎也可以在最后予以定夺。下面让我们回到拜占庭将军问题的假设里，在不基于信任的分布式网络中，四位将军的胜算又如何呢？ ? 首先由于四位将军之间缺乏信任，因此聚到小黑屋里开个密谋会的可能性被排除了（一旦在小黑屋里被胖虎绑架了怎么办？）；其次由于没有盟主，四个人的意见都会被同等的看重。在这种情况下，四位将军只能通过信使在各自营地之间传递消息，来商定进攻时间了。比如大雄觉得早上6点是发动进攻的好时机，他就会派信使将自己的意见告诉胖虎、小夫和静香，与此同时，胖虎可能认为晚上9点发动突袭更好，小夫更喜欢下午3点出击，而静香希望是上午10点，他们三人也会在同一时间派出自己的信使。这样一来，在第一轮通信结束后，四位将军每个人都有了四个可供选择的进攻时间，他们各自要在下一轮通信中把自己选定的时间告知另外三人。由于四个人的决策都是独立做出的，因此最终的选择结果就有256种可能，而只有当三人以上都恰好选择了同一时间的时候，共识才被达成，而这样的结果才64种，也就是说达成共识的概率仅为1/4。这还只是四位将军的情况，如果将军的人数是10人，100人，1000人呢？我们稍加计算就可以发现随着人数的增加，达成共识的希望会变得越来越渺茫。 把上面例子中的将军换成计算机网络中的节点，把信使换成节点之间的通信，把进攻时间换成需要达成共识的信息，你就可以理解共识问题所描述的困境了。达成共识的能力对于一个支付系统来说重要性不言而喻，如果你给家里汇了一笔钱买车，第二天去银行核实的时候柜台告诉你“关于你汇了多少钱的问题，我们的系统里有三个版本的记录”，这样的银行你显然是不敢把钱存进去的。在比特币出现之前共识问题是很难被完美解决的，要保证达成共识就需要采用集中式系统（除非节点满足特定条件），要想去中心化共识就无法保证。那么区块链技术又是如何解决这一难题的呢？（关注公众号weoption，回复“区块链”，可查看全文。）