区块链之什么是拜占庭将军问题

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

为了解决这个问题，数学家设计了一套算法，让将军们在接到上一位将军的信息之后，加上自己的签名再转发给除自己之外的其他将军。在这样的信息连环周转中，将军们可以在不找出叛徒的情况下达成共识，从而保证得到的信息和作出的决策是正确的。

区块链通过为发送信息加入了成本，也就是基于计算一个随机哈希算法得到遗传64 位的随机数字和字母组成的字符串的“工作量证明”，并加入了一个随机元素以保证在一个时间只有一个将军可以进行广播，解决了这个问题。

尽管单个哈希值用现在的计算机可以几乎即时的计算出来，但只有一个前13个字符是0的哈希值结果可以被比特币系统接受成为“工作量证明”。这样一个13个0的哈希值是极其不可能与罕见的，并且在当前需要花费整个比特币网络大约10分钟的时间来找到一个。在一台网络中的机器随机的找到一个有效哈希值之前，上十亿个的无效值会被计算出来，这就是减慢信息传递速率并使得整个系统可用的“工作量证明”。那台发现下一个有效哈希值的机器（或者说在我们类比中的城邦），把所有的之前的信息放到一起，附上它自己的，以及它的签名/印章/诸如此类，并向网络中的其他机器广播出去。只要其他网络中的机器接收到并验证通过了这个13个0的哈希值和附着在上面的信息，他们就会停止他们当下的计算，使用新的信息更新他们的总账拷贝，然后把新更新的总账/区块链作为哈希算法的输入，再次开始计算哈希值。哈希计算竞赛从一个新的开始点重新开始。如此这般，网络持续同步着，所有网络上的电脑都使用着同一版本的总账。最后，在个人向网络输入一笔交易的时候，他们使用内嵌在比特币客户端的标准公钥加密工具来同时他们的私钥以及接收者的公钥来为这笔交易签名。这对应于拜占庭将军问题中他们用来签名和验证消息时使用的“印章”。因此，哈希计算速率的限制，加上公钥加密，使得一个不可信网络变成了一个可信的网络，使得所有参与者可以在某些事情上达成一致（比如说攻击时间、或者一系列的交易、域名记录、政治投票系统、或者任何其他的需要分布式协议的地方）。

在分享一篇：


什么是拜占庭将军问题


什么是拜占庭将军问题
也被称为“拜占庭容错”、“拜占庭将军问题”。
拜占庭将军问题是Leslie Lamport（2013年的图灵讲得住）用来为描述分布式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。

这个例子大意是这样的：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的.

问题分析

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

• 先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。
• 再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻， 通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。

  叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

  
  

相信大家已经可以明白这个问题的复杂性了。

中本聪的解决方案
在出现比特币之前，解决分布式系统一致性问题主要是Lamport提出的Paxos算法或其衍生算法。Paxos类算法仅适用于中心化的分布式系统，这样的系统的没有不诚实的节点（不会发送虚假错误消息，但允许出现网络不通或宕机出现的消息延迟）。

中本聪在比特币中创造性的引入了“工作量证明（POW : Proof of Work）”来解决这个问题，有兴趣可进一步阅读工作量证明。
通过工作量证明就增加了发送信息的成本，降低节点发送消息速率，这样就以保证在一个时间只有一个节点(或是很少)在进行广播，同时在广播时会附上自己的签名。
这个过程就像一位将军A在向其他的将军（B、C、D…）发起一个进攻提议一样，将军B、C、D…看到将军A签过名的进攻提议书，如果是诚实的将军就会立刻同意进攻提议，而不会发起自己新的进攻提议。

以上就是比特币网络中是单个区块（账本）达成共识的方法（取得一致性）。

理解了单个区块取得一致性的方法，那么整个区块链（总账本）如果达成一致也好理解。
我们稍微把将军问题改一下：假设攻下一个城堡需要多次的进攻，每次进攻的提议必须基于之前最多次数的胜利进攻下提出的（只有这样敌方已有损失最大，我方进攻胜利的可能性就更大），这样约定之后，将军A在收到进攻提议时，就会检查一下这个提议是不是基于最多的胜利提出的，如果不是（基于最多的胜利）将军A就不会同意这样的提议，如果是的，将军A就会把这次提议记下来。



经济学分析

工作量证明其实相当于提高了做叛徒（发布虚假区块）的成本，在工作量证明下，只有第一个完成证明的节点才能广播区块，竞争难度非常大，需要很高的算力，如果不成功其算力就白白的耗费了（算力是需要成本的），如果有这样的算力作为诚实的节点，同样也可以获得很大的收益（这就是矿工所作的工作），这也实际就不会有做叛徒的动机，整个系统也因此而更稳定。

很多人批评工作量证明造成巨大的电力浪费，促使人们去探索新的解决一致性（共识）问题的机制：权益证明机制（POS: Proof of Stake）是一个代表。在拜占庭将军问题的角度来看，它同样提高了做叛徒的成本，因为账户需要首先持有大量余额才能有更多的几率广播区块，POS不是本文重点，以后在讲。

共识算法的核心就是解决拜占庭将军问题（分布式网络一致性问题）。