Zcash挖矿算法深度解析

说明

    本文转自 https://www.8btc.com/article/126531
    对于equish 算法，作者原论文下载链接为：https://download.csdn.net/download/xhoufei2010/11149927

zcash 简介

与比特币相比，Zcash 修改了挖矿算法。比特币使用的挖矿算法是 SHA256，而 Zcash 使用的是 Equihash。 Equihash算法由Alex Biryukov和Dmitry Khovratovich共同发明，其理论基础是著名的计算科学和密码学问题——广义生日悖论问题。

作者希望讨论Zcash如何使用Equihash算法，用尽可能简单的语言实现挖矿过程。

接下来解释Zcash挖矿的一般流程。注：作者仍然无法完全脱离代码来解释。

①构造块头 在执行挖矿算法之前，首先要构造块头。 Zcash的区块头结构如下，与比特币的区块头结构类似btc挖矿算法，区别在于随机数的位数。

图 1 Zcash 的区块头

nVersion，块版本号，在升级过程中发生变化。 hashPrevBlock，从上一个区块中获取。 nBits，由全网算力决定，每产生一个新区块就调整难度（比特币每2016个区块调整一次），算法为DigiShield v3/v4。 nTime，基本上取机器的当前时间轴。 hashMerkleRoot，该字段允许矿工自行调整。更改来自添加或删除块中包含的交易，或更改顺序，或修改 Coinbase 交易的输入字段。 nNonce，Zcash 提供 2256 个可能的值，而比特币提供 232 个。一般来说，hashMerkleRoot 和 nNonce 是发挥挖矿自由度的地方。

Zcash区块头构建的一般过程也和比特币类似：

选择要确认的交易，因为矿工可以从交易中获得手续费，所以一般在构建区块的时候选择尽可能多的交易，但不能超过容量限制（2M）。

确定Coinbase，这里记录成功构建区块后矿工将获得的收益（费用+奖励）。

构建Merkle树（收集交易信息），生成随机数V，写入其他参数

如图 1 所示构造 Block 头。

②转化为广义生日悖论问题

我们通常将比特币的“挖掘”过程比作解决算法问题。这个算法题的题目是通过处理Block头的函数给出的。比特币的算法：对Block头的参数进行两次SHA256运算，得到一个256位的字符串，与一个期望值目标进行比较。如果值小于目标，则挖矿成功，即SHA256(SHA256 (Block header)) 什么是广义生日问题？

用计算机语言定义广义生日悖论：随机生成一个由N个“n位字符串{Xi}”组成的列表L，

p>

需要在这些字符串中找到 2^k 个特定的 {Xij}，这样：

Zcash挖矿算法深度解析

通俗的说法：从this Find 2k完全相等的元素到列表L中，即找到2k个碰撞元素。

注：限于篇幅，本文只谈结论。有兴趣的读者可以自行查找“生日问题相关内容”。

Zcash 中如何处理 Block 头以获得“生日问题” 有一个专门的哈希函数 Equihash Generator。 Equihash Generator 的功能是将输入和索引映射到长度为 n 位的输出。设i∈{1 … N}，以生成的区块头（Block header）和整数n、k为输入，其中n、k的值由官方给出，通过

Zcash挖矿算法深度解析

函数进程可以生成一个由N个“n位字符串{Xi}”组成的列表L。

图 3

③“广义生日悖论”的解法用于解决“广义生日问题”。许多著名的算法，密码学家瓦格纳的算法就是其中之一。 Zcash 团队基于 Wagner 算法，经过 Alex Biryukov 和 Dmitry Khovratovich 等人的优化，得到了一个名为“OptimizedSolve”的算法，用于解决上述问题。

从理论上讲，公平地说，用于“工作量证明”的算法必须是问题的最优算法，因为如果算法不是最优的，可能有人会发明它并偷偷用更好的算法进行挖掘，在同等算力下，他挖矿成功的概率会大于其他人。但是，如果仔细检查“OptimizedSolve”算法，不难发现它还是有优化的可能。如何实现优化本文暂不考虑，作者后续文章会单独讨论这一点。

限于篇幅，“OptimizedSolve”算法的原理就不详细介绍了。有兴趣可以参考文献：《Equihash: Asymmetric Proof-of-Work Ba​​sed on the Generalized Birthday Problem》

解决过程：

以从Block头“n位字符串”导出的列表L作为“生日问题”的条件，利用改进算法“OptimizedSolve”从L^k中找到2个完全相等（碰撞）{Xij }，这样：

具体流程如图4所示

图 4

④难度过滤

到第③步，“生日问题”已经解决了。但是，并不意味着谁先构造和解决了“生日问题”，就赢得了“挖矿”的胜利。如果胜利条件仅仅是生成并解决一个“生日问题”，可能会出现以下问题：

1.从概率的角度来看，生成的列表L中可能没有2k个完全相等的值，即碰撞次数小于2k。这会导致一些“矿工”构建的“生日问题”无法解决，所以当出现这种情况时，“生日问题”必须重构一次。

2.“OptimizedSolve”的简单使用使得“挖矿”的难度难以控制，因为算法的运行时间服从泊松分布。

3.在内存充足的情况下，可以使用更复杂的技术迭代产生多个摊销成本更低的解，即运行这样的算法会使单位内存的运算成本降低与公平“挖矿”的概念。

（Zcash希望实现公平的“挖矿”，即大众参与挖矿，而不是矿池垄断挖矿。）

所以，和比特币一样，Zcash 也应用了一种难度调整算法，称为难度过滤器。

难度过滤器（表示为 H）是一种用于调整工作量证明的时间和内存要求的算法。在得到“生日问题”的碰撞解{Xij}后，必须进行Difficulty过滤器的检查。只有通过测试，才能算是“挖矿”成功。具体流程如图5所示。

图 5

1）难度过滤器的三个判断条件

注：H(S)表示输入S经过Difficulty filter H的算法过程的输出结果。-生日算法条件：

-难度算法条件：

结果有 d 个前导零

-绑定算法条件：

结果有 n*l/ (k+1) 个前导零，这对于所有满足条件的 w 和 l 都是正确的。

注意；前导零的数量是指一串二进制数，前几位为零。位数（见图5）.

-生日算法条件用于判断上一过程得到的解是否为满足条件的碰撞； - 难度算法条件用于判断当前难度是否合理。 ，并成为难度调整的依据； -添加绑定算法可以防止有人发明算法：算法使用足够的内存来摊销成本，以降低单位内存成本。 （这里只讨论结论，具体算法限于篇幅不展开讨论）

2）判断过程

如果一个矿工构造的“生日问题”能找到2^k个碰撞解，并且经过难度调整算法后，仍然满足三个条件，如果三个条件都满足，那么“矿工”挖了一个“矿” ，即该人成功构建了一个新区块。如果无法找到足够数量的解决方案，或者三个条件都不能满足，则“挖矿”失败btc挖矿算法，矿工需要修改随机数，从头开始，开始新一轮的“挖矿”。同样，这个过程也将成为Zcash挖矿难度调整的基础。每次生成新区块，都会进行难度调整。

④总结

Zcash挖矿的一般流程是先构造输入条件（区块头和各种参数），通过特定函数将输入条件转化为“广义生日问题的一般形式”。用优化算法分析问题，判断得到解的难度。如果同时满足算法条件和难度条件，则判断“挖矿”成功，否则调整随机数并重新计算。