ASIC 矿机中心化太严重?我们设计了一种对抗“矿霸”的算法

发布时间:2019-08-08 16:04:06 来源:金世豪娱乐网址-金世豪娱乐手机版-金世豪官方网站点击:22

  编者按:本文来自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 算法进行优化获得的性能增益应该非常有限。

  在 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 [ 3 ]的实现对动态搜索树进行插入/删除操作性能,来初步验证以上思路是否成立。实验中,我们使用具有以下配置的CPU,CPU的代码可以在这里找到:(https://github.com/QuarkChain/pyquarkchain/blob/1bcbb7401060a63773f26aa45558c62eb770be53/qkchash/set_benchmark.cpp)

  性能结果:

  几点补充说明

  参考文献