Ergo与Autolykos共识机制：第一部分
2022年5月30日
以下是对Ergo共识机制Autolykos的深入技术分析。由于这是一个冗长且详细的话题，我们将在接下来的两周内分段发布。第一部分，作者开始分解区块挖矿伪代码，并引导我们创建“列表R”。
第一部分
Autolykos，Ergo的共识机制，是少数仍然抵抗ASIC的非对称内存硬、工作量证明难题之一——从而确保区块链尽可能去中心化。Autolykos基于Equihash论文[1]和生日问题。简而言之，矿工的任务是找到_k (=32)个元素中的_N，使得这些元素的和的哈希值小于目标值。以下伪代码解释了挖矿过程，这个分析将详细分解每一行，因为网上很少有资源能完整解释Autolykos。
Autolykos区块挖矿伪代码
在讨论区块挖矿程序之前，算法首先需要一个非常大的循环群_G_，其素数阶_q_具有固定生成元_g_和单位元素_e_。这个素数群用于在基于Blake2b256的哈希函数中返回_Z/qZ_中的整数。
示例循环群，生成元z，单位元素1，阶数6[2]
我们不会过多关注循环群，因为它仅涵盖PoW方案的一小部分。现在，让我们逐行分析Autolykos区块挖矿。
第1行 – 输入h和m
PoW以两个输入开始：区块高度h和即将到来的区块头哈希m。区块头哈希是区块头组件的哈希值，例如前一个区块头哈希、Merkle根、随机数等。
第2行 – 计算列表R
首先，重要的是注意第2行中的_H()符号。这个符号调用哈希函数算法3。算法3是基于Blake2b256的哈希函数，并在整个Autolykos中使用。算法3指出，如果输入的Blake哈希值低于2256 (= 1664 = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000)，则返回_hash.mod(q)。如果不是，算法3将重复，直到达到有效范围内的数值哈希。作为参考，请注意_q_是群_G_的素数阶，Blake2b256哈希输出为256位，长度为64位，算法3将始终返回_Z/qZ_中的数值哈希。
基于Blake2b256的哈希函数
在第2行中，重点是创建_列表R_。_列表R_包含从[0, N)中的整数生成的31字节数值哈希的_r_值。_r_值由_takeright(31,H(j||h||M))_生成。变量如下：
- j，在[0, N)中的整数
- h，区块高度
- M，8kb的常量数据 - 填充以减缓哈希计算
_takeRight(31,H(…))部分意味着，给定_H(…)，一个32字节的Blake2b256输出，返回右侧的31字节（即小端（而其他哈希算法是大端））。换句话说，最重要的字节，即最左边的字节被丢弃。因此，每个_r_值是从32字节_H(j||h||M))输出中派生的31个最低有效字节。例如，如果_j = 1，r1 = takeRight(31,H(1||h||M))。_列表R_由_N_个元素组成，可以通过将_j_增加1 N-1_次为每个区块生成。由于_H(…)返回_hash.mod(q)，我们可以说_列表R_由_r0, 1, 2, 3 … N-1_组成，并且_列表R ⊂ Z/qZ。正如Autolykos v2白皮书[3]中所述，“_N_个元素是从区块高度和常量派生的，与Autolykos v1不同，因此矿工现在可以轻松重新计算区块候选（只有索引依赖于它们）。”换句话说，_j_始终在[0,N)中，_N_由_h_决定，M_始终是常量，而_h_每个区块变化，矿工计算_列表R_所需的唯一变量是_h。
_列表R_存储在RAM中。在Autolykos中，N = 226（67,108,864个整数）在614400之前的每个区块的实现中使用。因此，614400之前区块的内存需求为(226 * 31字节 =) 2.08GB。N在区块614400时首次增加。在区块614400之后，每51200个区块，_N_增加5%。换句话说，Ergo矿工的内存需求每~71天增加5%。在区块4198400时，_N_的值变为常量，等于2,143,944,600[4]。请注意，表中列出的最后两个值应为2,143,944,600，而不是2,147,387,550。在区块4198400之后，_列表R_的存储需求将为(31字节 * 2,143,944,600) = 66.46GB。
基于区块高度的N个元素
N个元素，Ethash与Autolykos
Autolykos与Ethash的相似之处在于，区块高度决定了存储在RAM中的_N_个元素。使用Autolykos，区块高度决定了存储的_N_个31字节数值哈希。使用Ethash，区块高度决定了存储的_N_个128B DAG页面。你可能会问，如果Ergo区块每2分钟发生一次，Ergo矿工如何能如此快速生成2GB+的数据集？以太坊矿工每100小时才重新生成DAG，因为这需要很长时间……对于Ergo矿工来说，计算_列表R_的负担是_N_个算法3的实例；请记住，每个_r值_的计算为_takeRight(31,H(j||h||M))。然而，GPU可以非常快速地完成这项工作，GPU通常具有32宽或64宽的多处理器，这意味着可以同时完成32或64个算法3的实例，具体取决于GPU。例如，像RTX570这样的32宽GPU可以在几秒钟内填充_列表R。
在第二部分，我们将从这里继续，继续解释Autolykos v2。请关注Ergo的社交媒体渠道，以获取第二部分的更新。
[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] 感谢Discord上的Wolf9466#9466
Share post
