从哈希运算到拜占庭将军

比特币的共识算法使得人类历史上首次完成了拜占庭将军问题（Byzantine Generals Problem）的求解。

拜占庭将军问题是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或不存在本问题。这个难题也被称为“拜占庭容错”、“拜占庭将军问题”、或者“两军问题”。

比特币网络是如何解决拜占庭将军问题的？先得从上一篇《数字指纹》说起。

公开的账本

上一篇文章

《数字指纹》

中提到SHA-256具有输入数字内容与输出哈希唯一对应的特点。

利用这一特点，将一个账本里的所有信息进行哈希运算得到一个哈希值，将其放到P2P网络上让所有的人都知道，这样大家都可以参与对该账本内容的验证工作，只要结果与公布的哈希值一致，则说明该账本的内容没有被篡改过。

按照时间顺序对该时间段内生成的账本进行依次验证，并且每次将前一个账本的哈希值作为这个账本的内容一起进行哈希，这就使得之前的所有账本与新增的账本产生关联。当一个账本的内容被篡改，不但会使该账本哈希值改变，同时会使得其后的所有账本哈希值改变。

一段时间内交易的集合，即账本就是区块block，其中还包括了上一个区块的哈希、创建时间、区块链难度、随机数nonce等；将一个个账本串联起来的哈希值，就是链chain。将账本哈希后放在P2P网络上，这样既实现了账务公开，又可以随时被查验，从而增加了账本的可信度。

但有一个关键问题，如何才能确保在P2P网络上第一个公布账本哈希的节点本身是可信的？又或如何防止验证账本的节点互相窜通故意作恶？即如何解决拜占庭将军问题。

基于博弈论的共识算法

比特币网络给的解决方法是采用工作量证明（Proof-of-Work），简单说就是：让坏人付出代价，让好人得到奖励。

对账本进行一次哈希所需的算力显然微不足道。但如果在账本内增加一个随机数nonce，每次对区块哈希后nonce都会生成一个全新的随机数，同时要求区块哈希运算后的值小于某个数（哈希头部要达到足够多的），这样就必须对区块进行多次哈希运算后才可以得到正确的哈希值。

对于SHA-256的哈希值，即256个比特来说，要得到头部是的概率50%，00的概率25%，000的概率12.5%......以此类推，哈希头部越多，数值越小，则所需的尝试的运算次数越多。

下图可以看出，想要得到满足系统给出的难度值，即足够小的哈希值，运算的次数就必须足够多。

对于记账的矿工来说，足够多的哈希运算次数就意味着需要足够大的算力，而提供算力是需要消耗电力的，也就是说想要在比特币网络参与记账工作，必须要消耗电力，这就设置了参与门槛。如果记错账了，不但得不到奖励，还要白白付出电力成本。

如果一个记账节点所投入的算力越大，他单位时间内可以进行的哈希运算次数就越多，那么他就越有可能第一个找到足够小的哈希值。比特币网络约每10分钟出一个块，目前对于10分钟内第一个找到满足系统难度要求的哈希值，即区块哈希值足够小的节点，给予12.5个比特币的奖励。

类比：数独游戏

比特币网络的规则与数独游戏类比再合适不过，且非常容易理解。

将比特币网络看成是全球每10分钟举行一次的数独游戏竞赛，只要你认为比赛规则是公平的，交报名费（电费）就可以随时参与比赛。这里聚集了全球顶级的脑力（算力）高手，因为第一名奖金丰厚（区块奖励）。比赛规则是：谁第一个用最短的时间求解到数独游戏的答案（最小哈希值），并将经过其他参赛选手的检查确认正确后（全网广播后其他矿工验证），即可获得奖金，与此同时开始下一轮的数独游戏。

数独游戏的共识是：第一个填出正确答案的选手大概率脑力最强，理应获得奖金；比特币网络的共识是：第一个算出正确哈希值的矿工大概率算力最强，理应获得区块奖励。