跳至主要內容
Change page

Dagger-Hashimoto

Dagger-Hashimoto 是以太坊挖礦演算法的最初研究實作與規範。Dagger-Hashimoto 後來被 Ethash 取代。挖礦已於 2022 年 9 月 15 日的合併中完全關閉。從那時起，以太坊改由權益證明 (PoS)機制來保障安全。本頁面僅供歷史參考——此處的資訊已不再適用於合併後的以太坊。

先決條件

為了更了解本頁面，我們建議您先閱讀工作量證明 (PoW) 共識、挖礦以及挖礦演算法。

Dagger-Hashimoto

Dagger-Hashimoto 旨在滿足兩個目標：

  1. 抗 ASIC：為該演算法建立專用硬體所帶來的效益應盡可能小。
  2. 輕客戶端可驗證性：區塊應能由輕客戶端有效率地驗證。

透過額外的修改，我們也說明了如何在需要時達成第三個目標，但代價是增加複雜性：

完整鏈儲存：挖礦應要求儲存完整的區塊鏈狀態（由於以太坊狀態樹的不規則結構，我們預期可以進行一些修剪，特別是某些常用的合約，但我們希望將此降至最低）。

DAG 產生

該演算法的程式碼將在下方以 Python 定義。首先，我們提供 encode_int 以將指定精度的無號整數編組為字串。同時也提供其反向操作：

接下來我們假設 sha3 是一個接受整數並輸出整數的函數，而 dbl_sha3 是一個雙重 SHA-3 函數；如果將此參考程式碼轉換為實作，請使用：

參數

演算法使用的參數為：

在此情況下，P 是一個被選定的質數，使得 log₂(P) 略小於 512，這對應於我們一直用來表示數字的 512 位元。請注意，實際上只需要儲存 DAG 的後半部，因此實際的 RAM 需求從 1 GB 開始，並以每年 441 MB 的速度增長。

Dagger 圖形建構

Dagger 圖形建構原語定義如下：

基本上，它從一個單一節點 sha3(seed) 開始建立圖形，然後根據隨機的先前節點依序加入其他節點。建立新節點時，會計算種子的模冪以隨機選擇一些小於 i 的索引（使用上方的 x % i），並將這些索引處的節點值用於計算以產生 x 的新值，然後將其輸入到一個小型的（基於 XOR 的）工作量證明函數中，最終產生圖形在索引 i 處的值。這種特定設計背後的原理是強制循序存取 DAG；在知道目前值之前，無法確定將要存取的下一個 DAG 值。最後，模冪運算會進一步對結果進行雜湊運算。

此演算法依賴於數論中的幾個結果。請參閱下方的附錄以了解相關討論。

輕客戶端評估

上述的圖形建構旨在允許透過僅計算少量節點的子樹並僅需要少量輔助記憶體來重建圖形中的每個節點。請注意，當 k=1 時，子樹只是一條向上延伸至 DAG 中第一個元素的值鏈。

DAG 的輕客戶端計算函數運作如下：

基本上，它只是上述演算法的重寫，移除了計算整個 DAG 值的迴圈，並將先前的節點查找替換為遞迴呼叫或快取查找。請注意，對於 k=1，快取是不必要的，儘管進一步的最佳化實際上會預先計算 DAG 的前幾千個值，並將其保留為計算的靜態快取；有關此程式碼實作，請參閱附錄。

DAG 的雙重緩衝區

在完整客戶端中，會使用由上述公式產生的 2 個 DAG 的雙重緩衝區 (double buffer) (opens in a new tab)。其概念是根據上述參數，每隔 epochtime 個區塊產生一次 DAG。客戶端不使用最新產生的 DAG，而是使用前一個。這樣做的好處是允許 DAG 隨著時間推移被替換，而不需要加入一個讓礦工必須突然重新計算所有資料的步驟。否則，可能會在固定間隔出現鏈處理突然暫時變慢的情況，並大幅增加中心化程度。從而在重新計算所有資料之前的幾分鐘內產生 51% 攻擊的風險。

用於產生計算區塊工作量所需 DAG 集合的演算法如下：

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 被認為是記憶體密集型 (RAM hard)，但它依賴於 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)

使用雙重 SHA-3 允許一種零資料、近乎即時的預先驗證形式，僅驗證是否提供了正確的中間值。這層外層的工作量證明對 ASIC 非常友善且相當薄弱，但它的存在是為了讓 DDoS 攻擊變得更加困難，因為必須完成這少量的工作才能產生不會被立即拒絕的區塊。以下是輕客戶端版本：

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 對區塊頭施加了額外的要求：

  • 為了讓雙層驗證發揮作用，區塊頭必須同時具有隨機數和 SHA-3 運算前的中間值
  • 區塊頭必須在某處儲存目前種子集的 SHA-3 雜湊值

延伸閱讀

知道有幫助過您的社群資源嗎？編輯此頁面並加入它！

附錄

如上所述，用於產生 DAG 的隨機數產生器 (RNG) 依賴於數論中的一些結果。首先，我們保證作為 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 僅採用少數幾個值。這可能會為識別出該模式的礦工提供優於未識別出該模式的礦工的優勢。

為了避免這種情況，我們引用了數論中的一個結果。安全質數 (Safe Prime) (opens in a new tab) 定義為一個質數 P，使得 (P-1)/2 也是質數。乘法群 (opens in a new tab) ℤ/nℤ 的成員 x 的_階 (order)_ 定義為最小的 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's Theorem)][lagrange]，我們得出 x 的階為 1、2、(P-1)/2 或 P-1。

x 的階不能為 1，因為根據費馬小定理 (Fermat's Little Theorem)，我們得出：

xP-1 mod P ≡ 1

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

x 的階不能為 2，除非 x = P-1，因為這會違反 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 滿足上述命題。

更有效率的基於快取的評估演算法