zcash pow equihash算法详解

1 综述

1.1 简介

Equihash是一种基于广义生日问题（Generalized Birthday Problem）的内存密集型工作量证明（PoW）算法，算法核心目标是抵抗 ASIC 专用挖矿设备，让普通GPU/CPU更易参与挖矿，同时保证安全性与效率。其最著名的应用是 Zcash（主网参数 n=200, k=9），也被 ZenCash、Horizen 等加密货币采用。
1. 普通生日问题

在一个房间里，至少需要有多少人，才能使得“至少有两个人生日相同”的概率大于50%？
通常通过计算“所有人生日都不同”的互补事件概率来求解。
假设：
一年有365天（忽略润年）
每个人的生日在365天中是等可能的
生日之间相互独立
计算过程：
设房间里有n个人，则
第1个人的任取一天都不会出现生日相同（碰撞）的情况，所以不同的概率是1；
第2个人只有生日和第1个人生日不同时才能满足生日不同，所以与之前人不同的概率是364/365；
第3个人要满足和前两个人都生日都不同才行，所以与之前人不同的概率是363/365；
...
第n个人与前n−1个人生日都不同的概率是(365-(n-1))/365；
所以，所有人生日都不同的概率p(n)为：

那么，至少有两个人生日相同的概率 P(n)就是：

著名结论：
当n=23时：

也就是说，只需要23个人，至少两人生日相同的概率就超过了50%。当n=57时，这个概率会超过99%。
在密码学中的应用（生日攻击）：
在密码学中，生日问题揭示了哈希函数碰撞的概率。假设一个哈希函数有N中可能的输出（比如N=2m），那么只需要计算大约sqrt(N)次哈希，就有相当大的概率找到两个不同的输入产生相同的输出（即发生碰撞）。
2. 广义生日问题

“至少需要有多少人，才能使得‘至少有一组k个人生日相同’的概率超过50%？”
普通生日问题是广义生日问题在k=2时的特例。例如：k=3时，至少有三个人生日相同；k=4时，至少有四个人生日相同。
这个问题比普通生日问题复杂得多，没有简单的闭合公式，通常需要近似或者数值计算。
解决广义生日问题的一个著名近似：要使一组k个人共享同一个生日的概率超过50%，大约需要的人数为：

其中N是可能的天数（例如365），k是要求的人数，还以N=365为例：
k=2（普通生日问题）：

这与之前精确计算的23人非常接近。
k=3：

这意味着大约需要82人，才有超过50%的概率找到至少三个人生日相同。
3. Equihash中广义生日问题

在Equihash算法中涉及的广义生日问题可以归纳如下：
1）由区块头数据通过Blake2b哈希生成长度为N的哈希串列表；
2）在列表中找到2k个哈希串的异或结果为 0（注意这里异或为0，并不是表示2k个完全相同的哈希串，这里的异或为零是更宽松的组合约束）；
3）最终解为满足条件的2k个哈希值的索引组合（最终需转换为字节流，作为区块的 nSolution 字段）。
1.2 算法及数据结构

tromp给出equihash算法工程实现：
https://github.com/tromp/equihash
1. 关键参数

在Zcash中使用的参数N=200，K=9，这意味着：
N（Width）：产生的哈希值总宽度为200bits（50字节）；
K（Steps）：算法分为9轮（实际上是K步碰撞），对应算法输出的29个索引；
HEADERNONCELEN：140字节，Blake2b哈希函数的输入数据长度，通常由Block Header（区块头）+ Nonce（随机数）组成。在Zcash中，这个总长度通常固定为140字节；
NDIGIT：K+1=10，在算法实现中会将N位哈希输出切分成10个小块（Digit）分轮逐层解决；
DIGITBITS：N/NDIGITS=200/10=20bits，每个Digit的位宽（也就是每一轮碰撞的长度L）；

PROOFSIZE：1bytes-hashbytes, ph+WN/8-hashbytes, hashbytes);46           // round 0 tags store hash-generating index47           s->tag = tree((block * NBLAKES + i) * HASHESPERBLAKE + j);48         }49       }50     }51 }[/code]以NBLAKES=1时为例进行分析，函数中第2行定义htl变量用于统一管理每轮digit处理时的相关参数，如其中成员变量prevhtunits用于指定上一个slot数据对应的htunit数组在内存中的位置，而nexthtunits用于指定下一个slot数据对应的htunit数组在内存中的位置；第3行给出了该轮有效哈希数据字节数，由于200bit中有10bit体现在桶编号里，所以这里190bit对应字节数是24；之后第6行for循环依次处理每个哈希输出，循环次数为NBLOCKS = (NHASHES+HASHESPERBLOCK-1)/HASHESPERBLOCK=2x220/2=220；第24行处for循环对应的逻辑是每个哈希输出结果可以产生两个slot数据；第30行将哈希输出的最低10bit作为桶编号；第37行根据桶编号取出相应的可用slot；第43~47行将剩余的哈希数据（去除10bit桶号）存储到slot中，并用tag记录index，具体来说对于slot对应的htunits[7]数组，索引[0]到[5]存储剩余哈希数据，索引[6]存储树节点tag索引。该轮执行完毕后所有桶存储于heap0，桶中的slot数据内存结构如下图：

2.3 次轮函数digit1

在调用完digit0函数后，每个桶中的哈希数据是原始哈希输出前10bit（Digit0前10位）结果相同的哈希的剩余哈希数据，在此轮要找到两个Digit0剩余10bit也相同的两两哈希对儿，并将它们的哈希数据进行异或，根据异或结果对应的Digit1前10bit进行再次分桶操作，函数内容如下：

1. #if RESTBITS < 8
2. // can't save much memory in such small buckets
3. #define SAVEMEM 1
4. #else
5. // an expected size of at least 512 has such relatively small
6. // standard deviation that we can reduce capacity with negligible discarding
7. // this value reduces (200,9) memory to under 144MB
8. // must be under sqrt(2)/2 with -DCANTOR
9. #define SAVEMEM 9/14        // 容量缩减因子
10. #endif // RESTBITS == 4
12. #endif // ifndef SAVEMEM
14. static const u32 NBUCKETS = 1<<BUCKBITS;    // number of buckets
15. static const u32 BUCKMASK = NBUCKETS-1;     // corresponding bucket mask
16. static const u32 SLOTRANGE = 1<<SLOTBITS;   // default bucket capacity
17. static const u32 SLOTMASK = SLOTRANGE-1;    // corresponding SLOTBITS mask
18. static const u32 SLOTMSB = 1<<(SLOTBITS-1); // most significat bit in SLOTMASK
19. static const u32 NSLOTS = SLOTRANGE * SAVEMEM; // number of slots per bucket
20. static const u32 NRESTS = 1<<RESTBITS;      // number of possible values of RESTBITS bits
21. static const u32 MAXSOLS = 8;               // more than 8 solutions are rare

复制代码

第3行定义collisiondata类型变量cd用于检测碰撞；第4行for循环依次处理每个桶；第6~7行首先获取当前桶数据指针，接下来获取当前桶中slot个数；第8行的for循环依次遍历每个slot，借助cd变量检测是否会发生碰撞；第9~10行以循环下标为索引取出slot1，并将其添加到cd碰撞检测器中；第11行for循环只要碰撞检测器中还存在碰撞，则依次处理碰撞；第12~13行取出和slot1发生碰撞的slot索引，并将相应slot0取出；接下来第14~17行通过比较两个slot的最后一个word来判断两个slot是不是“重复数据”（这种情况一般不会发生），如果是则忽略当前碰撞；第18行将slot0和slot1的哈希数据中第一个word进行异或，并取低10bit数据（即Digit1的低10bit）为下一轮的桶编号；第19~23行从heap1中获取该桶编号相应可用slot索引，如果溢出则忽略当前碰撞；接下来第24~28行先根据桶编号及slot索引获取相应的htunit数组内存存储空间，然后将slot0和slot1对应的哈希数据异或后存储到htunit数组的[0]到[5]对应的元素中（即4*6=8*3=24字节内存中）；第29行将碰撞对儿的原始桶编号和slot索引组成tree结构放入到htunit数组索引[6]元素中。该轮执行完毕后所有桶存储于heap1，桶中的slot数据内存结构如下图：

图中bucketid对应digit0之后输出heap0中相应的桶编号，s0和s1对应相应桶中的slot索引。
2.4 函数digit2及digitK

经过digit1轮处理后，heap1中每个桶内存储的都是异或后Digit0为全零且Digit1低10bit值相同的哈希对儿数据异或结果，在digit2函数中将进一步检测并处理两两哈希对儿异或结果之间碰撞，函数内容如下：

1. // each bucket slot occupies a variable number of hash/tree units,
2. // all but the last of which hold the xor over all leaf hashes,
3. // or what's left of it after stripping the initial i*n 0s
4. // the last unit holds the tree node itself
5. // the hash is sometimes accessed 32 bits at a time (word)
6. // and sometimes 8 bits at a time (bytes)
7. union htunit {
8.   tree tag;
9.   tree_t word;
10.   uchar bytes[sizeof(tree_t)];
11. };
13. #define WORDS(bits)    ((bits + TREEBITS-1) / TREEBITS)
14. #define HASHWORDS0 WORDS(WN - DIGITBITS + RESTBITS)
15. #define HASHWORDS1 WORDS(WN - 2*DIGITBITS + RESTBITS)
17. // A slot is up to HASHWORDS0 hash units followed by a tag
18. typedef htunit slot0[HASHWORDS0+1];
19. typedef htunit slot1[HASHWORDS1+1];
20. // a bucket is NSLOTS treenodes
21. typedef slot0 bucket0[NSLOTS];
22. typedef slot1 bucket1[NSLOTS];
23. // the N-bit hash consists of K+1 n-bit "digits"
24. // each of which corresponds to a layer of NBUCKETS buckets
25. typedef bucket0 digit0[NBUCKETS];
26. typedef bucket1 digit1[NBUCKETS];
27. typedef au32 bsizes[NBUCKETS];

复制代码

digit2除了部分细节digit2函数大体流程和digit1非常类似，如第10行在向碰撞检测器中添加slot时，slot1->word最低10bit对应的是digit1的高10bit值；第18行进一步对两个slot索引[1]位置的哈希值进行异或；第25~29行进一步只对slot剩余部分的哈希数据进行异或操作（前面的哈希数据经过碰撞已经全部为0）。digit2执行完毕后，会更新存储在heap0的各桶中内容，需要注意的是该轮处理过程中仅仅更新了slot中htunit数组的前6个word内容，在digit0中产生的tag并没有被改动（最后进行求解追溯时需要利用这里的数据），完美的实现了内存复用。

 
其他digitx处理过程类似不再详细进行说明，接下来看一下最后一个digitK（digit9）处理函数：

1. void alloctrees() {
2.     static_assert(2*DIGITBITS >= TREEBITS, "needed to ensure hashes shorten by 1 unit every 2 digits");
3.     heap0 = (bucket0 *)alloc(NBUCKETS, sizeof(bucket0));
4.     heap1 = (bucket1 *)alloc(NBUCKETS, sizeof(bucket1));
5. }
7. equi(const u32 n_threads) {
8.     static_assert(sizeof(htunit) == sizeof(tree_t), "");
9.     static_assert(WK&1, "K assumed odd in candidate() calling indices1()");
10.     nthreads = n_threads;
11.     //const int err = pthread_barrier_init(&barry, NULL, nthreads);
12.     //assert(!err);
13.     hta.alloctrees();
14.     nslots = (bsizes *)hta.alloc(2 * NBUCKETS, sizeof(au32));
15.     sols   =  (proof *)hta.alloc(MAXSOLS, sizeof(proof));
16. }

复制代码

digitK首先给出在digit8函数调用完成以后slot中数据内存结构，如下图所示：

 
上图中tag_digit7表示的是在digit7处理完成后对应heap1输出，digitK函数以上图的heap0为输入（偶数轮调用输出是heap0，奇数轮调用输出是heap1，每轮调用的输入又是上一轮调用的输出，这是就所谓的内存“乒乓”机制），digitK函数中整体处理过程和其他digit处理类似，只不过由于hash数据只剩30bits完全存储在一个word中，所以已经没必要再次进行分桶操作，所以第16行直接对相应的值进行了比较（等同于异或）并判断两个slot中的tag中是否发生重叠，在Equihash的K轮碰撞过程中，要求2K个原始输入索引必须互不相同，满足条件后产生潜在解，在candidate函数中会对潜在解做进一步检验，通过检验后才真正的产生解，具体内容可以参考candidate函数实现。
2.5 其他补充说明

1. collisiondata结构体

该结构体定义的主要内容如下：
[code]struct collisiondata {    // This maintains NRESTS = 2^RESTBITS lists whose starting slot    // are in xhashslots[] and where subsequent (next-lower-numbered)    // slots in each list are found through nextxhashslot[]    // since 0 is already a valid slot number, use ~0 as nil value#if RESTBITS