前言

Zcash是Zerocash协议的具体实现，笔者翻阅了Zerocash的白皮书，在Zerocash协议的设计中，并没有涉及到挖矿算法的设计，白皮书集中阐述了零知识证明以及交易匿名性的设计。因此只有在实现Zerocash协议的加密货币Zcash中才有挖矿算法的具体实现，笔者在这里对Zcash中的挖矿算法做一个简单的总结。

 

Zcash简介

Zerocash是对Zerocoin的升级，两者都是在比特币基础上提出的一个扩展，使加密货币更加私密，具体表现在付款人、交易金额、收款人的匿名性质。Zerocash协议的具体实现Zcash中使用的挖矿算法是Equihash ，和比特币类似也是基于工作量证明（Proof-of-Work aka PoS）的算法，不同之处在于，Equihash 算法是基于内存困难（Memory Hard）问题设计的：即在挖矿过程中需要算力的同时对矿机的内存要求较高，这样做的主要目的是抵抗ASIC芯片矿机，让普通计算机参与到挖矿过程中。

Equihash算法是卢森堡大学的SnT组织在2016 NDSS会议上推出的一种基于内存困难的工作量证明算法，该算法基于广义的生日悖论问题（generalized birthday problem）设计（寻找广义上哈希值碰撞），需要在时间和空间上进行权衡，但是容易受到不可预见的并行优化的影响，目前使用Equihash作为挖矿算法的加密货币有 ZCash, Horizen, Aion, Hush 和 Pirate Chain 。在介绍Equihash 算法之前，先简单介绍一下广义的生日悖论问题和基础概念。

 

广义生日悖论问题

定义：给定一个长为N的列表$L = \{ X_1,X_2,...,X_N\}$，其中$X_i$都是n比特长的01串（n-bit string），找到$2^k$个下标使得$X_{i_j}$满足下面的碰撞：

$$X_{i_1} \oplus X_{i_2} \oplus ... \oplus X_{i_{2^k}} = 0 \tag{1}$$

一个简单的例子如下：假如$X_{i_j}$都是由某个伪随机数生成器（PRNG）产生的，这里我们考虑哈希函数H，最简单的生成方式就是：$X_i = H(i)$，那么广义生日悖论问题就是寻找$\{i_j\}$使得：

$$H(i_1) \oplus H(i_2) \oplus ... \oplus H(i_{2^k}) = 0 \tag{2}$$

• 特别地，当$k=1$时，广义生日悖论问题就转变为了寻找哈希函数H的碰撞问题（collision），在$N = |L| > 2^{n/2}$时，求解该问题的时间空间复杂度都是$O(2^{n/2})$（排序算法）。
• 如果$k>1$，并且列表长度N较小，该问题是困难的。从信息论的角度来看，例如，$k = 2,N = 2^{n/4}$，目前并没有优于$O(2^{n/3})$的算法。

 

Wagner 算法

密码学家Wagner提出广义生日悖论问题在$k>1$、列表长度$N$足够大、包含若干个解的情况下的算法。当列表长度N是$2^{\frac{n}{k+1}}$量级的时候，它的时间复杂度和空间复杂度都是$O(2^{\frac{n}{k+1}})$。值得一提的，Wagner 算法也可以推广到广义的运算上，将$\oplus$换成模加运算等等也是可行的。在k比较大的时候：$k \ge log_2{n}$，可以直接通过高斯消元法解$GF(2)$上的方程组求解该问题（核空间），时间复杂度仅为$O(2^k)$。

具体算法过程参考以下Wagner算法的最初版本：

Wagner 算法时间空间复杂度： 在$N = 2^{\frac{n}{k+1}+1}, \ k^2<n$ 条件下，算法1平均可以产生2个解，空间复杂度为$O(\frac{N}{8}*(2^{k-1}+n))$字节，时间复杂度为$O((k+1)*N)$。

 

在Equihash 算法中提供的是优化版本的 Wagner 算法，在挖矿算法的设计中，必须要提供一个最优的puzzle解算法，否则，如果其他人设计出了更优化的算法，将在挖矿过程中占有优势，从而可能利用较少算力就可以对整个链发动攻击。（目前而言该算法也不是最优的）

Optimized Wagner 算法时间空间复杂度： 在$N = 2^{\frac{n}{k+1}+1}$ 条件下，平均可以产生2个解，空间复杂度为$M(n,k) = 2^{\frac{n}{k+1}}*(2^k+\frac{n}{2*(k+1)})$字节，时间复杂度为$T(n,k) = k* 2^{\frac{n}{k+1}+2}$。

 

更多的关于Optimized Wagner 算法的时间和空间的权衡估计，时间换空间、空间换时间、并行优化分析可以参考原论文。在此不赘述。

 

Equihash 算法

这里我们正式进入Zcash挖矿算法的设计。在设计 Equihash 算法的 puzzle 时，如果只是单纯用广义生日悖论问题，看谁算的快就可以拿到记账权的话，会导致很多问题。一个很重要的原因是Optimized Wagner 算法的运行时间是泊松分布的，而泊松分布是有记忆性的，这会导致在新块刚开始产生就挖矿的节点优势很大，后开始挖矿的节点就没有优势了，这样可能的一个结果就是：由于网络问题等等，某个节点发现链上的最后一个块已经产生有一段时间了，它这个时候加入挖矿，就很没有优势，还不如等下一个块加入链上，造成很多算力在停等的情况出现。因此Equihash 算法为了解决这个问题，引入了Difficulty filter的机制，目的就是让挖矿谜题的求解保持尽量无记忆性。

难度系数

难度调整（Difficulty filter）的原理就是让Optimized Wagner 算法的求解需要的时间影响很小，我们只要该算法的内存困难（抗ASIC攻击）即可，时间的难度调整由难度系数d调整，d参数也就是类似比特币中谜题的设计，要求特定数据组合起来的哈希值前d个是比特是0，也就是哈希值足够小。

具体方案设计是这样的，选定广义生日悖论问题的参数为$n,k$，难度系数为$d$，挖矿谜题为每次选择一个 I（由交易的哈希值、链上区块的变量等产生），找到 160比特的随机数 V 和 $\frac{n}{k+1}+1$ 比特的 $x_1,x_2,...,x_{2^k}$使得下面条件成立：

注意最后一个条件，可能会比较困惑，但是如果你仔细看了Optimized Wagner 算法，就会发现这是 Optimized Wagner 算法计算过程中就会满足的条件，因此挖矿过程中只要你使用了 Optimized Wagner 算法，就不再需要验证这个条件了。所以很妙的地方就在这里，如果将来某个黑客设计出了更优的算法，但是它的中间过程与 Optimized Wagner 算法大相径庭，也是不能够直接拿来挖矿，因为这个时候你需要额外的工作量来满足这个Alg.binding条件。但是这个条件一定程度上限制了未来挖矿算法的优化，只能说是利弊参半。

整个Equihash 算法的完整过程是这样的：

 

时间空间复杂度

按照前述 Wagner 算法的时间性能介绍，每次选择特定的V运行 Wagner 算法可以获得2个解，因此想要获得前d为都为0的满足条件的哈希值，大概需要$2^{d-1}$次，当Wagner 算法运行时间比较小时，这个运行时间分布时趋近于几何分布，即有着无记忆性，因此可以作为一个挖矿算法。因此总的运行需求估计如下：

• 空间复杂度：$M = M(n,k) \approx 2^{\frac{n}{k+1}+k}$ （字节）
• 时间复杂度：$T = 2^{d-1}*T(n,k) \approx (k+1)* 2^{\frac{n}{k+1}+d}$ H calls (第一个等号笔者加的，实际上是不对的)
• 目标解的大小：$size =2^k * (\frac{n}{k+1}+1) + 160$ bits （$V \ and \ x_1,x_2,...,x_{2^k}$）
• 验证的复杂度：$2^k$次H哈希操作和$\oplus$异或操作

因此，从上述结果来看，该算法设计满足求解困难，验证简单的条件，并且对内存需求很大，可以抵抗ASIC芯片专业化矿机攻击。

 

在 Equihash 算法实际应用中，一般为了方便会设置$n,k$使得$\frac{n}{k+1}+1$是8的倍数，这样就可以方便以字节为单位处理数据，在不考虑参数d的情况下，实际的Optimized Wagner 算法时间空间复杂度估算如下：

 

参数的选择由很大的自由空间，并且如果矿机的内存太小，就会导致时间复杂度大幅度上升，从而导致内存受限的ASIC矿机优势不明显。在一般电脑上的运行时间性能如下

并且由于实际设计中，Equihash 算法需要的内存空间会比较大，由于内存受限，就导致并行运行的性能优化并不显著。

 

Zcash 挖矿算法总结

Zcash使用的 Equihash 算法参数是：$n = 200, k=9$，对内存的要求是512MB，在单台运行内存大于512MB、2.1GHz的机器上求解一次广义生日悖论问题需要 10 s 左右，再通过调节难度系数d就可以控制整个区块链上的出块时间了。对于 Equihash 算法，它是基于广义生日悖论问题设计的内存困难的工作量证明算法，在一定程度上可以抵抗ASIC专业化矿机的优势，实现公平“挖矿”的目标：即普通计算机也可以利用空闲算力参与挖矿，而不是矿池垄断挖矿。

挖矿过程如下：

• 某矿工选择生成需要打包的交易的初始种子I，选择160比特随机数V，求解构造的“广义生日问题”; 如果能找到$2^k$个符合条件的比特串，并且满足前面定义的两个条件，则可以成功上传新区快。
• 如果不能找到解，或者条件不满足，则修改随机数V，开始新一轮的挖矿。
• 同时Zcash链上每生成一个新块，都会根据出块时间进行一次难度调整。

但是正如论文里面提到的，可能存在更优化的Wagner 算法或者全新的某种算法在未来出现，在求解广义生日悖论问题时性能远超目前使用的算法，因此论文里面添加了Alg.binding条件，防止该情况出现，但是该条件也不能完全防止未来更优化的算法在挖矿时的优势（大幅度优化时间空间性能、优化算法的子进程类似等等），同时也限制了挖矿的效率。不可否认的是，Zcash 不管从匿名性还是挖矿算法的设计，都大量利用了数学/密码学上的经典难题，保证了分布式系统的安全性、匿名性以及公平性，有着严谨的数学之美。

 

参考文献、链接

1. Equihash 论文：Equihash: Asymmetric Proof-of-Work Basedon the Generalized Birthday Problem LEDGER VOL 2 (2017) 1-30
2. Equihash wiki : https://en.wikipedia.org/wiki/Equihash
3. Equihash C++ 实现：https://github.com/khovratovich/equihash
4. Zerocash 白皮书：Zerocash: Decentralized Anonymous Payments from Bitcoin (extended version) 2014
5. Zerocash project：http://zerocash-project.org/
6. Intro to Zcash : https://hackmd.io/@jmsjsph/IntroZcashTech
7. Zcash挖矿算法深度解析：https://zhuanlan.zhihu.com/p/24450669