1703867834
区块链技术驱动金融：数字货币与智能合约技术 [:1703863956]
1703867835
区块链技术驱动金融：数字货币与智能合约技术 8.2 反ASIC解谜算法
1703867836
1703867837
首先我们从讨论设计一个可以反ASIC解谜(ASIC-resistant puzzles)的挑战开始，这个挑战也是最被广泛讨论和追求的可替代目前比特币挖矿解谜的一种。我们在第5章中讨论过，比特币挖矿最初是用普通电脑，然后再升级到GPU和定制化的FPGA设备，到现在基本上由非常强大的优化过的ASIC芯片所垄断。现在的ASIC的挖矿运算能力比一般电脑甚至早期的ASIC都要高太多。一般的电脑即使硬件本身是免费的，也会因为电费价格等因素而变得不可行。
1703867838
1703867839
这个转变意味着，在比特币生态系统里的大部分个体（例如使用比特币交易的客户和商家）已经无法参与到挖矿过程中了。有些人认为这是一个危险的势头，一小部分职业矿工控制了整个挖矿的过程。在中本聪最初有关比特币的论文里，用到过“一个CPU一票”的说法，这个说法时不时被有些人用来说明比特币应该是一个被全部用户所拥有的民主系统。
1703867840
1703867841
其他人觉得ASIC的崛起是不可避免的，而且这也不会伤害到比特币，这种希望实现反ASIC的愿望也只是有些人希望回到“过去的好时光”。对于反ASIC是否可取，我们保持中立的态度，因为只有这样，我们才可以深入讨论一些技术上的挑战和提议的方案，来实现反ASIC的目标。
1703867842
1703867843
反ASIC到底是什么意思
1703867844
1703867845
大致上说，我们想抑制为了挖矿而特别定制的设备的优势。这也可以理解为，设计一个解谜程序，让现有的普通电脑成为最廉价和最有效率的解谜运算设备。但这在现实中不可能，毕竟所有的通用电脑的中央处理器里已经针对一些特殊目的进行了优化。并不是所有的电脑都有相同的优化配置，并且它们随着时代而改变。比如，过去的10年中，英特尔（Intel）和AMD在芯片里加入特殊指令（通常叫作“增加硬件支持”）来更加有效地计算高级加密标准（Advanced Encryption Standard，简称AES）的区块密码。所以有些电脑在挖矿这个事情上总是会比其他电脑更加低效。另外，很难想象设计一个挖矿解密程序，而这些程序是依赖普通个人电脑诸如音响或显示器这些特性的，所以去除了那些通用特性的具有特殊目的的设备，很可能会更有效率，并且成本更低。
1703867846
1703867847
更加实际地说，我们有一个适中的目标：设计一个解谜程序，尽可能地减少最有效率的定制运算设备与通用电脑之间的效率差距。ASIC还是会不可避免地成为更加有效的挖矿机，但我们至少可以将其运算效能限制在一定范围内，从而让个人用户使用他们已有的通用电脑来挖矿仍具备一定的经济效应。
1703867848
1703867849
刚性内存解谜
1703867850
1703867851
大多数被设计成反ASIC的解谜程序中，最普遍被应用的叫作刚性内存解谜（memory-hard puzzles）——解谜需要大量的内存来计算，而不是靠大量的CPU时间。一个类似但又不一样的概念是内存限制解谜（memory-bound puzzles），花在读取内存上的时间，占据了这种程序大部分的计算时间。一个解谜可以是刚性内存类而不是内存限制类，或是内存限制类而不是刚性内存类，或是二者兼而有之。一个微妙但重要的区别在于，虽然CPU的速度是计算时间的瓶颈，但平行运算大量解谜的成本，还是被内存的成本所左右，或者反之亦然。通常对于运算类的解谜程序，我们要做到刚性内存和内存限制，就需要保证在运算过程中大量的内存被要求使用，使之成为一个限制性因素。
1703867852
1703867853
为什么刚性内存解谜或内存限制解谜可以反ASIC？因为用来计算哈希函数的逻辑运算只占了CPU里的一小部分，意思是在比特币的解谜计算里，ASIC不需要执行一些不必要的功能，而只需要执行计算哈希函数的相关功能，所以占了很大优势。另外一个相关因素是，不同的内存性能上的差异（和单位性能的成本）比不同处理器之间运算速度上的差异要小很多，所以，如果我们设计了一个刚性内存类的解谜，计算时需要相对简单的算力但需要大量的内存，这就意味着，解密成本的上升速率将会像内存成本提升速率那样，在一个相对低一些的水平。[1]
1703867854
1703867855
SHA-256已经被认定为不是刚性内存解谜算法。它只需要一个小小的256位模块，可以很容易地被放进CPU的注册机里。但设计一个刚性内存类的工作量证明解谜不是一件太难的事。
1703867856
1703867857
Scrypt
1703867858
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