Dagger-Hashimoto

上次修改时间: @xiaomage(opens in a new tab), 2024年3月4日

Dagger-Hashimoto 是以太坊挖矿算法的原始研究实现和规范。但是，Dagger-Hashimoto 已被 Ethash 取代。在 2022 年 9 月 15 日实施的合并后，挖矿完全关闭。此后，以太坊采用权益证明机制保护安全。本页面展示与历史有关的内容，其中的信息不再与合并后的以太坊相关。

前提条件

为了更好地了解此页面，建议提前阅读工作量证明共识、挖矿和挖矿算法。

Dagger-Hashimoto 算法

Dagger-Hashimoto 旨在实现两个目标：

ASIC 抗性：为算法打造专用硬件的益处应尽可能小。
轻量级客户端可验证性：区块应能被轻量级客户端高效验证。

在作出进一步修改后，我们还要具体说明如何在必要时实现第三个目标，但要以增加复杂性为代价：

完整链存储：挖矿需要存储完整的区块链状态（因为以太坊状态子树的不规则结构，我们预计将有可能进行一些修改，特别是一些经常用到的合约，但我们希望尽量减少这种情况）。

有向无环图世代

以下算法代码将在 Python 中定义。首先，我们定义了 encode_int，用于将指定精度的无符号整数封送为字符串。同时还定义了它的逆函数。

1NUM_BITS = 512
2
3def encode_int(x):
4    "Encode an integer x as a string of 64 characters using a big-endian scheme"
5    o = ''
6    for _ in range(NUM_BITS / 8):
7        o = chr(x % 256) + o
8        x //= 256
9    return o
10
11def decode_int(s):
12    "Unencode an integer x from a string using a big-endian scheme"
13    x = 0
14    for c in s:
15        x *= 256
16        x += ord(c)
17    return x
显示全部
 复制

接下来我们假设 sha3 是一个需要输入整数，然后输出整数的函数，而 dbl_sha3 是一个 double-sha3 函数；如果将此引用代码转换为实现，使用以下代码：

1from pyethereum import utils
2def sha3(x):
3    if isinstance(x, (int, long)):
4        x = encode_int(x)
5    return decode_int(utils.sha3(x))
6
7def dbl_sha3(x):
8    if isinstance(x, (int, long)):
9        x = encode_int(x)
10    return decode_int(utils.sha3(utils.sha3(x)))
显示全部
 复制

参数

该算法使用的参数有：

1SAFE_PRIME_512 = 2**512 - 38117     # Largest Safe Prime less than 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS,  # Size of the dataset (4 Gigabytes); MUST BE MULTIPLE OF 65536
5      "n_inc": 65536,                   # Increment in value of n per period; MUST BE MULTIPLE OF 65536
6                                        # with epochtime=20000 gives 882 MB growth per year
7      "cache_size": 2500,               # Size of the light client's cache (can be chosen by light
8                                        # client; not part of the algo spec)
9      "diff": 2**14,                    # Difficulty (adjusted during block evaluation)
10      "epochtime": 100000,              # Length of an epoch in blocks (how often the dataset is updated)
11      "k": 1,                           # Number of parents of a node
12      "w": w,                          # Used for modular exponentiation hashing
13      "accesses": 200,                  # Number of dataset accesses during hashimoto
14      "P": SAFE_PRIME_512               # Safe Prime for hashing and random number generation
15}
显示全部
 复制

P 在这种情况下为优先选择，因此 log₂(P) 仅略小于 512。512 对应于我们用来代表我们数目的 512 字节。请注意，实际上只需要存储有向无环图的后半部分，因此，实际内存要求最初为 1 GB，每年增长 441 MB。

Dagger 建图

Dagger 建图基本式的定义如下：

1def produce_dag(params, seed, length):
2    P = params["P"]
3    picker = init = pow(sha3(seed), params["w"], P)
4    o = [init]
5    for i in range(1, length):
6        x = picker = (picker * init) % P
7        for _ in range(params["k"]):
8            x ^= o[x % i]
9        o.append(pow(x, params["w"], P))
10    return o
显示全部
 复制

基本上，建图从单个节点 sha3(seed) 开始，然后根据随机的先前节点按顺序添加到其他节点上。创建一个新的节点后，将计算种子的模块化能力，以随机选择一些小于 i 的索引（使用上述 x % i），并且使用这些索引上的节点值进行计算，以产生新的 x 值，随后该值被提供给一个小的工作量证明函数（基于 XOR），最终在索引 i 生成图值。这种特殊设计背后的基本原理是强制按顺序访问有向无环图。如果当前值未知，则无法确定要访问的下一个有向无环图的值。最后，模幂运算会使结果更加恶化。

这种算法依赖于数字理论的若干结果。讨论情况见下文附录。

轻量级客户端评估

上述构图旨在实现图中每个节点的重构，只计算少量节点的子树，并且仅需少量的辅助内存。请注意，当 k=1 时，子树只是一个上升到有向无环图第一个元素的值链。

轻量级客户端中，有向无环图的计算函数如下：

1def quick_calc(params, seed, p):
2    w, P = params["w"], params["P"]
3    cache = {}
4
5    def quick_calc_cached(p):
6        if p in cache:
7            pass
8        elif p == 0:
9            cache[p] = pow(sha3(seed), w, P)
10        else:
11            x = pow(sha3(seed), (p + 1) * w, P)
12            for _ in range(params["k"]):
13                x ^= quick_calc_cached(x % p)
14            cache[p] = pow(x, w, P)
15        return cache[p]
16
17    return quick_calc_cached(p)
显示全部
 复制

本质上，它只是对上述算法的重写，删除了计算整个有向无环图值的循环，并用递归调用或缓存查找替换了早期的节点查找。请注意，对于 k=1 的情况，缓存是不必要的，尽管进一步的优化实际上预先计算了有向无环图的前几千个值，并将其作为静态缓存进行计算；有关此代码实现，请参见附录。

有向无环图的双倍缓冲

在完整客户端中，使用了上述公式生成的 2 个有向无环图的双倍缓冲(opens in a new tab)。具体概念是，根据上述参数，每个 epochtime 生成一个有向无环图。但客户端使用的并非是最新生成的有向无环图，而是前一个。这样做的好处是，有向无环图可以随着时间的推移而被替换掉，无需包含矿工必须突然重新计算所有数据的步骤。否则，定期的链处理可能会突然暂时放缓，并大幅提高中心化程度。因此，在重新计算所有数据之前的几分钟时间内，存在 51% 的攻击风险。

要生成用于块工作计算的有向无环图集，算法如下：

1def get_prevhash(n):
2    from pyethereum.blocks import GENESIS_PREVHASH
3    from pyethereum import chain_manager
4    if n <= 0:
5        return hash_to_int(GENESIS_PREVHASH)
6    else:
7        prevhash = chain_manager.index.get_block_by_number(n - 1)
8        return decode_int(prevhash)
9
10def get_seedset(params, block):
11    seedset = {}
12    seedset["back_number"] = block.number - (block.number % params["epochtime"])
13    seedset["back_hash"] = get_prevhash(seedset["back_number"])
14    seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
15    seedset["front_hash"] = get_prevhash(seedset["front_number"])
16    return seedset
17
18def get_dagsize(params, block):
19    return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]
20
21def get_daggerset(params, block):
22    dagsz = get_dagsize(params, block)
23    seedset = get_seedset(params, block)
24    if seedset["front_hash"] <= 0:
25        # No back buffer is possible, just make front buffer
26        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
27                          "block_number": 0}}
28    else:
29        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
30                          "block_number": seedset["front_number"]},
31                "back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
32                         "block_number": seedset["back_number"]}}
显示全部
 复制

Hashimoto

初始 Hashimoto 旨在将区块链用作数据集，执行从区块链中选择 N 个索引的计算，收集这些索引处的交易，对这些数据执行 XOR，并返回结果哈希值。 Thaddeus Dryja 的初始算法（为了保持一致性，被转化成 Python），具体如下：

1def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
2    hash_output_A = sha256(prev_hash + merkle_root + nonce)
3    txid_mix = 0
4    for i in range(64):
5        shifted_A = hash_output_A >> i
6        transaction = shifted_A % len(list_of_transactions)
7        txid_mix ^= list_of_transactions[transaction] << i
8    return txid_mix ^ (nonce << 192)
 复制

不幸的是，虽然 Hashimoto 被视为 RAM 硬件，但它依靠的是 256 位计算，计算量非常之大。然而，Dagger-Hashimoto 在索引其数据集时仅使用最低有效 64 位来解决此问题。

1def hashimoto(dag, dagsize, params, header, nonce):
2    m = dagsize / 2
3    mix = sha3(encode_int(nonce) + header)
4    for _ in range(params["accesses"]):
5        mix ^= dag[m + (mix % 2**64) % m]
6    return dbl_sha3(mix)
 复制

使用双 SHA3 可以实现零数据、近乎即时的预验证，仅验证是否提供了正确的中间值。此工作量证明的外层对专用集成电路高度友好且相当薄弱，但它的存在使分布式拒绝服务变得更加困难，因为必须完成少量工作才能生成不会立即被拒绝的区块。以下为轻量级客户端版本：

1def quick_hashimoto(seed, dagsize, params, header, nonce):
2    m = dagsize // 2
3    mix = sha3(nonce + header)
4    for _ in range(params["accesses"]):
5        mix ^= quick_calc(params, seed, m + (mix % 2**64) % m)
6    return dbl_sha3(mix)
 复制

挖矿与验证

现在，将它们全部整合到挖矿算法中：

1def mine(daggerset, params, block):
2    from random import randint
3    nonce = randint(0, 2**64)
4    while 1:
5        result = hashimoto(daggerset, get_dagsize(params, block),
6                           params, decode_int(block.prevhash), nonce)
7        if result * params["diff"] < 2**256:
8            break
9        nonce += 1
10        if nonce >= 2**64:
11            nonce = 0
12    return nonce
显示全部
 复制

以下为验证算法：

1def verify(daggerset, params, block, nonce):
2    result = hashimoto(daggerset, get_dagsize(params, block),
3                       params, decode_int(block.prevhash), nonce)
4    return result * params["diff"] < 2**256
 复制

轻量级客户端的友好验证：

1def light_verify(params, header, nonce):
2    seedset = get_seedset(params, block)
3    result = quick_hashimoto(seedset["front_hash"], get_dagsize(params, block),
4                             params, decode_int(block.prevhash), nonce)
5    return result * params["diff"] < 2**256
 复制

另外，请注意 Dagger-Hashimoto 对区块头有着额外的要求：

为了使双层验证起效，区块头必须同时具有随机数和中间值 pre-sha3
在某处，区块头必须存储当前种子集的 sha3

延伸阅读

还有哪些社区资源对您有所帮助？请编辑本页面并添加！

附录

如前所述，用于生成有向无环图的随机数生成依赖于数论的一些结果。 Lehmer 随机数生成程序是 picker 变量的基础，因此我们首先确保它具有很宽的周期。其次，只要一开始 x ∈ [2,P-2]，我们便能证明 pow(x,3,P) 不会将 x 映射到 1 或 P-1。最后，我们证明 pow(x,3,P) 在被视为散列函数时具有较低的冲突率。

Lehmer 随机数生成程序

虽然 produce_dag 函数不需要生成无偏随机数，但潜在的威胁是 seed**i % P 只取少数几个值。这可以为矿工识别模式提供优势。

为了避免这种情况，可采用数论结果。 安全素数(opens in a new tab)定义为素数 P，从而 (P-1)/2 也是素数。乘数组(opens in a new tab)中 x 的顺序（乘数组 ℤ/nℤ）定义为最小 m，以使

1xᵐ mod P ≡ 1

鉴于这些定义，我们得到：

观察 1。令 x 成为乘法组 ℤ/Pℤ 的一员，以获得安全素数 P。如果 x mod P ≠ 1 mod P 和 x mod P ≠ P-1 mod P，那么 x 的顺序是 P-1 或 (P-1)/2。

证明。由于 P 是一个安全素数，那么根据 [Lagrange's Theorem][lagrange]，我们得到 x 的顺序为 1、2、(P-1)/2 或 P-1。

x 的顺序不能是 1，因为根据费马小定理，我们得出：

1xP-1 mod P ≡ 1

因此，x 必须是 ℤ/nℤ 的乘法单位，并且是唯一的乘法单位。由于我们假设 x ≠ 1，所以这是不可能的。

x 的顺序不能是 2，除非 x = P-1，因为这将违反 P 是素数的事实。

从以上命题中，我们可以知道，迭代 (picker * init) % P 的循环长度至少为 (P-1)/2。这是因为我们选择 P 作为安全素数，强度几乎翻倍，且 init 处于 [2,2**256+1] 区间内。鉴于强度为 P，我们永远不应期待源自模幂运算的周期。

在有向无环图中分配第一个单元时（变量标签为 init），我们会计算 pow(sha3(seed) + 2, 3, P)。初看起来，这并不能保证结果既不是 1 也不是 P-1。然而，既然 P-1 是一个安全素数，我们还提供以下额外保证，这是观察 1 的必然结果：

观察 2。令 x 成为乘法组 ℤ/Pℤ 的一员，以获得安全素数 P，并让 w 成为自然数。如果 x mod P ≠ 1 mod P、x mod P ≠ P-1 mod P，且 w mod P ≠ P-1 mod P、w mod P ≠ 0 mod P，那么 xʷ mod P ≠ 1 mod P 且 xʷ mod P ≠ P-1 mod P

模幂运算用作散列函数

对于特定的 P 值和 w 值，函数 pow(x, w, P) 可能存在许多冲突。例如，pow(x,9,19) 的值只能接受 {1,18}。

鉴于 P 为素数，可以使用以下结果，选择一个用于模幂运算哈希函数的适当 w 值：

观察 3。令 P 为素数；当且仅当用于 ℤ/Pℤ 中所有 a 和 b 满足以下条件时，w 和 P-1 才能为互素。
`aʷ mod P ≡ bʷ mod P`，当且仅当 `a mod P ≡ b mod P`

因此，鉴于 P 为素数，且 w 与 P-1 为互素，我们得出 |{pow(x, w, P) : x ∈ ℤ}| = P，表示散列函数具有尽可能小的冲突率。

在特殊情况下，P 是我们选择的安全素数，那么 P-1 仅有系数 1、2、(P-1)/2 和 P-1。由于 P > 7，我们知道 3 与 P-1 互素，因此 w=3 满足上述命题。

更有效的缓存评估算法

1def quick_calc(params, seed, p):
2    cache = produce_dag(params, seed, params["cache_size"])
3    return quick_calc_cached(cache, params, p)
4
5def quick_calc_cached(cache, params, p):
6    P = params["P"]
7    if p < len(cache):
8        return cache[p]
9    else:
10        x = pow(cache[0], p + 1, P)
11        for _ in range(params["k"]):
12            x ^= quick_calc_cached(cache, params, x % p)
13        return pow(x, params["w"], P)
14
15def quick_hashimoto(seed, dagsize, params, header, nonce):
16    cache = produce_dag(params, seed, params["cache_size"])
17    return quick_hashimoto_cached(cache, dagsize, params, header, nonce)
18
19def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
20    m = dagsize // 2
21    mask = 2**64 - 1
22    mix = sha3(encode_int(nonce) + header)
23    for _ in range(params["accesses"]):
24        mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
25    return dbl_sha3(mix)
显示全部
 复制

back-to-top ↑