【分布式共识4】POW共识算法

先说比特币是如何通过Pow算法解决拜占庭将军问题的。

比特币

2008年，中本聪推出了一种点对点的电子现金系统——比特币。 比特币的基石是拜占庭共识协议。 比特币如何实现拜占庭共识协议将在下一章介绍。但首先，稍微了解一下比特币

贸易

比特币协议提供了一种数字货币的交易方式，每个人都可以就货币所有权和交易顺序达成共识。 货币所有权通过公钥确定。 全网需要就货币数量和货币所有权之间的关系达成共识。 可以通过签署转账交易（从一个账户到另一个账户）来转移货币所有权。 整个网络需要能够解决同样的钱不能花两次的问题。 由于没有能够验证交易的中央机构，因此需要在没有受信任的第三方的情况下解决这个问题。 也就是说，需要用去中心化的方式来解决这个问题。

解决方案：将每笔交易公开广播到网络中，网络中的节点可以有效地就先到达的交易达成共识。 每个节点检查先到达的交易的输出之前是否被花费。 困难在于：由于网络通信不及时（异步网络），所有节点收到的交易并不完全一致。 在这种情况下，很难就哪个交易先到达达成共识。 为了就交易顺序达成共识，交易在包含工作证明的块中加上时间戳。

该方法为交易顺序共识提供了一种解决方案：区块包含前一个区块的哈希值，以及最新的交易。

工作证明工作证明

为了实现交易的时间戳，Hash 交易数据。 比特币使用工作量证明方法。 网络中的每个节点都参与解决中等难度的密码难题。 问题的解决方法是：对区块中的所有数据进行SHA256哈希运算，得到的哈希值小于给定的目标值。 该块还包含一个 Nonce 值，通过递增 Nonce 来找到正确的哈希值。 此密码谜题旨在每 10 分钟找到一个谜题答案。

一旦找到正确的散列，节点就会将散列广播到网络。 这个哈希值很容易被网络中的其他节点验证，节点收到区块后可以对区块中的数据进行SHA256运算哈希值。

花费的 CPU 就是工作证明。 修改一个块需要重做这个块和这个块之后的所有块的工作量证明。 这意味着比特网络更倾向于最诚实的链，只要网络中的大多数节点都是诚实的。

Pow 的过程可以看作是投票的过程。 每一个新加入的区块都会累积之前的历史交易（区块串联起来形成一条链），每个节点会不断地投票给得票数最多的那条链。

攻击比特币网络

现在考虑一个可以存在于网络中的攻击。 恶意节点试图对先前花费的交易进行双花。 攻击者需要重做包含该交易的区块，以及该区块之后的所有区块，从而创建比当前诚实区块链更长的区块链。 只有当网络中的大多数节点切换到攻击者创建的区块链时，攻击者的攻击才会成功。 考虑包含在区块 b1 中的交易 T。 每个后续区块 b2, b3, b4, ... bn 都会降低交易 T 被修改的可能性，因为修改这些后续区块需要更多的计算能力。 中本聪用概率论证明，攻击者在六个区块后追上最长链的可能性降低到 0.0002428%。 在四个或更多块之后，这个概率下降到 0.0000012%。 每增加一个新的区块bn，被攻击的可能性就会呈指数下降，很快整个攻击的可能性就会低到可以忽略不计。 在实践中，比特币交易会在六个区块后得到确认，因为在这种情况下，攻击者追上的可能性很低比特币共识算法，可以认为交易有效，不会被修改。

工作量证明 Pow 实现拜占庭共识

现在让我们看看比特币的工作量证明如何解决计算机网络中的拜占庭将军问题。 比特币网络在没有中心化机构的情况下就交易顺序达成共识，拜占庭将军也是这样做的。 拜占庭将军需要进攻城堡，所有将军需要就任何将军何时可以提出进攻达成一致。

方案一：所有将领接受的攻击方案被认为是正式的攻击方案。 问题是：两个或更多的将军可能会同时发布不同的攻击计划。

这个问题模型通过工作量证明得到了简化。 在比特币工作量证明系统中，交易的顺序不被追踪，而是在将军之间达成共识。 每个将军根据工作证明解决一个适当难度的哈希难题。 每个谜题都有足够的难度。 只有当所有将军同时工作时，平均10分钟才能找到解谜的方法。 当将军找到问题的答案时，它会通过网络广播答案以及攻击计划。 一旦收到解决方案，每个将军都会根据广播中收到的攻击时间和攻击计划调整拼图。 然后将军继续解决下一个工作量证明。 这样，每个解都会在第一个解之后串联起来，形成一条链。 如果将军仍在对不同的攻击方案执行工作量证明计算，它将切换到最长的链。 最长的链积累了最多的 CPU 计算能力。

平均一小时后，这条链上就会有六个区块。 每个将军可以确定是否有足够的将军在最长的链上工作，并具有相同的初始攻击计划。 该链在一小时内累积到六个区块，表明大多数将军对同一个攻击计划执行工作量证明计算（CPU 投票）。 于是将军们就进攻时间达成一致。

综上所述

在不存在中心化权威的 P2P 网络中，比特币共识协议在功能上等同于一个受信任的中心化权威。 该协议解决了拜占庭将军问题中缺乏中央集权的问题。 帮助将军们就进攻时间达成共识。 此外，它还降低了同时提交多个攻击计划的可能性，同时也降低了攻击的可能性。 因此，比特币共识协议 Modern Byzantine Generals 中出现了问题。

拜占庭将军问题与比特币

拜占庭将军问题

比特币

攻击时间共识

目标

合法交易的共识

将军们散布在城堡周围

分配

节点分布在网络中

忠诚的将军和中尉

好的

可信节点

叛徒

坏的

邪恶节点

Tampering with messages（干扰忠诚将军之间的共识）

破坏

将无效和非法交易添加到区块中

我怎么知道这个消息是真的？

困难

如何知道交易是否合法

还没

解决方案

战俘

还没

共识

区块链+POW

Pow 如何运作

#!/bin/python

导入系统

导入时间

导入哈希库

从结构导入解包，打包

timestamp = str(time.time()) # 工作时间戳

message = "这是一条随机消息。" # 明文消息

随机数 = 0

猜测 = 99999999999999999999

有效负载 = 时间戳 + 消息

油门 = 100000000

目标 = 2**64 / 油门

payloadHash = hashlib.sha256(payload).digest()

开始=时间。 时间（）

而猜测>目标：

随机数 += 1

guess,=unpack('>Q',hashlib.sha256(hashlib.sha256(pack('>Q',nonce)+payloadHash).digest()).digest()[0:8])

打印（猜测）；

结束=时间。 时间（）

print "%s:%s:%s:%s:%s:%s:%s" %（时间戳、消息、随机数、猜测、有效负​​载、目标、结束-开始）

l timestamp 开始生成区块的时间戳

l message类似于Bispecial中的transaction，这里只是演示用字符串代替

l payload 是你要加密的东西的组合。

l nonce会从0增加到N，直到找到目标

l guess会保存答案，初始初始化为无穷大

l throttle相当于比特币中的难度

l target8字节的最大整数值（2^64）除以难度（throttle）

Timestamp, message, payload 就是你要发给网络的东西，可以是block data

Nonce、guess 和 throttle target 用于执行工作量证明计算。 Pow最重要的一点就是生成难，验证容易。

而猜测>目标：

随机数 += 1

guess,=unpack('>Q',hashlib.sha256(hashlib.sha256(pack('>Q',nonce)+payloadHash).digest()).digest()[0:8])

这三行是Pow算法的主要内容。 这是一个简单的循环。 它使用 SHA256 对数据进行两轮哈希处理。 前八个字节作为我们的答案。

比特币的除数（难度）在 2016 个区块后调整为增加或减少。 上图显示比特币共识算法，随着难度的增加，正确答案的可能取值范围缩小 ，也就是越难猜到

随机数 += 1

Nonce表示CPU的工作量。 在此示例中，随机数表示找到低于目标的猜测的累积工作量。 由于每次猜测都有可能低于目标值，因此它与随机数的生成方式无关。 因此，从 0 开始递增 nonce 比生成随机数更便宜。 当一个块被提交到网络时，将使用随机数来证明该块的正确性。

guess,=unpack('>Q',hashlib.sha256(hashlib.sha256(pack('>Q',nonce)+payloadHash).digest()).digest()[0:8])

猜测是经过两轮 SHA256 哈希后的 nonce 和 payload 的前 8 个字节。 因为target的范围是0..2^8，guess不可能超过target。 在每次循环之后，随机数是唯一会改变的值。

向网络提交随机数是安全的。 因为每个矿工的载荷都是独一无二的。 如果矿工Alice使用矿工Bob提交的nonce，Alice需要提供相同的payload，因为Alice不能在payload中放入Bob的公钥和自己的公钥，因为这会改变两轮SHA256哈希的输出. 改变后的输出必须满足小于目标的条件。 由于 Alice 的有效负载与 Bob 的有效负载不同，Bob 的随机数不适用于 Alice。