1703867859
现在最受欢迎的刚性内存解谜叫作Scrypt[2]，被第二大加密数字货币莱特币以及其他加密数字货币所用。
1703867860
1703867861
Scrypt是一个刚性内存的哈希函数，最早是为了加密密码而不容易被暴力破解（比如，反复试错破解），所以挖矿解谜与比特币用的“不完全哈希函数原像解谜”是一样的，只不过用Scrypt取代了SHA-256。
1703867862
1703867863
Scrypt在比特币被发明出来之前就已经存在，而且它是用来加密个人密码，这一点让我们对它的安全性有一定的信心。密码的哈希函数化其实与反ASIC有着相似的目的。出于安全性考虑，我们期望，一个有着定制化设备的攻击者不能够比使用一般电脑或者服务器的用户更快地计算密码的函数值。
1703867864
1703867865
Scrypt基本上有两个步骤：第一个步骤是在用随机数据填充随机存取存储器（Random Acess Memory，简称RAM）里面的缓存空间；第二步是从这块内存区域里虚拟随机地读取（或者更新）数据，同时要求整个缓存都存储在RAM里面。
1703867866
1703867867
1703867868
1703867869
1703867870
图8.1 Scrypt虚拟代码
1703867871
1703867872
图8.1展示了一段Scrypt的伪代码(pseudocode)来体现核心的计算原则，但我们也省略了一些细节——在实际中，Scrypt使用更大一点的数据块，然后用来充满缓存区的算法略微复杂一点。
1703867873
1703867874
为了理解为什么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)的计算变得足够慢，以此确保使用内存是更快的选择。
1703867875
1703867876
在时间与内存之间的权衡
1703867877
1703867878
如果没有一个较大的内存缓存，计算Scrypt会变得很慢，但是用较少的内存来增加相对较少的计算还是可能的。假设我们使用一个大小约N/2的缓存（而不是N的大小），现在，我们只在j是偶数的情况储存V[j]的值，丢掉那些j是奇数的值。而在第二次循环里，一半的情况下j为奇数的值将会被选到，但这种情况还是很容易被计算的。我们只需要简单地计算SHA-256(V[j-1])，因为V[j-1]在我们的缓存里。[3]在一半的时间内会产生这种情况，所以它增加了N/2个额外的SHA-256计算。
1703867879
1703867880
因此，对内存要求量的减半只会增加1/4的SHA-256计算量（从2N到5N/2）。总体来说，我们可以储存缓存区域V里的每个k排数据，即使用N/k的内存和计算（k+3）N/2次的SHA-256迭代计算。在这个限制下，如果我们设定k=N，我们就回到先前运算时间为O(N2)的计算。这些数字不一定非常精确地适用于Scrypt算法本身，但是渐近预测的方式确实是适用的。
1703867881
1703867882
除此之外，还有其他的设计可以弱化用时间来换取内存的能力。举例来说，如果一个缓存持续地在第二次循环中被更新，它可以让时间与内存之间的互换不是那么有效，因为这些更新必须被储存在内存中。
1703867883
1703867884
校验成本
1703867885
1703867886
Scrypt的另一个局限性是，它需要用与计算所用的同样大小的内存来做校验。为了让内存刚性有意义，N需要变得比较大。这意味着一个Scrypt的计算要比一个SHA-256的迭代计算（在比特币里只需要一个SHA-256计算就可以校验）昂贵许多倍。
1703867887
1703867888
这会产生负面的结果，因为在网络里的每个用户必须重复这个计算来检查每一个新发现的区块是否有效。这会减缓新区块传播和被认可的速度，从而增加了分叉攻击[4]的风险。它还要求每个客户端（即使是轻量级的SPV客户端）拥有足够的内存来有效地进行函数计算。这样一来，实际上在加密数字货币中能够被Scrypt用到的内存N是有限的。
1703867889
1703867890
一直到最近我们都不明确，是否有可能设计一个挖矿解谜程序在计算上是刚性内存类的，又可以很快地（不需要大量内存）进行校验。这个特性对密码进行哈希运算没有多大作用，在用于加密数字货币之前，这是Scrypt算法的主要用途。
1703867891
1703867892
在2014年，一个叫作杜鹃鸟周期的新解谜算法被约翰·特龙普（John Tromp）所提出（起这个名字是因为这个算法的特性与杜鹃鸟的特性类似，杜占雀巢）。杜鹃鸟周期算法，是从杜鹃鸟哈希表所衍生的一张图中寻找周期的难度而设定的，杜鹃鸟哈希表这种数据结构在2001年才被首次提出。除了建立起一个很大的哈希表之外，没有其他已知的方法来计算这个周期，结果却可以通过发现一个周期（相对小的）来简单地验证。
1703867893
1703867894
这个算法可能会让刚性内存或是内存限制类的证明工作在比特币共识里变得更加实用。可惜的是，这个函数无法在数学上证明，如果它不用内存的话就不能被有效地计算。通常，一个新的密码学算法看起来都是安全的，但是社区会对它持有保留意见，直到它存在了多年而没有被破解过。因为这个缘故，并且因为它也是最近才被发明的，当前杜鹃鸟周期算法还没有被任何加密数字货币所采用。
1703867895
1703867896
实际应用中的Scrypt
1703867897
1703867898
Scrypt被许多种加密数字货币所使用，包括莱特币在内的几种热门币，结果好坏参半。针对莱特币Scrypt算法参数的ASIC已经存在（然后被其他几种另类币所复制）。令人惊讶的是，相较于大众电脑，这些ASIC在算力上的提高比起SHA-256相对普通电脑的提高，至少旗鼓相当甚至要更大！所以，Scrypt最终还是无法反ASIC，至少在莱特币上是如此。莱特币的设计者起初宣称反ASIC是莱特币的一大优势。但现在他们已经收回了这个说法。
1703867899
1703867900
这可能是莱特币所用的数值N（内存使用参数）比较低所造成的，它只要求128KB就可以进行计算（如果使用时间内存互换的模式，可能所需要的内存更低，这也被普遍用于GPU以获得更快的缓存）。低数值N使设计一个不需要复杂的内存存储总线的轻量级挖矿ASIC变得很容易，通常这种复杂的总线是读取十亿字节（Gigabytes）级别的随机存取存储器所需要的，而这些通用电脑都具备。莱特币的开发者没有选择一个比较高的内存参数（这会使ASIC更加难以设计），因为他们认为高内存参数所导致的高成本的校验过程是不太现实的。
1703867901
1703867902
其他抵抗ASIC的方法
1703867903
1703867904
请回忆一下，我们的初衷是想让可以大幅度提升计算性能的ASIC的开发变得困难。刚性内存解谜只是其中一个方法，还有其他方法。
1703867905
1703867906
遗憾的是，其他的方法都不是很科学，并且没有作为刚性内存函数而被设计过或者攻击过。最有名的一个叫作X11，其实就是把11个不同的哈希函数结合在一起，被一个叫作“黑暗币”(Dark Coin)的另类币所用（后面这个另类币改名叫DASH），在DASH之后也被其他一些另类币所使用。X11的目的是使设计一个有效的ASIC变得十分复杂，因为所有的11个函数的计算模块都要在芯片上被实施。但这其实对硬件设计者来说，也不过是一个小小的不方便而已。如果有一个针对X11的ASIC诞生，那么马上会废弃掉X11的CPU和GPU挖矿。
1703867907
1703867908
