AsicBoost 是如何工作的？

Timo Hanke 和 Sergio Demian Lerner的AsicBoost 論文描述了一種將 ASIC 性能提高 20% 的方法。不過，細節上有點稀疏。他們在優化什麼？

介紹

AsicBoost 通過降低 SHA-256 計算的一部分的計算頻率，總體上加快了比特幣探勘（對於 ASIC 和 CPU 等）。

一個比特幣區塊頭是 80 字節長。它適合 SHA-256 散列的 2 個塊。它被散列成一個 32 字節的值，然後再次散列（1 個塊）以獲得與門檻值進行比較的最終值。

虛擬碼

進行比特幣挖礦的傳統方法如下所示：

while True:
   blockHeader = ...  # based on Merkle root and other fields
   sha256Block0 = sha256Expand(blockHeader[0 : 64])
   midState = sh256Compress(sha256InitVector, sha256Block0)

   for i in range(2**32):  # Try nonces
       blockHeader.nonce = i
       sha256Block1 = padAndExpand(blockHeader[64 : 80])
       singleSha = sh256Compress(midState, sha256Block1)

       sha256Block2 = padAndExpand(singleSha)
       doubleSha = sh256Compress(sha256InitVector, sha256Block2)
       if doubleSha < target:
           miningSuccessful(blockHeader)  # Jackpot!

請注意，內部循環有 2 次塊擴展計算和 2 次塊壓縮計算。

現在 AsicBoost 提出的是，我們以某種方式找到一堆不同但相同的blockHeader值。因為 Merkle 根欄位跨越兩個散列塊，這意味著我們需要按 Merkle 散列的最後 4 個字節對候選者進行分組。現在探勘算法是這樣的：sha256Block0``sha256Block1

while True:
   blockHeader = ...  # based on various fields
   candidates = dict()  # 4 bytes -> sets of blocks
   for i in range(...):  # Generate the more the merrier
       tempBh = blockHeader.randomizeMerkle()
       sha256Block0 = sha256Expand(tempBh[0 : 64])
       tempBh.midState = sh256Compress(sha256InitVector, sha256Block0)
       candidates[tempBh.merkleRoot[28 : 32]].add(tempBh)

   for i in range(2**32):  # Try nonces
       for key in candidates:
           tempBh = candidates[key][0]
           tempBh.nonce = i
           sha256Block1 = padAndExpand(tempBh[64 : 80])

           for tempBh in candidates[key]:
               singleSha = sh256Compress(tempBh.midState, sha256Block1)
               sha256Block2 = padAndExpand(singleSha)
               doubleSha = sh256Compress(sha256InitVector, sha256Block2)
               if doubleSha < target:
                   miningSuccessful(blockHeader)  # Jackpot!

現在請注意，內部循環對每個候選組執行 1 次塊擴展計算，然後對每個候選塊標頭執行 1 次塊擴展計算加上 2 次塊壓縮計算。

因此，當大多數候選組有多個候選時，該技術勝過傳統探勘，並且生成和排序候選的成本超過了每個候選最多節省一次塊擴展計算的收益。

我從下面的論文中複製了圖 2 和圖 3，以提供另一種解釋。

圖2：

圖 3：

從歷史上看，採礦由內循環（紅色）和外循環（綠色）組成。每次通過內部循環，隨機數都會增加。這僅影響塊 2，並導致重新評估所有紅色塊。在開始創建重複結果之前，您只能執行 40 億次 (2^32)。此時，外循環調整區塊數據的佈局以獲得新的隨機默克爾根欄位，然後重複。

在此實現中，您必須為每個內部循環執行 4 次大型操作。當更改 merkle root 作為外部循環的一部分時，您必須在正常 4 的基礎上執行額外的 2 個大型操作（綠色）。但是，AsicBoost 的作者註意到，在更改 merkle root 值時，有一個 1 :2^32 可能 Chunk 2 的內容不會改變，在這種情況下 Chunk 2 的擴展器的輸出也不會改變，所以我們可以跳過重做該計算。

此時的關鍵是生日問題。在我們開始探勘一個塊之前，我們可以計算幾個隨機 merkle 根並找到衝突（即具有相同最後 4 個字節或“尾部”的多個 merkle 根），而無需評估 2^32 附近的任何 merkle 根。此外，預先計算與這些不同的默克爾根相關聯的標記為“中間狀態”的值。

最後，這允許我們在不增加隨機數的情況下生成新摘要的另一種方法：重用目前的 Chunk 2 值，選擇一個與目前使用的尾部碰撞的新 merkle 根，並使用與關聯的值更新“中間狀態”那個默克爾根（我們之前計算過的）。然後重新評估除了附加到 Chunk 2 的 Expander 之外的所有紅色塊，因為我們沒有更改 Chunk 2 的值——這只是三個大型操作，而不是通常的四個。

例子

假設我們找到了 3 個都具有相同尾部的 merkle 根，並預先計算了它們相關的中間狀態（A、B、C）。我們的挖礦循環看起來像這樣：

1. 設置 nonce=0，midstate=A（4 次操作）。
2. 設置 midstate=B（3次操作）。
3. 設置 midstate=C（3次操作）。
4. 設置 nonce=1，midstate=A（4 次操作）。
5. 設置 midstate=B（3次操作）。
6. ……等等。

您預先計算的每個 merkle 根衝突都會為您節省 2^32 次擴展操作，因為您可以在所有 2^32 個隨機數中重複使用它。由於生日問題，預先計算這些碰撞的成本小於每次碰撞 2^32，因此它可以是淨收益。

在實踐中，您最終會得到多組不相交的碰撞默克爾根，而不僅僅是此處顯示的 1 組。因此，您可能會循環通過 {A, B, C}，然後是 {D, E, F}，並且從 C 切換到 D 將花費正常的 4 次操作，因為尾部已更改。或者，您可以將每個不相交的集合提供給礦工的不同核心/晶片。

引用自：https://bitcoin.stackexchange.com/questions/43579