第8章：比特币替代采矿谜题（一）

采矿难题是比特币的核心，因为他们的困难限制了任何一方控制共识程序的能力。因为比特币矿工为他们解决的谜题赚取了回报，我们预计他们将花费相当的精力去寻找任何可用的快捷方式来更快或更有效地解决这些难题，以期增加利润。另一方面，如果有帮助网络的，但是不能直接帮助他们更快地解决谜题的工作，矿工可能会被激励跳过它以降低成本。因此，谜题的设计在指导和指导参与网络方面发挥了重要作用。

在本章中，我们将讨论各种可能的替代谜题设计，假设我们可以修改比特币的谜题，甚至从头开始设计一个新的谜题。一个经典的设计挑战是制造出一个难题，它是专用的ASIC，它能平衡使用普通计算设备的用户和使用定制硬件的用户之间的游戏水平。我们还可以设计出哪些其他难以实现的谜题？我们还想鼓励或阻止哪些其他行为？我们将讨论几个有趣的例子，从减少能源消耗到产生一些对社会有用的副作用阻止采矿池的形成。其中一些已被altcoins（山寨币）使用，而另一些则是未来可能会被使用的研究思想。

8.1基本谜题要求

我们将从挖掘谜题的一些基本的安全要求开始。如果拼图不能满足保持比特币安全需求的基本要求，那么引入花哨的新功能并不好。

有许多可能的要求，我们在第2章和第5章中讨论过一些。挖掘谜题需要快速验证，因为网络上的每个节点都验证每一个谜题解决方案——甚至是没有直接参与挖掘的节点，包括SPV客户机。我们还希望具有可调节的难度，使得随着新用户进入网络，随着不断增加的哈希功率贡献，谜题的难度可以随着时间的推移而改变。这使得谜题足够困难以至于对区块链的攻击是昂贵的，但谜题解决方案仍然以相当稳定的速率（大约每十分钟在比特币中找到）被发现。

比特币的挖掘难度究竟是什么？到目前为止，我们只是把它称为“比特币的谜题”，更准确的说，我们可以将它称为局部哈希-原像谜题，因为目标是找到部分指定哈希输出的原像，换句话说，低于某个目标值的输出。一些其他稀有属性也可以工作，例如找到一个区块，它的哈希值至少有k位设置为零，但将输出与目标进行比较可能是最简单的。

很容易看出比特币的SHA-256哈希挖掘难题已经满足了这两个要求。通过调整单个参数（目标）可以达到任意的难度。检查解决方案是微不足道的，只需要一个SHA-256计算和一个比较，无论这个谜题有多么难以解决。

进度-游离度。另一个核心要求更微妙：在任何单位时间内赢得谜题解决方案的机会应该大致与所使用的散列功率成比例。这意味着，具有非常强大硬件的真正大型矿工只能在下一个矿工找到谜题解决方案中才占有比例优势。即使是小矿工，也应该有一定的成功机会获得补偿。

为了说明这一点，让我们考虑一个不能满足这个要求的不好的谜题。考虑一个挖掘谜题，需要几个步骤才能找到解决方案。例如，我们可能需要计算n个连续的SHA-256哈希值，而不是找到SHA-256哈希值低于某个目标的区块。这不会是有效的检查，但是现在没关系。这里面临的更大的问题是，由于它采取了N个准确步骤来寻找解决方案，那么网络中最快的矿工将永远是赢得下一个奖励的人。很快就会明白哪个矿工正在解决每一个难题，其他矿工根本就没有参与的动机。

再次，一个很好的谜题给每个矿工赢得下一个谜题解决方案的机会，与他们贡献的哈希力的数量成比例。想象一下，随机投掷一块飞镖，不同矿工持有的矿权对应着不同大小的目标。如果你考虑一下，这个要求意味着解决谜题的几率必须独立于你花了多少工作来解决这个问题（因为大型矿工总是花费更多的工作）。这就是为什么一个好的挖掘谜题被称为进步‐自由。

从数学的角度来看，这意味着一个好的挖掘谜题必须是一个无记忆的过程——任何其他东西都不可避免地会以某种方式奖励矿工过去的进展。因此，任何可行的谜题本质上都涉及到某种尝试和错误。 因此，找到解决方案的时间将不可避免地形成一个指数分布，如我们在第2章中所看到的。

可调节难度，快速验证和进度-游离度是比特币挖掘谜题的三个关键特性。基于SHA-256的局部原像发现肯定满足所有这三个特性。有些人认为比特币的挖掘谜题所满足的其他属性也是至关重要的，但是当我们探索其他潜在功能时，我们会讨论其他潜在需求。

8.2 ASIC性能谜题

我们将开始设计一个ASIC性能的谜题，这是迄今为止最广泛讨论和追捧的替代挖掘谜题。正如我们在第5章中讨论的那样，比特币挖掘最初主要用普通计算机完成，最终扩展到GPU和定制的FPGA器件，现在几乎完全由非常强大的优化ASIC芯片完成。

这些ASIC比通用计算设备更有效率，即使硬件是免费的，使用普通计算机（或甚至一些早期的ASIC）进行采矿也赚不回电价。

这种转变意味着参与比特币生态系统的大多数个人（例如使用比特币进行交易的客户或商家）不再在采矿过程中扮演任何角色。有些人认为这是一个危险的发展，一小部分专业矿工控制了采矿过程。在Satoshi Nakamoto关于比特币的原始论文中，使用了“一个CPU一票”这个词，它有时被认为比特币应该由所有用户拥有的民主制度。

其他人则认为，ASIC的兴起是不可避免的，而不是对Bitcoin的损害，而对ASIC性能的渴望只不过是希望回到“过去的好时光”。不考虑抵抗ASIC是否可取，我们可以深入探讨技术挑战和一些为实现这一目标而提出的方法。

抵抗ASIC意味着什么？一般来说，我们想减少使用定制的采矿硬件。严格解释这意味着设计一个难题，使现有的通用计算机成为最便宜和最有效的设备。但这是不可能的。毕竟，通用计算机已经有了专门的优化。并非所有产品都具有相同的优化，并且它们会随时间而改变。例如，在过去十年中，英特尔和AMD都加强了对特殊指令的支持（通常称为“添加硬件支持”），以更有效地计算AES分组密码。所以一些电脑在采矿时总是比其他电脑的效率要低。此外，很难想象设计一个依靠大多数个人计算机所包含的扬声器和屏幕等功能的挖掘谜题。因此，剥离这些功能的专用机器仍然可能会更便宜和更有效率。

因此，现实中我们的目标是一个更为温和的目标：提出一个难题，缩小最具成本效益的定制硬件和大多数通用计算机之间的差距。ASIC将不可避免地会更有效率，但是如果我们将其限制在一个数量级或更小的数量级，那么个别用户使用他们已经拥有的计算机可能仍然是经济的。

内存硬件谜题。被设计为ASIC性能应用最广泛的谜题被称为“内存谜题”——需要大量内存来计算，而不是，或者除了大量CPU时间之外的谜题。类似但具有不同概念的是内存限制谜题，其中访问存储器的时间主导总计算时间。一个谜题可以只是没有内存限制的内存困难（memory‐hard），或者没有内存困难（memory‐hard）的内存限制，或者两者兼而有之。这是一个微妙但重要的区别，因为即使CPU速度是计算时间的瓶颈，并行解决大量这种谜题的成本仍然可以由存储器的成本来支配，反之亦然。通常，对于一个计算谜题，我们需要一些内存困难（memory‐hard）和内存限制的东西，确保大量的内存的需要，且这是限制因素。

为什么内存困难（memory‐hard）和内存限制的谜题可以帮助ASIC性能？计算现代哈希函数所需的逻辑运算只是CPU中的一小部分，这意味着对于Bitcoin的谜题，ASIC通过不实施任何不必要的功能而获得了很大的里程。一个相关的因素是内存性能的变化（以及每单位性能的成本）远远低于不同类型处理器的计算速度的变化。所以如果我们设计一个内存困难的谜题，需要相对简单的计算但需要大量的内存进行计算，这意味着解决谜题的代价会随着内存成本的升高而提高。

正如我们所看到的那样，SHA-256确实没有记忆困难，它只需要一个很小的256位状态，很容易适应CPU寄存器。 但是设计一个记忆困难的工作证明谜题并不难。

Scrpt。最流行的内存困难谜题被称为scrypt。这个难题已被广泛应用于莱特币，第二大流行的加密货币，以及各种其他Bitcoin替代品。

Scrypt是一个内存困难哈希函数，最初设计为以难以强制的方式哈希密码，所以挖掘难题与Bitcoin的部分哈希原像谜题相同，除了用scrypt替换SHA-256。

事实上，scrypt之前存在的比特币和已经使用的哈希密码给安全性带来了一些信心。密码哈希具有类似的ASIC性能目标，因为就安全性起见，我们希望具有自定义硬件的攻击者无法在计算密码的哈希值上比合法用户或服务器（可能只有通用计算机）的速度更快。

Scrpt基本上有两个步骤。第一步是用随机数据填充随机存取存储器（RAM）的大量缓冲区。第二步是以伪随机顺序读取（并更新）该存储器，要求整个缓冲区存储在RAM中。

图8.1：Scrypt伪码

1 def scrpt（N，seed）：

2v=[0]*N//initialize memory buffer of length N

//Fill up memory buffer with pseudorandom data

3v[0]=seed

4for i = 1 to N：

5v[i] =SHA-256（v[i-1]）

//Access memory buffer in a pseudorandom order

6x=SHA-256（v[N-1]）

7for i = 1 to N：

8j=x % N//Choose a random index based on X

9X=SHA-256（X^V[j]）//Update X based on this index

10 return X

图8.1显示了Scrypt伪代码。它演示了核心原理，但我们省略了一些细节：实际上，scrypt在稍大的数据块上工作，填充缓冲区的算法稍微复杂一些。

为了看看为什么scrypt是内存困难的，我们设想试图在不使用缓冲区V的情况下计算相同的值。这肯定是可以的——然而，在第9行中，我们需要重新计算值V

[j]，这将需要计算SHA-256的迭代次数。因为在循环的每个迭代期间j的值将在0和N-1之间被伪随机选择，所以这将需要大约N / 2个SHA-256计算。这意味着计算整个函数现在将使用N*N/2=N的平方/2 SHA-256计算，而不是使用2N，如果使用缓冲区。因此，使用内存将scrypt从O（n）函数转换为O（N）。这应该很简单的选择n足够大，O（n）足够慢，使用内存更快。

时间记忆权衡。虽然在没有大型内存缓冲区的帮助下计算scrypt要慢得多，但仍然可以以较少的内存成本获得更多计算。假设我们使用大小为N /

2（而不是大小N）的缓冲区。现在，如果j是偶数，我们只能存储值V [j]，丢弃j是奇数的值。在第二个循环中，大约一半的时间将选择j的奇数值，但现在可以很容易地实时计算——我们只是计算SHA 256（v[j-1]），因为v[j-1]将在我们的缓冲区中。由于这是大约一半的时间，所以它增加了N / 2个额外的SHA-256计算。

因此，将我们的内存需求减半将SHA-256计算的数量增加了四分之一（从2N到5N / 2）。一般来说，我们可以使用SHA-256的N / k存储器和计算（k + 3）N

/ 2次迭代来仅存储缓冲器V的第k行。在极限中，如果我们设置k = N，我们将回到我们之前的计算，其中运行时间变为O（N）。 这些数字并不适用于scrypt本身，而是渐近的估算。

还有其他的设计可以减轻与时间交换内存的能力。例如，如果在第二个循环中不断更新缓冲区，那么由于需要存储更新，所以时间存储的折衷效果会降低。

验证费用。scrypt的另一个限制是，它需要尽可能多的内存来验证它的计算。为了使存储硬度有意义，N将需要相当大。这意味着，单次计算的scrypt比SHA-256的单次迭代要贵一个数量级，这是检查Bitcoin更简单的挖掘谜题所需要的。

这有一些负面的后果，因为网络中的每个客户都必须重复这个计算，以便检查所声称的新区块是否有效。这可能会减缓新区块的传播和接受程度，并增加分叉的风险。这也意味着每个客户端（即使轻量级的SPV客户端）都必须有足够的内存来有效地计算该功能。因此，可用于密码学中的scrypt的内存量N在一定程度上受到实际问题的限制。

直到最近，还不知道是否有可能设计一个难以计算内存困难但很快验证（易于记忆）的挖掘谜题。这个属性对于密码哈希是没有用的，它们在使用加密存储器之前一直是内存苦难功能的主要用例。

在2014年，约翰·特罗姆普（John

Tromp）提出了一个叫做杜鹃循环的新谜题。杜鹃循环是基于从布鲁克哈希表生成的图形中找到周期的难度，该表是仅在2001年提出的数据结构。如果不建立一个大的哈希表，没有任何已知的方法来计算它，但可以通过检查（相对较小）的循环来简单地进行验证。

这可能使内存困难或内存限制的工作证明更有用于比特币共识。不幸的是，没有数学证据表明这个函数不能有效地计算，而不使用内存。通常，新的加密算法看起来是安全的，但是社区不会相信，直到他们已经存在多年，没有发现攻击。由于这个原因，最近发现的布谷鸟循环在2015年之前并没有被任何加密的使用。

实践中的Scrypt。Scrypt已被用于许多加密的货币中，包括几个流行的例如Litecoin。结果有点混杂。Scrypt ASIC已经可用于Litecoin选择的参数（和许多其他山寨币altcoins复制）。令人惊讶的是，与通用计算机相比，这些ASIC的性能提升已经等于或大于SHA-256的性能提升！因此，至少在Litecoin使用的情况下，Scrypt最终不会是ASIC抗性（ASIC性能）。Litecoin的开发商最初声称ASIC性能是比特币的一个关键优势，但自此不再承认是这样。

这可能是由于Litecoin使用相对较低的N值（内存使用参数）的结果，仅需要128KB来计算（或更少，如果使用时间存储器权衡，这通常在GPU去完成，以使整个缓冲区适应更快的缓存）。这使得设计轻量级采矿ASIC相对容易，而无需像通用计算机那样访问千兆字节RAM所需的复杂内存访问总线。Litecoin开发人员没有选择更高的值（这将使ASIC更难设计），因为他们认为验证成本不切实际。

ASIC性能的其他方法。回想一下，我们最初的目标只是简单地使它难以构建具有显著性能加速的ASIC。内存困难只是这个目标的一种途径，还有一些其他的。

不幸的是，其他方法不是很科学，并没有像内存困难函数那样严格地设计或被攻击。最知名的是X11，它只是由称为Darkcoin（以后重命名为DASH）的altcoin引入的十一种不同哈希函数的组合，并且由其他几种使用。X11的目标是使得设计高效的ASIC变得相当复杂，因为所有11个功能必须在硬件中实现。但这不会带来什么，只会为硬件设计师带来一个不便。如果为X11构建了ASIC，那么肯定会使CPU和GPU开采过时。

边栏：X11的哈希函数来自哪里？2007年至2012年，美国国家标准学会举办了一项竞赛，选择了一个新的哈希函数系列作为SHA-3的标准。大量候选人提交了哈希函数，其中包含设计文档和源代码。虽然许多候选人在竞赛中被证明不具有加密安全性，但24名幸存者没有受到任何已知的加密攻击。X11选择了其中的11个，其中包括终极竞争者

已经提出但没有实际实施的另一种方法是将挖掘谜题作为移动目标。也就是说，采矿谜题本身会改变，就像Bitcoin的难度一样。理想情况下，这个谜题会改变，以前的谜题优化挖掘硬件将不再适用于新的谜题。目前还不清楚，我们如何经常为了获得我们所需要的安全要求而实际地改变这个谜题。如果这个决定是由一个altcoin的开发商做出的，那么这可能是一个不可接受的中央集权来源。例如，开发人员可能会选择一个新的谜题，他们已经开发了硬件（或只是优化的FPGA实现），给他们早期的优势。

也许谜题的序列可以自动生成，但这似乎也很困难。一个想法可能是采取一大堆哈希函数（例如，24个未被破坏的SHA-3候选人），并且每六个月至一年使用一次，这时间对于开发硬件太短。当然，如果预先知道这个时间表，那么在每个功能被使用的时候，硬件可以在时间节点上被设计出来。

ASIC蜜月。迄今为止，X11的ASIC缺乏的，即使显然可能构建，却展示了一个潜在的有用模式。由于没有使用X11的高性能计算机具有特别高的市场份额，所以任何人都没有足够的市场来构建X11的ASIC。一般来说，设计ASIC具有非常高的前期成本（时间和金钱）但每单位硬件产生的边际成本相对较低。因此，对于新的、未经验证的加密货币，如果新硬件可用于采矿之前货币可能会失败，则不值得投资建造硬件。即使有明确的市场，硬件单位准备就绪之前也会有时间延迟。第一台Bitcoin ASIC从首次设计后花费了一年多时间出货，而硬件行业则认为这是闪电般的速度。

因此，任何一个新的开采谜题的新的altcoin很可能会经历一个ASIC蜜月期，在此期间，GPU和FPGA挖掘（和潜在的CPU挖掘）将是有利可图的。可能无法阻止ASIC的浪潮，但也可能有一些价值吸引人们参与采矿（并赚取新的货币单位），同时引导他们。

反对ASIC性能的论据。我们已经看到，从长远来看，实现ASIC性能可能是不可能的。还有一些观点认为，从相对成熟的SHA-256挖掘谜题转向可能在密码学上较弱的新谜题是有风险的。此外，SHA-256采矿ASIC已经在接近现代限制的硬件效率设计，意味着指数增长期可能已经结束，因此SHA-256采矿将为网络提供最稳定。

最后还有一个观点认为即使在短期内，ASIC性能也是一个坏的特征。回顾第3章，即使有51％的矿工，许多类型的攻击对于他们来说是不合理的，因为它可能会使汇率崩溃，并降低矿工在硬件上的投资价值，因为他们从采矿中获得的比特币将会少得多。

由于具有高度ASIC性能的谜题，这个安全性论据可能会分崩离析。例如，攻击者可能暂时租用大量的通用计算能力（来自亚马逊EC2等服务），使用它来攻击，然后不受金钱的影响，因为他们不再需要在攻击后继续租用。相比之下，使用“ASIC友好”难题，这样的攻击者本来就需要控制大量的ASIC，这些ASIC仅用于挖掘密码。这样一个攻击者将最大限度地投资于未来的货币成功。遵循这个论据来达成逻辑结论，为了最大限度地提高安全性，也许采矿谜题不仅应该能够使高效的采矿ASIC成为可能，而且要被设计为使这些ASIC在加密的外部是完全无用的！

8.3有证实的工作

在第五章中，我们讨论了比特币矿业如何消耗能源（有人会说浪费），被经济学家称为负外部因素，这是一个潜在的问题。我们估计Bitcoin采矿消耗了几百兆瓦的功率。显而易见的问题是，为解决这些谜题所做的工作是否给社会带了一些其他的好处。这就相当于一种回收再利用的形式，可以帮助增加对加密货币的政治支持。当然，这个谜题仍然需要满足几个基本要求，使其适合在共识协议中使用。

以前的分布式计算项目。使用空闲计算机（或“备用周期”）的想法比Bitcoin要老得多。表8.3列出了一些最受欢迎的志愿者计算项目。所有这些项目都有一个属性，可能使它们适合用作计算谜题：具体地说，涉及一种“大海捞针”的问题，那里是一个大空间的可能解决方案和小部分的搜索空间可以相对快速并行检查。例如，在SETI @ home志愿者中，给予了观察到的无线电信号的小部分扫描潜在的模式，而在distributed.net志愿者中有一小部分潜在的密钥进行测试。

志愿者计算项目成功地将解决方案空间的一小部分分配给个人进行检查。事实上，这种模式是如此常见，所以开发了一个名为BOINC（伯克利开放基础设施网络计算）的特定图书馆，以便轻松地将个人完成的工作碎片化。

在这些应用中，志愿者主要是对潜在问题感兴趣，尽管这些项目还经常使用志愿者排行榜来展示他们贡献的计算量。这导致了一些尝试通过报告没有实际完成的工作来玩耍排行榜，要求一些项目要求发送少量冗余工作来检测作弊。为了在一个加密货币中使用，当然，动机主要是货币，我们可以预料到参与者试图在技术上尽可能地进行欺骗。

表8.3：热门“志愿者计算”项目

适应工作有用证明的挑战。鉴于这些项目的成功，我们可能会尝试直接使用这些问题。例如，在SETI @ Home的情况下，志愿者被给予测量统计异常的无线电观测部分，我们可能会认为，比一些阈值更少的统计学异常被认为是解决谜题的“获胜”解决方案，并允许任何找到一个门槛的矿工创建一个区块。

这个想法有一些问题。首先，请注意，潜在的解决方案并不一定是一个成功的解决方案。参与者可能会意识到某些片段比其他片段更容易产生异常。通过集中的项目，参与者被分配工作，所有的细分最终可以被分析（可能是更有希望的部分优先考虑）。然而，对于采矿，任何矿工都可以尝试任何部分，意思是矿工可能会首先尝试最有可能的部分。这可能意味着，如果更快的矿工知道他们可以先测试最有希望的部分，那么这个谜题就不是完全进展免费。与比特币的谜题进行比较，其中任何随机性都可能会产生一个有效的区块，所以所有矿工都被激励选择随机的随机数来尝试。这里的问题显示了比特币的谜题的一个关键特性，我们以前认为是理所当然的，这是一个等概率的解决方案空间。

接下来，考虑到SETI @ home根据射电望远镜所观测到的固定数据量进行数据分析的问题。有可能随着采矿能力的增加，不再有原始数据需要分析。再次与比特币进行比较，可以创造出无限数量的SHA-256谜题。这揭示了另一个重要的要求：需要一个取之不尽的谜题空间。

最后，考虑到SETI @ home使用受信任的集中管理员来管理新的无线电数据，并确定哪些参与者应该寻找。再次，由于我们使用我们的谜题来构建一个共识算法，我们不能假设一个集中的方式来管理这个难题。因此，我们需要一个可以被算法生成的难题。

哪些志愿者计算项目可能适合作为谜题？回到图8.3，我们可以看到，SETI @ home和Folding @ home显然不能用于分散的共识协议。两者都可能缺少我们现在添加到我们的列表中的所有三个属性。distributed.net所采用的加密暴力问题可能会起作用，尽管它们通常是针对那些想评估某些算法的安全性的公司设置的特定解密挑战而选择的。这些不能通过算法生成。我们可以在算法上生成解密挑战，由强力强制打破，但在某种意义上说，这正是SHA-256部分原像发现已经做到的，它没有任何有益的功能。

这使得伟大的互联网梅森素数搜索，结果证明是接近可行的。挑战可以通过算法生成（找到比上一个更大的素数），拼图空间是不竭的。事实上，它是无限的，因为已经证明有无数数量的素数（特别是无数个梅森素数）。

唯一真正的缺点是，大的梅森素数需要很长时间才能找到并且非常罕见。事实上，伟大的互联网梅森素数搜索在18年内只发现了14个敏森素数！显然，每年在一个区块链上添加少于一个区块显然是行不通的。这个具体问题似乎缺少我们在第8.1节中所说的可调整的困难属性。然而，事实证明，涉及查找素数的类似问题似乎可以作为一个计算难题。

Primecoin。在撰写本文时，在实践中部署的唯一有用的有效工作系统称为Primecoin。Prime coin的首要挑战是找到坎宁安的素数链。坎宁安链是k个素数的序列，使得链中的每个数字。也就是说，你拿一个素数，加倍，添加一个以获得另一个素数，并继续，直到你得到一个复合数字。序列2,5,11,23,47是长度为5的坎宁安链。95号链中潜在的第六个数字不是素数（95 = 5∙19）。最长的坎宁安链长度为19（从79910197721667870187016101开始）。推测和广泛认为，但未被证明，存在长度为k的坎宁安链。

现在，为了把它变成一个计算谜题，我们需要三个参数m，n和k，我们将一一解释。对于给定的挑战x（前一个区块的哈希），我们取x的第一个m位，并考虑长度为k或更大的任何链，其中链中的第一个素数是n位素数，并且具有相同的m领先位作为x是一个有效的解。请注意，我们可以调整n和k使难题更难。增加k（所需链长度）使问题指数更难，而增加n（起始素数的大小）会使线性更加困难。这提供了难度的微调。m的值只需要足够大，在看到前一个区块的值之前尝试预计算解决方案是不可行的。

我们讨论的所有其他属性似乎都像在提供：解决方案相对较快地进行验证，问题是无进展的，问题空间是无限的（假设一些经过深入研究的关于质数分布的数学推测是真实的），并且可以通过算法生成谜题。事实上，这个谜题已经用于Primecoin近两年了，这已经产生了坎宁安链中最大的知名素数，用于许多k值。Primecoin已经扩大到在其工作证明中包括额外的类似类型的主链，其中包括的“第二类”坎宁安链。

这提供了强有力的证据，证明有可能在某些有限的情况下证明有用的工作是切实可行的。当然，发现大型坎宁安链是有用的在很大程度上是值得商榷的。它们有可能在将来有一些应用的目的，它们对我们的集体数学知识肯定是一个小小的贡献。然而，目前它们没有已知的实际应用。

Permacoin和存储证明。一种有效工作证明的方法是存储证明（有时也称为可检索证明）。如果我们可以设计一个需要存储大量数据来计算的谜题，而不是要求一个单独的计算谜题呢？如果这些数据是有用的，那么矿工对采矿硬件的投资将有效地促进了广泛分布和复制的档案存储系统。

我们将看看Permacoin，第一个存储证据的建议是用于共识的。我们从一个大文件开始，我们称之为F。现在，我们假设大家都同意F的价值，且文件不会改变。例如，当启动加密安全性时，F可能由受信任的经销商选择，就像任何新货币需要达成一个创世区块一样。这将是一个公共价值的文件。例如，从“大型强子对撞机”收集的实验数据已经由几百PB（PB）组成。 为这些数据提供免费备份将是非常有用的。

当然，由于F是一个巨大的文件，大多数参与者将无法存储整个文件。但是，我们已经知道如何使用加密哈希函数来确保每个人都同意F而不知道整个事情。最简单的方法是每个人都同意H（F），但更好的方法是使用一个大的Merkle树代表F，并让所有的参与者都一致认同根的价值。现在，每个人都可以同意F的价值，证明F的任何部分是正确的是有效的。

在Permacoin中，每个矿工M存储一个随机子集。为了实现这一点，当矿工产生他们将用于接收资金的公钥时，它们哈希其公钥以产生他们必须存储以便能够挖掘的区块的伪随机集合。这个子集将是一些固定数量的区块.我们必须在这里假设，当他们开始挖掘时，他们有一些方法来获取这些区块——也许可以从规范的源码下载它们。

一旦矿工在本地储存，这个谜题就相当于传统的SHA-256挖掘。给定先前的区块哈希x，矿工选择随机随机值n并对其进行哈希以产生由个区块组成的伪随机子集。请注意，此子集取决于所选择的随机数和它们的公钥。最后，矿工计算n的SHA-256哈希和中的区块。如果这个哈希的值低于目标难度，他们已经找到了一个有效的解。

图8.4：在Permacoin中的文件中选择随机块。

在这个例子中，k = 6和k = 2。在实际实现中，这些参数会大得多。

验证解决方案需要以下步骤：

·验证是否从矿工的公钥和随机数n正确生成

·验证的每个块是否正确，通过验证其在Merkle树中的路径到F的全局约定的根。

·验证小于目标难度。

应该很容易看出为什么解决谜题需要矿工在本地存储所有的。对于每个随机数，矿工需要测试的区块的随机子集的哈希，从远程存储器获取网络将是非常慢的。

与scrypt的情况不同，如果k2足够大，则没有合理的时间/内存权衡。如果一个矿工只在本地存储了一半的，而k2= 20，那么在发现一个不需要任何区块的网络上，他们必须尝试一百万个随机数。因此，用常数因子减少它们的存储负担会成倍增加它们的计算负担。当然，将k2设置得太大将不会非常有效，因为k2 Merkle树路径必须在任何有效的解决方案中传输和验证。

在设定k时也有权衡。k越小，作为矿工就需要更少的储存空间，采矿就更民主。然而，这也意味着更大的矿工没有动力存储超过k1区块F，即使他们有能力存储更多。

像往常一样，这是一个轻微简化的完全permacoin提案，但这足以理解关键设计组件。当然，最大的实际挑战是找到一个非常重要的，公开的，需要额外复制的适当的大文件。如果文件F随时间而变化，以及随着时间的推移调整挖掘难度，也会有很大的复杂性。

长期的挑战和经济学。总结本节，有用的工作证明是一个非常自然的目标，但是鉴于共识协议的一个很好的计算谜题的其他要求，实现它是相当有挑战性的。虽然至少已知有两个例子在技术上可行的，primecoin和permacoin，带一些技术缺陷（主要是更长的验证时间）。此外，与我们在Bitcoin采矿征收的价值数百万美元的资金和兆瓦电耗相比，两者都提供相当小的公共利益。

有一个有趣的经济论证是，任何有用的工作证明的好处都应该是一个纯粹的公共利益。在经济学中，公共利益是一个非排他性，意味着没有任何机构可以避免使用它，而非竞争性的，这意味着被别人好的使用不影响其价值。典型的例子是灯塔。

我们在这里讨论的一些例子，如蛋白质折叠，可能不是一个纯粹的公共利益，因为一些公司（如大型制药公司）可能从增加蛋白质折叠的知识中获益更多。从根本上说，这些方面的采矿成本便宜，因为他们从公共利益中获益比其他方面获益更多。

原文始发于微信公众号（ 可可旅行人生 ）：第8章：比特币替代采矿谜题