MPT 下崗？智能合約區塊鏈的優化
發表於 2023-10-19 08:26 作者： LXDAO
作者：KJ， LXDAO
背景和動機
在开始講對 MPT 的改進之前，我們先談一談進行這項研究的背景。
本人在讀博並且做公鏈設計。這條公鏈除了核心的共識升級：有用的工作量證明以外，另一個重要的任務是實現兼容 ETH 的智能合約系統。我們目前已經實現了一個基於 Python 字節碼的虛擬機，並整合到一條區塊鏈的合約系統中，並且非常意外的做到了以太坊 RPC 兼容。我們使用 Python 構建了一個符合 ERC20 標准的智能合約進行測試，很自然的我們要在合約執行的下層，實現能承載千萬級別用戶的 KV 數據機構（類似於 Solidity 中的 Mapping，用來存儲每個账號下的代幣數量，這樣的账號可能有上億個）。
接下來，公鏈設計的工作內容很自然的觸達到了 MPT、Trie 等概念。我們參考了以太坊的設計，三棵樹，Trie，MPT 等。在此，我要感謝北大肖老師的區塊鏈視頻，（16-ETH-狀態樹_嗶哩嗶哩_bilibili 第 16 講），讓我們快速的理解了這一部分知識。
視頻鏈接：https://www.bilibili.com/video/BV1Vt411X7JF?t=11.0
發現瓶頸
幸運的是，在我們准備動手實現智能合約調用 MPT 之前，我們突發奇想的在 AWS 的服務器上運行了一個簡單的 MPT 樹 Benchmark 程序。當嘗試用 Trie 和 MPT 插入一億 KV 的數據量後，我們非常驚訝的得到了結果：MPT 樹的性能居然是這樣的低。
運行以下代碼，我們觀察到：向 Rocksdb 插入一千萬 KV 鍵值對，Trie 需要幾分鐘，MPT 需要幾小時。當我們把測試數據數量級增加到 1 億，MPT 插入程序需要運行數天。這意味着，區塊鏈使用 MPT 數據結構運行智能合約的時候，速度也會受到較大限制。
實驗證明，使用 MPT 數據結構帶來的开銷，既會拖慢智能合約的執行速度，也會降低區塊鏈節點的同步速度（即使在帶寬非常充足的時候，從其他節點下載數據並且重建節點，也必須花費數天時間）。然而，由於以太坊的數據結構設計很難被修改，即使我們用“更快”的編程語言重寫或者優化，如果不做底層數據結構上的更新，區塊鏈將很難突破性能的限制。
test_mpt_write.py
import mptimport rocksdbclass DBWrap:def __init__(self, db) -> None:self.db = dbdef __setitem__(self, key, value):self.db.put(key, value)def __getitem__(self, key):return self.db.get(key)conn = rocksdb.DB('mpt.db', rocksdb.Options(create_if_missing=True))storage = DBWrap(conn)root_hash = conn.get(b'root_hash')print('Prev root_hash', root_hash)trie = mpt.MerklePatriciaTrie(storage, root_hash)start = 0while True:for i in range(start, start+10000):k = str(i).zfill(32).encode('utf8')trie.update(k, k)root_hash = trie.root_hash()print(f"root_hash hex {root_hash.hex()}")print(start)start += 10000if start > 10000000:break
test_mpt_write.py
import rocksdbconn = rocksdb.DB('trie.db', rocksdb.Options(create_if_missing=True))start = 0while True:print(start)for i in range(start, start+10000):k = str(i).zfill(32).encode('utf8')conn.put(k, k)start += 10000if start > 10000000:break
鏈接：https://gist.github.com/kernel1983/f746c1470376e422a8efe3ee6782901d
還記得我在剛學寫代碼的時候，老師們告訴我們一個基本原理，程序 = 算法 + 數據結構。如果我們限定數據結構，那么即使在算法上拼命優化（這往往需要數年的學術努力，很多情況下幾乎無法再提高），也很難突破當前數據結構的性能限制。那么非常學術的改進方案，尋找性能更好的 MPT 代替算法，研究可能會花費數年時間。作爲在這個方向努力的前輩，Verkle Tree 使用多項式的方式優化區塊鏈數據結構，我們則會嘗試一些更加獨特和簡單的思路。
我們採用第一性原理思考方式，能不能不用 MPT ？如果我們可以繞开 MPT 直接在 Trie 之上實現智能合約，就不再有 MPT 帶來的开銷 （馬一龍的第一性原理，一個不存在的東西是不會有性能开銷的）。
作爲代價，我們新設計的方案可能無法與現有 MPT 直接兼容，但是由於不修改以太坊 RPC 接口，所以可以重用很多現有以太坊基礎設施：比如 Etherjs 和 MetaMask。繞开 MPT 屬於內部數據結構優化，這是對區塊鏈性能的自由探索。
前置知識
Rocksdb 和 Trie
Trie 字典樹，是一種大學課本中提及高級的樹數據結構，在肖老師的視頻中 MPT 就是基於 Trie 字典樹構建的。我們可以認爲 Trie 的實現環境是在內存當中。
但是我們工程上，是無法直接使用 Trie 直接實現產品，因爲我們還需要讓數據在硬盤上持久化，這一步驟又有很多工程上的優化，所以我們一般基於 Rocksdb 來實現 MPT 樹。
Rocksdb 是 FB 基於 leveldb 的开源 Fork，底層使用了 LSMT（參考論文 The log-structured merge-tree）。從抽象的角度，我們可以把 Rocksdb 認爲是一個優化過的，可以持久化的字典樹。
Rocksdb 的基本使用非常簡單，主要用到的是 Get put 和按前綴 Iterate 查詢三種基本操作。
狀態機
狀態機是經常被人們用來建模區塊鏈的工具，它非常簡單：給一個原有狀態加上一個輸入, 得到一個新狀態。
以太坊的全局狀態可以理解成狀態機的狀態，比如在區塊 1 的時候, 所有智能合約的 KV 值就是一個全局狀態，一個區塊中所有的交易，被 EVM 執行，可以理解成狀態機的輸入，比如一個 Mint 合約調用，使得一個用戶的 Balance 和合約的 Total 變量在區塊 2 變爲 1000。
一個容易被人們忽視的狀態機概念，叫狀態轉換函數，它定義了輸入的規則，當輸入不合理的時候，會拒絕輸入信息。比如，我們嘗試轉账給別人一個負數金額的時候，這樣的交易就不會被執行 (當然，有 Bug 的智能合約可以接受這樣的交易，在 ETH 中，狀態轉換函數可以通過圖靈完備的語言自定義)。
MPT 介紹
有可能你已經聽說過以太坊三棵樹，分別叫交易樹，狀態樹，和回執樹。他們都是 MPT 樹，全稱是 Merkle Patricia Tries 。其中，狀態樹可能是最適合使用 MPT 數據結構的用例。具體可以參考肖老師的視頻講解。
MPT 樹基於 Trie 數據結構之上，能夠像默克爾樹一樣把所有狀態數據，計算成一個根哈希，放到以太坊的區塊頭。以太坊區塊頭裏有三棵 MPT 樹的根哈希，我們通常叫做三棵樹。
區塊頭中是否可以不放置全局狀態的樹根呢？可以的，比特幣區塊中放置的就是交易，並把交易的默克爾根放進了區塊頭（使用了默克爾樹，但沒有使用 MPT）。但是比特幣沒有以太那樣的智能合約，也沒有全局狀態的概念。以太坊在最初設計帶智能合約的區塊鏈的時候，拋棄了比特幣的 1 M 區塊設計和 UTXO，選擇 MPT 數據結構和账戶模型，以及用 Gas 來解決停機問題，滿足了智能合約運行中對於全局狀態的需求。
那么，以太坊中使用 MPT 的目標是什么呢?
1.通過區塊頭中的默克爾根，查找區塊鏈對應的狀態。
2.節省重復數據佔用的空間。
3.可以通過根哈希驗證狀態是否正確。
其中第 1 點是剛需，執行 EVM 的同時需要讀取各種狀態，如果使用類似比特幣 UTXO 的設計模式，需要回溯很多區塊才能得到某個用戶的账戶余額狀態。使用 MPT 則很好的滿足需求。
第 2 點，MPT 節省空間，區塊鏈狀態可以看成是一個巨大的字典。每個區塊，僅僅有一小部分 Key 被更新，大部分 Key 還是保持原有值。使用 MPT 樹可以僅僅更新需要更新的鍵值，無需在每個區塊將未改動的狀態復制一遍。
第 3 點，MPT 的優勢是，使用根哈希訪問到的狀態鍵值，已經完成了全局狀態的驗證。這也是在寫入 MPT 樹時候，比較耗時的主要原因。如果不使用 MPT，節點依然可以在同步區塊期間，驗證數據的一致性。
不使用 MPT 完成第 1 和第 2 點，我們就可以繞开 MPT 的开銷。所以我們要基於 Trie（可以理解爲 Rocksdb）設計一個方案，存儲區塊鏈的狀態數據。
設計
我們主要設計一個基於 Trie 的方案來存儲鏈上狀態，根據第一性原理，不存在 MPT 數據結構，就沒有運行 MPT 所需要的系統开銷。只要基於 Trie 的智能合約系統可以被實現並正確運行，就意味着優化已經完成。實踐中我們可以把 Rocksdb 看成是一個 Trie，更簡單的理解，就是一個高性能的 KV 數據庫。
使用 [globalstate 爲前綴_合約地址_變量名_區塊高度_區塊哈希] 作爲 KV 數據庫的鍵值，比如以下格式。其中 0x1 是合約地址，Total 是變量名，1 是區塊高度，ABC1234 是區塊哈希值（後面會省略）
globalstate_0x1_total_1_abc1234
在以太坊 Solidity 中，變量可以定義爲 Memory、Storage 和 Calldata，我們主要關注 Storage 類型，因爲它會被存儲在全局狀態中。除了簡單變量外，我們還考慮 Mapping，因爲區塊鏈上用戶的數量級是全球級別的，所以會出現超大的 KV mapping。除此以外，Array 等數據類型，我們會當成簡單數據結構處理，直接 Json 後存入 Rocksdb。我們在編碼的時候，應當很自然的估算 KV 數據結構中的 Value 數據數量級，以選擇適當的存儲方式。
合約存儲狀態變量
如果不使用 MPT，我們如何實現 MPT 的第一點和第二點設計目標呢？
假設我們在 ERC20 合約中有一個變量 Total，這個變量只有在 Token 數量總量增加（Mint）或者減少（Burn）的時候才會改變，但是用戶 A 向用戶 B 轉账（Transfer）的時候 Total 的值保持不變。
爲了簡單，假設合約地址是 0x1，在區塊高度爲 1 的時候，合約的 Owner 進行了一次 Mint 2000，在高度爲 2－8 區塊上，用戶進行了多次轉账，現在區塊高度是 9。
此時，我們只需要向數據庫查詢以 [globalstate_0x1_total_] 前綴的 Key。雖然我們的當前最新區塊是 9，但是由於 Total 變量在 2-8 區塊都沒有發生變化，所以以上查詢的第一個結果將是 [globalstate_0x1_total_1] 的值，所以我們找到了 Total 變量的最新值，在區塊 1 的時候發生過改變的 Total 變量。
此時，新區塊又產生，假設用戶在第 9 區塊和第 11 區塊又做了兩次 Mint。這裏我們發現 Rocksdb 的一個特性，如果我們有以下 Key
globalstate_0x1_total_1 : 2000
globalstate_0x1_total_9 : 4000
globalstate_0x1_total_11 : 6000
那么搜索的第一個結果總是區塊 1，而不是最新區塊 11。因爲我們暫時沒有從 Rocksdb 文檔中找到改變搜索結果順序的參數，所以我們用了一個小技巧，使用一個較大的數字比如 100 去減區塊高度（實際會大得多），並且補零，所以最新區塊會排在搜索結果最前面。
globalstate_0x1_total_089 : 6000
globalstate_0x1_total_091 : 4000
globalstate_0x1_total_099 : 2000
存儲 Mapping 類型
前面我們提到了，Mapping 數據結構的 Key 量級有可能是海量的，所以我們不可能將 Mapping 中上萬個 Key 的字典 Json 成一個字符串，否則添加刪除 Key，或者修改 Value 的代價會是非常可怕的。
假設用戶的地址是 0x2，我們稍稍擴展一下之前的存儲 Key 格式：
[globalstate_0x1_[balance_0x2]_2] : 2000
這裏之前的 [變量名]，擴展成了[變量名 + Mapping 字典的 Key]
以上數據代表用戶 0x2 在區塊高度 2 的 Balance 余額是 2000，如果沒有更新的數據覆蓋當前的余額，那么用戶在區塊 2 的數據就代表着最新狀態。
globalstate_0x1_balance_0x2_098 : 2000
globalstate_0x1_total_0x1_099 : 2000
驗證區塊
和默克爾樹根一樣，MPT 樹根也代表着對全局狀態的一種驗證。只要我們可以保證區塊數據一致性，是否一定要用 MPT 並且把 Root 寫進區塊頭，是可以在設計上取舍的。
我們在區塊設計上做了一些改進，讓區塊頭包含了兩個 Body，一個是交易數據塊，另外一個是狀態更新數據塊。
交易數據塊包含所有交易的哈希，礦工或者節點可以某個區塊高度的全局狀態开始，按照交易數據塊中的給出的順序執行完所有交易，得到下一個區塊的全局狀態。如果交易量很大，執行又不太可能並行（因爲會打亂交易順序），所以如果要求全世界的節點都執行一遍所有交易，是比較費時間的。
爲此，我們設計了狀態更新數據塊，其中包括了運行完所有交易以後，被更新過的全局狀態鍵值。如果是一個落後很多區塊的節點，那么在選擇運行虛擬機執行所有交易以外，它也可以根據狀態更新 Body 的內容，直接向數據庫插入鍵值，以節約運算量，縮短同步時間。
當然，執行所有交易更新的鍵值，和狀態更新區塊包含的 Diff，必須完全一致，否則這個新區塊是不合法的。
假設全世界有 10000 個節點，當我們擲色子設定百分之一的概率去執行交易，大約 100 個節點會執行交塊交易，其他節點則信任接狀態更新數據塊的內容，那么這個區塊鏈系統中很多節點將能節省大量重復運算。
實現
在完成了之前的設計之後，我們馬上着手實現這一想法。
首先，我們將 Python VM 整合進了區塊鏈系統。這是一個由 Python 實現的 Python 虛擬機，目前它兼容 PY 3.10 的字節碼。我們希望智能合約可以使用 Python 的部分語法，比如我們只需要函數，並不希望开發者使用 Class，所以我們目前並沒有完全支持所有的 PY 字節碼。
關於編譯器，Solidity 需要开發專用的編譯器，將源代碼轉換成 EVM 字節碼。使用 Python 可以借助這個有三十年歷史的優秀基礎設施語言，輕松的將 Python 源碼轉換成 PY 字節碼，用戶幾乎感覺不到編譯時間。
我們的 VM 代碼倉庫如下，歡迎大家給我們提意見，修復潛在安全問題：
鏈接：https://github.com/EcoPoW/python_stf_vm
第二步，我們开發了一個 Python 版本的 ERC20，代碼一直在更新。不同於 Solidity，我們並沒有使用關鍵字來標識變量的存儲方式，所有的局部變量都在內存中，我們使用 _get 和 _put 全局函數來讀取和寫入狀態。
鏈接：https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py
感謝 Python 3 提供的 Annotation 功能，我們可以從 RPC 中把本來調用 EVM 的交易數據，轉換成 Python 可以接受的類型，比如 Uint256、Uint8 直接轉換成 Python int。函數輸出的值也可以自動轉換成 RPC 接受的 ABI 類型。
第三步，我們實現 _get 和 _put 函數，採用本文設計的方案來在區塊鏈運行過程中，存儲 Python VM 執行中讀取和寫入的區塊鏈狀態數據。狀態數據的讀取和寫入都會先經過內存，只有當交易成功執行，所有對狀態的修改才會被匯總成狀態更新數據塊，連同交易數據塊和經過共識算法區塊頭一起廣播到整個區塊鏈網絡當中。
鏈接：https://github.com/EcoPoW/BitPoW/blob/master/state.py
落地和改進
對於從提出問題，到設計，以及編碼實現，我們大約花了兩個月時間。
通過整個夏天的設計 + 實際的編碼，新的智能合約系統，僅僅使用字典樹 Trie 而不依賴 MPT 數據結構，已經可以落地運行（大家可以通過 Github clone 來嘗試本地運行測試節點）。繞過基於 MPT 的智能合約存儲，意味着在帶寬充分的條件下，一億 KV 大小的節點的同步時間，可以從好幾天，降低到幾分鐘。智能合約的執行效率也將變快，CPU 所消耗的計算量，會更多的用在執行字節碼，而不是構建默克爾樹所需要的哈希運算。我們很幸運，在工程實現智能合約的時候，沒有直接沿用“工業標准”的設計，而是先嘗試優化和減法，得到了一個“數據結構”正確的智能合約區塊鏈。因爲不同於 Web2 產品，我們比喻成一邊开汽車一邊換輪胎，Web3 區塊鏈更像是火箭發射。一個運行中的區塊鏈，是很難進行大結構改進的，所以我們只能改進“下一個”系統，在上线前做好充分准備。
目前，我們設計的 BitPoW 區塊鏈的 Testnet2 號測試網已經部署，大家都可以通過 RPC 使用 MetaMask 連接到這條區塊鏈上進行測試，嘗試基於 Python VM 的 ERC20 轉账。同時，我們還有很多工作尚未完成，我們仍然需要依靠社區來推動這一新型區塊鏈基礎設施。
我們歡迎大家來了解和實際上手測試這些新概念驅動的技術實現，包括對於移除 MPT 後的性能測試，對於新智能合約和新鏈的安全測試。
總結
至此，我們繞开了 MPT 設計了直接基於 Trie 的智能合約存儲方案。目前，我們在基於 Python vm 的區塊鏈上實現了這一改進，作爲可行性證明。從發現問題到提出方案，到從代碼實現，我們大約花了三個月時間，但是這次研究的更重要之處在於，我們在此之前和許多普通人一樣，從課堂學習到 MPT 知識後，並未進一步思考去改進它。解決方案並不復雜，但是需要實踐和行動。
解決方案並不復雜，但是需要實踐和行動。在實踐中積極思考，才能找到靈感，進一步的創新。
非常感謝 LXDAO 對本次研究的支持，也希望在社區中能認識更多對區塊鏈底層感興趣的朋友們。這個行業還非常早期，基礎設施遠未成熟。我們希望推動區塊鏈底層知識的普及，讓更多人可以一起參與到技術革新的最前沿。
標題：MPT 下崗？智能合約區塊鏈的優化
地址：https://www.coinsdeep.com/article/55979.html
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。
上一篇