以太坊賬戶和合約數據的存儲方式一直是有待優化的難點,核心開發者 Guillaume Ballet 提出一種方案可以通過 3 個步驟完成向二叉樹格式轉換。

原文標題:《以太坊核心開發者: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。

以太坊協議簡化重要進展:三步將十六叉樹轉換爲二叉樹圖 1: 這是一棵十六叉 trie 樹示例,顯示了值「v」如何存儲在鍵 0xaa 處。此樹只有 2 字節長的鍵,並且只沿 0xaa 鍵的子樹被展開。爲了簡潔起見,不相關的子樹被替換爲「…」

注意,這棵樹很淺,也很寬。然後將其與以下相同鍵與值對的二叉樹表示法進行比較。在二進制中,170 表示爲 10101010。

以太坊協議簡化重要進展:三步將十六叉樹轉換爲二叉樹圖 2: 和圖 1 中相同的鍵值對,以二叉樹形式進行存儲。爲了簡潔起見,不相關的子樹被表示爲「…」

你可以看到,這棵樹要深得多,也窄得多。

在以太坊中,每個區塊都包含一個 stateRoot 字段,它是 MPT 根的哈希值。總而言之,這個哈希,是通過對根的 16 個子項的哈希列表進行哈希運算而獲得的。這些子哈希列中的每一個,又依次是其子哈希列表的哈希,依此類推。

每次生成一個新區塊時,礦工都會更新帳戶樹並重新計算其根哈希值。哈希存儲在新區塊的 stateRoot 字段中,然後新區塊被密封。

以太坊協議簡化重要進展:三步將十六叉樹轉換爲二叉樹圖 3 區塊頭的 state root 字段指向十六叉樹的根

問題就出現在這裏了:通過對所有節點進行哈希運算來重新計算哈希根花費的時間太長,因此,爲了計算根節點,礦工將從數據庫中檢索同級哈希(sibling hash)。儘管從數據庫中獲取所有子葉並對整棵樹進行哈希運算所需的時間不多,但此操作仍然需要大量時間。這是因爲必須要從數據庫中獲取每個哈希。

在十六叉樹中,通常每個階段要獲取 15 個同級哈希。在上面的示例中,這就是 30 個哈希。

即使更深入,二叉樹每個階段也只需要一個同級哈希。在上面的示例中,就只有 8 個哈希!這就是爲什麼在實踐當中,二叉樹實際上要更好的原因。

覆蓋轉化法

不幸的是,要將以太坊從十六叉樹切換到二叉樹,並不是一件容易的事。有很多數據需要轉換,並且執行更改需要花費超過 15 秒的區塊時間。

除此之外,想象一下,你正在翻譯一本 5000 頁的書籍,作者一直打電話告訴你他對故事做了調整,這會影響到你已經翻譯過的頁面……而這可能會一直持續下去。

這就是目前以太坊遇到的問題,因爲用戶可以更新已轉換的地址,這意味着你必須重新開始轉換過程。

解決此問題的建議是設一個過渡期,在此期間,在十六叉樹的頂部放置一棵覆蓋二叉樹,它的作用是保存狀態發生的所有更改,直到基樹轉換爲二叉樹。

這種過渡會分成三步進行:

第 1 步-轉換

在這種方法中,確定在區塊高度 H1 處,區塊具有兩個 stateRoots:一個用於「基礎」十六叉樹,一個用於「覆蓋」二叉樹。

以太坊協議簡化重要進展:三步將十六叉樹轉換爲二叉樹圖 4: 在轉換過程中,區塊具有 2 個狀態根(state Root):一個是傳統十六叉樹的只讀根,第二個是「覆蓋」二叉樹的根

十六叉樹被認爲是隻讀的,因此對狀態的任何更新都將是對覆蓋樹的更新。

當一筆交易讀取或更新一個帳戶時,系統首先搜索覆蓋樹。如果在那裏找不到帳戶,系統將在舊的十六叉樹中搜索該值。

而在同時,十六叉樹正在後臺轉換。現在可以不用擔心插入,因爲所有更改都存儲在頂部樹中。

第 2 步-基轉換

後臺轉換過程完成後,礦工將通過轉換結果替換隻讀的十六叉樹基礎根來宣佈他們已準備好進行切換。對狀態的讀寫操作與步驟 1 相同。

以太坊協議簡化重要進展:三步將十六叉樹轉換爲二叉樹圖 5: 轉換的第二個階段,區塊頭將十六叉樹基礎根替換爲其二叉樹轉換基礎根,以向網絡發送信號,告知它們已準備就緒

當一個足夠大的序列區塊對轉換後的基礎根具有相同的值時,這意味着大多數礦工都完成了轉換,並對轉換後的樹的外觀達成了共識。接下開,就進入到合併過程。

第 3 步-合併兩顆樹

合併過程會逐漸進行:每次生成新區塊時,都會從疊加層中刪除 n 個鍵,然後將其重新插入到基礎樹中。該過程將持續進行,直到從疊加層中刪除所有鍵爲止。在此階段,覆蓋狀態根將從區塊頭中刪除。

除此之外,如果交易執行寫入覆蓋樹中找到的鍵,則該鍵將從覆蓋樹中刪除,並直接寫入到基礎樹。

下一步

我們已經創建了一個 初步的原型,以便估計完成轉換所需的時間。我們相信,整個過程可以在合理的時間內(大約幾天)完成。隨着算法的改進,我將發佈更多的細節。

致謝

這項提議得益於 Alexey Akhunov,Vitalik Buterin,Anna George,Sina Mahmoodi,Tomasz Stanczak 以及 Martin H. Swende 提供的寶貴意見。

相關討論

來源鏈接:medium.com