共识算法

为了让整个P2P网络保持相同的数据，同时保证每个参与者的公平性，整个系统的所有参与者必须有一个统一的协议，也就是我们这里要说的共识算法。 所有比特币节点都遵循统一的协议规范。 协议规范（共识算法）由相关的共识规则组成，可分为两大核心：工作量证明和最长链机制。 所有规则（共识）的最终体现是比特币的最长链。 共识算法的目的是保证比特币一直运行在最长的链上，从而保证整个记账系统的一致性和可靠性。

工作证明

工作量证明（POW）可以简单理解为确认你做了一定工作量的证明。 监控工作的整个过程通常是极其低效的，而通过证明工作结果来证明相应的工作量已经完成是一种非常高效的方式。 比如在现实生活中，毕业证、驾照等，也是通过检验结果（通过相关考试）来证明的。

一、产地

工作量证明系统（或协议、函数）是一种针对拒绝服务攻击和其他服务滥用的经济对策。 它需要发起者进行一定量的计算，这意味着计算机需要消耗一定的时间。 这个概念最早是由 Cynthia Dwork 和 Moni Naor 在 1993 年的一篇学术论文中提出的[1]。 Proof of Work 一词实际上是在 Markus Jakobsson 和 Ari Juels 于 1999 年的文章 [2] 中提出的。

Hash Cash [3] 是 Adam Back 于 1997 年发明的一种工作量证明机制，用于抵抗邮件拒绝服务攻击和垃圾邮件网关滥用。 在比特币之前，hash cash 被用于垃圾邮件过滤，也被微软用在了 Hotmail/Exchange/Outlook 等产品中（微软使用了一种与 hash cash 不兼容的格式，并将其命名为 e-mail stamp）。

Hal Finney 还以可重用工作量证明 (RPOW) 的形式在前比特币加密货币实验中使用了 Hashcash。 另外，戴维的B-money，Nick Szabo的Bit-Gold，这些比特币的先驱都是在hash cash的框架下挖矿。

2. 工作量证明的基本原则

工作量证明系统的主要特点是客户端需要做一些困难的工作才能得到一个结果，而验证者可以很容易地通过结果检查客户端是否做了相应的工作。 该方案的一个核心特征是不对称性：工作对请求者来说是适度的，对验证者来说很容易验证。 它不同于验证码，验证码的设计出发点是人类容易破解而计算机不易破解[4]。

下图显示了工作证明的过程。

例如[5]，给定一个基本字符串“Hello, world!”，我们给出的工作量要求是可以在这个字符串后面加上一个叫做nonce（随机数）的整数值，用于对字符串进行SHA-256哈希运算改变字符串（加入nonce后），如果得到的哈希结果（以16进制表示）以“0000”开头，则验证通过。 为了实现这个工作量证明的目标。 我们需要不断递增 nonce 值，并对获得的新字符串进行 SHA-256 哈希运算。 根据这个规则，需要 4251 次计算才能找到前 4 位恰好为 0 的散列。

“你好，世界！0”=> 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64

“你好，世界！1”=> e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8

“你好，世界！2”=> ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7

...

“你好，世界！4248”=> 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965

“你好，世界！4249”=> c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6

“你好，世界！4250”=> 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

通过这个例子，我们对工作量证明机制有了初步的了解。 有人认为，如果工作量证明只是这么一个过程，是不是只需要记住nonce是4521，计算就可以通过验证呢？ 当然不是，这只是一个例子。

接下来，我们简单的把输入改成“Hello, world+整数值”，整数值的范围是1到1000，也就是说输入变成了一个1000个值的数组：Hello, world！ 1; 你好世界！ 2;...;你好，世界！ 1000. 然后，对于数组中的每个输入，依次执行上例中要求的工作量证明——找到前面有 4 个 0 的 hash hash。

由于哈希值的伪随机性，根据概率论的相关知识很容易计算得到。 预计需要 216 次尝试才能获得 4 个前导 0 的哈希值。 而如果统计一下刚才1000次计算的实际结果，你会发现平均计算次数是66958次，非常接近216次（65536次）。 在这个例子中，数学期望的计算次数就是需要的“工作量”，重复多次的工作量证明将是一个符合统计规律的概率事件。

统计输入字符串列表和实际计算得到相应目标结果的次数如下：

你好世界！ 1=>42153

你好世界！ 2=>2643

你好世界！ 3=>32825

你好世界！ 4=>250

你好世界！ 5=>7300

...

你好世界！ 995=>164819

你好世界！ 996=>178486

你好世界！ 997=>22798

你好世界！ 998=>68868

你好世界！ 999=>46821

比特币系统中的工作量证明机制与上面的例子类似，但比它复杂一点。

3. 比特币的工作量证明

对于比特币网络中的任何一个节点来说，如果要生成一个新的区块并将其写入区块链，就必须解决比特币网络的工作量证明难题。 本题的三个关键要素是工作量证明函数、区块和难度值。 工作量证明函数是这道题的计算方式，区块决定了这道题的输入数据，难度值决定了理解这道题需要的计算量。

比特币网络中使用的工作量证明函数就是上面提到的 SHA-256。 区块的数据结构上面已经提到了，但是区块的生成过程并没有详细描述。 块实际上是在工作量证明链接期间生成的。 矿工不断构建区块数据，检查计算结果是否满足工作量，从而判断区块是否满足网络难度。 区块头是比特币工作量证明的输入数据。

难度值是矿工挖矿的重要参考指标，它决定了矿工需要经过多少次哈希运算才能产生一个合法的区块。 比特币区块大约每 10 分钟生成一次。 如果新区块的生成要在不同的网络算力条件下都保持这个速率，则必须根据网络算力的变化调整难度值。 简单地说，难度值设置为每 10 分钟出一个新区块的速率，与挖矿能力无关。

难度调整在每个完整节点中独立且自动发生。 每2016个区块，所有节点都会根据统一的公式自动调整难度值。 这个公式是根据生成最新的2016个区块所花费的时间和预期时间（预期时间为20160分钟，即两周，根据每10个实际时间与预期时间的比例，使相应的调整（或做难或易），即如果出块速度快于10分钟，则增加难度，慢于10分钟，则降低难度。

这个公式可以总结如下：

新难度值=旧难度值*（过去2016个区块花费的时间/20160分钟）

工作证明需要有一个目标值。 比特币工作量证明的目标值（Target）计算公式如下：

目标值=最大目标值/难度值

其中，最大目标值为常数值：0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

目标值的大小与难度值成反比。 比特币工作量证明的实现是矿工计算的区块哈希值必须小于目标值。

比特币工作量证明的过程我们也可以简单理解为，通过不断改变区块头（即尝试不同的nonce值）并将其作为输入，进行SHA-256哈希运算，找到一个特定格式的nonce。散列值的过程（即需要一定数量的前导0）。 需要的前导 0 越多，就越难。

比特币矿工为解决这个工作量证明难题所采取的步骤可以大致概括如下：

1）生成一个coinbase交易并与所有其他交易组成交易列表打包进区块，通过Merkle Tree算法生成Merkle Root Hash。

2）将Merkle Root Hash等相关字段组装成一个区块头，将区块头的80字节数据作为工作量证明的输入。

3）不断改变区块头中的随机数（即nonce的值），对每一个改变的区块头（即SHA256（SHA 256（Block_Header））进行两次SHA-256运算，并将结果值进行转换反转并与当前网络目标值对应的十进制字符串进行比较。 如果小于目标值，则问题成功解决，工作量证明完成。

该过程可以用下图表示：

比特币的工作量证明就是我们俗称的“挖矿”的主要工作。 理解工作量证明机制，将为我们进一步理解比特币区块链的共识机制打下基础。

最长链机制

比特币网络要求所有节点都遵循一个协议（共识），本地保存的所有区块链必须是本地节点验证过的最长链。 由于区块链的每个区块都必须引用前一个区块，因此最长的链最难推翻。

理论上，矿工可以在任意一个区块的基础上开始计算下一个区块。 但只有最长区块链上的区块才能被系统识别并获得挖矿奖励。 打包一个区块获得的奖励，只有在该区块加入99个新区块（100个确认）后才能使用。 这是保证区块链不分裂的重要机制。

哈希算力攻击

比特币最初是为了实现一个点对点的电子现金系统而设计的，这个系统的问题是如何避免双重支付问题。 共识算法的目标是减少双重支出的可能性。 在中本聪的白皮书中，他对设计的比特币系统进行了数学计算，以验证整个比特币系统双重支付的概率。 在此引用相关原文，让大家感受一下比特币区块链系统的安全性。 性别。

1.计算

想象以下场景：攻击者试图生成一条比诚实链扩展得更快的替代链。 即使这个目标达到了，也不意味着系统可以让攻击者为所欲为，比如凭空造币，或者拿走本不属于他的币。 节点永远不会接受无效交易，诚实节点也永远不会接受包含无效交易的区块。 攻击者唯一可以尝试的就是更改他自己的一笔交易，并尝试从他最近的支出中取回钱。

诚实链和攻击链之间的竞赛具有二项式随机游走（Binomial Random Walk）的特征。 成功事件表示诚实链延长一个区块，领先优势增加1，失败事件表示攻击链延长一个区块，差距减少1。

攻击者成功填补给定缺口的概率类似于赌徒破产问题。 假设一个赌徒有无限透支额度比特币共识算法，然后开始以潜在的无限次赌博来弥补他的亏空，那么我们可以计算出他补足亏空的概率，即攻击链追上诚实链，如下图[6]：

假设 p > q，那么攻击成功的概率会随着攻击者必须赶上的块数的增加而呈指数下降。 概率是攻击者的大敌，如果一开始没有侥幸破局，那么他越落后，成功的机会就变得无限渺茫。

现在考虑新交易的接收者必须等待多长时间，直到他足够确信发送者不再能够更改交易。 假设付款人是一个攻击者，他想让收款人相信他已经付款了，然后在一段时间后把已经付款的钱重新寄回给自己。 付款人希望届时收款人知道，这于事无补。

为此，收款人生成一个新的密钥对，然后在交易签署前不久将公钥发送给付款人。 这避免了付款人预先准备一条链，然后不断地在这个区块上工作，直到他的链幸运地超过诚实链，然后立即执行支付。 在这种情况下，一旦发出交易，攻击者就会悄悄准备一条包含交易替代版本的平行链。

收款人会等待交易出现在第一个区块，然后等到它之后连接了 z 个区块。此时，他仍然无法确切知道攻击者前进了多少个区块，但假设诚实区块将采取出块的平均期望时间，则攻击者的潜在进度服从泊松分布，分布的期望为

在这种情况下，要计算攻击者赶上的概率，请将泊松分布的概率密度乘以攻击者已前进的区块数，再乘以攻击者在给定该数字的情况下仍能赶上的概率：

这简化为以下形式，避免对无限序列求和：

转换为C语言代码[7]：

#include double attackersuccessprobability（double q， int z）{
    double p = 1.0 - q；
    double lambda = z * （q / p）；
    double sum = 1.0；
    int i， k；
    for （k = 0； k <= z； k++）
    {
        double poisson = exp（-lambda）；
        for （i = 1； i <= k； i++）
            poisson *= lambda / i；
            sum -= poisson * （1 - pow（q / p， z - k））；
    }
    return sum；}

对其进行运算，可以得到如下的概率结果，发现概率随着z的取值呈指数下降。

当q=0.1时：

z=0p=1.0000000

z=1p=0.2045873

z=2p=0.0509779

z=3p=0.0131722

z=4p=0.0034552

z=5p=0.0009137

z=6p=0.0002428

z=7p=0.0000647

z=8p=0.0000173

z=9p=0.0000046

z=10p=0.0000012

当 q=0.3 时：

z=0p=1.0000000

z=5p=0.1773523

z=10p=0.0416605

z=15p=0.0101008

z=20p=0.0024804

z=25p=0.0006132

z=30p=0.0001522

z=35p=0.0000379

z=40p=0.0000095

z=45p=0.0000024

z=50p=0.0000006

求解阶数 p

使 p

q=0.10z=5

q=0.15z=8

q=0.20z=11

q=0.25z=15

q=0.30z=24

q=0.35z=41

q=0.40z=89

q=0.45z=340

计算结果表明，无论攻击者算力占全网的比例如何，随着区块链中区块确认次数的增加，重复支付的概率会越来越低。 只有当你拥有比较高比例的算力时，你才能成功，而这其实可以通过增加确认次数来避免。 如果付款方和接收方调整相应的参数作为交易的条件，比如在交易完成前指定N次确认，那么区块链的双花问题在这个体系下就变得异常困难。

2.51%算力攻击

虽然比特币系统的设计已经大大降低了双重支付的可能性，但是没有绝对安全的系统。 当攻击者拥有全网一半以上算力时，就有能力推翻原来已确认的交易，使恶意双花成为可能，业内形象地称之为51%算力攻击。 攻击者掌握了全网51%的算力后，可以利用这些算力重新计算已确认的区块，使区块分叉，完成双花，获取收益。 如果攻击者发起攻击，他可以：

1）控制自己的交易，一个发给接收者，另一个发给自己，这样最后发给自己的交易成功，接收者失败，欺骗接收者，实现双花成功。

2）防止别人的交易被打包成区块，使交易无法确认。

3）阻止他人产生新区块，获得区块奖励。

不能做的事情如下：

1）控制他人发送的交易。

2）防止他人发送交易。

3）改变每个区块的奖励金额。

4）凭空生成硬币。

5）发送不属于他的硬币。

从以上内容不难看出，攻击者实施51%算力攻击的唯一好处就是完成自己交易的双花，对交易接收方进行诈骗。

从经济学的角度来看这个攻击问题，攻击者通过攻击获得收益，但是这需要成本（算力成本）比特币共识算法，只有攻击获得的收益大于成本，并且也大于收益通过他的诚实工作获得，攻击者会自发地发起攻击意图。 一个理智的人，一个为了更大的利益而攻击的人，实际上不会发动这样的攻击。 这就造成了 51% 攻击的悖论。 攻击者在发起攻击时必须考虑自己的利益。 由于成本较高，算力所有者会选择诚实的工作。

除了上述的攻击成本外，攻击实际上取决于社区的理性选择，这也使得攻击的成功率非常低。 历史上，Ghash.io 的算力接近 51%，曾引起社区恐慌。 矿工选择撤离，最终Ghash.io的算力急剧下降。 国内的4个矿池也出现了整体算力接近51%的情况。 2015年，国内矿池联盟配合不遵守社区软分叉协议，产生新版本号的区块，导致区块高度为36731~36736的相关区块不符合社区协议。 此外，其他矿池基于36731生成了新版区块，但并未选择在中国生成的新区块的链上进行挖矿。 这件事也在社区引起热议。 最终，国内几大违反社区协议的矿池将挖出的区块作废，并在符合社区协议的链上挖出新版本号的新区块。 历史上的很多事件已经证明，除了共识算法，社区成员的理性选择也是维护整个区块链系统安全的保障。

共识算法探索

1.战俘

POW 使用的哈希算法在原理上接近于暴力破解过程。 随着比特币的发展和市值的提升，市场上出现了专为比特币使用的SHA-256算法开发的ASIC矿机，使系统总算力不断攀升。 算力的快速提升，不仅降低了挖矿过程的去中心化程度，同时也带来了越来越高的能耗。 这一现象在社区引发讨论。 所以有新的山寨币试图使用不同的哈希算法来证明工作。

山寨币鼻祖莱特币除了修改了比特币的相关参数外，最大的调整是共识算法的改变，将比特币工作量证明使用的SHA-256哈希算法改为Scrypt哈希算法。 不同的是Scrypt hash算法本身不适合并行计算，所以很难制造专业的ASIC矿机。 在实践中，随着莱特币市值的增加，人们也为Scrypt制作了专业的矿机。 竞赛币暗黑币采用的X11算法是将11个哈希算法串联起来作为工作量证明的哈希函数，以防止专业的ASIC芯片矿机。 后来出现了专门针对矿池挖矿的算法SpreadX11，其代表就是山寨币Spreadcoin。

2. 收款机

POS（Proof Of Stake）是一种不同于工作量证明的共识机制。 它不使用竞争哈希计算，而是通过节点的所有权证明来达成共识。 有人认为，随着区块奖励的减少，工作量证明机制最终会导致系统出现“公地悲剧”，而权益证明机制对矿工的激励机制可以更好地维持系统安全。

真正使用POS机制的数字货币是点点币（PPC，PPCoin）。 这里首先要介绍币龄的概念。 在比特币中，UTXO所在区块的高度与当前最长链的高度之差决定了未花费货币的年龄。 差值越大，币龄越高。 Unspent的使用也代表币龄的消耗。 在POS机制中，一笔交易可以消耗的币龄被视为POS的一种形式，POS是指一种货币所有权的证明。 拥有币并拥有更高币龄的节点有权产生新的区块。

三、总结

新的共识算法的发明往往源于工作量证明的能耗优化和专业矿机挖矿的阻力。 很多人都在寻找任意一个节点（通过GPU或者CPU，也就是一台电脑）来参与全网挖矿的方法。 以太坊发明了自己的挖矿算法ethash来对抗拥有专业芯片的矿机，同时宣称将采用POW+POS机制运行整个区块链网络。

此外，大量私有链尝试采用或发明不同的共识算法。 有限的去中心化使我们能够采用更高效和低成本的共识算法。 对于比特币区块链这样的公链，由于需要实现完全去中心化，具有所有节点完全平等、自由加入等特点，相应一定规模的资源消耗几乎是不可避免的。

[1] 德沃克，辛西娅； Naor, Moni (1993)。 “通过处理定价，或者，打击垃圾邮件，密码学的进步”。 CRYPTO '92：计算机科学讲义第 740 期（Springer）：139–147。

[2] 雅各布森，马库斯； Juels, Ari (1999)。 “工作证明和面包布丁协议”。 通信和多媒体安全（Kluwer 学术出版社）：258–272。

[3] 引自。

[4] 引自。

[5] 引自。

[6] W. Feller，概率论及其应用简介，1957 年。

[7] 引自。