采矿难题是比特币的核心，因为他们的困难限制了任何一方控制共识程序的能力。因为比特币矿工为他们解决的谜题赚取了回报，我们预计他们将花费相当的精力去寻找任何可用的快捷方式来更快或更有效地解决这些难题，以期增加利润。另一方面，如果有帮助网络的，但是不能直接帮助他们更快地解决谜题的工作，矿工可能会被激励跳过它以降低成本。因此，谜题的设计在指导和指导参与网络方面发挥了重要作用。
在本章中，我们将讨论各种可能的替代谜题设计，假设我们可以修改比特币的谜题，甚至从头开始设计一个新的谜题。一个经典的设计挑战是制造出一个难题，它是专用的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.4不可出售的谜题（不可外包的谜题）
我们来看看替代采矿谜题的另一个潜在设计目标：防止采矿池的形成。正如我们在第5章和其他地方所讨论的，大多数比特币矿工都是矿池的一部分，而不是独立的。这导致了几个大型的水池，它们共同代表了大部分的采矿能力。由于每个池都由中央池管理员操作，有些人认为这是比特币的分散化核心设计原则的一个危险的趋势，并且会损害其安全性。
虽然大多数共享的采矿池是一个明显的问题，但是任何大型的集中管理池都可能实现非默认的采矿策略并攻击网络。这些池也是黑客尝试和妥协立即控制大量采矿权的一个有趣的目标。池运营商可能会勾结审查交易或强制执行高额的交易费用。至少，大多数矿工在池中也意味着大多数矿工没有运行完全验证节点。
有趣的是，这些担忧在投票领域有相似之处。在美国和许多其他国家，个人出售选票是违法的。可以说，参与一个由其他人控制的池类似于在比特币共识协议中出售你的选票。
池的技术要求。回想一下，采矿池似乎是一个紧急现象。没有证据表明Satoshi在比特币的原始设计时正在考虑采矿池。几年来，在许多不认识或彼此信任的人之间，有效率的池是不可能出现的。
正如我们在第5章中看到的，采矿池通常通过指定一个带有已知公钥的池操作符来工作。每个参与采矿的矿工照常采矿，但向池经营者发送股份。这些股票是“接近失误”或“部分解决方案”，这将是较低难度水平的有效解决方案。这显示了池操作员矿工要执行多少工作。每当一个池参与者找到一个有效的区块时，池操作人员将根据他们提交的股票数量在池参与者中分配奖励。正如我们在第5章中讨论的，有很多公式来分配收入，但所有采矿池都遵循这一基本结构。
因此，池的存在依赖于比特币的至少两个技术属性。首先，矿工很容易通过提交股份来证明（概率）他们正在做多少工作。通过选择足够低份额的股票阈值，矿工可以轻松地证明他们正在以任意精度执行的工作量，无论找到有效区块的实际难度如何。考虑到我们需要一个可以随意创造的谜题，挖掘谜题的这个方面看起来很难改变。
第二，池成员可以很容易地向池运营商证明他们正在遵循规则，并努力寻找有效的区块，这将奖励整个池。这是因为该池的公钥致力于包含该区块Merkle交易树中的coinbase交易。一旦矿工发现一个块或甚至一个份额，他们就不能改变哪个公钥是新铸造的硬币的接收者。
区块丢弃攻击。在实施采矿池的这个方案中有一个缺点：没有什么可以强制参与的矿工在找到它们时向池管理器提交有效的区块。假设有一个池成员对大型采矿池感到不安。他们可以通过采矿和提交股票来参与池，就像正常的那样，但如果他们真的找到一个能奖励池的有效的区块，那么他们就干脆放弃它，而不要告诉池运营商。
这种攻击降低了池的整体采矿能力，因为攻击者的工作对找到有效的区块没有帮助。然而，攻击者仍然会因为似乎正在提交有效的股份而获得回报，并且只是运气不好找不到任何有效的区块。如果采矿池被设计为收入中立（即所有采矿奖励都重新分配给参与者），那么这次攻击可能导致池在亏损中运行。
这种攻击有时被称为蓄意或怠工攻击，被认为是一种破坏行为的形式，因为攻击似乎对攻击者和池的代价都是昂贵的。攻击者失去了钱，因为他们丢弃的每个区块都会导致一些比例的区块奖励被归还给他们。当然，攻击者仍能得到被发现的其他谜题解决方案的奖励。
似乎任何理性的攻击者都不会采用这种策略，因为他们会失去金钱，而不会获得任何有形的东西。事实证明，令人惊讶的是，在有些情况下，这个策略是有利可图的，如下面的框所述。但无论如何，我们想要设计一个全新的采矿谜题配方，以确保这种策略总是有利可图的。
边栏：阻止池之间的丢弃攻击。人们多年来一直认为，参与者放弃代表池发现的有效区块不能有利可图。 事实证明，如果一个采矿池使用它来攻击另一个矿池，这个策略可以是有利可图的。这被提出了非常多次，首先在2015年Ittay Eyal的一篇论文中进行了深入分析。
我们来看一个简单的例子：假设两个采矿池A和B各占总采矿能力的50%。现在假设B使用其一半的采矿能力（占总容量的25%）作为A池的成员开采，但丢弃发现的所有区块，我们可以在一个简化的模型中显示，B现在将获得总奖励的5/9，大于通常采矿的50%。在这种简单的情况下，将其一半的采矿能力用于攻击可以显示为采矿池B的最佳策略。
多个池的情况会越来越复杂。在撰写本文时，大量的实践中没有观察到区块丢弃。但从长远来看，仍然有可能有这样的攻击将使得大型采矿池的可行性收到质疑。
奖励破坏。我们的设计目标是使矿工们在一个交易池中被激励进行挖掘，但不向管理员提交有效的区块。目前，只有交易池管理者可以收集采矿奖励，因为管理者要求所有参与者在其正在采矿的coinbase交易区块中包含一个特定的公钥。适当的包含可以很容易地检查提交的部分解决方案。交易池管理员是唯一知道私钥的团体，因此可以确定新生成硬币的位置。
但是，如果我们要求所有参与者也知道私钥怎么办（因此可以在开采区块后重定向资金）？为了做到这一点，我们需要一个谜题，每个解决方案的尝试都需要coinbase交易中的私钥知识。我们可以从“找到一个哈希低于某个目标的区块”到“找到签名的哈希低于某个目标的区块”来改变这个谜题。这个签名必须使用coinbase交易中的相同公钥来计算。
这样一个谜题可以让交易池管理员有两个难以置信的选择。他们可能会将私钥分配给所有交易池参与者，在这种情况下，他们都可以窃取所有资金。或者，他们可以代表交易池参与者执行签名。计算签名比计算哈希值贵一个数量级，但是在这种情况下，交易池管理器将会做大部分的繁重工作。交易池管理者只要做一个独家矿工就好了。
不可外包采矿的利弊。由于这个谜题不能有效地被外包给一个不可信的参与者，所以如果不是完全不可能，要形成一个具有不可信参与者的采矿池，这是一个更具挑战性的问题。它有效地防止了所有池，甚至P2Pool的努力，使一个分散的交易池没有交易池管理者。
有一个观点认为，部署这样一个谜题可能会导致更多的集中化，而不是更少，因为它会阻止小矿工参与，他们会面临很大的差异。这只会留下大量的采矿作业。目前，虽然交易池可能名义上控制了大量的采矿能力，但不清楚的是，他们可以使用它来发起攻击，而不会看到他们许多成员的缺陷。这仍然是一个悬而未决的问题，风险会更大——大型采矿池，或将采矿限制在大到足以生存的高度差异的运营商。
圣杯将设计一个共识协议，这是“自然”的低方差，通过奖励矿工少量的低难度的谜题。这意味着矿工不需要搭建交易池，而小矿工仍然可以参与。简单地减少区块之间的平均时间将不起作用——由于所得到的方差相当于今天的大型采矿池，因此需要减少1,000或更多的因子。但是，区块之间的延迟将不到一秒钟，并且过时区块的数量将是高度混乱的。如果有一个备选版本共识协议，这将确保更容易的采矿难题，而不需要立即广播所有解决方案，这仍然是一个悬而未决的问题。
8.5利害关系证明和虚拟采矿
为了整理这一章，我们来看看用虚拟采矿代替计算谜题的想法。这个术语指的是一组不同的方法，但它们都有共同点，他们只需要参与矿工的一小部分计算资源。
关闭采矿循环。作为一个思想实验，假设比特币或另一种加密货币成为全球支付的主要形式。矿工们将开始一些初始化的隐式货币，用它来购买采矿设备和电力，消耗这些资源，并且在此过程中，以采矿奖励的形式获得新的加密货币。这个过程不断燃烧能源和原材料。
图8.5：比特币采矿的循环
一旦采矿硬件成为商品，电力是一种商品（通常已经是这样），与其他矿工相比，没有一个矿工将他们的初始加密货币持有量转换成采矿回报有重大的优势。
激励虚拟挖矿的基本问题是：如果我们消除了在电力和设备上花钱的步骤，会发生什么？毕竟，这个过程主要用于证明谁在矿业上投资最多。为什么不简单地按所有货币持有者实际持有货币数量的比例分配采矿权力？
回想一下，比特币开采的最初目标是确保在区块链的状态下进行投票，而拥有更多计算能力的矿工获得更多的投票。我们可以更改我们的“投票”制度，以便投票权取决于我们目前持有的货币数量。
虚拟挖矿的优势。这种方法的主要优势是显而易见的：它消除了图8.5中采矿周期的浪费，剩下的是一个“封闭的”系统，如图8.6所示。
图8.6：虚拟采矿周期
除了简单，这种方法将显著减少比特币的环境足迹。它不会将能源消耗降低到零，因为矿工们总是必须花费一些计算资源来与网络进行通信并进行验证。一些虚拟采矿方案也需要少量的挖矿计算。但无论如何，在比特币进行的绝大多数采矿工作都可能被淘汰。
虚拟采矿业可能减少集权化趋势。因为没有涉及采矿硬件，所以不关心ASIC优势，所有矿工都能像所有其他矿工一样“高效”地开采。任何虚拟挖矿谜题都能实现ASIC抗扰谜题的所有目标。
也许最重要的是，虚拟挖矿可能会解决我们在ASIC抗性谜题的背景下讨论的问题，即矿工可能不会投资于货币的长期健康发展。任何拥有任何比特币的人，实际上是货币的利益相关者，而强大的虚拟矿工（如拥有所有货币的51％以上的矿工）是一个非常大的利益相关者。他们有动机去做使整个系统受益的事情，因为它增加了他们所持有硬币的价值。这一论点甚至比持有大量矿业设备的矿业者的价值更为强大，其价值取决于货币的未来不会表现出恶意。
这就是股权证明术语来源的地方。除了消除采矿和节约能源外，也许虚拟采矿的最根本的动力是确保采矿是由货币利益相关者来完成的，而这些利益相关者最有动力作为系统的良好管理者。
实施虚拟采矿：Peercoin。虚拟挖掘有许多变化，我们将介绍一些最常见的想法。我们应该强调，这些想法还没有以科学严谨的方式进行研究，也没有经历比特币受欢迎的工作证明的实际测试水平。
首先，我们将考虑Peercoin2012年采取的方法， 这是第一个推出股权证明的代币（altcoin）。Peercoin是一种混合的工作证明/股权证明算法，其中“股份”由“硬币年龄”指定。
一个特定未消费的交易输出的硬币年龄是该产出所持有的仍然未消费的金额和区块数量。现在，为了在Peercoin开采一个矿区，矿工必须像比特币一样解决一个基于SHA-256的计算难题。然而，这个谜题的难度根据他们愿意消费多少硬币年龄（coin-age）进行调整。为了做到这一点，该区块包括一个特殊的“组合”交易，其中一些交易仅用于将其硬币年龄重置为零。在投币交易中消耗的硬币年龄的总和决定了工作证明谜题使给定区块有效是多么地困难。
矿工有可能挖掘很少的股权和大量的计算能力，但选择困难的公式，以便在消耗一些硬币年龄时更容易找到一个区块。计算谜题的效果主要是为了确保两个矿工试图消耗类似数量的硬币年龄时，该过程是随机的。
许多虚拟采矿代币采用了略有不同的设计，包括Nxt，BitShares，BlackCoin和Reddcoin。在每个这些中，一些数量的股权被用来使计算谜题变得更加容易，据称计算谜题不再是采矿的主要挑战。
替代形式的股权。这几个混合模式的替代品值得讨论：
·权益证明。最纯粹的证据形式只是为了让那些控制大量货币的人更容易采矿。这与Peercoin的硬币证明类似，只有年龄未考虑在内。这种方法的缺点是，与成功采矿后重置的硬币年龄不同，最富有的参与者总是被给予最简单的挖掘谜题。
·存续证明。在这种提法中，当矿工使用硬币来制造区块时，它们会冻结一定数量的区块。这可以被认为是硬币年龄的一个镜像：这个系统奖励在未来相当长的一段时间内愿意让硬币长时间不动的矿工，而不是奖励过去长期持有未用硬币的矿工。在这两种方法中，矿工权益的有效性都来自于无法使用硬币执行其他行动的机会成本。
无利害关系的问题。虚拟开采是当前研究的一个活跃领域，存在着大量的开放性问题。虽然使用虚拟挖矿启动并存活了一些加密货币，但是他们已经面临与比特币相同的压力，以抵挡积极的攻击者。
虚拟开采方案的通用漏洞是经常被称为无利害关系的问题和利益冲突攻击。假设a <50％的攻击者正在尝试创建一个k区块的分支。正如我们之前讨论过的，这种攻击将以极大的概率在k中指数级增长而失败。在传统采矿中，一次失败的攻击具有重大的机会成本，因为矿工在采矿过程中可能已经获得了采矿奖励，而不是在其失败的攻击中浪费了采矿资源。
使用虚拟挖掘，这个机会成本是不存在的。矿工可以利用自己的股份挖掘当前最长的链条，同时尝试创建一个叉子。 如果他们的分支成功，它将消耗大量的股份。如果失败，其失败记录将不会反映在最后的最长链。
因此，理性的矿工们可能会不断尝试分拆链条。已经作出各种尝试来解决这个问题。大多数虚拟采矿方案在使用检查点防止长叉时更具攻击性，但正如前面所讨论的，这是一个分散共识协议的终结点。
对于Ethereum（在2015年中期推出的altcoin，我们将在第10章中讨论），一项名为Slasher的提案允许对试图分叉链条的矿工进行惩罚。在Slasher中，使用矿权挖矿需要使用与构成矿工股权的交易相对应的私钥签署当前区块。如果矿工曾经使用相同的利益来签署两个不一致的链（两者都不是另一个的前缀），Slasher允许矿工在块链中稍后输入这两个签名，作为不当行为的证明，收集这一股份的一部分作为赏金。虽然这似乎是一个有效的解决方案，但协议的细节相当复杂，尚未成功部署。
可能存在的最终对策是，正如我们已经看到的传统采矿方案，矿工可能根本没有强大的动机来攻击，因为这样会损害系统并破坏他们的利益，即使攻击是成功的。
虚拟挖矿的其他缺点。另外还有两个缺点值得一提。第一个是，即使在没有利益冲突的情况下，某些形式的虚拟挖掘也可能使一些类型的攻击变得更加容易，因为这样可以“抢救”一些采矿权。例如，可以汇集大量的硬币，以便能够大量涌入采矿，或许引入叉子。即使像Slasher这样的系统也被涌来阻止两个链上的采矿同时进行，这是可能的。为了阻止这种攻击，Peercoin将年龄参数限制在计算硬币年龄的90天。
第二个问题是，如果一个矿工在一个虚拟采矿系统中获得了51%的可用股份，那么他们就可以通过只在自己的区块上开采而保持它的永久性，本质上是控制区块链。即使从采矿奖励和交易费用中产生新的股份，51%矿工将获得这一新的股份，他们在总股本中的份额将慢慢接近100%。在传统采矿业中，即使有51%矿工存在，也总是有可能出现一些新矿工将拥有更多的采矿设备和能源，并减少大多数矿工。虚拟采矿更难避免这个问题。
虚拟挖掘实际可行吗？虚拟采矿在主流的比特币社区仍然有些争议。有一个观点认为，安全性基本上需要燃烧真实资源，需要真正的计算硬件和消耗真实的电力才能找到谜题解决方案。如果这个论据被相信，那么工作证明的明显浪费可以解释为你得到安全的成本。但是，这一观点尚未得到证实，正如虚拟采矿的安全性尚未得到证实一样。
总之，有很多事情可能会改变比特币的挖掘谜题，这是一个火热的研究和创新领域。然而，到目前为止，没有一种替代品似乎既表现出理论上的正确性，也被认为是实际可应用的。例如，尽管scrypt已经成为代币（altcoins）的热门选择，但实际上并没有实现ASIC抵抗，其用途还不清楚。完全可能的是，替代采矿谜题将在未来取得更大的成功。毕竟，比特币本身就是经过几十年的失败尝试，创造了一个加密的货币，并设法在原则设计和实际的权衡之间达到了最佳的水平。
更多阅读
本文定义了记忆功能并提出了scrypt：
Percival,Colin. S tronger key derivation via sequential memory-hard functions.Self-published, 2009.
关于记忆功能的早期论文：
Abadi,Martin, Mike Burrows, Mark Manasse, and Ted Wobber. Moderately hard,memory-bound functions.ACM Transactions on Internet Technology, 2005.
Dwork,Cynthia, Andrew Goldberg, and Moni Naor. O n memory-bound functions forfighting spam. In Advances in Cryptology-Crypto, 2003.
杜鹃循环建议：
Tromp,John. C uckoo Cycle: a memory-hard proof-of-work system. IACR Cryptology ePrintArchive 2014.
Permacoin提案：
Miller,Andrew, Ari Juels, Elaine Shi, Bryan Parno, and Justin Katz. Permacoin:Repurposing bitcoin work for data save. IEEE Security and Privacy, 2014.
本文讨论了不同的哈希函数设计和SHA-3比赛：
Preneel,
Bart. First 30 years of cryptographic hash functions and the NIST SHA-3
competition.In Topics in Cryptology——CT-RSA, 2010.
关于不可外包谜题的建议：
Miller,Andrew, Elaine Shi, Ahmed Kosba, and Jonathan Katz. NonoutsourceableScratch-Off Puzzles to Discourage Bitcoin Mining Coalitions.Pre-print 2015.
