本文從翻譯Vitalik Buterin 的一篇部落格開始介紹三個概念:
Merkle Tree: 默克爾樹
Merkle Patricia Tree: 默克爾帕特裡夏樹
Merkle Proofs: 默克爾證明
Merkle Tree是區塊鍊的一個基礎概念; 雖然可以通過構造包含所有交易的區塊頭的方式而不使用Merkle Tree, 但是如此笨重的設計注定讓區塊鍊無法走的更遠。感謝Merkle Tree讓以太坊可以運作在小型裝置上:智能手機,平闆電腦,甚至是slock.it即将生産的IOT裝置。
Merkle Tree到底是何方神聖?下面我們娓娓道來。
最簡單的Merkle Tree的形式是下圖展示的這種二叉樹。每個節點有兩個孩子, 葉子節點是資料的哈希值。
為什麼像上圖這樣設計呢? 因為這種結構可以提供一種叫Merkle Proofs的機制。
如上圖所示, Merkle Proofs包含三部分: 待驗證的塊資料的哈希(如圖中的9Dog:64), 根哈希(如圖中的6c0a), 驗證路徑(圖中黃色部分: 1FXq:18, ec20, 8f74)。
證明驗證過程:
9Dog:64和1Fxq:18 求哈希。
上步結果和ec20求哈希。
上步結果和8f74求哈希。
上步結果和根哈希(6c0a)比對是否一緻。
Merkle Proofs最早應用在比特币中, 如下圖所示比特币用所有交易的哈希構造了一顆Merkle Tree, 而Merkle Tree的根哈希寫在區塊頭中:
之是以這樣做的目的是因為這種設計可以支援SPV(簡單支付驗證): 為了驗證一筆交易無需下載下傳所有區塊和交易資訊, 隻需下載下傳80位元組的區塊頭就可以了。區塊頭包含5類資料:
前一個區塊頭的哈希
時間戳
挖礦難度
工作量證明nonce
上一段提到的所有交易組成的Merkle Tree的根哈希
如果用戶端想驗證一筆交易的可靠性, 隻需要按照上述的Merkle Proofs過程提供交易哈希和路徑, 再經過一系列哈希運算後比對根哈希就可以了。
這樣用戶端避免了下載下傳所有區塊資料進行交易驗證的噩夢, 我們稱這種用戶端為輕用戶端。
但是上述過程雖然可以驗證一筆交易的有效性, 但是它無法提供更強大的能力。 例如它無法提供驗證一個賬号目前持有多少資産? 雖然輕用戶端可以查詢多個節點并且通過某種協定保證了至少一個可信節點傳回的是真實的資訊來檢視賬戶餘額, 但是這樣做無疑更複雜。
是以為什麼不從一開始的資料結構上就解決這類問題呢? 以太坊設計正是為此而來。
以太坊中的區塊頭包含三顆Merkle Tree, 分别是: 交易樹, 單據樹, 狀态樹。
這種設計使得更複雜的輕用戶端協定成為可能, 甚至可以處理以下問題:
這筆交易已經包含在一個區塊了麼? (交易樹可以處理)
告訴我過去30天, 這個位址觸發的所有X事件的資訊(類似前一段火爆的ico的智能合約) (單據樹可以處理)
我的賬戶現在有多少餘額? (狀态樹可以處理)
這個賬戶是否存在? (狀态樹可以處理)
如果執行這筆交易會發生什麼? (比較複雜, 不說明了)
最上面我們介紹了二叉的Merkle Tree形式; 對于交易樹而言這種二叉的資料結構已經非常優秀了, 因為交易樹是一次性計算寫入後再也不會改變的,是以它對計算效率的要求并不高。
但是對于狀态樹情況就比較複雜了, 比如以太坊中的狀态是一個key-value的map。key是賬戶位址, values則包含了每個賬戶的balance,nonce,code 和 storage。下面是測試網絡上的狀态資料的描述:
不同于交易樹, 狀态樹因為交易的發生,賬戶的新增等動作會頻繁的進行插入,更新等操作。如何讓樹的插入和更新變得高效, 我們需要一種新的樹形資料結構,新的資料結果需要具備兩個特性:
樹的深度有限,哪怕收到攻擊使得樹的深度持續增加。否則樹深度過大會導緻計算緩慢而無法正常服務。
樹根哈希的計算僅依賴資料,不依賴更新的次序。無論對樹更新的次序如何根哈希的結果是确定的。
帕特裡夏樹是最符合我們需求的了, 一句話解釋什麼是帕特裡夏樹: 每個節點有16個孩子表示路徑, 分别代表了16進制的的16個字元。例如path為dog的16進制表示是: 6 4 6 15 6 7, 查找它的過程就是從根節點開始找到低6個孩子,然後進入下一層對應節點找到第4個孩子...依此類推。
上面是對Vitalik Buterin(以太坊創始人)部落格的翻譯, 整體内容比較淺顯沒有涉及具體的知識點, 算是介紹性的部落格。
下面列一些有價值參考資料:
<a href="https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/">原文</a>
<a href="https://github.com/ethereum/wiki/wiki/Patricia-Tree">帕特裡夏樹</a>
<a href="https://en.wikipedia.org/wiki/Radix_tree">字典樹</a>
<a href="https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/">MPT</a>