跳至主要內容
Change page

Dagger-Hashimoto

頁面最後更新： 2026年4月3日

Lilian_chouL (opens in a new tab)
sudosu.tws (opens in a new tab)
comme.le.gnuc (opens in a new tab)
+5

Dagger-Hashimoto 是以太坊挖礦演算法的原始研究實作和規範。 Dagger-Hashimoto 已被 Ethash 取代。 在 2022 年 9 月 15 日的 合併 之後，挖礦已徹底關閉。 此後，以太坊改用 權益證明 機制來保障安全。 本頁面展示歷史相關內容，其中的資訊與合併後的以太坊不再相關。

先決條件

為了更深入了解本頁內容，我們建議您先閱讀關於 工作量證明共識、挖礦 以及 挖礦演算法 的資訊。

Dagger-Hashimoto

Dagger-Hashimoto 旨在實現兩個目標：

  1. 專用積體電路抗性：為演算法打造專用硬體的益處應盡可能地小。
  2. 輕量用戶端可驗證性：區塊應能被輕量用戶端高效驗證。

在進一步修改後，我們還要具體說明如何在必要時實現第三個目標，但要以增加複雜性為代價：

完整鏈儲存：挖礦需要儲存完整的區塊鏈狀態（由於以太坊狀態樹的結構不規則，我們預計將有可能進行一些修剪，特別是一些經常用到的合約，但我們希望盡量減少這種情況）。

DAG 產生

以下演算法程式碼將以 Python 定義。 首先，我們定義了 encode_int，用於將指定精確度的無符號整數封送為字串。 同時也定義了它的逆函式：

接下來，我們假設 sha3 是一個需要輸入整數，然後輸出整數的函式，而 dbl_sha3 是一個 double-sha3 函式；如果將此參考程式碼轉換為實作，請使用以下程式碼：

參數

演算法使用的參數如下：

P 在這種情況下為選定的素數，使得 log₂(P) 僅略小於 512，對應於我們用來表示數字的 512 位元。 請注意，實際上只需要儲存有向無環圖的後半部分，因此，實際隨機存取記憶體需求最初為 1 GB，且每年增長 441 MB。

Dagger 圖形建構

Dagger 建圖基礎單元的定義如下：

基本上，建圖從單一節點 sha3(seed) 開始，然後根據隨機的先前節點按順序添加到其他節點上。 建立一個新節點後，計算種子的模冪，以隨機選擇一些小於 i 的索引（使用上述 x % i），並使用這些索引上的節點值進行計算，以產生新的 x 值，隨後該值被提供給一個較小的工作量證明函式（基於 XOR），最終產生索引 i 上的圖形值。 這種特殊設計背後的基本原理是，強制依序存取有向無環圖；如果目前值未知，則無法確定要存取的下一個有向無環圖的值。 最後，模冪運算會進一步對結果進行雜湊。

這種演算法依賴於數字理論的若干結果。 討論情況見下文附錄。

輕用戶端評估

上述構圖旨在實現只計算少量節點的子樹，並且僅需少量的輔助記憶體，便完成圖中每個節點的重構。 請注意，當 k=1 時，子樹只是一個上升到有向無環圖第一個元素的值鏈。

輕量用戶端中，有向無環圖的計算函式如下：

本質上，它只是對上述演算法的重寫，刪除了計算整個有向無環圖值的循環，並用遞歸呼叫或快取查找取代了早期的節點查找。 請注意，對於 k=1 的情況，快取是不必要的，但進一步的最佳化實際上預先計算了有向無環圖的前幾千個值，並將其作為靜態快取進行計算；有關程式碼實作，請參閱附錄。

DAG 的雙緩衝區

在完整用戶端中，會使用由上述公式產生的 2 個 DAG 的 雙緩衝區 (opens in a new tab)。 其概念是，根據上述參數，每隔 epochtime 個區塊就會產生一個有向無環圖。 但用戶端使用的並非是最新產生的有向無環圖，而是前一個。 這樣做的好處是，有向無環圖可以隨著時間的推移而被替換掉，無需包含一個步驟，讓礦工必須突然重新計算所有資料。 否則，定期的鏈處理可能會突然暫時放緩，並大幅提高中心化程度。 因此，在重新計算所有資料之前的幾分鐘時間內，存在 51% 攻擊風險。

要產生用於計算區塊工作的有向無環圖集，演算法如下：

Hashimoto

初始 Hashimoto 旨在將區塊鏈用作資料集，執行從區塊鏈中選擇 N 個索引的計算，收集這些索引處的交易，對這些資料執行 XOR，並傳回結果雜湊值。 Thaddeus Dryja 的初始演算法（為了保持一致性，已轉換成 Python）具體如下：

def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
    hash_output_A = sha256(prev_hash + merkle_root + nonce)
    txid_mix = 0
    for i in range(64):
        shifted_A = hash_output_A >> i
        transaction = shifted_A % len(list_of_transactions)
        txid_mix ^= list_of_transactions[transaction] << i
    return txid_mix ^ (nonce << 192)

遺憾的是，雖然 Hashimoto 被視為隨機存取記憶體密集型演算法，但它依靠的是 256 位元運算，計算開銷非常之大。 不過，Dagger-Hashimoto 在索引其資料集時，僅使用最低有效 64 位元來解決此問題。

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

使用雙重 SHA3 可以實現零資料、近乎即時的預驗證，僅驗證是否提供了正確的中間值。 此工作量證明的外層對專用積體電路高度友善且相當薄弱，但它的存在使分散式阻斷服務變得更加困難，因為必須完成少量工作才能產生不會立即被拒絕的區塊。 以下為輕量用戶端版本：

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

挖礦與驗證

現在，將它們全部整合到挖礦演算法中：

以下為驗證演算法：

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

輕量用戶端的友善驗證：

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

另外，請注意 Dagger-Hashimoto 對區塊頭有額外的要求：

  • 為了使雙層驗證起效，區塊頭必須同時具有隨機數和中間值 Pre-sha3
  • 區塊頭必須在某處儲存目前種子集的 sha3

延伸閱讀

知道一個曾經幫助你學習更多社區或社團資源? 歡迎在本頁自由編輯或添加內容！

附錄

如前所述，用於產生有向無環圖的隨機數產生依賴於數論的一些結果。 首先，我們確保作為 picker 變數基礎的 Lehmer 隨機數產生器 (RNG) 具有很長的週期。 其次，只要一開始 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) ℤ/nℤ 中一個成員 x 的_階_定義為最小的 m，使得 

xᵐ 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]，x 的階為 1、2、(P-1)/2 或 P-1。

x 的階不可能是 1，因為根據費馬小定理：

xP-1 mod P ≡ 1

因此 x 必須是 ℤ/nℤ 的唯一乘法單位。 由於我們已假設 x ≠ 1，因此這是不可能的。

除非 x = P-1，否則 x 的階不能是 2，因為這將違反 P 是質數的事實。

從上述命題中，我們可以得知迭代 (picker * init) % P 將具有至少 (P-1)/2 的循環長度。 這是因為我們選擇了 P 為約等於 2 的更高次冪的安全質數，且 init 處於 [2,2**256+1] 區間內。 考慮到 P 的大小，我們不應該預期模冪運算會產生循環。

當我們給有向無環圖 (DAG) 中的第一個單元 (標記為 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 為一個質數；w 和 P-1 互質，若且唯若對於 ℤ/Pℤ 中所有的 a 和 b：

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 滿足上述命題。

更高效的快取型評估演算法

這篇文章對您有幫助嗎？