本项目的目标是设计一种在CPU上可以较为高效的工作量证明方案，该方案可以有效确保在GPU、FPGA、ASIC上难以同样的效率执行。创造性地设计单向函数CryptoHello，满足y=CryptoHello(x)。CryptoHello满足散列函数应有的特性，即单向性、雪崩性、随机性，其计算效率在CPU上较高，但是在GPU、FPGA、ASIC上难以发挥出性能。
为了防止GPU、FPGA、ASIC上的高效实现，CryptoHello的设计需要满足以下特征：
（1）内存受限。需要较大空间的内存容量，而且对内存有大量的随机访问。考虑到CPU 和GPU的cache容量差异，内存容量大约在1MB左右。
（2）高度串行化。CryptoHello的计算过程中基本没有可以并行执行的成分，必须严格按照串行执行；
（3）大量的控制相关性。即CryptoHello中需要执行比较多的条件分支指令，而且这些分支转移的概率均接近50%；
（4）组合多种的散列函数。这主要是防止ASIC芯片中针对每种散列函数专门定制设计。如果是有很多种散列函数，将大幅度增加ASIC芯片的芯片面积。
【定义1】 单向函数族hi，0≤i≤15，共计16种不同的单向函数。每个单向函数的输入固定为256位（h0的输入可以是任意长度），输出固定为256位。
【定义2】 工作存储器M，总容量为|M|字节，|M|能被32整除，目前设置在为1M。
【定义3】 伪随机函数发生器seed(uint48 s)为设置随机数发生器种子，rand()为随机数发生器结果，返回48位无符号整数。该函数满足Xn+1 = (aXn + c) mod m, n ≥0，其中m = 248，a =25214903917, c = 11（glibc的rand48()线性同余伪随机数发生器）
【定义4】 单向函数y=H(x)，其中y为256位。
【定义5】 reduce_bit(x, y)将x的内容规约到y位。设x的位数为l，应满足l≥y。
将x的长度补零扩展到y的整数倍，得到长度为L的二进制串X，然后再将X分为L/y段长度为y的段，将这L/y段内容异或得到最终结果。
【定义6】 RRS(x, y)将x循环右移y位。
算法分为三步骤：1）初始化工作存储器M；2）修改工作存储器M内容；3）根据工作存储器内容产生最后的结果。
输入：x 单向函数y=CryptoHello(x)的输入
输出：M 工作存储器
参数：K 用于调整计算速度，K越大计算速度越快
中间变量：
a, b均为长度为32个字节的向量，a[c1:c2]表示其中的第c1:c2个字节；
i为32位无符号整数；
- a[0:31]=h0(x);
- i从0到|M|/32-1循环 //如果|M|为1M，循环2^15次
2.1 如果i mod K ≠0 //K是一个可以选择的参数，用于调整产生速度
2.1.1 b[0 : 7] = rand0()xor(rand0()<<16); 2.1.2 b[8 :15] = rand1()xor(rand1()<<16);
2.1.3 b[16:23]= rand2()xor(rand2()<<16);
2.1.4 b[24:31]= rand3()xor(rand3()<<16);
2.1.5 b[0 : 31]= RRS(b[0:31], reduce_bit(i,8));
2.1.6 M[32i:32i+31]=b[0:31];
2.1.7 a[0:31]= a[0:31] xor b[0: 31];
2.2 否则
2.2.1 t=reduce_bit(a[0:31],4);
2.2.2 a[0:31]=ht(RRS(a[0:31], reduce_bit(i,8)));
2.2.3 seed0(reduce_bit(a[ 0: 7],48)); seed1(reduce_bit(a[ 8:15],48));
seed2(reduce_bit(a[16:23],48)); seed3(reduce_bit(a[24:31],48));
2.2.4 M[32i:32i+31]= a[0:31];
算法说明
本算法的目的是产生一个容量大小为|M|的伪随机内存内容。算法第2步中，每次循环每次产生32字节内容，其中连续K-1次由随机数发生器产生（2.1步），1次由单向函数产生（2.2步）。单向函数的计算速度较慢，而随机数发生器的填充速度较快，通过增加K可以减少单向函数的调用时间，提升填充速度。
在随机数填充部分（2.1.1到2.1.4步）中，有四路48位独立设置种子的随机数产生器，它们的结果合成一个64位的伪随机数。在合成64位随机数后，再使用不定长循环移位方法增加预测产生内容的难度。确定32字节随机数块的因素有两个：四个48位的随机数种子和2^15种循环变量i的可能性，因此决定这32字节内容的输入可能性总共有2^(96+15)=2^111。这使得难以通过预计算的方法，预先确定每个存储块的内容。
调用单向函数族时（2.2.2步），其输入内容不仅仅依赖于上一次单向函数的输出，而且依赖于前面K-1个存储块的内容（2.1.7步）这使得单向函数的计算必须在随机数填充完成后才能进行。单向函数输入的内容依赖于256位的数值和256种移位数，其可能性达到2^(256+8)=2^264，从而使得2.2.2步难以通过预计算方式存储。
2.2.3步将为后续的随机数填充设定新的种子，这使得后续的随机数填充块必须在单向函数计算完成之后才能继续。
从上述分析可以看出，该方法满足以下特征：1）必须严格顺序执行；2）决定每32字节存储块内容的因素都足够大，难以通过预计算方法产生。
算法-1流程图
输入：M M[addr]表示地址为addr的一个字节
参数：L 用于平衡存储器访问和散列函数计算之间的时间比例，目前设置为1
C 用于调整计算轮数，不应该小于|M|/128
输出：M
c 32字节数组，用于向下一个算法传递随机变量
中间变量：s, t1, t2为8位无符号整数，i为32位无符号整数，r为64位无符号整数，b为64字节数组，a为32字节数组
- a[0:31]=c[0:31]=h0(M[|M|-32:|M|-1]); r=reduce_bit(a[0:31], 64); //对最后一块进行散列
- i从0到C次循环
2.1 seed(reduce_bit(a[0:31], 48)); //初始化随机数发生器
2.2 j从0到64*L-1循环 //修改存储器内容，并产生新的散列函数输入
2.2.1 base=(rand()+r) mod 2^64; offset= (reduce_bit(r,8)<<8)+1; //产生随机地址
2.2.2 addr1=(base-offset) mod |M|; addr2=(base+offset) mod |M|
2.2.3 t1=M[addr1]; t2=M[addr2]; s=a[j mod 32];
2.2.4 M[addr1]= t2 xor s; M[addr2]= t1 xor s; b[j mod 64]=t1 xor t2; //修改工作存储器
2.2.5 r=(r+s+t1+t2) mod 2^64; 2.3 t=reduce_bit(r,4); 2.4 a[0:31]=reduce_bit(b[0:63], 256); 2.5 a[0:31]=ht(RRS(a[0:31], reduce_bit(i+r,8))); 2.6 c[0:31]=c[0:31] xor a[0:31]
算法说明
算法的第1步获取M的最后一块内容进行散列函数计算，这就需要完整地完成算法-1之后才能进行本算法，保证了两个算法的顺序性。
算法的核心是第2步，其主要目的是随机化地修改M中的内容。分为两个阶段：1）根据参数随机地修改存储器内容（2.1~2.2步）；2）根据排序后的内容使用单向函数族，重新产生存储器修改参数。
在存储器修改阶段，每次修改2个字节的内容，其地址的产生由上一次单向函数的结果a和r共同决定。其中r的修改（2.2.5步）依赖于前面所有存储器访问的值和单向函数的结果。2.2步的每次循环中，会产生两个存储器访问地址，它们的差距是2×offet+2。由于offset的低8位为0，使得在offset不等于0的情况下，两者的差距在512字节以上，此时这两次存储器访问不会落在同一个cache行中。当reduce_bit(r,8)大于4时，两者的差距在2K以上，而2KB往往是DRAM的一个存储行大小。这使得两次存储器访问很大可能不是在一个存储行中，但是也存在着在一个存储行中的可能性，以增加ASIC存储器系统设计的复杂性。2.2.4步中采用异或方法将两个存储器的内容和单向函数的内容进行相互交叉叠加，保持了原有内容的随机性。
2.5步的单向函数输入取决于当次循环的存储器访问内容，当前循环次数i，以及r（包含了该算法前面执行过程的历史信息）。
2.6步将所有单向函数的执行信息融合在c中，作为后续算法的随机数输入。
算法-2流程图
输入：M 工作存储器
c 上一级算法的随机数种子
参数：D 用于调整单向函数的计算次数。D越大，单向函数的计算次数越少，速度越快，一般设置为素数
输出：y
- y[0:31]=c[0:31]; i=0;
- 循环
2.1 t= reduce_bit(y[0:31],4);
2.2 d=reduce_bit(y[0:31], D)+1;
2.3 j从0到d循环 //至少循环一次
2.3.1 y[0:31]=y[0:31] xor M[32i, 32i+31];
2.3.2 i++;
2.3.3 如果i =|M|/32-1，则
2.3.3.1 y[0:31]=h0(RRS(y[0:31], reduce_bit(i+t,8)));算法结束
2.4 y=ht(RRS(y[0:31], reduce_bit(i+t,8)));
算法说明
该算法的主要目的是快速地基于存储器M的内容产生最后结果，以32字节为单位一段顺序访问存储器M。2.3步中将上次单向函数的结果与d段存储器的内容通过异或方式叠加。d是依赖于上次单向函数结果，且处于0~2^D-1之间的随机值。这里存在着并行计算的可能性，但是由于2.3步中起始的i和d都无法事先预知，无疑会增加判断的难度。
2.4步中单向函数计算加入了循环变量i的因素，使得其输入不仅仅依赖于y，而且和循环的位置相关。通过2.3.1步，单向函数的输入蕴含了所有存储器内容的信息。
2.3.3.1和2.5步决定了在算法的最后一步必须执行单向函数h0。
算法-3流程图
在特定参数的设置下，这三步算法的操作数量如表1-1所示。
表1-1 单向函数CryptoHello的操作数量
| 算法 | 单向函数调用次数 | 存储器访问 |
|---|---|---|
| 算法1 | |M|/32K次 | |M|/32次256位存储器写入 |
| 算法2 | C次 | 128CL次8位存储器读出 128CL次8位存储器写入 |
| 算法3 | |M|/(32*2^(D-1))次 | |M|/32次256位存储器读出 |
参数设置： |M|=1M, K=128, L=4, C=512, D=8
我们使用了如表1-2所示的单向函数族。表1-3给出了各种单向函数的实现细节。
表1-2 单向函数族
| t | 类别 | 函数名 | 代码来源 |
|---|---|---|---|
| 0 | SHA-3 | SHA3-256 | OpenSSL |
| 1 | SHA-1 | SHA-1 | OpenSSL |
| 2 | SHA-2 | SHA-256 | OpenSSL |
| 3 | SHA-2 | SHA-512 | OpenSSL |
| 4 | Whirlpool | Whirlpool | OpenSSL |
| 5 | RIPEMD | RIPEMD-160 | OpenSSL |
| 6 | BLAKE2 | BLAKE2s(256bits) | OpenSSL |
| 7 | AES | AES(128bits) | OpenSSL |
| 8 | DES | DES | OpenSSL |
| 9 | RC4 | RC4 | OpenSSL |
| 10 | Camellia | Camellia(128bits) | OpenSSL |
| 11 | CRC | CRC32 | JTR |
| 12 | HMAC | HMAC(MD5) | OpenSSL |
| 13 | GOST | GOST R 34.11-94 | JTR |
| 14 | HAVAL | HAVAL-256/5 | JTR |
| 15 | Skein | Skein-512(256bits) | JTR |
表1-3 各种单向函数的实现细节
1. 1. SHA1
2. $hash[ 0:19] = sha1($input)
3. $hash[20:39] = sha1(~$input) // ~为按字节取反
4. $output[0:31] = reduce_bit(hash[0:39], 256)
5.
6. 2. SHA256
7. $output[0:31] = sha256($input)
8.
9. 3. SHA512
10. $hash[0:63] = sha512($input)
11. $output[0:31] = reduce_bit(hash[0:63], 256)
12.
13. 4. SHA3-256
14. $output[0:31] = sha3-256($input)
15.
16. 5. Whirlpool
17. $hash[0:63] = whirlpool($input)
18. $output[0:31] = reduce_bit($hash[0:63], 256)
19.
20. 6. RIPEMD-160
21. $hash[ 0:19] = ripemd160($input)
22. $hash[20:39] = ripemd160(~$input)
23. $output[0:31] = reduce_bit(hash[0:39], 256)
24.
25. 7. BLAKE2s(256bits)
26. $output[0:31] = blake2s($input)
27.
28. 8. AES(128bits)
29. $hash[0:31] = sha256($input)
30. $hash2[0:15] = md5($hash[0:31])
31. $key = aes128_set_key($hash2[0:15])
32. $output[ 0:15] = aes128_encrypt($key, $hash[ 0:15])
33. $output[16:31] = aes128_encrypt($key, $hash[16:31])
34.
35. 9. DES
36. $hash[0:31] = sha256($input)
37. $hash2[0:15] = md5($hash[0:31])
38. $key = DES_set_key_unchecked($hash2[0:15])
39. $output[ 0: 7] = DES_encrypt($key, $hash[ 0: 7])
40. $output[ 8:15] = DES_encrypt($key, $hash[ 8:15])
41. $output[16:23] = DES_encrypt($key, $hash[16:23])
42. $output[24:31] = DES_encrypt($key, $hash[24:31])
43.
44. 10. GOST R 34.11-94
45. $output[0:31] = gost($input)
46.
47. 11. HAVAL-256/5
48. $output[0:31] = haval5_256($input)
49.
50. 12. Skein-512(256bits)
51. $output[0:31] = skein512_256($input)
52.
53. 13. CRC32
54. $hash[0:31] = sha256($input)
55. $output[0:31] = crc32($hash[0:31]) // 按字进行 冗余校验码
56.
57. 14. HMAC(MD5)
58. $hash[0:15] = hmac_md5($input, $input) // HMAC_MD5的key和message均为输入
59. $output[0:31] = sha256($hash[0:15])
60.
61. 15. Camellia(128bits)
62. $hash[0:31] = sha256($input)
63. $hash2[0:15] = md5($hash[0:31])
64. $key = Camellia_set_key($hash2[0:15])
65. $output[ 0:15] = Camellia_encrypt($key, $hash[ 0:15])
66. $output[16:31] = Camellia_encrypt($key, $hash[16:31])
67.
68. 16. RC4(256bits)
69. $hash[0:31] = sha256($input)
70. $hash2[0:15] = md5($hash[0:31])
71. $key = RC4_set_key($hash2[0:15])
72. $output[0:31] = RC4($key, $hash[0:31])
单向函数CryptoHello的标准输出：
CryptoHello(“0123456789”)= cb98c372548618317a2dc286a7481701e5ea94892c9eb371d932c83d94ddd459
CryptoHello(“HelloWorld”)= 8d184a295c91aa46243c64452c0417fcff4d5ea67b30d43dd1e5a358171b9929
对单向函数CryptoHello执行10^6次。第1次输入为空值，第i次的输入xi为上次输出yi-1，输出为yi。将yi按照顺序拼接在一起，形成 32M 字节的数据流Y。
对Y执行NIST的随机数测试工具集 ，进行频数测试和游程测试。结果如表1-3所示，可以看到频率和游程测试的P值均大于0.01，所以生成的序列是随机的。
表1-3 单向函数CryptoHello的随机性检查结果
| 测试项 | P - value |
|---|---|
| 频率测试(Frequency) | 0.859141 |
| 游程测试 | (Runs) |
我们使用了服务器、PC机、服务器X和嵌入式系统等四种，具体参数如表2-1所示。
表2-1 CPU测试平台
| 硬件平台 | 平台1服务器 | 平台2PC机 | 平台3服务器X | 平台4嵌入式系统 |
|---|---|---|---|---|
| 处理器型号 | E5-2609 | Core i5 7500 | E5-2692 v2 | TX1 |
| 微结构 | Haswell | Kaby Lake | Ivy Bridge | A57 |
| SIMD支持 | SSE 2/3/4.1/4.2 AVX/AVX2 | SSE 2/3/4.1/4.2 AVX/AVX2 | SSE 2/3/4.1/4.2 AVX | NEON |
| 物理核数 | 2*6 | 4 | 2*12 | 4 |
| 超线程 | 不支持 | 不支持 | 支持 | 不支持 |
| 主频 | 1.9 GHz | 3.4 GHz | 2.20 GHz | 2.1 GHZ |
| 主存容量 | 64 GB | 8 GB | 64 GB | 2 GB |
| L1 Cache（每核） | 32 KB+32 KB | 32KB+32 KB | 32 KB+32 KB | 32 KB+32 KB |
| L2 Cache（每核） | 256 KB | 256KB | 256 KB | 2MB（共享） |
| L3 Cache | 15MB | 6MB | 30MB | |
| 操作系统 CentOS 6.6（64 bits） | Windows 10（64 bits） | Red Hat Enterprise 6.2 | Ubuntu 14.04 LTS | |
| 编译器 | gcc7 (GCC) 7.1.0 | Microsoft VS2015 C/C++ 19.00.24215.1 | icc 14.0.2 |
在测试平台1、2、3上分别对单向函数族的性能进行了测试，如表2-2所示。
表2-2 单向函数族的性能(单位：Mps，即每秒完成单向函数计算的次数)
| t | 类别 | 函数名 | 平台1 | 平台2 | 平台3 |
|---|---|---|---|---|---|
| 0 | SHA-3 | SHA3-256 | 1.01 | 1.28 | 1.02 |
| 1 | SHA-1 | SHA-1 | 2.15 | 4.51 | 3.19 |
| 2 | SHA-2 | SHA-256 | 2.81 | 5.26 | 3.72 |
| 3 | SHA-2 | SHA-512 | 1.34 | 3.68 | 2.54 |
| 4 | Whirlpool | Whirlpool | 0.92 | 2.43 | 1.50 |
| 5 | RIPEMD | RIPEMD-160 | 0.95 | 1.51 | 1.46 |
| 6 | BLAKE2 | BLAKE2s(256bits) | 1.66 | 2.42 | 2.48 |
| 7 | AES | AES(128bits) | 0.92 | 1.79 | 1.28 |
| 8 | DES | DES | 0.66 | 1.25 | 0.91 |
| 9 | RC4 | RC4 | 0.72 | 1.42 | 1.06 |
| 10 | Camellia | Camellia(128bits) | 1.07 | 2.04 | 1.52 |
| 11 | CRC | CRC32 | 2.16 | 3.98 | 2.94 |
| 12 | HMAC | HMAC(MD5) | 0.47 | 0.66 | 0.67 |
| 13 | GOST | GOST R 34.11-94 | 0.37 | 0.73 | 0.50 |
| 14 | HAVAL | HAVAL-256/5 | 1.67 | 2.43 | 1.81 |
| 15 | Skein | Skein-512(256bits） | 2.17 | 4.47 | 3.17 |
从上表可以看出，吞吐率最高的算法为SHA256，最低的算法为GOST或者HMAC。吞吐率最高者是最低者的7.5~8.0倍左右。
在平台1上使用单核的情况下，单向函数CryptoHello的执行时间分布如表2-3所示。
表2-3 单向函数H的执行时间分布
| 步骤 | 算法1初始化存储器 | 算法2的2.2步修改存储器 | 算法2的2.5步单向函数族计算 | 算法3产生最后结果 |
|---|---|---|---|---|
| 比例 | 36% | 53% | 1% | 10% |
可以看出单向函数CryptoHello中的主要计算开销在于算法2中的修改存储器内容。
单向函数CryptoHello性能与线程数的关系如表2-4和图2-1所示。其中每个平台的最优性能如黑体所示，恰为对应平台的核数。
表2-4 不同平台上单向函数CryptoHello的性能（单位：每秒的计算次数）
| Number of Threads | 1 | 4 | 8 | 12 | 16 | 24 | 32 | 48 | 64 |
|---|---|---|---|---|---|---|---|---|---|
| Server | 80 | 315 | 628 | 938 | 837 | 836 | 867 | 858 | 763 |
| PC | 168 | 641 | 634 | 631 | 633 | 629 | 627 | 625 | 625 |
| ServerX | 115 | 443 | 797 | 1186 | 1578 | 2337 | 2208 | 2177 | 2171 |
| Embedded System | 73 | 138 | 133 | 133 | 133 | 133 | 133 | 132 | 133 |
图2-1 不同平台上单向函数CryptoHello的性能（单位：每秒的计算次数）
GPU平台选择当前主流的消费级显卡GTX 1080和GTX Titan X，具体参数如表2-4所示。
表2-5 GPU主要参数
| 显卡型号 | GTX 1080 | GTX Titan X | RX VEGA 64 |
|---|---|---|---|
| 架构 | Pascal | Maxwell | Vega |
| 核数 | 2560 | 3072 | 4096 |
| 主频 | 1.6GHZ | 1.0GHZ | 1.423GHZ |
| 显存容量 | 8GB | 12GB | 8GB |
| 显存宽度 | 256位 | 384位 | 2048位 |
| 显存带宽 | 320GBps | 336GBps | 512GBps |
| 功耗 | 180W | 250W | 295W |
由于显存容量有限，因此在一块GPU上最多同时执行4K个散列函数，占据显存4K*1MB=4GB。
在GPU上的一个重要选择是多个线程同时执行一个单向函数CryptoHello，还是一个线程执行一个单向函数。我们认为上述三个主要算法内部缺乏明显的并行性，难以实现多个线程同时执行一个单向函数，只能采用一个线程一个单向函数的执行方式。此时，全GPU系统中共计有4K个线程。这将导致限制GPU性能的第一个问题：可以并行执行的线程数量太少，整体并行性有限。
GPU采用的是SIMT（单指令多线程）方法，一个Warp（=32）个线程执行同一条指令。在具有分支指令的情况下，如果线程之间的执行路径不同，则需要分别串行执行每个线程的所有路径，直至一个Warp中的所有线程执行到相同路径为止。
在上述算法中，不同输入的单向函数H需要从16个单向函数中近乎随机地选择一个执行。32个线程同时能选择同一个单向函数的概率为(1/16)^31 = 4.7×10^-38，严重限制了GPU多线程并行性的发挥。
在算法-3的2.3步中，循环的次数根据输入数据的不同在1~2^D-1之间变化，这也将导致一个Warp的线程执行时间依赖于最长的循环次数。
在算法-2中，对工作存储器M的访问是以字节为单位，而且地址随机性强。由于GPU片上Cache容量非常有限，这使得算法-2中的存储器访问基本上需要从显存中读取。虽然GPU显存的访问宽度高达256位（甚至384位），但是真正有效的仅仅只有1个字节，这使得GPU存储器访问带宽仅仅只有3%的利用率。
由于大量依赖于显存访问，使得访存指令的延迟长达数百个周期，而且由于线程数量很少，难以掩盖这些访存指令的长延迟。
性能
GPU版本的代码实现中支持以下几个动态调整功能：
1）根据机器中显卡个数动态创建多线程进行计算；
2）多线程互斥获取输入数据并行计算，支持任何规模的输入数据；
3）根据显卡的显存大小，动态设置workitem数目。
表2-6和图2-2给出了三种GPU卡的性能，输入数据从1K~1000K共测试7种数据规模，经过系统测试发现每次kernel计算的线程设置为1024时性能最优。
表2-6 不同GPU上单向函数CryptoHello的性能
（单位：每秒的计算次数，单卡，线程设置为1024）
图2-2 不同GPU上单向函数CryptoHello的性能
图2-2中，GTX 1080和Titan X的性能接近，而Vega64的性能明显较低。我们认为，这主要是因为我们的算法是存储器带宽受限的，而与核数关系不大。由于在算法-2中的存储器访问基本单位是字节，因此，虽然GPU的显存位宽很高，但是真正有效的数据传输率却非常低。三种GPU的存储器系统相关参数如表2-7所示。
表 2-7 GPU 存储器系统的主要参数
| 显卡型号 | GTX 1080 | GTX Titan X | RX VEGA 64 |
|---|---|---|---|
| 显存宽度(bit) | 256 | 384 | 2048 |
| 显存峰值带宽(GBps) | 320 | 336 | 512 |
| 字节访问时显存带宽利用率 | 3.13% | 2.08% | 0.39% |
| 字节访问时有效显存带宽(GBps) | 10 | 7 | 2 |
由此可以看出，虽然VEGA64的核数最多且显存峰值带宽最高，但是其在算法-2中的有效存储器带宽却是最低的。由于算法-2在整个计算过程中占据了一半以上的时间，所以VEGA64的性能反而较低。GTX 1080和Titan X的有效显存带宽相近，所以两者的性能基本相同。
表2-8对比了CPU和GTX 1080两者的最佳性能。可以看出，虽然显卡核数和存储器峰值带宽远远高于CPU，但是由于本算法的设计，显卡的性能较一般PC机还有一定差距。而CPU的性能与其核数又成正比关系，核数越多性能越高。
表2-8 CPU和GPU上单向函数H的性能对比（单位：每秒的计算次数）
| 分类 | 平台 | 最佳性能 |
|---|---|---|
| CPU | 服务器X | 2337 |
| CPU | 服务器 | 938 |
| CPU | PC | 641 |
| GPU | GTX 1080 | 538 |
典型的支持对称加解密运算和Hash运算的ASIC芯片，其结构如图3-1所示，分为水平方向上的以CPU为核心的控制流，和垂直方向上的运算数据流。
在垂直方向上，片外大容量存储器、片内高速缓存和加速运算模块阵列一起构成了实现加速运算的核心数据流。由于实现对称加解密运算和Hash运算的加速运算模块之间具有简单而规则的数据并行性，且单个加速运算模块的电路规模很小，仅为1K至2K门，因此这种ASIC加速芯片的设计重点是充分利用和扩展数据处理的并行性，从而获得更好的加速效果，具体措施有：
- 1、扩展片内高速数据缓存到片外大容量数据存储的带宽。这主要是通过采用更宽的数据总线和更多的芯片引脚来实现的（但同时也引入了昂贵的封装管壳开销）；
- 2、扩展片内的数据并行处理能力。这主要是通过在片内加入更多的加速运算模块，同时加速运算模块以并行运算的方式来提升处理能力。由于对称加解密运算和Hash运算的核心组合运算，这些运算的复杂度低，而且运算执行往往可以在一拍内完成，阵列式结构可以取得好的效果。
图3-1 典型ASIC加速芯片的结构
在水平方向上，CPU核负责执行控制流操作。主要包括片内数据缓存中的数据结构组织和调整，以及各个加速运算模块的工作模式的协调和管理。在这种芯片架构中，CPU核没有处于影响整个ASIC加速芯片速度和性能的关键路径上。
为了抑制采用图4.1中的ASIC芯片，以及基于ASIC芯片构造的矿机的发展，引入了Memory-Hard改进算法。Memory-Hard改进算法的核心，是提高加速运算模块对片内高速缓存容量的需求。由于实现高速数字电路的CMOS VLSI工艺和大容量SRAM工艺存在较大的差异，在高速ASIC芯片中集成的SRAM存储器容量存在一个产品良率和性价比的工程上限。
通过修改算法，不断提升加速运算模块对片内SRAM容量的要求，导致片内最大容量的SRAM可以支持的加速运算模块的数量逐步减少，最终导致ASIC加速芯片因性价比问题退出挖矿。与此算法相对应的ASIC加速芯片的结构如下图3-2所示。
图3-2 采用Memory-Hard算法的ASIC加速芯片结构
Memory-Hard改进算法可以有效地降低单芯片中可以集成的加速运算模块的数量，但由于加速运算模块自身的电路规模小（1K至2K门），这样单个ASIC加速芯片的成本可以有效控制，进而可以通过采用多芯片并行工作的方式来提升板级系统整体的算法执行速度。我们需要设计更加有效的ASIC芯片和矿机抑制算法。
实际上通过分析上述三个算法的原理和结构可知，通过综合采用这三个经过串行化改造的算法的组合，整体算法执行所消耗的时间中，复杂、串行化和密集访存的程序控制流行执行占用了90%以上的时间，散列函数计算所占用的时间低于10%。ASIC加速芯片中加速运算模块解决的是对应于散列函数指令执行的加速问题，这部分的性能提升仅限于算法执行的10%以下的部分。
这样的算法特征对ASIC芯片设计与实现产生了极大的限制，表现在以下三方面：
1、对于占90%以上时间的程序控制流和指令串行执行部分，简单的加速部件方案难以直接实现；
2、对于常规的基于状态机控制器的ASIC设计方案，虽然状态机控制器从理论上能够实现复杂的控制结构，但是无法对必须顺序执行指令序列的有效加速；
3、专用加速模块的仅仅只能加速10%的计算负载，对整体性能的提升没有太大帮助。
对于必须顺序执行的指令序列，现代微处理器提供深度指令流水线和多级Cache等机制，以有效开发多条指令之间的并行性，因此我们认为可行的加速ASIC芯片方案，应采用以高速CPU为核心的SOC芯片设计，来达到加速算法执行的目的。由此得到一种新的复杂控制流算法来抑制和改造ASIC加速芯片，对应的芯片结构如下图3-3所示。
图3-3 采用复杂控制流算法的ASIC加速芯片结构
从图3-1的比较分析可知，集成了4个ARM A57核的嵌入式处理器TX1，在执行我们专门设计的三个经过串行化改造的算法组合时，其加速效果按1核、2核、3核到4核的顺序逐步递增，采用更高核数的虚拟核调度和执行，其加速效果维持不变，这与算法的串行执行机制是一致的，同时也达到了我们预期的算法设计目标。
同时从图3-1的对比分析可知，我们提出的单向函数H算法，在不同的硬件平台上运行都遵循相同的规则，即：算法执行速度与单个物理CPU核的性能成正比，与系统集成的物理CPU核的数量成正比。
针对我们提出的单向函数H，可行的ASIC芯片设计方案应采用以高速CPU为核心的SOC芯片设计，且该SOC芯片应满足两个要求：
1、单个物理CPU核的性能应足够高；
2、芯片中应集成尽量多的物理CPU核。
目前市场上最主流CPU核为ARM公司提供的系列微处理器。按第一个要求，目前可用的高性能CPU核是ARM的A73核，最高主频可以达到2.8GHZ；按第二个要求，单芯片可以集成的A73核可以达到4个。这是因为在10nm工艺下，集成4个A73核，采用64KB指令L1 Cache和64KB数据L1 Cache，以及2MB L2 Cache的芯片面积已经达到5mm2，更多CPU核和Cache存储的集成将大幅提高芯片的单片成本。
在此4个A73核的设计方案下，其处理器核数远远少于表2-1中服务器和天河二号的处理器核数，因此其性能也将弱于已有CPU的实现方案。
与此同时，该SoC芯片投片成本高昂，主要包括以下两部分：
1、 CPU核的License费。ARM A73核的单次使用License费是5百万美元，三年无限次使用License费是1千5百万美元；
2、芯片掩膜的NRE费用。支持最快速度的7纳米工艺，每层掩膜的费用约为2万美元，标准SOC芯片需要制作50层掩膜，费用在100万美元左右。
考虑到研发投入，研制该SoC的费用大约在1千万到2千万美元左右，而且需要大约2年的时间才能量产。