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（随机数）组成。