感謝 Guillaume Ballet 和 Tanish Jasoria 的回饋，以及感謝 Stateless Implementors Call 參與者就此主題進行的先前討論。

在本文中，我們深入探討狀態樹原像生成主題，包括：

• 解釋足夠的背景來理解該主題適合協議演進的位置。
• 需要對 EIP-7612 和 EIP-7748 進行高層解釋才能正確理解該問題。
• 為原像提出潛在的文件格式，並分析更複雜的格式是否值得。
• 提供一個新的原像工具，使用非存檔 reth 來產生和驗證原像文件，並產生本文中使用的數據，以便可以重現。

如果您知道為什麼需要為未來的樹轉換產生原像，請跳過上下文部分。

情境

路線圖的Verge部分提議用新樹取代目前的 Merkle Patricia Trie (MPT)，新樹在實現無狀態性和進一步 SNARKifying L1 方面更加有效。

當今的主要樹候選是 Verkle 樹 ( EIP-6800 ) 和二叉樹 ( EIP-7864 )。如果您想了解有關這種二分法的更多信息，請閱讀EIP-7864 討論主題。本文的主題與該決定無關，因此您可以假設任何未來的道路。

由於使用了新樹，我們需要一個策略將現有資料從 MPT 移至新樹。今天提出的策略是使用覆蓋樹（ EIP-7612 + EIP-7748 ）轉換數據，我們稍後會進行探討。

假設我們想將帳戶的資料（nonce、balance、code hash）從 MPT 移至新樹。 MPT 中的樹鍵是keccack(address) ，但在新樹中，它是new_key(address) ，其中new_key不一定是keccak 。 EL 用戶端必須能夠存取樹中每個鍵的底層原像（即，在本例中為address ）。如果他們只有keccack(address)就不可能計算new_key(address) 。這同樣適用於帳戶狀態嘗試。

簡而言之，網路中每個將經歷從 MPT 到新目標樹的狀態轉換的節點都應該能夠解析帳戶和儲存樹的每個 MPT 金鑰原像。

EL 用戶端不儲存樹密鑰原像嗎？

不幸的是，沒有。根據 EL 用戶端的當前架構和資料庫設計，這些原像可能是根據現有資料計算出來的，但這僅適用於少數客戶端。

樹密鑰原像和客戶端資料庫之間關係的一些範例：

• Geth 有一個 flatdb，可以比使用樹更快存取狀態。此資料庫中的鍵是帳戶的雜湊值或帳戶雜湊和儲存槽哈希的串聯，即基於哈希的鍵。使用雜湊版本的金鑰對於同步來說是有意義的，並且從來沒有真正的動機來證明保存原像的額外儲存是合理的。
• Erigon 和 Reth 也有一個 flatdb，但是該資料庫中的鍵是未散列的樹鍵，這對於解決這個問題非常方便。
• Nethermind 還沒有 flatdb，所以它依賴高效地訪問樹來進行狀態訪問，但他們計劃很快推出（密鑰散列）flatdb。

這意味著，除非您是 Erigon 或 Reth 節點，否則您沒有樹鍵的實際原像。據ethernodes.org稱，非 Erigon+Reth 節點佔網路的 80% 以上，這意味著大多數網路都存在這個原像問題。即使對於 Erigon 或 Reth 節點，能夠獲取原像也並不意味著他們現在有有效的方法來解決它們。為了更好地理解這一點，讓我們更深入地探討原因。

原像在樹轉換中如何使用？

了解覆蓋樹和狀態轉換 EIP 如何協同工作可以更好地回答這個問題。您可以閱讀 EIP，但這裡有一個壓縮摘要，可以繼續進行原像討論。

EIP-7612 概述

注意：此 EIP 引用了 Verkle，但該想法與目標樹無關，因此它也適用於二元樹。

EIP-7612 解釋如何將新樹引入協定：

• MPT 在分叉區塊處變為唯讀（即凍結）。
• 建立一棵新的空樹（例如，Verkle 或 Binary）。
• 區塊執行產生的狀態更新僅寫入新樹。
• 副作用是，僅使用樹讀取狀態意味著讀取新樹，如果未找到條目，則檢查 MPT。

總之，它是一個兩級（即覆蓋）樹，其中基礎樹（MPT）被凍結，而頂部樹（Verkle 或 Binary）從頭開始，接收寫入。關於最後一條，EL 用戶端有一個 flatdb 來存取狀態，所以並不一定意味著您必須進行雙樹查找。

EIP-7748 概述

現在我們了解了 EIP-7612，接下來就是 EIP-7748 發揮作用的時候了：

• 在定義的區塊時間戳記（ CONVERSION_START_TIMESTAMP ）處，轉換過程開始。請注意，EIP-7612 活化和CONVERSION_START_TIMESTAMP之間必須有足夠的時間，這樣我們才能保證 MPT 被凍結（即，鏈已完成，因此任何重組都無法改變這一事實）
• 在下一個區塊中，在執行交易之前：
  • 確定性地從 MPT 中取得CONVERSION_STRIDE樹條目。
    • 樹條目的概念在 EIP（即命名轉換單元）中定義更精確——我們在這裡稍微簡化了一下。
    • CONVERSION_STRIDE 值仍有待確定，因為它是The Block執行狀態轉換開銷和完整轉換持續時間之間的權衡。正確的值取決於哪個是目標樹，因為 Verkle 比 Binary 具有更昂貴的重新散列。
  • 如果它不是一個過時的值，我們會將其複製到頂部樹中 - 由於 EIP-7612 已被激活，區塊執行可能已經為這個 MPT 鍵寫入了一個新值，該值不能被覆蓋。
• 繼續執行上述操作，直到我們完成所有 MPT 鍵的遍歷。

狀態轉換步驟發生在交易執行之前的設計決策是有益的，因為 EL 用戶端可以在下一個區塊到達之前執行狀態轉換步驟。

與原像檔案相關的這個過程的主要事實是我們對 MPT 條目進行迭代的順序。目前建議的順序是在 MPT 中進行完整的深度優先遍歷 (DFW)：在帳戶 trie 中執行 DFW，當到達葉子節點時，在帳戶儲存 trie 中執行 DFW，然後繼續遍歷帳戶嘗試。我們先遷移帳戶儲存槽，然後遷移帳戶的資料。

讓我們看一個例子來更好地理解它。假設CONVERSION_STRIDE為 5，且我們處於狀態轉換的第一個區塊。以下是我們在步行過程中可能會看到的 MPT 條目：

1. 帳戶 trie 金鑰0x000000abc...等於keccak(address_A) 。我們注意到address_A有一個帶有兩個儲存槽的儲存 trie，因此我們將 DFW 放入其中。
   1. 步驟＃1：帳戶address_A儲存樹的金鑰為0x0000131...等於keccack(storage_slot_A) ，這表示我們將address_A的storage_slot_A值遷移到新樹。
   2. 步驟＃2：帳戶address_A儲存樹的金鑰為0x0003012...等於keccack(storage_slot_B) ，這表示我們將address_A的storage_slot_B值遷移到新樹。
   3. 步驟#3：由於我們遷移了所有儲存槽，我們現在遷移address_A帳戶的nonce，balance和code。
2. 帳戶 trie 金鑰0x000000ffa...等於keccak(address_B) 。 address_B是 EOA
   1. 步驟＃4：沒有儲存槽，因此在儲存 trie 中沒有完成 DFW。我們遷移address_B帳戶的nonce、balance、以及code。
3. 帳戶 trie 金鑰0x000005630...等於keccak(address_C) 。我們注意到address_C有一個包含 1000 個儲存槽的儲存 trie，因此我們對其進行 DFW。
   1. 步驟＃5：帳戶address_C儲存樹的金鑰為0x0000021...等於keccack(storage_slot_A) ，這表示我們將address_C的storage_slot_A值遷移到新樹。

請注意以下幾點：

• 帳戶 trie 和潛在 trie 中的行走順序是基於哈希的，而不是地址或普通的儲存槽值。這是 trie 中 DFW 的結果，因為鍵是位址或儲存槽的雜湊值。
• storage_slot_A與address_A和address_C是不同的數字（例如分別為 10 和 24）。它們的意思是 DFW 在儲存嘗試中行走時發現的第一個儲存槽。如上文所述，儲存槽行走順序是基於哈希的，而不是「自然」排序，因此storage_slot_A可以大於storage_slot_B 。
• 上述觀點也是我們需要原像的原因——第一個鍵的值為0x000000abb ，您需要知道它對應於地址address_A以便您可以重新散列以確定新樹中哪個鍵。
• 最後遷移的條目只是account_C的第一個儲存槽，但我們仍然有 99 個剩餘的槽。由於我們已經達到 CONVERSION_STRIDE 限制，我們將在下一個區塊中繼續遷移這些內容！

您還可以在此處找到有關此 EIP 的討論，其中有一些視覺效果可以幫助補充此解釋。

回顧

以上內容可望澄清以下事實：

• 原像檔案必須包含凍結的 MPT 帳戶樹中所有現有的address_X 。
• 原像檔案必須包含所有凍結的 MPT 儲存嘗試中所有現有的storage_slot_X 。
• 由於 MPT 是凍結的，行走是確定性的，我們需要原像的順序是完全預先決定的。

原像文件

現在我們深入研究這個原像文件的不同維度：

• 分配
• 可驗證性
• 產生和編碼
• 用法

本文主要關註生成和編碼，但為了完整性我們也涉及其他維度。在我們到達生成部分之前，請假設該檔案是神奇地生成和編碼的。

分配

假設原像檔案以某種方式生成，那麼該檔案如何到達網路中的所有節點？在無狀態實施者呼籲 (SIC) 、L1 事件研討會和非正式討論中多次探討這個主題。

在與許多（但總體樣本較小）核心開發人員交談後，目前的共識是，期望客戶端透過多個潛在的 CDN 下載此文件可能是可以的。原像。

其他討論的選項包括：

• 具有協議內分發機制。
• 將所需的原像分發到每個區塊上。

這個主題非常有爭議，因為這些選項在複雜性、協議熱路徑所需頻寬和壓縮機方面有不同的權衡。儘管與許多核心開發人員進行了交談，但他們的代表性仍然不足以得出結論說 ACD 會得出相同的結論。

本文主要討論原像的生成和編碼格式，無論這個文件如何分發，我們都必須這樣做。

可驗證性

如上所述，完整節點將從可能不受信任的一方或被駭客入侵的供應鏈的地方接收此文件。如果檔案損壞或無效，則完整節點將在轉換過程的某個時刻被阻止。

透過執行所描述的樹遍歷、讀取預期的原像、計算 keccak 雜湊值並驗證它是否符合客戶端的期望，可以輕鬆驗證該檔案。驗證此文件後，無論何時開始轉換，都可以安全地使用它，並保證客戶端不會因解析原像而被阻塞——此保證對於轉換期間網路的穩定性至關重要。此驗證時間必須考慮到 EIP-7612 啟動和 EIP-7748 CONVERSION_START_TIMESTAMP時間戳之間的時間延遲*。

當然，驗證此文件的其他方法更快，但需要更多假設。例如，由於產生檔案的任何人都會獲得相同的輸出，因此客戶端團隊可以自行產生並對檔案的雜湊值/校驗和進行硬編碼。當檔案被下載/匯入時，驗證可以將檔案的雜湊值與硬編碼的雜湊值進行比較。

產生和編碼

現在我們知道文件必須包含哪些資訊以及以什麼順序存取這些訊息，我們可以考慮如何在文件中對這些數據進行編碼。理想情況下，我們希望編碼能夠滿足以下屬性：

• 針對預期的讀取模式進行最佳化：狀態轉換是主鏈運行時在背景進行的任務，因此讀取所需資訊應該是高效率的。
• 優化大小：如前所述，文件必須以某種方式分發。頻寬是一種寶貴的資源；用得少一點比較好。
• 複雜度低：此文件只會使用一次，因此簡單的編碼格式就好。透過創建新的複雜格式來重新發明輪子是沒有意義的，除非它們能夠提供特殊的好處，但同時需要更長的時間來確定和測試。

有一個非常簡單且明顯的候選編碼，可以按照我們之前探索的範例進行如下描述： [address_A][storage_slot_A][storage_slot_B][address_B][address_C][storage_slot_A]... 。我們按照預期的行走順序將原始原像直接連結在一起。

這種編碼有以下好處：

• 由於不需要前綴字節，因此編碼格式沒有任何開銷。儘管原像條目具有不同的大小（位址為20 位元組，儲存槽為32 位元組），但EL 用戶端可以知道接下來要讀取多少位元組，這取決於它們是否應該解析樹遍歷中的位址或儲存槽。
• EL 用戶端始終對檔案進行前向線性讀取，因此不存在隨機存取。即將到來的使用部分將對此進行擴展。

在深入研究這種編碼的效率之前，讓我們嘗試為主主網產生此檔案並了解其大小。為此， 我們創建了一個工具，使用同步的 reth 完整節點（即不一定存檔）來產生、驗證和執行稍後將介紹的其他分析。不久前，我們創建了一個geth 工具，但它需要從 genesis 同步節點並啟用--cache.preimages標誌。

我們可以透過執行preimages generate --datadir <...> --eip7748來建立原像檔案。以下是有關中階機器中產生的檔案的一些事實：

• 生成時間：~1 小時
• 未壓縮的檔案大小：42GiB
• 壓縮檔案大小（zstd）：36GiB

請注意，網路中運行 Reth（或潛在的 Erigon）節點的任何人都可以產生該文件，並且輸出始終相同，因為給定一個凍結的 MPT，原像就是固定的。

深入研究編碼效率

儘管編碼格式的編碼開銷為零，但壓縮和未壓縮大小之間的差異表明了壓縮機。讓我們來探究為什麼會出現這種情況。

我們可以將文件中的每個原像條目放在兩個儲存桶中：

• 解決原像
  • 重複資料刪除
    • 由於帳戶樹包含每個帳戶的唯一訊息，因此文件中每個[address_X]條目都是唯一的，因此不存在重複資料刪除的機會。
  • 壓縮：
    • 位址是哈希值，因此沒有機會壓縮它們。
• 儲存槽原像
  • 重複資料刪除
    • 它們在文件中重複，因為多個合約可以（並且確實）在儲存槽使用上重疊。例如，多個合約使用儲存槽 0、1 和 2。
    • 最大的重複儲存槽組是頂級槽，因為它們共享0x00000...前綴（例如，上一個項目中提到的那些）。
    • 當合約具有數組或哈希圖時，由於哈希將變數映射到儲存槽的性質，儲存槽在儲存槽空間中變得更加分散。
  • 壓縮
    • 儲存槽的壓縮機會各不相同。例如，帶有0x00000..前綴的儲存槽（即頂部合約變數）非常可壓縮，因為它們具有許多零位元組。其他儲存槽主要都是哈希的結果；它們並不是那麼可壓縮（但可「重複資料刪除」）。

總之，位址無法被重複資料刪除或壓縮，但儲存槽確實有機會被重複資料刪除/壓縮。然而，很難知道其影響會有多大以及是否值得。

若要進行更深入的分析，您可以執行preimage storage-slot-freq分析工具。我們先看一下輸出：

 Database block number: 21662206 Top 1000 storage slot 29 -byte prefix repetitions: 0000000000000000000000000000000000000000000000000000000000 : 57150357 ( 4.65 %) ~1580MiB (cumm 1580MiB)f3f7a9fe364faab93b216da50a3214154f22a0a2b415b23a84c8169e8b: 13671109 ( 1.11 %) ~378MiB (cumm 1958MiB)8a35acfbc15ff81a39ae7d344fd709f28e8600b4aa8c65c6b64bfe7fe3: 9429136 ( 0.77 %) ~260MiB (cumm 2219MiB)f652222313e28459528d920b65115c16c04f3efc82aaedc97be59f3f37: 8580073 ( 0.70 %) ~237MiB (cumm 2456MiB)405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3: 7750842 ( 0.63 %) ~214MiB (cumm 2671MiB)a66cc928b5edb82af9bd49922954155ab7b0942694bea4ce44661d9a87: 3545488 ( 0.29 %) ~98MiB (cumm 2769MiB)c2575a0e9e593c00f959f8c92f12db2869c3395a3b0502d05e2516446f: 2663837 ( 0.22 %) ~73MiB (cumm 2842MiB)...

（完整輸出較長，可在此處找到）

此程式計算具有相同 29 位元組前綴的儲存槽數量，例如前綴00000....00 ：

• 儲存槽位數量約5700萬個，佔總量的4.65%。
• 它映射到原像檔案大小的~1580MiB。
• cumm值是到目前行為止的大小總和。例如，前 3 個儲存槽原像前綴佔原像檔案的 2219MiB。

您可能想知道第二行、第三行和接下來行中的值是什麼：

• f3f7...是keccak(0x000000..08)
• 8a35...是keccak(0x000000..04)

這些前綴的出現是因為許多合約分別在儲存槽 8 和 4 中定義了陣列。這意味著原像檔案中的值是這些插槽號碼的雜湊值。由於數組中的項是從該基值連續的，因此這些“頂級數組”是原像文件中的頂部前綴。

選擇 29 個位元組作為前綴沒有什麼特別之處；這個想法是捕獲分組頂級變數和數組。對於雜湊圖，條目分佈在整個儲存槽空間中，因此重複資料刪除的機會較少。隨著合約變數中出現更多的“嵌套”，這種可能性會更低。這就是為什麼頂部前綴是頂級數組，所以它是有意義的。

如果您查看完整的輸出鏈接，前 1000 個前綴佔 ~4GiB，接近我們透過 zstd 獲得的 ~6GiB 壓縮。當然，尾巴很長，所以最佳尺寸可能更好。

嘗試將重複資料刪除作為檔案格式的一部分會增加檔案格式規範的複雜性。可以透過分離要保存在 RAM 中的前 N ​​個原像來保留準線性讀取。儘管如此，如果與簡單格式 + zstd 相比，為了減小尺寸而增加額外的複雜性，那麼這可能不值得。請記住，這是一次性下載。它可以在時段持續時間的非關鍵部分下載，甚至可以透過單獨的網路連結下載（但這需要手動操作）。

請注意，儘管 zstd 是一種使用廣泛的壓縮工具，但它為 EL 用戶端添加了新的依賴項。此外，可能需要額外的時間空間來解壓縮檔案（但可能有辦法避免這種情況）。無論如何，本文的主要目標是提供有關儲存槽尺寸尾部如何表現的真實測量，並引發有關該主題的更多討論。

用法

值得一提的是有關 EL 用戶端如何使用此文件的一些事實：

• 由於檔案是線性讀取的，因此保留一個遊標來指示在下一個區塊的開始處繼續讀取的位置很有用。
• 保留最後 X 個區塊的遊標位置清單有助於處理重組。如果發生重組，則很容易再次在檔案中尋找相應的位置。
• 當客戶端在插槽中大部分處於空閒狀態時，客戶端也可以在記憶體中預先載入下一個 X 區塊原像，從而避免在The Block熱路徑執行中產生額外的 IO。
• 如果將整個檔案保存在磁碟上太麻煩，您可以刪除鏈終止點之後的舊值。我們懷疑這是否值得增加額外的複雜性，但這是一個取決於 EL 客戶團隊的實作細節。

結論

本文在樹狀轉換協議演化的背景下探討了原像文件的上下文、問題和解決方案空間。這裡提出的想法都不是最終的，也不指望在 ACD 中達成明顯的共識。

主要目標是提供足夠深入的解釋，以提高社區中盡可能多的人的水平，不斷進步，並希望成為一種資源，以加快未來 ACD 關於這個主題的討論。