综述
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)为：
image
那么，至少有两个人生日相同的概率 P(n)就是：
image
著名结论：
当n=23时：
image
也就是说，只需要23个人，至少两人生日相同的概率就超过了50%。当n=57时，这个概率会超过99%。
在密码学中的应用（生日攻击）：
在密码学中，生日问题揭示了哈希函数碰撞的概率。假设一个哈希函数有N中可能的输出（比如N=2m），那么只需要计算大约sqrt(N)次哈希，就有相当大的概率找到两个不同的输入产生相同的输出（即发生碰撞）。
2. 广义生日问题
“至少需要有多少人，才能使得‘至少有一组k个人生日相同’的概率超过50%？”
普通生日问题是广义生日问题在k=2时的特例。例如：k=3时，至少有三个人生日相同；k=4时，至少有四个人生日相同。
这个问题比普通生日问题复杂得多，没有简单的闭合公式，通常需要近似或者数值计算。
解决广义生日问题的一个著名近似：要使一组k个人共享同一个生日的概率超过50%，大约需要的人数为：
image
其中N是可能的天数（例如365），k是要求的人数，还以N=365为例：
k=2（普通生日问题）：
image
这与之前精确计算的23人非常接近。
k=3：
image
这意味着大约需要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：1<<K=512，解包含的索引数量，即最终需要提交这512个索引作为工作量证明；
BASE：1<<DIGITBITS=220=1048576，碰撞空间大小，因为每一轮要检查20bits的碰撞，那么就有220种可能的数据，可以把该值想象成有1048576个“理论上的抽屉”，后续需要把初始哈希串放入这些抽屉里；
NHASHES：2*BASE=2097152（200百万），算法第一步生成的初始哈希串总数，如果只生成 BASE个数据，那么平均每个抽屉里只有1个数据，这时无法和其他串发生碰撞（找不到配对），算法就无法继续，为了保证每一轮都能顺利进行，需要让每个“理论抽屉”里平均至少有2个数据；
HASHESPERBLAKE：512/N=2，标准Blake2b输出是512bits，equihash算法中需要的是200bits的哈希串，所以512bits可以切出2个200bits哈希串，剩下的112位被丢弃；
HASHOUT：HASHESPERBLAKE*N/8=50字节，Blake2b算法输出50字节即可（2x200bits）；
在Tromp的Equihash工程实现中，引入了Bucket（桶）和Slot（槽）两个用于管理内存和数据的关键概念，在Equihash算法中，有几百万个数据需要处理，如果把它们放在一个大数组里排序，速度太慢，所以要使用“分治法”。
Bucket (桶) —— 数据的“大分组”
定义：Bucket 是内存中的一块逻辑区域，用于存放具有相同前缀（Prefix）的哈希串。
决定因素：BUCKBITS，如果 BUCKBITS = 10，说明有210 = 1024个桶。数据的前10位决定了它去哪个桶。
物理形态：在 C++ 代码中，Bucket 通常不是一个复杂的 class，而仅仅是计算出的内存偏移量 (Offset)。
Bucket_0 的内存地址 = 起始地址 + 0
Bucket_1 的内存地址 = 起始地址 + (每个桶的大小)
作用：减少碰撞搜索范围。数据一旦进入不同的桶，它们在当前轮次绝对不可能碰撞，所以后续计算完全不需要考虑跨桶的情况，这对 CPU 缓存非常友好。
Slot (槽) —— 数据的“具体容器”
定义：Slot是Bucket内部的一个最小存储单元。
决定因素：SLOTBITS，如果SLOTBITS = 12，说明每个桶最多能容纳212 = 4096个数据（Slot）。
存储内容：Slot里不存完整的哈希值（浪费空间），只存必要的压缩信息：
1）索引 (Index)：这组数据最初是来自哪个（或哪些）原始输入。
2）剩余位 (Rest Bits)：除去桶编号（前缀）后，剩下的哈希位。
固定大小 (Flat Memory)：在Tromp的代码中，并没有使用链表（Linked List）来动态增加 Slot，因为指针跳转太慢。
他预先分配了固定大小的内存：总内存 = 桶数量 × 每个桶的Slot数量 × Slot大小。
风险：如果运气不好，某个哈希前缀出现太多次，导致对应桶的数据超过了 Slot 的上限，就会发生溢出 (Overflow)，这部分多余的数据通常会被丢弃（为了性能牺牲一点点求解概率）。
结合以上内容，给出和桶和槽相关参数
RESTBITS：10，对于20位的Digit来说，前10位用于确定它属于哪个Bucket，则还有10位是剩余的数据位；
BUCKBITS：DIGITBITS-RESTBITS=10，210是桶的总数，Digit前10位确定“桶号”；
SLOTBITS：RESTBITS+1+1=12，这个参数定义了一个桶最多能装多少个数据（Slot），总数据量是NHASHES=2x220，桶的总数是210，则平均每个桶会分到2x220/210=211=2048个数据，11正好对应RESTBITS+1，而定义中的第2个+1是除于安全冗余考虑，由于哈希分布是随机的，有的桶数据少，有的桶数据多。为了防止数据多的桶溢出（Overflow），这里多给了1位空间（即容量翻倍），允许一个桶最多装212 = 4096个数据。
2. Wagner算法
Equihash要求找到2K个不同的输入xi，使得：
H(x1) XOR H(x2) XOR ... XOR H(x2^k) = 0
例如在K=9时，需要有512个不同索引的哈希XOR = 0。此时直接暴力找512个XOR=0的组合不现实，因此引入了Wagner's algorithm。
Wagner的思路非常简单但很强大：
把“求2K个数XOR=0”转换成K轮“两两XOR消除部分前缀”的逐层合并。
首先对备选哈希数据按前缀不同进行分桶，每个桶中都是有相同前缀的哈希数据（相当于抹掉部分哈希前缀位），之后流程结构如下：
image
最终XOR被零掉的bit = (k+1) × N/(k+1) = N ⇒ 全部 XOR 为 0。在Wagner算法中每轮处理主要做以下操作：
1）依次处理每个桶，桶内为以消除部分相同前缀的哈希串；
2）进一步查找桶内具有特定位相同前缀的哈希对（能产生碰撞的两个哈希）；
3）将碰撞哈希对进行异或产生新的哈希数据（会消除相同前缀），同时将之前桶号及索引（桶内位置）进行数据组合（最后进行解回溯时使用）；
4）根据异或哈希数据按特定位前缀再次进行分桶（前缀相同分入到相同桶）；
再上述过程中查找碰撞对儿其实就是在搜索前缀相同的哈希，保证之后的异或操作会消除相应的bit，而之后根据哈希前缀进行分桶也是类似，也是保证在同一个桶内的哈希都是前缀相同的，便于在进行多线程处理时都是在同一桶内进行的。
2 源码解析
2.1 内存结构
1. 关键宏定义
首先看如下宏定义：
复制代码
#if RESTBITS < 8
// can't save much memory in such small buckets
#define SAVEMEM 1
#else
// an expected size of at least 512 has such relatively small
// standard deviation that we can reduce capacity with negligible discarding
// this value reduces (200,9) memory to under 144MB
// must be under sqrt(2)/2 with -DCANTOR
#define SAVEMEM 9/14 // 容量缩减因子
#endif // RESTBITS == 4
#endif // ifndef SAVEMEM
static const u32 NBUCKETS = 1<<BUCKBITS; // number of buckets
static const u32 BUCKMASK = NBUCKETS-1; // corresponding bucket mask
static const u32 SLOTRANGE = 1<<SLOTBITS; // default bucket capacity
static const u32 SLOTMASK = SLOTRANGE-1; // corresponding SLOTBITS mask
static const u32 SLOTMSB = 1<<(SLOTBITS-1); // most significat bit in SLOTMASK
static const u32 NSLOTS = SLOTRANGE * SAVEMEM; // number of slots per bucket
static const u32 NRESTS = 1<<RESTBITS; // number of possible values of RESTBITS bits
static const u32 MAXSOLS = 8; // more than 8 solutions are rare
复制代码
SAVEMEM定义内存容量缩减因子，根据桶内数据密度，在保证求解率的前提下，减少每个桶的槽位（Slot）数量，从而降低整体内存占用。默认的SLOTRANGE (212=4096) 包含了大量的冗余空间。当RESTBITS足够大（>=8）时，意味着每个桶的元素足够多，可以安全地将容量从默认的SLOTRANGE缩减到9/14，以节省内存。
2. 存储结构体定义
复制代码
// each bucket slot occupies a variable number of hash/tree units,
// all but the last of which hold the xor over all leaf hashes,
// or what's left of it after stripping the initial i*n 0s
// the last unit holds the tree node itself
// the hash is sometimes accessed 32 bits at a time (word)
// and sometimes 8 bits at a time (bytes)
union htunit {
tree tag;
tree_t word;
uchar bytes[sizeof(tree_t)];
};
#define WORDS(bits) ((bits + TREEBITS-1) / TREEBITS)
#define HASHWORDS0 WORDS(WN - DIGITBITS + RESTBITS)
#define HASHWORDS1 WORDS(WN - 2*DIGITBITS + RESTBITS)
// A slot is up to HASHWORDS0 hash units followed by a tag
typedef htunit slot0[HASHWORDS0+1];
typedef htunit slot1[HASHWORDS1+1];
// a bucket is NSLOTS treenodes
typedef slot0 bucket0[NSLOTS];
typedef slot1 bucket1[NSLOTS];
// the N-bit hash consists of K+1 n-bit "digits"
// each of which corresponds to a layer of NBUCKETS buckets
typedef bucket0 digit0[NBUCKETS];
typedef bucket1 digit1[NBUCKETS];
typedef au32 bsizes[NBUCKETS];
复制代码
1）htunit类型
htunit联合体类型是Equihash求解器中存储数据的最小通用单元，联合体的特性是，它内部的所有成员共享一块内存空间，这意味着tag、word和bytes都是对同一32/64位内存的不同解释。
image
引入联合体的目的：提高代码的灵活性和性能。当进行复杂的位操作时，使用 word；当处理索引时，使用tag；当进行底层内存操作时，使用 bytes。
2）槽定义
Slot是存储一个碰撞数据项的容器，它是一个定长数组，用于存储哈希数据和树节点信息。
typedef htunit slot0[HASHWORDS0 + 1];
大小：HASHWORDS0 + 1个htunit，位数WN - DIGITBITS + RESTBITS = 200 - 20 + 10 = 190，则HASHWORDS0值为6个WORDS，再+1，最终为7个WORDS。
用途：用于第0轮的输出，即digit0输出的存储结构。
结构：数组的前HASHWORDS0个单元存储压缩后的哈希数据；最后一个单元（+1）存储该数据项的树节点tag。
即slot0对应的类型为大小为7个htunit的数组。
typedef htunit slot1[HASHWORDS1 + 1];
大小：HASHWORDS1 + 1 个 htunit，位数WN - 2*DIGITBITS + RESTBITS = 200 - 2*20 + 10 = 170，则HASHWORDS1值也为6个WORDS，再+1，最终也为7个WORDS。
用途：用于第1轮的输出，即digit1输出的存储结构。
压缩：由于HASHWORDS1 <= HASHWORDS0（因为第1轮又消除了20位），slot1通常比slot0更小，从而可能会节省些许内存（在N=200情况下这两个值是相同的）。
在后续的乒乓操作中会复用这两个内存结构。
3）桶定义
桶是相同类型槽的集合。
typedef slot0 bucket0[NSLOTS];
保存slot0类型数据的数组型桶结构，它是包含NSLOTS=2633个slot0类型数据的定长数组。
typedef slot1 bucket1[NSLOTS];
保存slot1类型数据的数组型桶结构，它是包含NSLOTS=2633个slot1类型数据的定长数组。
4）内存堆定义
digit结构定义了整个内存堆，对应于乒乓机制的中一个“球台”。
typedef bucket0 digit0[NBUCKETS];
用于存储初始轮次数据的内存堆结构（通常是乒乓机制中的heap0），它由NBUCKETS=1024个bucket0组成，其中每个桶都使用slot0存储数据。
typedef bucket1 digit1[NBUCKETS];
用于存储后续轮次数据的内存堆结构（通常是乒乓机制中的heap1），它由NBUCKETS=1024个bucket1组成，其中每个桶都使用slot1存储数据。
5）辅助结构
typedef au32 bsizes[NBUCKETS];
含义：桶大小数组（Bucket Sizes）。
用途：au32通常是原子32位无符号整数。这个数组用于在多线程环境中安全地追踪每个桶当前实际存储了多少个数据项。这是多线程无锁写入的关键：每个线程写入数据后，原子性地增加对应桶的计数器。
3. 内存分配
在进行碰撞检测前首先进行必要的内存分配，主要内容如下：
复制代码
void alloctrees() {
static_assert(2*DIGITBITS >= TREEBITS, "needed to ensure hashes shorten by 1 unit every 2 digits");
heap0 = (bucket0 *)alloc(NBUCKETS, sizeof(bucket0));
heap1 = (bucket1 *)alloc(NBUCKETS, sizeof(bucket1));
}
equi(const u32 n_threads) {
static_assert(sizeof(htunit) == sizeof(tree_t), "");
static_assert(WK&1, "K assumed odd in candidate() calling indices1()");
nthreads = n_threads;
//const int err = pthread_barrier_init(&barry, NULL, nthreads);
//assert(!err);
hta.alloctrees();
nslots = (bsizes *)hta.alloc(2 * NBUCKETS, sizeof(au32));
sols = (proof *)hta.alloc(MAXSOLS, sizeof(proof));
}
复制代码
