每個基本塊不會改變控制流(如沒有JUMP)。因此,我們可以確定,一旦我們開始執行一個基本塊,要么它將運行到最后,要么它將耗盡Gas。我們假定這方案會更為高效,但仍未測試其替代方案來作對比。
為了提高效率,相鄰的基本塊將會合并直到每個基本塊的最小長度為128字節(這是一個可配置的參數)。然后將它們插入trie樹中,使用其第一個字節的索引作為鍵。客戶端最終將此trie樹的根存儲在記錄該合約的新創建的賬戶中。如下所示,代碼trie樹實際上成為了狀態trie樹的子樹(類似于存儲trie樹)。
默克爾化的合約代碼成為了狀態trie樹的子樹。為了簡化圖表,我使用了二進制trie樹(而不是以太坊中使用的MPT樹)。路徑和鍵值也不太準確。
讓我們通過提交調用合約的交易來進行測試。礦工執行交易并標記在執行過程中觸及的塊(在本例中為塊1和塊3)。當發布區塊時,礦工會納入合約賬戶狀態證明和觸及代碼塊的turbo證明[9]。
觸及塊與驗證代碼根所需的哈希作為turbo證明進行傳輸
收到該區塊后,無狀態客戶端可以驗證合約是否為狀態的一部分以及是否有著正確的屬性:余額,nonce值,狀態根和代碼根。然后,它可以根據代碼根去驗證代碼塊及其鍵值。上述信息足以讓客戶端從這些塊中重構出部分字節碼并讓其它塊留空。值得注意的是,根據我們采用的塊分割算法,客戶端知道每個塊(第一個除外)都以JUMPDEST開始,因而可以安全地執行跳轉。
從trubo證明,我們可以重構字節碼。給定交易所不需要的塊則留空。
實驗
為了測試,我們編寫了一個原型[10],其通過Geth的RPC端口抓取主網區塊及初始狀態。然后,原型在這些區塊中運行交易,每當遇到新合約時,把合約分割成塊并對觸及塊進行標記。當區塊中的所有交易被處理后,原型會為這些塊生成turbo證明。我們在更新后的初始狀態(僅僅把合約代碼替換為由證明計算得到的重構代碼)下重新運行這些交易。為了檢查正確定,我們比較了使用的Gas量以及區塊的布隆過濾器。對最近的50個區塊進行處理,我們可以看到代碼量的減少在40%到60%之間。
警告:這些數據雖然看上去不錯,但請記住,我們需要數萬個區塊的數據來得出有說服力的結論,而且原型正處于初始階段,因此很可能有Bug。
何去何從
你可能仍記得,每個塊的最小長度是一個可配置的參數(上文把其設為128字節)。修改該參數會對塊見證的大小有著兩種相反影響。例如減少至32字節,讓塊的粒度更細,從而減少了需要發送的代碼總量。但同時也增加了trie樹的深度,最終導致證明所需的哈希數增大。下一步將會對最小塊大小的設定進行更徹底的分析,看看是否有一個最為節約空間的值。不管最小塊大小的值,從十六進制trie樹切換為二進制 trie 樹會將證明所需的哈希值減少為原來的1/4(見這里[11]),從而進一步減小塊見證的大小。
對于該原型,我們選擇將代碼分割為一個個基本塊,但也存在著其它各種各樣的分割算法,有些更為簡單,有些更為復雜。最簡單的方法是把代碼分割為固定大小的塊(如每32個字節為一個塊)。目前,該方案的唯一問題圍繞在 PUSH 數據和 JUMPDEST 分析之上。
此文由 中國比特幣官網 編輯,未經允許不得轉載!:首頁 > 比特幣新聞 » 引介 | EVM 字節碼的默克爾化