作者：Suhas Daftuar
原文出版於 2019 年 2 月。
摘要
比特幣的區塊頭中包含了一個對該塊所確認的交易集合的承諾，這是用交易的 id（交易的連續兩次 SHA256 計算的哈希值）構造出一棵默克爾樹、然後在區塊頭中包含樹根，來實現的。相應地，憑藉它，我們可以向一個比特幣輕客戶端證明某一筆交易被某一個區塊確認，辦法是提供從樹根到交易的默克爾路徑。然而，這其中的默克爾樹的特殊構造，有幾種安全性上的弱點，包括至少兩種會影響 Bitcoin Core 共識邏輯的區塊熔融性漏洞，以及一種對輕客戶端的攻擊（一筆無效的交易可以被 “證明” 出現在了某個區塊中），比起找出連續兩次 SHA256 哈希運算的碰撞，只需少得多的工作量。
致謝
許多人都在 bitcoin-dev 郵件組中報告過本總結中描述的部分問題，包括 Sergio Lerner 和 Peter Todd 。本總結基於筆者與 Johnson Law 和 Greg Maxwell 的私人 IRC 討論。我認為，第三章中討論的部分觀察最初來自 Luke Dashjr 。
1 背景
1.1 默克爾根的構造
回顧一下，Bitcoin 所用的默克爾根構造從對每一筆交易 [1] 作連續兩次 SHA256 運算（double-SHA256）、得出哈希值 $H$ 作為樹上的葉子開始。對每一對連續的葉子，我們拼接葉子、並對葉子作連續兩次 SHA256 哈希運算，以結果哈希值作為這對葉子的父節點。重要的是，如果樹上某一層的節點是奇數個，那麼最後一個元素會先被複制，所以，其父節點會是該元素複製自身、相互拼接後的哈希值。舉個例子，如果一個區塊內有三筆交易，那麼默克爾樹就會長這樣：
這裡，Node1 是用 H(H(Tx1)||H(Tx2)) 計算出來的，而 Node2 是用 H(H(Tx3)||H(Tx3)) 計算出來的。最後，默克爾根是用 H(Node1||Node2) 計算出來的，並且這個默克爾根會出現在區塊頭中。
如果一個區塊只有一筆交易，那麼默克爾根就會是這一筆交易的哈希值。注意，每個有效的區塊都至少要包含一筆交易。
1.2 Bitcoin Core 中的區塊有效性
Bitcoin Core 的共識邏輯將區塊驗證分成幾個部分，並跟蹤一個區塊在所有這些階段中的有效性。舉個例子，在處理一個新的區塊頭的時候（一般來說會在收到區塊之前），區塊頭會在網絡的共識規則下檢查有效性。稍後，區塊到達的時候，區塊也會分階段處理，先運行無語境（context-free）的檢查（不依賴於任何其它區塊和區塊頭），然後是依賴於該區塊所在區塊頭鏈的檢查，最後是對交易及它們的簽名的檢查、該區塊是否屬於最多工作量的區塊頭鏈的檢查。
每一個存儲好的區塊頭都有一個相關的緩存數值，用來跟蹤相關的區塊已經完成了多少項驗證。如果一個區塊被發現是無效的，Bitcoin Core 會永久存儲該塊的無效狀態，而且會避免重複處理該塊以及該塊的後續區塊。
在下一章中，我們會討論圍繞這種永久標記無效區塊以防止攻擊者使用這種優化措施來分裂網絡的顧慮。
2 複製交易，CVE-2012-2459
這是寫在 Bitcoin Core 源代碼中的：
警告！如果你是為學習密碼學 以及/或者 設計一種將要使用默克爾樹的新系統，請記住，下面的默克爾樹算法有一個跟交易 id 重合相關的嚴重錯誤，最終會產生漏洞（CVE-2012-2456）。原因在於，如果某個時刻，在列表中的哈希值的數量是奇數，則最後一個哈希值會被複制，以計算下一層（這在默克爾樹中是不常見的設計）。這導致交易的特定排序會產生相同的默克爾根。舉個例子，這兩棵樹： A A / \ / \ B C B C / \ | / \ / \ D E F D E E F/ \ / \ / \ / \ / \ / \ / \1 2 3 4 5 6 1 2 3 4 5 6 5 6交易列表 [1, 2, 3, 4, 5, 6] 跟 [1, 2, 3, 4, 5, 6, 5, 6]（5 和 6 被重複了）會得出相同的哈希值 A（因為 (F) 和 (F, F) 的哈希值都是 C）。漏洞在於，你可以發送一個帶有重複交易列表的區塊，它跟原版區塊有相同的默克爾根值、相同的區塊哈希值，但卻無法通過驗證。然而，如果接收節點將這個區塊標記為永久無效的，就不再能接收同一區塊沒有篡改過（因此可能是有效）的版本。我們通過檢測這種情形來防止這種誤傷：檢測會在列表末尾哈希兩個完全相同的哈希值的行為，並跟具有無效默克爾根的區塊採取相同的處理措施。假設沒有 double-SHA256 的碰撞，這將檢查出所有已知的改變交易而不影響默克爾根的方法。在下一節中，我們會討論一種新的區塊熔融性，是在上述註釋撰寫之時尚未發現的。
3 由默克爾樹歧義導致的弱點
Greg Maxwell 已經（在 IRC 私人通信中）指出，一種弱點根源於默克爾樹上的 “葉子與節點之間缺乏域分隔”。默克爾樹上的非葉子節點是一個 64 字節的輸入（其子節點的拼接）的哈希值。同時，葉子節點是一筆交易（不帶見證的序列化形式）的哈希值。如果一筆交易的序列化形式（不帶見證數據）可以是 64 字節，那麼就無法區分葉子節點與非葉子節點，就可能暴露出安全漏洞。
3.1 區塊熔融性
考慮一個帶有 2 筆交易的區塊 $B$ 。區塊 B 的默克爾根值是這樣的：
再想象一個只有 1 筆交易的區塊。那麼默克爾根會是 H(Tx1) 。
假設一個對等節點轉發了 $B$ 的區塊頭，並聲稱 $B$ 只有一筆交易，而不是兩筆交易，而且區塊中的交易 $T$ 的序列化形式正是 H(Tx1)||H(Tx2) 。如果 T 能夠成功反序列化為一筆交易 [2]（並且真的能重新序列化為 H(Tx1)||H(Tx2)），那麼 $T$ 的哈希值就能跟區塊頭中的默克爾根值相匹配。如果 T 是無效的，那麼收到這種版本的區塊 $B$ 的節點就會拒絕這個區塊，把它當成無效區塊。然而，如果接收節點永久將這個區塊哈希值標記為無效的，就再也不能處理也接受真正有效的區塊 $B$，即使誠實節點傳輸過來的是兩筆有效的交易。這可以用來讓一個節點脫離共識。
這種攻擊可以普遍化，在一個帶有 $N$ 筆交易的區塊中，攻擊者聲稱這個區塊實際上有 N/2k 筆交易，全部都是 64 字節的 “交易”，它們的哈希值就是原本樹上第 k 行的節點。如果這些 64 字節的數值全部都能成功反序列化為交易（因此可以被溝通），那麼收到這個區塊的節點節點就不應該將這個哈希值永久標為無效的，即使這些 64 字節的交易都是無效的。
**3.1.1 為了製作這樣的 2 交易區塊，使得默克爾根的原像可以反序列化為一筆交易，需要付出多少工作量？ **
交易是這樣序列化的：
[version][vin][vout][locktime]版本號和鎖定時間都是 4 字節長的字段，沒有反序列化的要求。而 $vin$（交易輸入）和 $vout$（交易輸出）是這樣序列化的：
[|vin|][vin0]...[vinn][|vout|][vout0]...[voutn]而 $vin$ 的大小是使用比特幣的 “緻密體積” 編碼的。因為每一個 $vin$ 都包含一個 32 字節的前序交易哈希值，而我們希望創建能夠成功反序列化為一筆交易的 64 字節，那麼我們可以約束 |vin| 為 1，只需要一個字節（0x01）就能編碼。每一個 $vin_i$ 都由以下字段組成：
[hash][index][scriptSig][sequence]其中 hash 就是 32 字節的前序交易哈希值，而 index 是一個 4 字節長的序列號、索引到由 hash 指定的交易的 $vout$ 向量。有效的 coinbase 交易必須是由一個空的前序交易哈希值，而且索引號要設為 Oxffffffff，但無效的 coinbase 交易不會受到這些數值的約束。
scriptsig 會編碼成一個腳本長度加上該腳本的內容，所以會有一個約束：長度必須跟讀取的字節數量相匹配。目前，我們可以假設一個空的 $scriptSig$，只長 1 個字節，編碼為 0x00。
而sequence 是一個 4 字節長的字段，沒有約束。
$vout$ 數組也會跟長度一起編碼，為了讓序列化有效，也要遵守這個規則。所以我們也約束 $vout$ 的體積為 1，這會引入多一個固定字節 0x01。剩餘的 vout 向量會這樣序列化：
[amount][scriptPubKey]amount 是一個 8 字節長的字段，表示數量，而 scriptPubKey 跟 scriptSig 一樣，有一個長度編碼，所以至少是 1 字節。
總結以下，一筆可以成功反序列化的 64 字節的交易可以這樣構造出來：
A = 版本號（4 字節，無約束）
B = vin 數量（1 字節，有約束）
C = 前序交易 id（32 字節，無約束）
D = 前序輸出索引號（4 字節，無約束）
E = 腳本簽名（1 字節，有約束）
F = sequece（4 字節，無約束）
G = vout 數量（1 字節，有約束）
H = amount（8 字節，無約束）
I = 腳本公鑰的長度（1 字節，有約束）
J = 腳本公鑰的剩餘部分（4 字節，無約束）
K = locktime（4 字節，無約束）
這裡，我們將 $vout_0$ 中的 $scriptPubKey$ 設為總計 5 字節，從而交易是 64 字節長，而且成功的反序列化僅僅約束上述那些字節（長度編碼）。但完整地看，我們可以看出，我們只需要 $scriptPubKey$ 和$scriptSig$ 的長度總和為 4 字節。
還要注意，64 個字節中，只有 4 個 字節是被約束的，而它們都出現在不同的半截中。所以，要製作一個默克爾根值的原像可以有效反序列化為 64 字節交易的區塊頭，只需要搜索 8 個比特，就可以找出一個可用的 coinbase 交易（它會哈希成第一個 32 字節），再加上大約 22 比特的搜索（（1/5）* 224，所以稍小於 22 比特）就可以找出第二筆交易，其哈希值是第二個 32 字節 —— 非常少的計算量。
（譯者注：這裡的意思是，你需要找出這樣一個 64 字節的數值：它本身可以被反序列化為一筆交易；而它的前 32 字節剛好是某個 coinbase 交易的哈希值，而其後 32 字節剛好是另一筆交易的哈希值。也可以說，你要找出 一個 coinbase 交易 + 一個普通交易 的組合，它們的哈希值的拼接，恰好可以反序列化為一筆交易。）
3.1.2 製作一個其默克爾樹的某一行節點全部可以反序列化為有效交易的區塊需要多少工作量？
注意，一個區塊的第一筆交易必須是 coinbase 交易，並且，如前所述，這很大程度上約束了代表第一筆交易的前 32 字節：只有 4 個字節的版本號是沒有約束的。所以，需要搜索至少 28*8 = 224 比特，才能找出樹上給定一行的第一個節點的前一半會跟一筆 coinbase 交易匹配的情形，然後是繼續搜索，找出後一半會跟一筆一定程度上有意義的交易相匹配的情形（這會容易很多，只有 16 字節左右是被約束的，所以只需 128 比特的搜索就可以找出一個碰撞）。當然，可以使用默克爾樹上的任意一行，但很明顯，這在計算上應該是不可行的。
3.2 對 SPV（輕）客戶端的攻擊
SPV 客戶端被預期能夠接收證明某筆交易出現在某個區塊中的證據。這種證據的性質是給客戶端提供一條貫通默克爾樹的路徑，從樹根一直到交易。
沿默克爾樹向下然而，假設一筆（有效的）64 字節的交易 $T$ 被包含在一個區塊中，且其後面 32 字節（比之前 32 字節更少約束）被精心構造過，以至於跟其它假的、無效的交易 F 碰撞。設 $R$ 為默克爾根值，那麼我們有：
R = H(H(H(...H(T)||H(...)...)T = [32bytes]||[H(F)]如果這樣的交易是可能構造出來的，那麼一個節點就可以愚弄一個 SPV 客戶端，使之相信 $F$ 在這個區塊中 —— 因為他可以提供從默克爾根到 $T$ 的默克爾路徑、然後將 $T$ 解釋為一個內部節點（而不是葉子節點）。因為一個區塊中有多少筆交易，在區塊頭中是看不出來的，SPV 客戶端並不能先知道這個數量，因此，也就無法知道樹的正確深度。
3.2.1 製作一筆有效的 64 字節交易，使得其後 32 字節跟另一筆交易的哈希值相碰撞，需要多少工作量？
注意Sergio Lerner 已經公開了一項專門的分析，指出可以用 72 比特的搜索實現；Peter Todd 也公開了一項分析，聲稱只需 60 比特的搜索就可以實現。
從上面的圖示，我們可以知道，交易的前 32 字節受到更多的約束，因為它包含的更多是被花費的前序輸出，它必須是有效的（否則交易就無效了）。那麼，我們關注後 32 字節：
C = 前序交易 id（前序交易 id 剩餘的 5 字節，無約束）
D = 前序輸出索引號（4 字節，21 比特有約束）
E = scriptSig（1 字節，有約束）
F = sequence（4 字節，如果交易版本號為 1，則無約束）
G = 交易輸出的數量（1 字節，有約束）
H = amount（8 字節，約 33 字節是有約束的，見下文）
I = scriptPubKey 的長度（1 字節，有約束）
J = scriptPubKey 的剩餘部分（4 字節，無約束）
K = locktime（4 字節，約 29 比特無約束，見下文）
我們可以假設前序交易 id 的剩餘比特是沒有約束的，因為一旦我們找出一筆候選交易，我們就可以作專門的 40 比特的搜索，找出一個其前序交易 id 的後 5 個比特符合我們要求的輸入。類似地，我們可以部分約束前序輸出索引號，僅僅要求它不要大於（假設）2048，因為我們可以假設我們有能力創建一個帶有 2048 個輸出的交易、且合適的輸出位置有合適數額的交易。
我們可以假設 $sequence$ 是沒有約束的，因為這個字段對版本 1 的交易沒有共識上的含義。因為我們假設了交易的前 32 字節是固定的，所以我們假設版本號是 1 。
而 $amount$ 是一個 8 字節的字段。如果攻擊者可以獲得很多錢，那麼就有更多的比特不受約束，因為共識約束是輸出的價值要小於或等於輸入的價值。然而，因為這種交易的輸入資金是任何人都可以花費的（或者任何人都沒法花費的），用在這種攻擊中的資金可能找不回來（如果攻擊者也是一名礦工，則可以嘗試通過重新花費同一個區塊來找回資金，雖然其他礦工可能孤立這個區塊，從而盜取攻擊者的手續費和任何人都可以花費的輸出）。而且，只要我們資金可能會丟失，我們就必須考慮相同成本可以運行的其他攻擊，例如挖掘少量無效區塊並使用這些區塊來攻擊輕客戶端（注意，雖然這些攻擊的性質是不一樣的，因為本攻擊可以欺騙輕客戶端、使之相信一筆假交易已經得到了任意多數量的區塊確認 —— 這可能會比挖出少量假區塊更有價值，因為假區塊沒有這種讓目標交易獲得任意多數量區塊確認的能力）。
為便於討論，我們將攻擊者願意承擔的代價大致設為 25 BTC，當前它的價值是 2 個區塊獎勵。這時候，被約束的比特數量為 33 個。（如果我們假設攻擊者願意冒 687 BTC 的風險，那麼所需的搜索數量就會下降 5 個比特）。
$locktime$ 是一個 4 字節的整數，如果超過 5 0000 0000，就會被解釋成 Unix 時間；如果小於這個數值，就會被解釋成區塊高度。當前的時間大概是紀元以來 14 億秒，所以我們估計有 9 億個有效的 locktime 數值，這是大概 29 比特的自由度。
綜上所述，我們有 81 比特是受約束的，意思是，可以運行 81 比特的搜索（加上額外的 40 比特，以構造出提供可被任何人花費的資金的注資交易）的攻擊者，就可以用這種辦法愚弄 SPV 輕節點。（注意：這比我們預期的，需要 128 比特的搜索（找出兩筆具有相同哈希值的交易），要小得多。）
4 漏洞與緩解
4.1 區塊熔融性
區塊熔融性所帶來的共識分裂風險，根源於圍繞無效區塊的處理邏輯。如上面的 Bitcoin Core 代碼註釋所述，我們已經意識到，只要被處理的區塊可能被熔融，共識邏輯就絕對不能將任何區塊頭永久標記成無效的：只要對應於同一個區塊頭的某一個區塊可能是有效的，將該區塊頭永久禁用就可能導致共識分裂。
複製交易複製交易的問題自 Bitcoin-Qt 版本 0.6.1 以來就已經被修復了。那時（和現在）有一組對進入區塊的檢查（在一個叫做 CheckBlock() 的函數中執行），這時候如果檢查不通過，則區塊不會被存儲 —— 而且檢查錯誤也不會被永久緩存。對複製交易的新檢查也被加入到這組檢查中，從而解決了問題。
沿默克爾樹向上另一個也在 CheckBlock() 中執行的檢查跟 coinbase 交易有關：如果一個區塊中的第一筆交易不具有 coinbase 交易所需滿足的結構 —— 一個輸入，其前序交易哈希值全部是 0 ，而索引號全部是是 1 —— 那麼這個區塊也將不能通過驗證。這個檢查的副作用在於，在我們甚至還不知道章節 3.1 所討論的區塊熔融性時，它就已經實質上防止了這個問題 —— 如前所述，它讓攻擊者需要至少 224 比特的搜索工作量，才能產生一個能夠通過 coinbase 交易檢查的熔融區塊。
從 Bitcoin Core 0.13.0 以來，圍繞處理區塊熔融性的實現改變了，所以默克爾樹熔融的可能性可以在 CheckBlock() 中檢查出來，然後一個標籤會跟蹤這個區塊是否被熔融過。這個標籤會被決定這個區塊是否應被永久禁用的邏輯中。但 CheckBlock() 依然會被調用兩次：一次會帶有出現故障提前返回的特性，如前所述；另一次則是在存儲區塊之前（要求通過檢查）。因此，即使一個區塊在 CheckBlock() 中失敗，並且是出於讓我們認為它肯定無效（不可能是出於熔融）的理由，函數的邏輯也不會讓該區塊永久禁用。
因此，調用兩次似乎是多餘的。在 Bitcoin Core 代碼提交 dbb89dc 中，看起來多餘的調用被刪除了，從而，當 CheckBlock() 因為不確定知曉的熔融可能而出錯時，這個錯誤會將對應的區塊永久禁用。因此，Bitcoin Core 0.13.0、0.13.1 和 0.13.2 都易受 3.1 章節所述攻擊的傷害。
當這個問題在私下裡發現之後，這個變更在 Bitcoin Core 代碼提交 ba803ef 中反轉了，趕在了 0.14.0 發佈的前面。0.13 版本是已知唯一易受這種攻擊的版本。
未來可能會有更進一步的緩解措施，例如，如果一個區塊完全由 64 字節的交易組成，就絕不會被永久標記為無效區塊 [3]；或者，在共識中禁用 64 字節的交易。這些更直接的修復措施的提議已被推遲，等待輕客戶端所面臨的問題（如章節 3.2 所述）的發現和緩解措施。
4.2 輕客戶端
為保護輕客戶端免受 3.2 章所述的攻擊，可以採用許多緩解措施。從 Bitcoin Core 0.16.1 開始，64 字節的交易就無法再進入交易池。如果礦工也採用這個規則，則可以合理提出一項共識變更，讓 64 字節的交易無效，如果得到採用，就將永遠消除默克爾樹上葉子和內部節點之間的模稜兩可，而且，也能保護現有的輕客戶端（它們不需要任何變更） [4]。
注意，在比特幣區塊鏈上，已經出現過少量的 64 字節交易。
輕客戶端可以採用的另一個緩解措施是，要求證據也包含對 coinbase 交易的證據以及 coinbase 交易本身（用於確定默克爾樹的深度，這個深度對於一個區塊中的所有交易來說都必須相同）。這將要求輕客戶端軟件的變更 —— 尤其是，要驗證進入的 coinbase 交易具有預定義的形式 —— 但不需要共識變更。
Sergio Lerner 也在他的報告中討論了額外的緩解措施。
參考文獻
Sergio Lerner ，“Leaf-Node Vulnerability in Bitcoin Merkle Tree Design”，2017 年 8 月 4 日。https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/
Peter Todd，“Trusted merkle tree depth for safe tx inclusion proofs without a soft fork”，2018 年 6 月 7 日。https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016091.html
腳註
1. 在本文中，我們只討論區塊頭中的默克爾根值，因此，交易是在沒有見證的情況下被序列化、然後運行哈希的。 ↩
2. 注意，任何區塊，無論是否熔融過，僅在可以被溝通 —— 也即消息可以根據網絡的消息處理規則被反序列化 —— 的時候，才會被節點認為是一個區塊。無法理解的消息會直接被拋棄掉。 ↩
3. 注意，本文的 “64 字節” 指的是交易不帶見證時序列化之後的長度。 ↩
4. 我們省略了通過沿默克爾樹往上、聲稱一個內部節點是利益相關交易的針對 SPV 節點的攻擊。在合理的假設下，可以用 116 比特的工作量來欺騙輕客戶端其某個輸出已被花費掉了。如果共識變更讓 64 字節的交易無效、輕客戶端也修改成拒絕 64 字節的交易，就完全不再需要擔心這個問題。 ↩
