编者按：本文来自QuarkChain（ID：quarkchain），作者：QuarkChain团队，星球日报经授权转载。
我们写作这篇文章的目的，主要是想通过展示我们关于这个主题的一些初步想法，来和同行进行讨论，欢迎大家提意见。
动机
众所周知，比特币挖矿主要是由是由 ASIC（针对专门应用开发的集成电路）矿机来完成的。这是因为 ASIC 设备的效率（从焦耳/哈希的角度看）比普通 CPU 高 1000 多倍。由于高性能 ASIC 的制造被掌控在少数几个厂商手中，这引起了人们对于挖矿中心化的担忧。
因此，开发者们提出了几种抵抗 ASIC 优化的算法，其中包括：Ethhash、CyptoNight 和 Equihash。但不幸的是，市场上还是出现了一些针对以上算法进行 ASIC 优化的矿机，它们声称比 CPU 或者显卡挖矿显著的提高了效率（有关内容请参阅 https://github.com/if.lse/ProgPOW）。
在这些算法中，Ethash 可能是被 ASIC 优化后效率增益最小的一种。Ethash 算法的核心思想是通过执行内存密集型操作而取代计算密集型操作。这样内存的读取性能成为哈希算法的瓶颈，从而限制 ASIC 的优化效果。如果假设定制开发的硬件很难提高内存的读取速度，则通过 ASIC 对 Ethash 算法进行优化获得的性能增益应该非常有限。
基于顺序统计的哈希算法的想法（Oshash）
在 Ethash 算法的启发下，我们提出一种新的算法（Oshash），旨在通过限制 ASIC 的并行计算能力，从另一个方面来抵抗 ASIC 对挖矿效率的提升。先让我们看看 ASIC 的优化是如何工作的。
一组固定指令实际上可以被分解成一个电路流水线，因此每个时钟周期（有时是多个周期），ASIC可以同时求解多个输入值的哈希值。例如，a+b+c+d的指令可以被流水线化，使得每个运算周期可以同时计算3个不同的输入：1, a0+b0；2, b1+c1；3, c2+d2
可以在ASIC中建立多个电路逻辑，同时并发的计算多个指令。例如，上文的a + b + c + d指令可以被设计为(a + b) + (c + d)，将在2个周期中完成计算。
目前，这种流水线化的思想还被广泛地应用于诸如x86之类的现代处理器中，这些x86中具有分支预测器[2]和流水线微处理器。一种避免处理器计算流水线的方法是执行多个if-then-else命令，然后在不同的分支上执行不同的代码路径，这使得流水线和分支预测变得很难。
为了打破执行过程的并发性，我们可以考虑采用于状态依赖的思路——任何未来的指令都依赖于当前状态，而这种状态（当前状态）可以频繁地被改变，这意味着我们不能预先执行未来的指令。
基于顺序统计的哈希算法
在本节中，我们将介绍我们提出的顺序统计哈希算法（Oshash）。该算法试图打破流水线，使代码的执行路径变得更加随机。在介绍这种新算法之前，让我们重新回顾一下Ethash算法的核心内容，看看Ethash是如何生成一个哈希值的：
Input:
- state: 128-byte state
- datablock: an array of large amount of data, each data is 64 bytes
- H(x, y): a fast hash algorithm, x and y has the same size, return the hash value with the same size as x
- R(x): return an 32-bit random integer derived from x
Algorithm:
for i in range(64):
p = R(state) % (len(datablock) - 1)
newdata = [datablock[p], datablock[p + 1]]
state = H(state, newdata)
return state
Oshash算法的初步方案如下：
Input:
- state: 128-byte state
- datablock: an long array with each entry being 8 bytes
- H(x, y): a fast hash algorithm, x and y has the same size, return the hash value with the same size as x
- R(x): return an 64-bit random integer derived from x
Algorithm:
for i in range(64):
p = R(state) % len(datablock)
newdata = []
for j in range(128 / 8):
newdata = newdata.add(datablock.find_by_order(p))
# Remove the pth smallest element from datablock
datablock.remove_by_order(p)
# Add a random data to the datablock, e.g.,
# datablock.insert(R([newdata[end]]))
# Find the next index, e.g.,
# p = R([state, p]) % len(datablock)
state = H(state, newdata)
return state
Oshash算法与Ethash的关键差异如下：
原算法是根据随机索引数p去寻值，而新算法根据第p位的最小值去寻值。
在读取了datablock变量中的一个数据后，该数值将被删除，新的随机数值值将被插入到datablock中。
由于datablock是一个支持有序数据查找的动态列表，因此datablock的有效实现方式可以是一棵具有顺序统计的动态搜索树（DST，例如，AVL树、红黑树、B+树）。想要使用流水线来加速树的删除/插入操作是困难的，因为树的执行路径是随机的，并且高度依赖于随机输入量。
CPU和FPGA实现的性能比较
我们将对比CPU和FPGA [ 3 ]的实现对动态搜索树进行插入/删除操作性能，来初步验证以上思路是否成立。实验中，我们使用具有以下配置的CPU，CPU的代码可以在这里找到：（https://github.com/QuarkChain/pyquarkchain/blob/1bcbb7401060a63773f26aa45558c62eb770be53/qkchash/set_benchmark.cpp）
CPU型号: Intel i7-7700K
OS操作系统: Ubuntu 16.04 LTS
编译器: g++ 5.4.0
编译命令: g++ -O3 -std=gnu++17
线程数: 1
键值数: 64K
键值类型: unsigned 64-bit random integers
性能结果：
FPGA：每秒执行397万个插入/删除操作
CPU：每秒执行446万个插入/删除操作
几点补充说明
跟FPGA实现的搜索性能比较（每秒能完成2.42亿次搜索），FPGA实现的插入/删除操作的性能要低得多，这是因为每个插入/删除操作需要更多的执行周期，而每个搜索任务可以在一个周期中完成。
实验中，FPGA的性能是根据Virtex 5 LX330 FPGA测算的，该FPGA可能已经过时了。如果采用最新的FPGA，性能可能会提升一些。
CPU的性能是根据单线程/单核测算的，如果使用多线程/多核，性能可能会更高。
本测算中CPU中的键值大小是64位， FPGA中的是32位。
参考文献
https://github.com/ifdefelse/ProgPOW
Branch preditor, Wikipedia, https://en.wikipedia.org/wiki/Branch_predictor
Yang, Y-H. E. and Prasanna, V. K., High Throughput and Large Capacity Pipelined Dynamic Search Tree on FPGA, 18th Annual ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, 2010
