作者：KJ
親愛的LXDAO 的朋友們，大家好！
本文由LXDAO 專家小組成員KJ編寫，內容涉及到區塊鏈底層設計的許多知識，閱讀者如果有相關知識儲備，例如MPT（默克爾前綴樹），Trie（前綴樹或字典樹），配合以太坊EVM虛擬機知識，食用更佳。
閱讀本文可以更深刻的理解區塊鏈鏈上儲存的機制，以及優化手段。
背景和動機
在開始講對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 mpt
import rocksdb
class DBWrap:
def __init__(self, db) -> None:
self.db = db
def __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 = 0
while 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 += 10000
if start > 10000000:
break
test_mpt_write.py
import rocksdb
conn = rocksdb.DB(‘trie.db’, rocksdb.Options(create_if_missing=True))
start = 0
while True:
print(start)
for i in range(start, start+10000):
k = str(i).zfill(32).encode(‘utf8’)
conn.put(k, k)
start += 10000
if 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 點是剛需，執行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 對本次研究的支持，也希望社群中能認識更多對區塊鏈底層有興趣的朋友們。這個行業還非常早期，基礎設施遠未成熟。我們希望推動區塊鏈底層知識的普及，讓更多人可以一起參與到科技革新的最前線。
