编辑“工作量证明（PoW）”

'''工作量证明（PoW）''' 是一种加密证明方式，其中一方（证明者）向其他方（验证者）证明其已经付出了特定数量的计算努力。验证者随后可以以极少的努力确认这一支出。该概念最早在 1993 年由 Moni Naor 和 Cynthia Dwork 在 Hashcash 中实现，作为一种通过要求服务请求方进行一些工作（通常是计算机处理时间）来阻止拒绝服务攻击和其他网络服务滥用（如垃圾邮件）的方法。术语“工作量证明”首次出现在 1999 年 Markus Jakobsson 和 Ari Juels 的论文中，并被正式化。该概念在 2004 年被 Hal Finney 通过“可重复的工作量证明”思想应用到数字代币上，使用的是 160 位安全哈希算法 1（SHA-1）<ref>[https://www.investopedia.com/terms/p/proof-work.asp What Is Proof of Work (PoW) in Blockchain?] By Scott Nevil</ref>。

工作量证明后来被比特币作为去中心化、无需许可的网络共识基础所推广，矿工通过竞争附加区块和挖掘新货币来进行工作，每个矿工的成功概率与其所投入的计算努力成正比。PoW 和 PoS（权益证明）是目前最知名的 Sybil 攻击防范机制，在加密货币的背景下，它们是最常见的机制<ref>[https://www.europarl.europa.eu/cmsdata/150761/TAX3%20Study%20on%20cryptocurrencies%20and%20blockchain.pdf Cryptocurrencies and blockchain] European Parliament. July 2018.</ref>。

工作量证明方案的一个关键特征是其不对称性：计算工作对于证明者或请求者而言必须适度困难（但可行），而对于验证者或服务提供者而言检查起来则非常容易。这一理念也被称为 CPU 成本函数、客户端难题、计算难题或 CPU 定价函数。另一个常见特征是内建的激励结构，通过将计算能力分配到网络上，奖励以加密货币的形式提供价值<ref>[https://chainbulletin.com/proof-of-work-explained-in-simple-terms Proof of Work Explained in Simple Terms] - The Chain Bulletin</ref>。

工作量证明算法的目的是通过设定较大的能量和硬件控制要求来防止数据被操纵，而不是证明某项工作已完成或某个计算难题已被“解决”。工作量证明系统因其能源消耗问题而受到环保人士的批评。

== 背景 ==
工作量证明（PoW）的概念源于早期研究，旨在防止垃圾邮件和拒绝服务攻击（DoS）。PoW 的最早实现之一是 Hashcash，由英国密码学家 Adam Back 于 1997 年创建。它被设计为一种反垃圾邮件机制，要求电子邮件发送者执行一个小的计算任务，从而有效地证明他们在发送电子邮件之前已经消耗了资源（以 CPU 时间的形式）。对于合法用户而言，这个任务是微不足道的，但对于试图发送大量邮件的垃圾邮件发送者来说，执行该任务会产生显著的成本。

Hashcash 的系统基于寻找满足特定标准的哈希值这一概念，这一任务需要计算工作，因此充当了“工作量证明”。其思想是通过让发送大量电子邮件的行为在计算上变得昂贵，从而减少垃圾邮件的数量。

在 Hashcash 中使用的一个流行系统是通过部分哈希反转来证明已经进行过计算，作为发送电子邮件的善意标记。例如，以下标题表示要向 calvin@comics.net 发送一封邮件，需要进行大约 252 次哈希计算：
 X-Hashcash: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE
它通过单次计算进行验证，方法是检查戳记（去除 X-Hashcash: 标头，包括冒号和任何空白字符，直到数字 '1'）的 SHA-1 哈希值是否以 52 个二进制零开头，也就是 13 个十六进制零：
 0000000000000756af69e2ffbdb930261873cd71
PoW 系统是否能够真正解决像垃圾邮件问题这样的拒绝服务问题尚有争议；该系统必须使垃圾邮件发送者发送垃圾邮件的行为变得显著不具生产力，但又不应阻止合法用户发送电子邮件。换句话说，真正的用户在发送电子邮件时不应遇到任何困难，但垃圾邮件发送者必须花费大量计算能力才能一次发送许多电子邮件。工作量证明系统已被更复杂的加密系统所使用，例如比特币，它使用了类似于 Hashcash 的系统。

== 变种 ==
工作量证明协议有两类。

* '''挑战-响应协议''' 假设请求方（客户端）和提供方（服务器）之间有直接的互动连接。提供方选择一个挑战，例如选择一个具有某种属性的集合中的某个项，请求方在集合中找到相关的响应，并将其返回给提供方进行检查。由于挑战由提供方当场选择，因此其难度可以根据提供方当前的负载进行调整。如果挑战-响应协议具有已知解决方案（由提供方选择），或者已知解决方案存在于有限的搜索空间内，则请求方一侧的工作可能是有限的。

* '''解决方案-验证协议''' 则不假设有这样的连接：因此，问题必须在请求方寻求解决方案之前自我设定，提供方必须检查问题选择和找到的解决方案。大多数这样的方案是无界的概率迭代过程，例如 Hashcash。

已知解决方案协议通常比无界概率协议具有稍低的方差，因为矩形分布的方差低于泊松分布的方差（在均值相同的情况下）。减少方差的一种通用技术是使用多个独立的子挑战，因为多个样本的平均值将具有更低的方差。

还有一些固定成本函数，例如时间锁难题。

此外，这些方案所使用的底层函数可能是：

* '''CPU绑定'''：计算速度受处理器的限制，计算速度在时间上有很大的变化，也会在高端服务器和低端便携设备之间有所不同。
* '''内存绑定'''：计算速度受主内存访问（无论是延迟还是带宽）的限制，其性能预计对硬件的演变不那么敏感。
* '''网络绑定'''：如果客户端必须执行很少的计算，但必须从远程服务器收集一些令牌，然后再查询最终的服务提供方。在这种情况下，工作实际上并不是由请求方执行的，但由于获取所需令牌的延迟，仍然会产生延迟。

最后，一些 PoW 系统提供捷径计算，允许知道某个秘密（通常是私钥）的参与者生成便宜的 PoW。其原理是，邮件列表持有者可以为每个收件人生成戳记，而不会产生高成本。是否需要此功能取决于使用场景。

== 工作量证明函数列表 ==
以下是已知的工作量证明函数列表：

* 大素数模运算的整数平方根
* 弱化的 Fiat–Shamir 签名
* Ong–Schnorr–Shamir 签名，被 Pollard 破解
* 部分哈希反转：本文形式化了工作量证明的概念，并引入了“面包布丁协议”的相关思想，这是一个“可重用的工作量证明” (RPoW) 系统。
* 哈希序列
* Puzzles
* 基于 Diffie-Hellman 的难题
* Moderate
* Mbound
* 北海道难题（Hokkaido）
* 杂树（Cuckoo Cycle）
* 基于 Merkle 树的
* 引导游览难题协议

== 参考链接 ==
<references />