首先我们从讨论设计一个可以反ASIC解谜(ASIC-resistant puzzles)的挑战开始，这个挑战也是最被广泛讨论和追求的可替代目前比特币挖矿解谜的一种。我们在第5章中讨论过，比特币挖矿最初是用普通电脑，然后再升级到GPU和定制化的FPGA设备，到现在基本上由非常强大的优化过的ASIC芯片所垄断。现在的ASIC的挖矿运算能力比一般电脑甚至早期的ASIC都要高太多。一般的电脑即使硬件本身是免费的，也会因为电费价格等因素而变得不可行。
这个转变意味着，在比特币生态系统里的大部分个体（例如使用比特币交易的客户和商家）已经无法参与到挖矿过程中了。有些人认为这是一个危险的势头，一小部分职业矿工控制了整个挖矿的过程。在中本聪最初有关比特币的论文里，用到过“一个CPU一票”的说法，这个说法时不时被有些人用来说明比特币应该是一个被全部用户所拥有的民主系统。
其他人觉得ASIC的崛起是不可避免的，而且这也不会伤害到比特币，这种希望实现反ASIC的愿望也只是有些人希望回到“过去的好时光”。对于反ASIC是否可取，我们保持中立的态度，因为只有这样，我们才可以深入讨论一些技术上的挑战和提议的方案，来实现反ASIC的目标。
反ASIC到底是什么意思
大致上说，我们想抑制为了挖矿而特别定制的设备的优势。这也可以理解为，设计一个解谜程序，让现有的普通电脑成为最廉价和最有效率的解谜运算设备。但这在现实中不可能，毕竟所有的通用电脑的中央处理器里已经针对一些特殊目的进行了优化。并不是所有的电脑都有相同的优化配置，并且它们随着时代而改变。比如，过去的10年中，英特尔（Intel）和AMD在芯片里加入特殊指令（通常叫作“增加硬件支持”）来更加有效地计算高级加密标准（Advanced Encryption Standard，简称AES）的区块密码。所以有些电脑在挖矿这个事情上总是会比其他电脑更加低效。另外，很难想象设计一个挖矿解密程序，而这些程序是依赖普通个人电脑诸如音响或显示器这些特性的，所以去除了那些通用特性的具有特殊目的的设备，很可能会更有效率，并且成本更低。
更加实际地说，我们有一个适中的目标：设计一个解谜程序，尽可能地减少最有效率的定制运算设备与通用电脑之间的效率差距。ASIC还是会不可避免地成为更加有效的挖矿机，但我们至少可以将其运算效能限制在一定范围内，从而让个人用户使用他们已有的通用电脑来挖矿仍具备一定的经济效应。
刚性内存解谜
大多数被设计成反ASIC的解谜程序中，最普遍被应用的叫作刚性内存解谜（memory-hard puzzles）——解谜需要大量的内存来计算，而不是靠大量的CPU时间。一个类似但又不一样的概念是内存限制解谜（memory-bound puzzles），花在读取内存上的时间，占据了这种程序大部分的计算时间。一个解谜可以是刚性内存类而不是内存限制类，或是内存限制类而不是刚性内存类，或是二者兼而有之。一个微妙但重要的区别在于，虽然CPU的速度是计算时间的瓶颈，但平行运算大量解谜的成本，还是被内存的成本所左右，或者反之亦然。通常对于运算类的解谜程序，我们要做到刚性内存和内存限制，就需要保证在运算过程中大量的内存被要求使用，使之成为一个限制性因素。
为什么刚性内存解谜或内存限制解谜可以反ASIC？因为用来计算哈希函数的逻辑运算只占了CPU里的一小部分，意思是在比特币的解谜计算里，ASIC不需要执行一些不必要的功能，而只需要执行计算哈希函数的相关功能，所以占了很大优势。另外一个相关因素是，不同的内存性能上的差异（和单位性能的成本）比不同处理器之间运算速度上的差异要小很多，所以，如果我们设计了一个刚性内存类的解谜，计算时需要相对简单的算力但需要大量的内存，这就意味着，解密成本的上升速率将会像内存成本提升速率那样，在一个相对低一些的水平。[1]
SHA-256已经被认定为不是刚性内存解谜算法。它只需要一个小小的256位模块，可以很容易地被放进CPU的注册机里。但设计一个刚性内存类的工作量证明解谜不是一件太难的事。
Scrypt
现在最受欢迎的刚性内存解谜叫作Scrypt[2]，被第二大加密数字货币莱特币以及其他加密数字货币所用。
Scrypt是一个刚性内存的哈希函数，最早是为了加密密码而不容易被暴力破解（比如，反复试错破解），所以挖矿解谜与比特币用的“不完全哈希函数原像解谜”是一样的，只不过用Scrypt取代了SHA-256。
Scrypt在比特币被发明出来之前就已经存在，而且它是用来加密个人密码，这一点让我们对它的安全性有一定的信心。密码的哈希函数化其实与反ASIC有着相似的目的。出于安全性考虑，我们期望，一个有着定制化设备的攻击者不能够比使用一般电脑或者服务器的用户更快地计算密码的函数值。
Scrypt基本上有两个步骤：第一个步骤是在用随机数据填充随机存取存储器（Random Acess Memory，简称RAM）里面的缓存空间；第二步是从这块内存区域里虚拟随机地读取（或者更新）数据，同时要求整个缓存都存储在RAM里面。
图8.1 Scrypt虚拟代码
图8.1展示了一段Scrypt的伪代码(pseudocode)来体现核心的计算原则，但我们也省略了一些细节——在实际中，Scrypt使用更大一点的数据块，然后用来充满缓存区的算法略微复杂一点。
为了理解为什么Scrypt是刚性内存类的，我们先想象一下如果我们要计算同样的值，但不用缓存区V( 参见图8.1)。这当然也是可行的——但在第9行代码里，我们需要重新动态地计算值V[j]，这需要进行j次的SHA-256的迭代运算。因为j的值在每次迭代循环里会从0和N-1中虚拟随机地选择，因此这平均需要N/2次SHA-256计算。这意味着计算整个函数需要N×N/2=N2/2个SHA-256计算，但是如果使用一个缓存的话，只需要进行2N次运算。因此，缓存的使用将Scrypt的时间复杂度从O(N2)转换成O(n)。这样一来，只要简单地选一个足够大的N值使得O(N2)的计算变得足够慢，以此确保使用内存是更快的选择。
在时间与内存之间的权衡
如果没有一个较大的内存缓存，计算Scrypt会变得很慢，但是用较少的内存来增加相对较少的计算还是可能的。假设我们使用一个大小约N/2的缓存（而不是N的大小），现在，我们只在j是偶数的情况储存V[j]的值，丢掉那些j是奇数的值。而在第二次循环里，一半的情况下j为奇数的值将会被选到，但这种情况还是很容易被计算的。我们只需要简单地计算SHA-256(V[j-1])，因为V[j-1]在我们的缓存里。[3]在一半的时间内会产生这种情况，所以它增加了N/2个额外的SHA-256计算。
因此，对内存要求量的减半只会增加1/4的SHA-256计算量（从2N到5N/2）。总体来说，我们可以储存缓存区域V里的每个k排数据，即使用N/k的内存和计算（k+3）N/2次的SHA-256迭代计算。在这个限制下，如果我们设定k=N，我们就回到先前运算时间为O(N2)的计算。这些数字不一定非常精确地适用于Scrypt算法本身，但是渐近预测的方式确实是适用的。
除此之外，还有其他的设计可以弱化用时间来换取内存的能力。举例来说，如果一个缓存持续地在第二次循环中被更新，它可以让时间与内存之间的互换不是那么有效，因为这些更新必须被储存在内存中。
校验成本
Scrypt的另一个局限性是，它需要用与计算所用的同样大小的内存来做校验。为了让内存刚性有意义，N需要变得比较大。这意味着一个Scrypt的计算要比一个SHA-256的迭代计算（在比特币里只需要一个SHA-256计算就可以校验）昂贵许多倍。
这会产生负面的结果，因为在网络里的每个用户必须重复这个计算来检查每一个新发现的区块是否有效。这会减缓新区块传播和被认可的速度，从而增加了分叉攻击[4]的风险。它还要求每个客户端（即使是轻量级的SPV客户端）拥有足够的内存来有效地进行函数计算。这样一来，实际上在加密数字货币中能够被Scrypt用到的内存N是有限的。
一直到最近我们都不明确，是否有可能设计一个挖矿解谜程序在计算上是刚性内存类的，又可以很快地（不需要大量内存）进行校验。这个特性对密码进行哈希运算没有多大作用，在用于加密数字货币之前，这是Scrypt算法的主要用途。
在2014年，一个叫作杜鹃鸟周期的新解谜算法被约翰·特龙普（John Tromp）所提出（起这个名字是因为这个算法的特性与杜鹃鸟的特性类似，杜占雀巢）。杜鹃鸟周期算法，是从杜鹃鸟哈希表所衍生的一张图中寻找周期的难度而设定的，杜鹃鸟哈希表这种数据结构在2001年才被首次提出。除了建立起一个很大的哈希表之外，没有其他已知的方法来计算这个周期，结果却可以通过发现一个周期（相对小的）来简单地验证。
这个算法可能会让刚性内存或是内存限制类的证明工作在比特币共识里变得更加实用。可惜的是，这个函数无法在数学上证明，如果它不用内存的话就不能被有效地计算。通常，一个新的密码学算法看起来都是安全的，但是社区会对它持有保留意见，直到它存在了多年而没有被破解过。因为这个缘故，并且因为它也是最近才被发明的，当前杜鹃鸟周期算法还没有被任何加密数字货币所采用。
实际应用中的Scrypt
Scrypt被许多种加密数字货币所使用，包括莱特币在内的几种热门币，结果好坏参半。针对莱特币Scrypt算法参数的ASIC已经存在（然后被其他几种另类币所复制）。令人惊讶的是，相较于大众电脑，这些ASIC在算力上的提高比起SHA-256相对普通电脑的提高，至少旗鼓相当甚至要更大！所以，Scrypt最终还是无法反ASIC，至少在莱特币上是如此。莱特币的设计者起初宣称反ASIC是莱特币的一大优势。但现在他们已经收回了这个说法。
这可能是莱特币所用的数值N（内存使用参数）比较低所造成的，它只要求128KB就可以进行计算（如果使用时间内存互换的模式，可能所需要的内存更低，这也被普遍用于GPU以获得更快的缓存）。低数值N使设计一个不需要复杂的内存存储总线的轻量级挖矿ASIC变得很容易，通常这种复杂的总线是读取十亿字节（Gigabytes）级别的随机存取存储器所需要的，而这些通用电脑都具备。莱特币的开发者没有选择一个比较高的内存参数（这会使ASIC更加难以设计），因为他们认为高内存参数所导致的高成本的校验过程是不太现实的。
其他抵抗ASIC的方法
请回忆一下，我们的初衷是想让可以大幅度提升计算性能的ASIC的开发变得困难。刚性内存解谜只是其中一个方法，还有其他方法。
遗憾的是，其他的方法都不是很科学，并且没有作为刚性内存函数而被设计过或者攻击过。最有名的一个叫作X11，其实就是把11个不同的哈希函数结合在一起，被一个叫作“黑暗币”(Dark Coin)的另类币所用（后面这个另类币改名叫DASH），在DASH之后也被其他一些另类币所使用。X11的目的是使设计一个有效的ASIC变得十分复杂，因为所有的11个函数的计算模块都要在芯片上被实施。但这其实对硬件设计者来说，也不过是一个小小的不方便而已。如果有一个针对X11的ASIC诞生，那么马上会废弃掉X11的CPU和GPU挖矿。
X11的哈希函数出自何处？
从2007年至2012年，美国国家标准委员会组织了一个竞赛，这个竞赛选取新的哈希函数家族来作为SHA-3的标准，大量包含了设计文档和源代码的哈希函数作为候选方案被提交。虽然有很多候选方案在竞赛中被证实并不符合密码学安全规范，但其中有24个哈希函数经受住了所有已知的密码学攻击，X11选择了其中的11种，包括获得最终胜利的Keccak[5]
另外被提出但还没有被实施的一个方法是使用一个移动的目标值来作为挖矿解谜。也就是说，解谜算法本身就会变化，就像比特币里的难度会周期性地改变一样。在理想的状态下，为上一个解谜算法而被优化过的挖矿硬件，对下一个解谜算法不再适用。我们不是很清楚要多久改变一次解谜算法，才能达到我们需要的安全要求。如果这是由另类币的开发者所决定的，这可能就变成了一种不可接受的中心化来源。比如，开发者可以根据他们已经开发出来的一种硬件（或者只是优化过的FPGA），去设计一个相对应新的解谜算法，他们自然就有了针对这个新算法的早期优势。
或许这些解密算法的顺序能够被自动生成，但这看上去也很难。一个想法是选择一大堆哈希函数（比如24个没有被攻破的基于SHA-3的算法），然后每个用上6个月到一年，在这么短的周期里很难开发新的硬件。当然如果这个顺序安排被事先知道，相应的硬件设计就可以按照函数使用的时间表来进行。
ASIC的蜜月
目前市面上还没有针对X11的ASIC面世，即便都清楚这种芯片的生产是可能的，这种现象显示了可能很有用的规律。因为适用X11算法的另类币的市值都不高，简单来说，还没有足够的市场价值吸引人去设计和生产针对X11的ASIC。一般来说，设计ASIC的前期投入都很高（不管是时间还是资金），同时生产单个硬件的利润相对来说比较低。因此，对于新的还没有被证实的加密数字货币，是不值得去投资研发针对性的ASIC，因为在新的硬件设备可用之前这个货币就可能失败了。即使有一个明显的市场需求，也会有硬件研发生产到出货的延迟。第一批比特币的ASIC从最初设计到最终出货花了近一年时间，这在硬件行业里已经算是很快了。
正因为如此，任何使用新的挖矿解谜算法的另类币都会经历一个ASIC蜜月期，在这段时间内，用GPU和FGPA挖矿(或许CPU挖掘)的利润会比较高。对于永久阻止ASIC的浪潮不太可能，但是吸引个人参与挖矿（并且因此而获得新币）的做法，在新币还处于步步为营的阶段，还是有价值的。
对于抵抗ASIC的争论
我们已经可以看到，从长远来讲做到反ASIC是不太可能的。但是也有一些其他意见，觉得从已经被证明的SHA-256解谜算法转变为一个密码学角度偏弱的新解谜算法，会存在一定的风险。甚者，SHA-256的挖矿ASIC已经接近当今硬件效能的极限了。这意味着，ASIC所带来的指数型增长可能结束了，之后SHA-256挖矿也会因此给网络带来最大的稳定性。
最后，还有一种意见认为，在短期内反ASIC也不好。在第3章中，我们曾探讨过即使一个拥有全网51%算力的矿工，他如若尝试做出很多类型的攻击，也并不理性。因为这样一来会使币值汇率崩溃，使得矿工在挖矿设备上的巨额投资大幅减值，他通过挖掘赚来的比特币的价值也会大幅下降。
对于一个高度反ASIC的解谜算法，这个安全性的说辞可能会站不住脚。举例来说，一个攻击者可能会暂时租用巨大算力［比如像亚马逊（Amazon）的EC2服务］，用它来攻击，然后不会承受任何财务上的损失，因为他们不需要在攻击后继续租用这个服务。相比较而言，对于一个“对ASIC友好”的解谜算法，攻击者就不得不控制一大堆只可以用作加密货币挖矿的ASIC。这样的一个攻击者其实应该是看好比特币未来的发展，做了一个最大限度的投资。按照这个逻辑进行推理的话，为了最大限度地保护安全，或许挖矿解谜算法应该被设计成不仅仅要让有效的挖矿ASIC被设计生产出来，更应该让那些ASIC除了用于加密货币的解谜运算之外，没有任何其他用途！
[1] 也就是花费更多去提高内存的效能，并不能以相同比例去提高解谜的效能。——译者注
[2] Scrypt是由著名的FreeBSD黑客Colin Percival为他的备份服务Tarsnap开发的。Scrypt不仅计算所需时间长，而且占用内存也多，使得并行计算多个摘要异常困难，因此利用rainbow table进行暴力攻击更加困难。Scrypt没有在生产环境中大规模应用，并且缺乏仔细的审察和广泛的函数库支持。——译者注
[3] j是奇数时，减1为偶数，我们存的是有偶数的值的。——译者注
[4] 有关分叉攻击的内容，可以参见本书第5章。——译者注
[5] Keccak算法为SHA-3的一种加密标准。——译者注。