Bitguai.com

区块链技术丨改变世界
做高价值的区块链资讯媒体

ProgPoW算法:优化显卡性能,抵制ASIC

目标就是要让这个算法的需求与显卡相匹配:如果该算法要部署在特定的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:每个循环的数学运算次数;默认值是8

ProgPoW用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 << 16) + wnew);
 uint32_t SHR3 = (st.jsr ^= (st.jsr << 17), st.jsr ^= (st.jsr >> 13), st.jsr ^= (st.jsr << 5));
 uint32_t CONG = (st.jcong = 69069 * st.jcong + 1234567);
 return ((MWC^CONG) + SHR3);
 }

混合数据的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 < PROGPOW_REGS; i++)
 mix[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 < 8; i++)
 result[i] = 0;
 // keccak(header..nonce)
 uint64_t seed = keccak_f800(header, nonce, result);
 // initialize mix for all lanes
 for (int l = 0; l < PROGPOW_LANES; l++)
 fill_mix(seed, l, mix);
 // execute the randomly generated inner loop
 for (int i = 0; i < PROGPOW_CNT_MEM; i++)
 progPowLoop(prog_seed, i, mix, g_dag, c_dag);
 // Reduce mix data to a single per-lane result
 uint32_t lane_hash[PROGPOW_LANES];
 for (int l = 0; l < PROGPOW_LANES; l++)
 {
 lane_hash[l] = 0x811c9dc5
 for (int i = 0; i < PROGPOW_REGS; i++)
 fnv1a(lane_hash[l], mix[l][i]);
 }
 // Reduce all lanes to a single 128-bit result
 for (int i = 0; i < 8; i++)
 result[i] = 0x811c9dc5;
 for (int l = 0; l < PROGPOW_LANES; l++)
 fnv1a(result[l%8], lane_hash[l])
 // keccak(header .. keccak(header..nonce) .. result);
 return (keccak_f800(header, seed, result) <= target);
 }

内循环采用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 < PROGPOW_REGS; i++) mix_seq[i] = i; for (int i = PROGPOW_REGS - 1; i > 0; i--)
 {
 int j = kiss99(prog_rnd) % (i + 1);
 swap(mix_seq[i], 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 < PROGPOW_LANES; l++)
 {
 // global load to sequential locations
 uint64_t data64 = g_dag[offset_g + l];
 // initialize the seed and mix destination sequence
 int mix_seq[PROGPOW_REGS];
 int mix_seq_cnt = 0;
 kiss99_t prog_rnd = progPowInit(prog_seed, mix_seq);
 uint32_t offset, data32;
 int max_i = max(PROGPOW_CNT_CACHE, PROGPOW_CNT_MATH);
 for (int i = 0; i < max_i; i++)
 {
 if (i < PROGPOW_CNT_CACHE)
 {
 // Cached memory access
 // lanes access random location
 offset = mix[l][mix_src()] % PROGPOW_CACHE_WORDS;
 data32 = c_dag[offset];
 merge(mix[l][mix_dst()], data32, rnd());
 }
 if (i < PROGPOW_CNT_MATH) { // Random Math data32 = math(mix[l][mix_src()], mix[l][mix_src()], rnd()); merge(mix[l][mix_dst()], data32, rnd()); } } // Consume the global load data at the very end of the loop // Allows full latency hiding merge(mix[l][0], data64, rnd()); merge(mix[l][mix_dst()], data64>>32, rnd());
 }
 }

本文由比特怪小编整理编辑发布,文章地址:https://www.bitguai.com/block/jishu/23626.html,转载请注明出处!

免责声明:转载此文为传递更多市场信息,不代表比特怪的观点和立场,请自行参考。



商务合作(QQ):755847138
媒体合作:Market@bitguai.com
底部导航

本站除标明"本站原创"外所有信息均整理转载自互联网,版权归原作者所有。如有不妥,请联系我们修改或删除。

CopyRight 2017-2018 Bitguai.com All Rights Reserved丨苏ICP备18049263号-1 百度地图 谷歌地图 RSS订阅


比特怪成立于2017年,秉承做高价值的区块链技术和应用为核心的区块链资讯媒体。网站内容主要涵盖区块链技术、游戏、应用场景和区块链项目落地等。让区块链技术应用服务于各个行业。