作者：Ruben Somsen
來源：https://gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd
使用關於哪些輸出將保持不花費的提示，實現近乎無狀態的、完全可並行的比特幣區塊鏈驗證。所有其它的 輸入/輸出 都會在一個哈希聚合值中高效劃去；如果驗證成功且提示都是正確的，這個聚合值最終會是零。
引言
驗證是比特幣的核心。驗證速度上的所有提升都會給這個系統的可擴展性（以及所有建立在它基礎上的東西）帶來直接的影響。出於這個理由，提升驗證性能可能是我們可做的最重要的事情之一。
SwiftSync 的一般觀察是，如果我們有兩個集合（在這裡，是輸入和輸出），而我們想知道這兩個集合的差別（也即 UTXO 集），驗證這個問題的一個給定答案（在有提示的情況下）會比計算這個答案本身要容易得多。（就我所知）有創見的地方是，具體如何對這個集合應用上述觀察。這種觀察似乎在其它與區塊鏈有關的環境中也是有用的，也許還不止於此。
當前，在 Bitcoin Core 中發生的常規驗證需要按順序遍歷區塊鏈（同時運行一些獨立於上下文的微小檢查）、向 UTXO 集添加輸出、隨後檢索（被花費的）輸出然後移除它們。通常 UTXO 集無法放進內存中，從而因為硬盤讀寫而進一步放慢速度。
SwiftSync 完全改變了這種模式，並且不會 改變安全假設。不再有數據庫檢索、內存使用量降低到近於零，而且所有驗證都可以並行完成。這就從可能的瓶頸清單中劃去了內存、硬盤讀寫和單線程性能。剩餘的瓶頸是 CPU 和帶寬，而且你在這兩樣上的條件越好，你驗證起來就越快。
本協議的無狀態性可能也使之非常適合內存受限的環境，比如使用專門的硬件（FPGA 和 ASIC）來驗證區塊鏈、構造零知識證據，或者僅僅為其它操作（比如 Schnorr 簽名的批量驗證）釋放更多內存。你也可以輕鬆將驗證負擔分散到多臺設備中。
我們需要進一步的基準測試來確定 SwiftSync 到底有多快，但非常初步的概念驗證（還沒實現任何並行化）已經顯示出令人驚訝的 5.28 倍加速。
協議概述
對於鏈上的每一個輸出，我們需要一個提示來表明這個輸出到區塊鏈頂端是否依然未被花費，但一個提示只需要一個比特（壓縮之後小於 100 MB）。
如果提示是不正確的，驗證就會失敗（這是一個 DoS 界面），這樣的提示應該來自一個可靠的來源（裡不然，你的全節點軟件的二進制文件） [1]。
我們將依賴於 “assumevalid” 以跳過特定的檢查。這並非必需的，但這樣可以得到一個更優雅、更節約帶寬的協議。assumeavlid 的具體後果、非 assumevalid 的版本以及 SwiftSync 跟 “assumeutxo” 的關係，我們會在後文解釋。
我們以順序獨立（完全可並行）的方式來處理所有的輸入和輸出。我們唯一要求的狀態是一個 32 字節場的哈希聚合值（不需要使用內存，也沒有硬盤的隨機讀寫）。本協議的行賄能隨著可用的 CPU 和帶寬而線性擴展。
對於每一個輸出：
- 如果提示表明該輸出到鏈頂端也不會被花費：
- 那就把它寫入 UTXO 集（也即僅追加 —— 我們不需要這些數據，直到 SwiftSync 完成，迴歸常規驗證模式）
- 反之：
- 哈希它的輸出點，然後添加到哈希聚合值中
對每一個輸入：
- 哈希它的輸出點（輸入本身會攜帶），然後從哈希聚合值中移除它
在我們完成 SwiftSync 的時候，哈希聚合值的數值應該是 0，從而證明我們寫入 UTXO 集中的 輸出都是未花費，而且其它輸出都只花費了一次（沒有重複花費）。
下文還有更多細節，不過本協議的核心就是如此了。
細節
關於哈希聚合值
我們所需的一切僅僅是，能夠知道集合 A（被花費的輸出）跟集合 B（輸入）是否一致，不論順序。這種獨立於順序的屬性保證了：在添加之前移除一個元素也不會造成問題，也即使之完全可以並行化。
在數學上，直接哈希原像，然後 加入/減去 這個結果（模運算）幾乎 就夠了 —— 我們還需要加入一個秘密值鹽，以保證數據不能從外部操縱（廣義的生日問題）。 [2]
例子
花費掉的輸出：outpoint_A、outpoint_B
輸入：outpoint_C、outpoint_D
如果 hash(outpoint_A||salt) + hash(outpoint_B||salt) - hash(outpoint_C||salt) - hash(outpoint_D||salt) == 0，那就證明，我們的花費掉的輸出的清單跟輸入的清單是完全一致的（即 (A==C && B==D) || (A==D && B==C)），而剩下的就會跟 UTXO 集完全一致。
關於 assumevalid
根據當前已經實現的狀態，assumevalid 僅僅用於跳過腳本驗證。它背後的安全論證是，用戶已經相信了自己的軟件是正確的，所以他們也可以信任一個關於一條鏈的有效性的聲明。除了腳本以外，還有別的東西可以跳過，但大部分剩餘的檢查都不昂貴，而且/或者 難以移除，可能這就是留下它們的原因。如果我們稍微擴大 assumevalid 的用法，我們可以顯著減少驗證輸入所需的數據量。請看。
UTXO 集中的一個完整條目包含以下數據：
- 輸出點
- 輸出腳本
- Coinbase 標籤
- 區塊高度
- 數額
簡單情形
沒有 assumevalid 的時候，若要檢查輸入，所有這些數據都必須可用。在 assumevalid 版本的 SwiftSync 中，我們只使用輸出點（即上面這個清單中的（1））。這是很方便的，因為這個數據在每一個輸入的內部就有。省略（2）是很容易理解的 —— 反正在 assumevalid 中，腳本是不檢查的 —— 但其餘數據呢？
跳過（3） coinbase 標籤意味著我們不再能夠檢查一個從 coinbase 中創建的輸出是否早於允許花費的時間就被花掉了 —— 這些輸出本質上都有一個暗含的長達 100 個區塊的相對時間鎖。為了檢查這樣的相對時間鎖，我們也需要知道（4）區塊高度。類似地，交易中的 nsequence 字段也可以用來啟用（我們不會檢查的）相對時間鎖。
區塊高度這個數據也會間接幫助一些僅在並行驗證情形中才會遇到的事情：它保證了輸出會在被花費之前（而非之後）創建。注意，僅有區塊高度可能是不夠的，因為一個輸出可能會在被創建的同一個區塊中就被花掉。稍後我們會詳細討論這個問題，因為我們需要在非 assumevalid 版本中明確地處理這個問題。
另一個我們會在稍後處理的問題是 BIP30，當前，它需要完全訪問 UTXO 集。UTXO 集是完全可尋址的，但對 assumevalid 版本來說，應該不需要它。
在 assumevalid 模式下包含跳過上述檢查，應該是完全沒有爭議的，因為沒有一項檢查的重要性比得上腳本檢查（也就是 assumevalid 已經跳過的檢查） [3]。
更難的情形
跳過（5）數額檢查是可以辯論的，因為沒有數額檢查，你就不再能主動檢查通脹 bug。幸運的是，這是有解決辦法的 —— 我們可以將來自 UTXO 集的數額加總起來，然後檢查它有沒有超過總的貨幣發行量。注意，這也應該包含 OP_RETURN 輸出的數額。
這種辦法的侷限性之一是，沒有能夠計算出礦工 沒有 取走的資金的簡單辦法，因為我們隱式地跳過了手續計算。理論上來說，如果某人拿走了這些未被申領的資金，我們也不會注意到。從稀缺性的角度看，這並不比 assumevalid 的最壞情形 —— 通過一個無效的腳本，不正當地取得了資金 —— 更糟。此外，可以這樣拿走的資金的數量是非常少的 [4]。
最後，還有一種後果無疑 是個缺點，但不是太大。因為在檢查一個區塊的輸入的時候，我們沒有完整的前序輸出數據，所以我們也無法生成所謂的 “undo” 數據 —— 在區塊鏈重組事件中回滾區塊鏈所需的數據。這就意味著，我們無法回滾得比 assumevalid SwiftSync 點更深。以剪枝（pruned）模式運行 Bitcoin Core 會有完全一樣的侷限性。有一種實用的處理辦法：對最新的 X 個區塊，不實用 assumevalid SwiftSync ；X 只需要取你認為不太可能發生重組的深度即可。
簡而言之，通過依賴於一個最小延申的 assumevalid 定義、接受（跟剪枝節點一樣）遇到深度重組就必須重新同步的要求，我們就可以得到一個非常乾淨、簡單的協議。當然，在非 assumevalid 模式下驗證的能力也是很重要的，所以我們接下來就討論這部分。
不用 assumevalid
不用 assumevalid 的 SwiftSync 可以完全驗證所有的共識規則，但我們需要一些額外的步驟。除了加入和減去哈希後的輸出點，我們還需要將檢查一個輸入所需的所有東西（見上文的 5 數據列表）都包含在哈希值中。
添加這些到哈希聚合值中是容易的，因為在需要添加的時刻（處理輸出的時候），這些數據我們都有。但想要移除它們的時候（處理輸入的時候），我們只有輸出點 —— 所以沒只好重新下載缺失的數據。相比於常規的完全驗證，可能需要額外 15% 的數據，這裡面還有大量可以高效編碼的空間 [5]。
我們可以讓用戶在外部下載這些數據，但也可以考慮讓點對點網絡來提供這些數據。可能幸運的是，大部分的節點都已經擁有這些數據了 —— 前面提到過允許節點重組區塊鏈的 undo 數據就是我們需要的 [6]。注意，我們還需要給我們提供提示的同一個來源給我們提供 undo 數據的一個哈希值，以保證隨機對等節點不會給我們無效的數據、導致驗證失敗 [7]。
因為我們現在會檢查數額，所以對 UTXO 集的單獨通脹檢查就不需要了，但我們確實會遇上一些（上一節已經提及的）新問題。
區塊內的交易順序
因為並行化在 SwiftSync 中是默認選項，我們並不必然知道輸出會不會在被創建之前就被花掉，比如說，輸出可能在同一個區塊中被創建然後被花掉（在所有其它情形中，檢查區塊高度就足夠了）。
雖然這個問題的存在是不可否認的，但如果你深入思考，會覺得它的後果沒什麼大不了的 [8]。但我們確實可以解決這個問題，而且只要我們處理了它，就會更容易討論安全問題。
最直接也最實用的方式是，使用一種逐區塊的緩存。你可以認為它是一種逐區塊的微型 UTXO 集（技術上來說，它只需要能夠證明順序的數據就足夠了），是按順序構造出來的。我們只需要在一個輸入的（創生）區塊高度與當前區塊相同的時候，檢索輸入就可以了，雖然可能有理由做更多 [9]。這會讓協議不那麼優雅，因為我們加回了一些狀態，而且做了順序搜索，但這會侷限在單區塊的環境下 —— 我們依然可以完全自由地並行處理所有區塊。
如果我們想堅持無緩存策略、完全避免搜索和順序檢查，還有更多的選擇 [10]，但對於運行在常規硬件上的全節點來說，區塊緩存應該已經夠好了。
BIP30 驗證
為了讓 SwiftSync 等價於常規的完全驗證，它也需要滿足 BIP30 的要求，即使它不能訪問 UTXO 集。BIP30 是在 2012 年 3 月才激活的，但它的執行範圍是從創世區塊開始到 BIP34 激活的時刻（區塊高度 227931，2013 年 3 月）。BIP30 通過無效化產生已經存在的未花費輸出的區塊來防止重複輸出。理論上，BIP30 並不能完全防止重複交易（BIP34 可以，但也帶來了一些沒有解決的問題），因為創建、花費然後重新創建依然是可以的，雖然在現實中這從沒發生過。
在 BIP30 激活以前，出現過兩個重複輸出，相同的 coinbase 交易輸出被創建了兩次。第二個輸出就覆蓋了第一個，實際上讓第一個輸出無法花費。這些實例在 BIP30 中被當作例外。更多信息可以在這裡找到。
SwiftSync 沒有 UTXO 集的概念，所以我們無法跟蹤一個輸出是否已經存在。幸運的是，可以設計出另一種方法，給我們相同的結果。我們可以直接保存一個包含了每一筆 coinbase 交易 id 的換從，從而檢查它們的唯一性。這隻需要佔用 227931 * 32 字節 ~= 7MB 的內存，而且我們還可以進一步優化它，甚至讓它變成無狀態的，只要我們想 [11]。它不僅等價於 BIP30，也是我們今天的做法的更快速的直接替換。
還有一種理論上存在的場景，就是一次狂暴的重組，回滾到 2013 年，導致 BIP34 永不激活、BIP30 永久持續。與其解決這個若有若無的情形，更實用的解決方案是（如果發生了這種事，就）直接返回非 SwiftSync 驗證。
SwiftSync 與 assumeutxo
Assumeutxo 和 SwiftSync 是完全正交的。Assumeutxo 從一個假設是正確的 UTXO 集開始，然後在後臺執行驗證，從而驗證這個假設的真偽。後面這部分就是我們可以使用 SwiftSync 的地方。
assumeutxo 所導致的一種複雜性是，它需要兩套狀態：一套是從 assumeutxo 點到當前的鏈頂端，一套是從創世區塊到 assumeutxo 點。一旦後臺的驗證完成，我們將再次回到一套狀態。因為 SwiftSync 是近於無狀態的，所以在後臺驗證中使用它可能會讓事情變得更簡單。
一個重要但非常容易解決的差別在於，雖然我們不再需要構造出一個 UTXO 集，我們依然需要驗證作為起點的 assumeutxo 的 UTXO 集，跟可以從 SwiftSync 提示中導出的 UTXO 集是完全一樣的。我們可以通過相同的哈希聚合技巧來實現這一點。
每次我們處理一個被提示會留在 UTXO 集中的輸出時，我們就將它加入哈希聚合值中（這將是完整 UTXO 集數據的一個哈希值，不僅僅是輸出點）。類似地，我們哈希 assumeutxo 的 UTXO 集中的每一個條目，然後從哈希聚合值中移除它們。如果兩者都是正確的，那麼我們最終也會得到一個 0。
令人滿意的是，此時如果使用的是非 assumevalid 版本的 SwiftSync，甚至不再需要每個輸出一比特的提示，因為不論一個輸出最終會不會存在於 UTXO 集中，你添加到哈希聚合值中的數據都將是完全一樣的（即 輸出 - 輸入 - UTXO == 0）。這樣的優雅讓我陶醉。
致謝
驗證過程的優化是人們經年累月討論的一個話題。許多人都走在我前面，探索了相關的想法。Cory Fields 的 UHS 可能是與本協議最相似的，而它本身又是 Bram Cohen 的 bitfields 想法的改進。Tadge Dryja 的 utreexo 也在狀態縮減、並行化以及跟緩存相關的初始化區塊同步（IBD）提示方面與本協議有重疊。
感謝 theStack 和 0xb10c 給出最初的基準測試和統計數字。我也想感謝積極開發 IBD 優化的 Bitcoin Core 開發者們 —— davidgumberg、l0rinc 以及 andrewtoth —— 以及給出了有益討論的人，以及提供了反饋的其他許多人。
腳註
1. 在接收提示上，我們還有沒有別的選擇？依賴於存放在你的軟件中的數值的一個缺點是，軟件可能是幾個月前發行的。而在利用完其中的提示之後，驗證過程又會顯著慢下來。另一種可能是從一個受信任的第三方處接收[非 assumevalid 的 SwiftSync]提示。在最壞情形下，這個第三方會說謊，你的驗證最終會失敗。重要的是，你不會因此認為無效的鏈是有效的。兩種方法混用也是可以做到的（即是在你的節點離線的時候也能追上），但這樣的話我們就要加入額外一些邏輯，以從 SwiftSync 會話之間的集合中移除 UTXO。最後，提示也可以承諾到鏈上，但這就需要一次軟分叉。 ↩
2. MuHash 和 XOR 堆疊跟使用秘密鹽的哈希聚合值孰優孰劣？MuHash是可行的替代，如果我們希望移除秘密鹽的要求的話（比如說，為了允許客戶端之間的狀態比較），但這對我們的應用場景來說似乎太過了。XOR 是不夠的，因為元素出現兩次之後就會相互抵消（一次是輸入，一次是輸出）。可以通過額外的檢查來彌補這一點，但那就跟我們這裡提出的方法非常接近了。 ↩
3. 如果我們忽略時間鎖和交易排序，在最壞的情況下會發生什麼事？未被強制執行的時間鎖或者失序的交易僅僅意味著一些資金會過早被花費，或者交易的順序出現了一些奇怪的事情（先是資金從一個還不存在的輸出中花掉了，也就是製造了通脹，後來這個不存在的輸出又被創建了出來，從而抵消了通脹）—— 如果這個通脹最終沒有被糾正，SwiftSync 驗證就會失敗。最重要的是，這不會被 assumevalid 的最壞情況 —— 無效的腳本花掉了一個輸出 —— 更壞。 ↩
4. 如果我們 確實 想對礦工沒有取走的資金作一個更加精確的檢查呢？理論上，我們可以給礦工沒有取走全部應得手續費的區塊的所有輸入添加數額提示，並提供哪些輸出在這些區塊中被花掉的提示（譯者注：原文如此，疑應為 “哪些輸出在這些區塊中被創建”）。對於這些具體的實例，我們可以在哈希值中包含數額。礦工可以通過總是留下 1 聰來發動騷擾。要求承諾總手續費或者不允許遺留手續費的軟分叉會是更徹底的解決方案。也就是說，考慮到最差的情形也不會比 assumevalid 已經假設的情形更差，所以接受這種侷限性是完全合理的。在乎的人應該選擇禁用 assumevalid。 ↩
5. 我們如何為非 assumevalid 版本壓縮所需的數據？這裡有大量的高效壓縮和去重機會。有許多重複的模式（例如，標準交易）、我們知道其原像的哈希值（例如，P2SH）以及頻繁出現的輸出（例如，近期區塊高度出現的絕大部分輸入）。來自 BIP337 的部分觀念沒準也可以重用。 ↩
6. 通過 P2P 網絡來提供 undo 數據的辦法還能對別的用途有用嗎？它讓剪枝節點可以回滾得比自己的修建點更深，只要他們保存了被修剪的 undo 數據的一個哈希值（很遺憾，assumevalid 的 SwiftSync 無法做到這一點），並且對等節點願意為他們分叉出去的區塊提供 udo 數據。因為 undo 數據基本上讓你可以脫離環境、完全地驗證區塊，像 “PoW 欺詐證明”（通過選擇性驗證分叉區塊的低帶寬區塊鏈驗證）這樣的協議也可以從中受益。 ↩
7. 還有別的辦法，可以提供 undo 數據而不帶來 DoS 問題嗎？最直接的辦法就是哈希這一數據、放到每一個區塊裡面，然後使之成為共識的一部分；但軟分叉是很難的。還有一種理論上的點對點方法是，在對等節點之間比較 undo 數據的狀態，如果有差異，就找出哪個對等節點在說謊（只要至少一個對等節點是誠實的，就可以奏效），但這也相對複雜。這樣做的一個例子（雖然是在不同的環境下）可以在這裡找到。 ↩
8. 假設我們不檢查區塊內的交易排序，攻擊者可以如何利用這一點？接受一條交易排序不正確的鏈不會對資金所有權和通脹產生 任何 影響。唯一的問題是，常規的完全驗證節點會拒絕這種替代性排序，所以它會成為一個硬分叉。然而，這種分叉不會發生，除非這個替代性排序真的出現在了最多工作量證明的鏈上。要設想一個攻擊者可以實質上利用這一點的情形是非常困難的。這裡作一個嘗試：（1）顛覆當前具有最多工作量證明的鏈，挖出一個使用這種替代性排序的區塊；（2）讓受害者執行一路執行 SwiftSync 驗證到鏈頂端，從而讓他們相信你的替代性排序（也許要先汙染他們用的軟件？）；（3）讓受害者在這個 “錯誤” 鏈上跟你購買比特幣。最終，“好” 的鏈會再次打敗你的 “壞” 的鏈。總而言之，看起來這種攻擊並不會比你直接賣出你的比特幣，然後重組掉這些交易更高效。即使攻擊者的目標僅僅是製造混亂，也無法說出大規模重組與這種攻擊在效果上有什麼區別。 ↩
9. 也許我們可以通過緩存而不是重新下載每一個 UTXO 來節約帶寬？是的，而且也有很好的處理方法，但確實會增加更多複雜性，並讓整個驗證過程更連續（難以並行）。你可以讓緩存覆蓋多個區塊，甚至可以進一步，提供哪些輸出將被花費的提示。這這能會讓一些瓶頸又回來，比如帶寬。 ↩
10. 如果我們沒有緩存，該如何檢查區塊內的排序？我們可以向 UTXO 集加入一個額外的元素：一個正統的交易編號（輸出編號也可以，而且出於其它原因很有吸引力，但其精確性超出了我們的需要）。現在，加入一個輸出要被花費了，而其創生區塊高度與當前高度相同，那麼我們就檢查交易編號，以驗證它在我們正在求值的交易 之前 就創建出來了。這種方法的缺點在於，它會增大完整的 UTXO 集的大小（每個條目要增加 2 字節）。更有趣的方法可能是為每一個我們知道其會在同一個區塊中被花費的輸出加入額外的提示。具體來說，我們提示將要花掉它的交易的編號（必須大於包含它作為輸出的交易的交易編號 —— 我們只需要編碼兩者的差值就可以了），然後將這個提示包含在哈希值中。現在，當我們遇到一個其創生高度與當前高度匹配的輸入時，我們就在哈希中包含其交易編號，然後將它從聚合值中移除。不幸的是，一個輸出在創生的同一個區塊中就被花掉的情形非常常見，所以必要的提示數據可能會增加很多。雖然緩存是一種更顯然的辦法，比較它與無緩存替代方案的基準應該還是有趣的。 ↩
11. BIP30 是另一個要用到緩存的地方 —— 該如何優化呢？我們可以通過截斷 txid 來減少數據集。一般來說，我們會擔心碰撞，但我們可以通過預先計算具體的、需要保留的比特來保證沒有碰撞，從而保證在這條具體的鏈上有一個無碰撞的結果（使用一個鹽來重新哈希也可以做到，但計算起來更慢）。從信息理論上來說，這可以讓每個 txid 降低到 18 比特，雖然這在計算上是做不到的。實際來說，我們應該可以做到 4 字節內（甚至 3 字節以內）。這樣，數據體積就減少到小於 1 MB。我們也可以更進一步，拋棄這個狀態，在哈希聚合值的幫助下搜索。為此，我們要提供一個截斷後哈希值的有序列表。我們要遍歷這個列表，檢查每一個元素都比上一個元素更大（從而證明唯一性），同時將它們添加到哈希聚合值中。當我們在區塊中遇到它們的時候，再從哈希聚合值中移除它們（如果最後我們會得到 0，就證明了集合等價）。 ↩
