🚧 Stagnant Standards Track: Core

EIP-1485: TEthashV1

Authors	trustfarm <trustfarm.info@gmail.com>, trustfarm <cpplover@trustfarm.net>
Created	2018-11-01
Discussion Link	https://ethereum-magicians.org/t/anti-eth-asic-mining-eip-1488-pr/1807

简单总结
摘要
动机
规范
原理
测试结果::
版权

简单总结

此 EIP 修改了 ethash，目的是破坏专门为当前 ethash 挖矿算法设计的 ASIC 矿机。

摘要

此 EIP 旨在通过以非常低的风险方式修改 PoW 算法，并从已弃用的 FNV Hash 算法更新到最新的哈希算法，从而实现“淘汰当前 ASIC 矿机”的目标。

以下 TEthashV1 算法建议安全地过渡 PoW 算法，并保护 MIX 部分中的 FNV 算法。

动机

通过更新 FNV0 算法，以最小的更改提供原始 Ethash 工作量证明验证。

规范

1. 关于 ETHASH FNV0 的参考资料

FNV 在 ETHASH 中的应用

在 ETHASH 中，FNV Hash 用于

1) 数据聚合函数，MIX 部分。
Ethash 算法

  Header + Nonce
         |
      Keccak 
         |
    **[MIX 0]**  --> **[DAG Page]**
         |               |
       Mixing         <--|
        ...
         |
    **[Mix 63]**
         |
         |-----> Mix64  [Process] ---> Mix Digest [32B]

FNV 用于 DAG 生成和 Mixing，用于随机访问或 DAG 页面。

2. 当前应用的 Ethash FNV 哈希实现现在已弃用。

[FNV-0hash (已弃用)](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-0_hash(deprecated))

这是一种简单的哈希算法

   hash = 0
   for each byte_of_data to be hashed
   	hash = hash × FNV_prime
   	hash = hash XOR octet_of_data
   return hash

在分析 FNV-0 时，当哈希输入更改 1~2 位时，存在非常弱的雪崩效应。参阅FNV-Analysis 参考部分

我们需要研究和应用更新的 FNV 哈希或短消息哈希算法。

3. FNV1A 哈希算法描述

先前提出的算法基于 FNV1 EIP-1355

在 FNV1A 中，存在一个看起来像“缺少偏移偏差”的实现。

引用原始算法 FNV1A

use hash offset
FNV-1a hash
The FNV-1a hash differs from the FNV-1 hash by only the order in which the multiply and XOR is performed:[8][10]

   hash = FNV_offset_basis
   for each byte_of_data to be hashed
   	hash = hash XOR byte_of_data
   	hash = hash × FNV_prime
   return hash

FNV_offset_basis 和异或与乘法的计算顺序更改，使其比 FNV0 具有更多的异或和乘法计算，但具有更安全的哈希效果。并通过使用素数来生成分散边界条件（0、偶数等）。

4. FNV1A 的实际实现

考虑到实际计算资源，在 TEthashV1 中，哈希 byte_of_data 用于 4 字节对齐的数据。

在 TETHashV1 中，完全遵循 FNV1A 实现。

TETHASHV1 FNV1A 实现

以下是 TETHashV1 中采用的 FNV1A 的参考实现。

// Reference Pseudo c/cpp implementation
// 参考伪 C/cpp 实现

#define FNV_PRIME 0x01000193U
#define FNV_OFFSET_BASIS  0x811c9dc5U

#define fnv1a(x, y)         ((((FNV_OFFSET_BASIS^(x))*FNV_PRIME) ^ (y)) * FNV_PRIME)
#define fnv1a_reduce(a,b,c,d) (fnv1a(fnv1a(fnv1a(a, b), c), d))

FNV1A 的另一个字节对齐实现，调用 FNV1c

#define FNV_PRIME   0x01000193U
#define FNV_OFFSET_BASIS  0x811c9dc5U

#define fnv1i(x)           (  (( (( ((                                          \
                                ( ((FNV_OFFSET_BASIS^( ((x)>>24)&0x000000ff )) * FNV_PRIME) \
                            ^   (((x)>>16  )&0x000000ff)) * FNV_PRIME) \
                            ^   (((x)>>8   )&0x000000ff)) * FNV_PRIME) \
                            ^   (((x)      )&0x000000ff)) * FNV_PRIME) \
                            )
#define fnv1c(x, y)            ((fnv1i(x) ^ (y)) * FNV_PRIME)

5. FNV-Analysis

用于 TEthashV1 的 FNV Mix 算法分析

如何测试和分析参考测试代码。

您可以在终端中通过简单的方式对其进行编译。无需其他库，

gcc -o fnvtest fnvcltest.c

您可以执行它

fnvtest

F(00,00)::VEC(0, 0, ffffffff, 0)::      FNV  :00000000, DF=00000000(00) DS(00000000), FNV1 :00000000, DF=00000000(00) DS(00000000), FNV1a:117697cd, DF=117697cd(17) DS(117697cd), FNV1c:1210d00f, DF=127f8dbf(20) DS(11a1725f),         F___RC=efe1b9c4, DF:efe1b9c4(19) , F1__RC=deb68dfe, DF:deb68dfe(22) , F1A_RC=99bad28b, DF:99bad28b(17) , F1C_RC=e29fa497, DF:e29fa497(18)
F(00,01)::VEC(0, 1, ffffffff, 0)::      FNV  :00000001, DF=00000001(01) DS(00000001), FNV1 :01000193, DF=01000193(06) DS(01000193), FNV1a:1076963a, DF=010001f7(09) DS(01000193), FNV1c:1110ce7c, DF=03001e73(11) DS(01000193),         F___RC=fefffe6d, DF:111e47a9(14) , F1__RC=d9fd8597, DF:074b0869(12) , F1A_RC=72c287e0, DF:eb78556b(19) , F1C_RC=6b6991ef, DF:89f63578(17)
F(00,02)::VEC(0, 2, ffffffff, 0)::      FNV  :00000002, DF=00000003(02) DS(00000001), FNV1 :02000326, DF=030002b5(08) DS(01000193), FNV1a:0f7694a7, DF=1f00029d(11) DS(01000193), FNV1c:1410d335, DF=05001d49(09) DS(030004b9),         F___RC=d8fd8404, DF:26027a69(13) , F1__RC=9b16d24c, DF:42eb57db(19) , F1A_RC=c17f0ecb, DF:b3bd892b(18) , F1C_RC=a5be8e78, DF:ced71f97(21)
F(00,03)::VEC(0, 3, ffffffff, 0)::      FNV  :00000003, DF=00000001(01) DS(00000001), FNV1 :030004b9, DF=0100079f(10) DS(01000193), FNV1a:0e769314, DF=010007b3(09) DS(01000193), FNV1c:1310d1a2, DF=07000297(09) DS(01000193),         F___RC=b2fb099b, DF:6a068d9f(16) , F1__RC=5c301f01, DF:c726cd4d(17) , F1A_RC=94cf402e, DF:55b04ee5(16) , F1C_RC=aea1a025, DF:0b1f2e5d(17)
F(00,04)::VEC(0, 4, ffffffff, 0)::      FNV  :00000004, DF=00000007(03) DS(00000001), FNV1 :0400064c, DF=070002f5(10) DS(01000193), FNV1a:0d769181, DF=03000295(07) DS(01000193), FNV1c:0e10c9c3, DF=1d001861(09) DS(050007df),         F___RC=8cf88f32, DF:3e0386a9(14) , F1__RC=1d496bb6, DF:417974b7(17) , F1A_RC=89401d59, DF:1d8f5d77(20) , F1C_RC=e4e96c7c, DF:4a48cc59(13)
F(00,05)::VEC(0, 5, ffffffff, 0)::      FNV  :00000005, DF=00000001(01) DS(00000001), FNV1 :050007df, DF=01000193(06) DS(01000193), FNV1a:0c768fee, DF=01001e6f(11) DS(01000193), FNV1c:0d10c830, DF=030001f3(09) DS(01000193),         F___RC=66f614c9, DF:ea0e9bfb(20) , F1__RC=de62b86b, DF:c32bd3dd(19) , F1A_RC=346e222c, DF:bd2e3f75(21) , F1C_RC=502e5f82, DF:b4c733fe(20)
F(00,06)::VEC(0, 6, ffffffff, 0)::      FNV  :00000006, DF=00000003(02) DS(00000001), FNV1 :06000972, DF=03000ead(10) DS(01000193), FNV1a:0b768e5b, DF=070001b5(09) DS(01000193), FNV1c:1010cce9, DF=1d0004d9(10) DS(030004b9),         F___RC=40f39a60, DF:26058ea9(13) , F1__RC=9f7c0520, DF:411ebd4b(16) , F1A_RC=b376a527, DF:8718870b(13) , F1C_RC=1241a9a4, DF:426ff626(17)
F(00,07)::VEC(0, 7, ffffffff, 0)::      FNV  :00000007, DF=00000001(01) DS(00000001), FNV1 :07000b05, DF=01000277(08) DS(01000193), FNV1a:0a768cc8, DF=01000293(06) DS(01000193), FNV1c:0f10cb56, DF=1f0007bf(15) DS(01000193),         F___RC=1af11ff7, DF:5a028597(13) , F1__RC=609551d5, DF:ffe954f5(22) , F1A_RC=14293bea, DF:a75f9ecd(21) , F1C_RC=49d34bba, DF:5b92e21e(16)
F(00,08)::VEC(0, 8, ffffffff, 0)::      FNV  :00000008, DF=0000000f(04) DS(00000001), FNV1 :08000c98, DF=0f00079d(12) DS(01000193), FNV1a:09768b35, DF=030007fd(12) DS(01000193), FNV1c:1a10dca7, DF=150017f1(12) DS(0b001151),         F___RC=f4eea58e, DF:ee1fba79(21) , F1__RC=21ae9e8a, DF:413bcf5f(19) , F1A_RC=eeebb7a5, DF:fac28c4f(17) , F1C_RC=7da04f47, DF:347304fd(16)
F(00,09)::VEC(0, 9, ffffffff, 0)::      FNV  :00000009, DF=00000001(01) DS(00000001), FNV1 :09000e2b, DF=010002b3(07) DS(01000193), FNV1a:087689a2, DF=01000297(07) DS(01000193), FNV1c:1910db14, DF=030007b3(10) DS(01000193),         F___RC=ceec2b25, DF:3a028eab(14) , F1__RC=e2c7eb3f, DF:c36975b5(18) , F1A_RC=54e1aef8, DF:ba0a195d(15) , F1C_RC=d425e1af, DF:a985aee8(16)
F(00,0a)::VEC(0, a, ffffffff, 0)::      FNV  :0000000a, DF=00000003(02) DS(00000001), FNV1 :0a000fbe, DF=03000195(07) DS(01000193), FNV1a:0776880f, DF=0f0001ad(10) DS(01000193), FNV1c:1c10dfcd, DF=050004d9(08) DS(030004b9),         F___RC=a8e9b0bc, DF:66059b99(15) , F1__RC=a3e137f4, DF:4126dccb(15) , F1A_RC=213fcd63, DF:75de639b(20) , F1C_RC=7e1d2751, DF:aa38c6fe(18)
F(00,0b)::VEC(0, b, ffffffff, 0)::      FNV  :0000000b, DF=00000001(01) DS(00000001), FNV1 :0b001151, DF=01001eef(12) DS(01000193), FNV1a:0676867c, DF=01000e73(09) DS(01000193), FNV1c:1b10de3a, DF=070001f7(11) DS(01000193),         F___RC=82e73653, DF:2a0e86ef(16) , F1__RC=64fa84a9, DF:c71bb35d(19) , F1A_RC=5598ce46, DF:74a70325(14) , F1C_RC=6400c630, DF:1a1de161(14)
F(00,0c)::VEC(0, c, ffffffff, 0)::      FNV  :0000000c, DF=00000007(03) DS(00000001), FNV1 :0c0012e4, DF=070003b5(10) DS(01000193), FNV1a:057684e9, DF=03000295(07) DS(01000193), FNV1c:1610d65b, DF=0d000861(07) DS(050007df),         F___RC=5ce4bbea, DF:de038db9(17) , F1__RC=2613d15e, DF:42e955f7(18) , F1A_RC=6a220ff1, DF:3fbac1b7(20) , F1C_RC=6e781da4, DF:0a78db94(15)
F(00,0d)::VEC(0, d, ffffffff, 0)::      FNV  :0000000d, DF=00000001(01) DS(00000001), FNV1 :0d001477, DF=01000693(07) DS(01000193), FNV1a:04768356, DF=010007bf(11) DS(01000193), FNV1c:1510d4c8, DF=03000293(07) DS(01000193),         F___RC=36e24181, DF:6a06fa6b(17) , F1__RC=e72d1e13, DF:c13ecf4d(18) , F1A_RC=168d4944, DF:7caf46b5(19) , F1C_RC=65bbcfa1, DF:0bc3d205(13)
F(00,0e)::VEC(0, e, ffffffff, 0)::      FNV  :0000000e, DF=00000003(02) DS(00000001), FNV1 :0e00160a, DF=0300027d(09) DS(01000193), FNV1a:037681c3, DF=07000295(08) DS(01000193), FNV1c:1810d981, DF=0d000d49(09) DS(030004b9),         F___RC=10dfc718, DF:263d8699(15) , F1__RC=a8466ac8, DF:4f6b74db(20) , F1A_RC=93e667bf, DF:856b2efb(19) , F1C_RC=76f80ee3, DF:1343c142(11)
F(00,0f)::VEC(0, f, ffffffff, 0)::      FNV  :0000000f, DF=00000001(01) DS(00000001), FNV1 :0f00179d, DF=01000197(07) DS(01000193), FNV1a:02768030, DF=010001f3(08) DS(01000193), FNV1c:1710d7ee, DF=0f000e6f(13) DS(01000193),         F___RC=eadd4caf, DF:fa028bb7(17) , F1__RC=695fb77d, DF:c119ddb5(17) , F1A_RC=0f485682, DF:9cae313d(17) , F1C_RC=3667e8dc, DF:409fe63f(18)
F(00,10)::VEC(0, 10, ffffffff, 0)::     FNV  :00000010, DF=0000001f(05) DS(00000001), FNV1 :10001930, DF=1f000ead(13) DS(01000193), FNV1a:01767e9d, DF=0300fead(14) DS(01000193), FNV1c:0210b6df, DF=15006131(09) DS(1500210f),         F___RC=c4dad246, DF:2e079ee9(17) , F1__RC=2a790432, DF:4326b34f(16) , F1A_RC=d10adebd, DF:de42883f(16) , F1C_RC=1ce48e12, DF:2a8366ce(15)

F(00,01) : 是输入 x,y

VEC(0, 1, ffffffff, 0) : 是 fnv_reduce 输入向量 (a,b,c,d)

FNV :00000001, DF=00000001(01) DS(00000001) :

FNV(00,01) 结果是 00000001，
DF : 是更改的位计数，与之前的输出相比，在这种情况下，prev[00,00] current[00,01] 输入更改了 1 位，并且输出结果更改了 1 位。
DS : 是先前结果和当前结果的距离，ABS(prev_fnvresult,current_fnvresult)。

** 基本上，DF 越高，哈希算法越好。

F___RC=fefffe6d, DF:111e47a9(14) : fnv_reduce = fnv(fnv(fnv(a,b),c),d) 结果是 fefffe6d，不同的位数是 14 位。

原理

就 ethash 算法而言，它无法永久阻止 ASIC。

而且，当前 ethash 算法的 FNV 函数已弃用。

因此，需要对其进行升级，这将使当前基于 ethash 的 ASIC 过时。

当前 TETHASHV1 FNV1A 实现基于大多数 ethash，这已经过长时间的验证。

另一种对 Ethash 算法进行大差异化的提议需要进行长时间的密码分析，并需要 GPU 代码优化时间。

验证和优化时间线示例

original ethminer (2015) -> claymore optimized miner (2016) [1年]

genoil ethminer (2015) -> ethereum-mining/ethminer (2017) [2年]

测试结果::

由于更多的核心计算时间，Tethash 矿机在 GPU 上的哈希率降低了 2~3%。

版权

本作品已获得知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议的许可。

Citation

Please cite this document as:

trustfarm <trustfarm.info@gmail.com>, trustfarm <cpplover@trustfarm.net>, "EIP-1485: TEthashV1 [DRAFT]," Ethereum Improvement Proposals, no. 1485, November 2018. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-1485.