我们写作这篇文章的目的,主要是想通过展示我们关于这个主题的一些初步想法,来和同行进行讨论,欢迎大家提意见。
动机
众所周知,比特币挖矿主要是由是由 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 的优化是如何工作的。
目前,这种流水线化的思想还被广泛地应用于诸如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的关键差异如下:
由于datablock是一个支持有序数据查找的动态列表,因此datablock的有效实现方式可以是一棵具有顺序统计的动态搜索树(DST,例如,AVL树、红黑树、B+树)。想要使用流水线来加速树的删除/插入操作是困难的,因为树的执行路径是随机的,并且高度依赖于随机输入量。
CPU和FPGA实现的性能比较
我们将对比CPU和FPGA [ 3 ]的实现对动态搜索树进行插入/删除操作性能,来初步验证以上思路是否成立。实验中,我们使用具有以下配置的CPU,CPU的代码可以在这里找到:(https://github.com/QuarkChain/pyquarkchain/blob/1bcbb7401060a63773f26aa45558c62eb770be53/qkchash/set_benchmark.cpp)
性能结果:
几点补充说明
参考文献
本文来源:Odaily