原文標題：《以太坊核心開發者：mpt 十六叉樹將被替換》
撰文：guillaume ballet
編譯：灑脫喜
想象一下，你正在翻譯一本 5000 頁的書籍，作者一直打電話告訴你他對故事做了調整，這會影響到你已經翻譯過的頁面……而這可能會一直持續下去，這就是以太坊從當前使用的 mpt 十六叉樹轉變為二叉樹結構中遇到的一個類似困境。對此，以太坊核心開發者 guillaume ballet 提出了一種方案，可以在大約幾天的時間內，透過 3 個步驟完成這一轉換手術。
圖片來自：tuchong.com
對於該提案，以太坊聯合創始人 vitalik 評論稱：
「來自 ballet 的重要研究基礎，它會使以太坊無狀態變得友好，同時創造了一個機會，以大大簡化該協議。期待在未來的幾個月中，來自以太坊 1.x 開發人員更加出色的工作及成果。」
以下是譯文：
影響以太坊的眾多問題之一是賬戶和合約資料的儲存方式，以太坊目前選擇的結構稱為默克爾帕特里夏樹 (merkle patricia tree，或簡稱 mpt）。儘管從理論上講，它是很有意義的，但在實踐中，它帶來的問題要比其解決的問題要更多。多年來，核心開發人員一直在討論向二叉樹（binary tree）的轉換，在本文中，我將闡明我對這一問題的看法，然後給出一個解決它的方法。
提議的過程引入了一個過渡期，在此期間，兩種樹結構都會存在。這樣做的好處是，在轉換樹結構時，主鏈可以保持執行，並且還可以確保將所有帳戶轉換為二叉樹格式。
背景
目前，以太坊的賬戶是被儲存到一棵十六叉樹當中的。所謂十六叉，就表示一個節點有 16 個子節點，理論上這是很好的，因為這意味著你需要更少的「階段」來儲存你所有的資料。
例如，這就是以十六叉樹的形式表示鍵與值對（170，v）的過程。在十六進位制中，170 表示為 0xaa，因此你只需要兩層：其中之一用於第一個 a，另一層則用於第二個 a。
注意，這棵樹很淺，也很寬。然後將其與以下相同鍵與值對的二叉樹表示法進行比較。在二進位制中，170 表示為 10101010。
圖 2: 和圖 1 中相同的鍵值對，以二叉樹形式進行儲存。為了簡潔起見，不相關的子樹被表示為「…」
你可以看到，這棵樹要深得多，也窄得多。
在以太坊中，每個區塊都包含一個 stateroot 欄位，它是 mpt 根的雜湊值。總而言之，這個雜湊，是透過對根的 16 個子項的雜湊列表進行雜湊運算而獲得的。這些子雜湊列中的每一個，又依次是其子雜湊列表的雜湊，依此類推。
每次生成一個新區塊時，礦工都會更新帳戶樹並重新計算其根雜湊值。雜湊儲存在新區塊的 stateroot 欄位中，然後新區塊被密封。
問題就出現在這裡了：透過對所有節點進行雜湊運算來重新計算雜湊根花費的時間太長，因此，為了計算根節點，礦工將從資料庫中檢索同級雜湊（sibling hash）。儘管從資料庫中獲取所有子葉並對整棵樹進行雜湊運算所需的時間不多，但此操作仍然需要大量時間。這是因為必須要從資料庫中獲取每個雜湊。
在十六叉樹中，通常每個階段要獲取 15 個同級雜湊。在上面的示例中，這就是 30 個雜湊。
即使更深入，二叉樹每個階段也只需要一個同級雜湊。在上面的示例中，就只有 8 個雜湊！這就是為什麼在實踐當中，二叉樹實際上要更好的原因。
覆蓋轉化法
不幸的是，要將以太坊從十六叉樹切換到二叉樹，並不是一件容易的事。有很多資料需要轉換，並且執行更改需要花費超過 15 秒的區塊時間。
除此之外，想象一下，你正在翻譯一本 5000 頁的書籍，作者一直打電話告訴你他對故事做了調整，這會影響到你已經翻譯過的頁面……而這可能會一直持續下去。
這就是目前以太坊遇到的問題，因為使用者可以更新已轉換的地址，這意味著你必須重新開始轉換過程。
解決此問題的建議是設一個過渡期，在此期間，在十六叉樹的頂部放置一棵覆蓋二叉樹，它的作用是儲存狀態發生的所有更改，直到基樹轉換為二叉樹。
這種過渡會分成三步進行：
第 1 步-轉換
在這種方法中，確定在區塊高度 h2 處，區塊具有兩個 stateroots：一個用於「基礎」十六叉樹，一個用於「覆蓋」二叉樹。
十六叉樹被認為是隻讀的，因此對狀態的任何更新都將是對覆蓋樹的更新。
當一筆交易讀取或更新一個帳戶時，系統首先搜尋覆蓋樹。如果在那裡找不到帳戶，系統將在舊的十六叉樹中搜尋該值。
而在同時，十六叉樹正在後臺轉換。現在可以不用擔心插入，因為所有更改都儲存在頂部樹中。
第 2 步-基轉換
後臺轉換過程完成後，礦工將透過轉換結果替換隻讀的十六叉樹基礎根來宣佈他們已準備好進行切換。對狀態的讀寫操作與步驟 1 相同。
圖 5: 轉換的第二個階段，區塊頭將十六叉樹基礎根替換為其二叉樹轉換基礎根，以向網路傳送訊號，告知它們已準備就緒
當一個足夠大的序列區塊對轉換後的基礎根具有相同的值時，這意味著大多數礦工都完成了轉換，並對轉換後的樹的外觀達成了共識。接下開，就進入到合併過程。
第 3 步-合併兩顆樹
合併過程會逐漸進行：每次生成新區塊時，都會從疊加層中刪除 n 個鍵，然後將其重新插入到基礎樹中。該過程將持續進行，直到從疊加層中刪除所有鍵為止。在此階段，覆蓋狀態根將從區塊頭中刪除。
除此之外，如果交易執行寫入覆蓋樹中找到的鍵，則該鍵將從覆蓋樹中刪除，並直接寫入到基礎樹。
下一步
我們已經建立了一個 初步的原型，以便估計完成轉換所需的時間。我們相信，整個過程可以在合理的時間內（大約幾天）完成。隨著演算法的改進，我將釋出更多的細節。
致謝
這項提議得益於 alexey akhunov，vitalik buterin，anna george，sina mahmoodi，tomasz stanczak 以及 martin h. swende 提供的寶貴意見。
相關討論
來源連結：medium.com
