找回密码
 立即注册

QQ登录

只需一步,快速开始

  • QQ空间
  • 回复
  • 收藏

ASIC 矿机中心化太严重?怎样设计算法来降低 ASIC 矿机的挖矿效率

kg01 2018-10-16 19:33:20 显示全部楼层 阅读模式 打印 上一主题 下一主题
我们写作这篇文章的目的,主要是想通过展示我们关于这个主题的一些初步想法,来和同行进行讨论,欢迎大家提意见。
动机
众所周知,比特币挖矿主要是由是由 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

    本文来源:Odaily
  • 回复

    使用道具 举报

    说点什么

    您需要登录后才可以回帖 登录 | 立即注册