ProgPoW是一种PoW算法，旨在缩小与专用的ASIC之间的效率差距。它几乎利用了标准硬件（GPU）的所有性能，并预先为以太坊网络中最常见的硬件进行了调整和优化。自从首个比特币挖矿ASIC问世以来就出现了很多新的PoW算法，旨在维持“ASIC抗性”。而所谓的“ASIC抗性”则在于抵制PoW挖矿算力的中心化，防止采用这类算法的币种被少数参与者操控。本文将首先介绍ProgPoW这个新算法以及其为“ASIC抗性”带来的影响。另外，文章还会分析不同的PoW算法在硬件中的使用状况，并作出比较。最后，我们会通过分析代码来谈一谈ProgPoW的部署方式。简单介绍一下ProgPoWProgPoW的设计目标就是要让这个算法的需求与显卡相匹配：如果该算法要部署在特定的ASIC上，那么与显卡相比，其效率提升幅度并不大。ProgPoW的主要特点是：– 将keccak_f1600（64位字）改为keccak_f800（32位字）来减少对总算力的影响– 增加混合状态– 在主循环中添加随机数学序列– 添加支持随机地址的低延时、小规模的缓存读取– 将DRAM（动态随机存取存储器）读取从128字节增加到256字节尽管ASIC也可以部署这个代码，但在效率方面几乎没有任何帮助。大多数显卡都需要支持上述特点。唯一可优化的部分在于：移除图形管线（显示、几何引擎、表面纹理等）以及浮点数学。这将提高大约1.1-1.2倍的效率，比Ethash（2倍）或者Cryptonight（50倍）要少得多。标准硬件的PoW应用概述随着大型矿池的不断发展，形成了少数矿池控制大量算力的局面，因为只有加入这些矿池，小矿工才能获得更稳定的经济收益。虽然有些人认为大型的集中式矿池违背了“ASIC抗性”，但有一点很重要，即基于ASIC的币种事实上反而更加中心化，原因如下：1. 不存在自然的分布：除了挖矿之外，这类专业硬件不会创造其它经济目的，因此大多数人不会持有这类硬件。2. 没有后备组织：当价格波动性较大以及容易受到操控的时候，没有后备的硬件或者利益相关方可以入场。3. 准入门槛较高：入场较早的矿工已经非常富有，他们可以在未知的新币种上投入资金和生态资源。因此，通过挖矿进行的初始代币分配存在局限性，可能导致中心化的“经济偏差”。4. 委托中心化 VS 部署中心化：虽然矿池的中心化是用户委托造成的，但硬件的单一化则不是：只有这种硬件的特定买家才能参与挖矿，因此不可能在短时间内剥夺矿池的控制权。5. 即使采用去中心化的挖矿方式，也很难实现去中心化的控制：一旦大型ASIC制造商参与进来，设计后门硬件就变得毫无意义。在市场中保证透明和公平对ASIC制造商来说没有任何好处。尽管维持“ASIC抗性”的这一目标是非常有价值的，但“ASIC抗性”这个概念是存在谬误的。CPU（中央处理器）和GPU（显卡）本身就是ASIC。理论上来说，任何可以在商用ASIC（CPU或GPU）上运作的算法都能够部署特定的ASIC。部分算法甚至被刻意做成是“ASIC友好型”——部署ASIC后的挖矿效率远远高于运行普通硬件的同类算法。这一现象对于专业的ASIC矿机制造商来说极具吸引力。因此，ASIC抗性指的是：专业的硬件和普及度及应用度更高的硬件之间的效率差距。定制和通用硬件之间的效率差越小就意味着抗性越强，算法也就越好。这种效率差是衡量PoW算法质量的合理标准。效率意味着绝对的性能、效能功耗比或者性价比——这几点之间都是高度相关的。如果一家公司生产且控制的ASIC效率极高，那么他们就能够控制51%的网络算力，就很可能发动攻击。PoW算法一览SHA256（部署ASIC后挖矿效率增长约1000倍）SHA算法是一系列的简单数学运算——加法、逻辑和旋转运算。处理CPU或GPU的单点运算需要获取并解码一条指令，从寄存器文件中获取数据，执行这条指令，然后把结果写到寄存器文件中。这个过程需要大量的时间和资源。在ASIC中实现的单点运算需要少量的晶体管和导线。这意味着每个单独的操作只需要消耗极少的功率、空间或时间。通过列出所需操作的序列就可以构建散列核心（hashing core）。这个散列核心可以在短时间内执行操作序列，与CPU和GPU相比，所需消耗的功率和空间也更少。比特币ASIC由许多相同的散列核心和一些最小的芯片外通信组成。Scrypt和NeoScrypt（部署ASIC后挖矿效率增长约1000倍）从算法和位操作上来看，Scrypt和NeoScrypt与SHA类似。不幸的是，采用这类算法的币种，例如莱特币，他们的PoW挖矿算法只使用一种容量介于32kb和128kb之间的暂存器。这个暂存器的容量非常小，非常适合ASIC，因此这个算法的ASIC部署与SHA类似，都会造成效率的大幅提升。X11和X16R（部署ASIC后挖矿效率增长约1000倍）X11（以及类似的X系列）要求11个独一无二的散列核心以固定的顺序排列。每个散列核心的效率都和单个SHA核心类似，因此从总体设计上来看，两者的效率增长依然类似。X16R要求多个散列核心通过简单定序状态机进行互动。每个单独的核心都会有类似的效率增长，测序逻辑将花费最少的功率、空间以及时间。Baikal BK-X就是一种包含多个散列核心以及一个可编程定序器的ASIC，其已经进行了升级以支持哈希排列顺序不同的新算法。Equihash（部署ASIC后挖矿效率增长约100倍）150mb的状态（state）很大，但是通过ASIC是有可能实现的。通过ASIC可以快速完成位串的读出（binning）、排序和对比。Cuckoo Cycle（部署ASIC后挖矿效率增长约100倍）一旦发生时间/内存权衡攻击（Time/Memory Tradeoff attacks），芯片所需状态量就不明确了。一个专业的图遍历（graph traversal）核心和SHA计算核心的效率增长类似。CryptoNight（部署ASIC后挖矿效率增长约50倍）与Scrypt相比，CryptoNight做的计算要少得多，需要2mb的暂存器（没有已知的时间/内存权衡攻击）。这个大容量的暂存器将会主导ASIC部署，限制散列核心的数量以及ASIC的绝对性能。ASIC几乎完全由片上SRAM（静态随机存储器）组成。Ethash（部署ASIC后挖矿效率增长约2倍）由于大容量DAG（数据库可用性组）的存在，Ethash需要外部存储。然而，它只需要这一点——需要对内存加载结果进行计算的情况很少。因此，ASIC可以从一定程度上消除GPU的复杂性和能耗，只需要形成一个连接到小型计算引擎的内存接口。ProgPoW算法演练这里生成的DAG和Ethash中的完全一样。唯一的区别是生成了额外的PROGPOW_SIZE_CACHE值的数据，这些数据将驻留在L1缓存中，而不是在framebuffer（帧缓存）中。ProgPoW可以采用以下参数进行调试，相关设置已经针对一系列通用GPU进行了调整：– PROGPOW_LANES：为计算一个散列实例而协调的平行行数；默认值为32– PROGPOW_REGS：寄存器文件的使用大小；默认值是16– PROGPOW_CACHE_BYTES：缓存器容量；默认值是16*1024– PROGPOW_CNT_MEM：帧缓冲器访问的次数，定义为算法的外部循环；默认值是64（和Ethash一样）– PROGPOW_CNT_CACHE：每个循环的缓存访问次数；默认值是8– PROGPOW_CNT_MATH：每个循环的数学运算次数；默认值是8ProgPoW用FNV1a来合并数据。Ethash用FNV1来合并数据，但FNV1a能够实现更好的分布特性。ProgPoW用KISS99生成随机数。这是最简单的（最少指令）随机数生成器，通过了TestU01统计测试。像Mersenne Twister这样更复杂的随机数生成器可以在专用ASIC实现有效部署，从而提高挖矿效率。uint32_t fnv1a(uint32_t &h, uint32_t d) { return h = (h ^ d) * 0x1000193; } typedef struct { uint32_t z, w, jsr, jcong; } kiss99_t; // KISS99 is simple, fast, and passes the TestU01 suite // https://en.wikipedia.org/wiki/KISS_(algorithm) // http://www.cse.yorku.ca/~oz/marsaglia-rng.html uint32_t kiss99(kiss99_t &st) { uint32_t znew = (st.z = 36969 * (st.z & 65535) + (st.z >> 16)); uint32_t wnew = (st.w = 18000 * (st.w & 65535) + (st.w >> 16)); uint32_t MWC = ((znew > 13), st.jsr ^= (st.jsr
混合数据的lane *REGS是从散列的种子进行初始化的。void fill_mix( uint64_t hash_seed, uint32_t lane_id, uint32_t mix[PROGPOW_REGS] ) { // Use FNV to expand the per-warp seed to per-lane // Use KISS to expand the per-lane seed to fill mix uint32_t fnv_hash = 0x811c9dc5; kiss99_t st; st.z = fnv1a(fnv_hash, seed); st.w = fnv1a(fnv_hash, seed >> 32); st.jsr = fnv1a(fnv_hash, lane_id); st.jcong = fnv1a(fnv_hash, lane_id); for (int i = 0; i = kiss99(st); }
主要的搜索算法采用了Keccak海绵函数（宽度为800位，448比特率和352的容量）来生成一个种子，扩展种子，并在混合数据过程中加载序列和进行随机运算，然后压缩结果到最终的Keccak排列（参数相同）进行目标比较。bool progpow_search( const uint64_t prog_seed, const uint64_t nonce, const hash32_t header, const uint64_t target, const uint64_t *g_dag, // gigabyte DAG located in framebuffer const uint64_t *c_dag // kilobyte DAG located in l1 cache ) { uint32_t mix[PROGPOW_LANES][PROGPOW_REGS]; uint32_t result[8]; for (int i = 0; i = 0; // keccak(header..nonce) uint64_t seed = keccak_f800(header, nonce, result); // initialize mix for all lanes for (int l = 0; l ); } // Reduce all lanes to a single 128-bit result for (int i = 0; i = 0x811c9dc5; for (int l = 0; l
内循环采用FNV和KISS99从prog_seed生成随机序列。这个随机序列决定访问哪个混合状态以及执行什么随机运算。由于对prog_seed的更改相对较少，因此可以预料到的是，在挖矿过程中将会编译progPowLoop，而不是进行动态执行。kiss99_t progPowInit(uint64_t prog_seed, int mix_seq[PROGPOW_REGS]) { kiss99_t prog_rnd; uint32_t fnv_hash = 0x811c9dc5; prog_rnd.z = fnv1a(fnv_hash, prog_seed); prog_rnd.w = fnv1a(fnv_hash, prog_seed >> 32); prog_rnd.jsr = fnv1a(fnv_hash, prog_seed); prog_rnd.jcong = fnv1a(fnv_hash, prog_seed >> 32); // Create a random sequence of mix destinations for merge() // guaranteeing every location is touched once // Uses Fisher–Yates shuffle for (int i = 0; i = i; for (int i = PROGPOW_REGS - 1; i > 0; i--) { int j = kiss99(prog_rnd) % (i + 1); swap(mix_seq, mix_seq[j]); } return prog_rnd; }
将数值合并到混合数据中的数学运算是为了保持熵。// Merge new data from b into the value in a // Assuming A has high entropy only do ops that retain entropy // even if B is low entropy // (IE don't do A&B) void merge(uint32_t &a, uint32_t b, uint32_t r) { switch (r % 4) { case 0: a = (a * 33) + b; break; case 1: a = (a ^ b) * 33; break; case 2: a = ROTL32(a, ((r >> 16) % 32)) ^ b; break; case 3: a = ROTR32(a, ((r >> 16) % 32)) ^ b; break; } }
为随机数学选择的数学运算在CUDA和OpenCL（通用GOU的两种主要编程语言）中易于实现。// Random math between two input values uint32_t math(uint32_t a, uint32_t b, uint32_t r) { switch (r % 11) { case 0: return a + b; case 1: return a * b; case 2: return mul_hi(a, b); case 3: return min(a, b); case 4: return ROTL32(a, b); case 5: return ROTR32(a, b); case 6: return a & b; case 7: return a | b; case 8: return a ^ b; case 9: return clz(a) + clz(b); case 10: return popcount(a) + popcount(b); } }
主循环：// Helper to get the next value in the per-program random sequence #define rnd() (kiss99(prog_rnd)) // Helper to pick a random mix location #define mix_src() (rnd() % PROGPOW_REGS) // Helper to access the sequence of mix destinations #define mix_dst() (mix_seq[(mix_seq_cnt++)%PROGPOW_REGS]) void progPowLoop( const uint64_t prog_seed, const uint32_t loop, uint32_t mix[PROGPOW_LANES][PROGPOW_REGS], const uint64_t *g_dag, const uint32_t *c_dag) { // All lanes share a base address for the global load // Global offset uses mix[0] to guarantee it depends on the load result uint32_t offset_g = mix[loop%PROGPOW_LANES][0] % DAG_SIZE; // Lanes can execute in parallel and will be convergent for (int l = 0; l >32, rnd()); } }