當前，區(qū)塊鏈技術大紅大紫，都說區(qū)塊鏈是公開透明的，不可篡改的且不依賴信任節(jié)點的系統(tǒng)。

那么區(qū)塊鏈的數(shù)據(jù)是如何存儲的？區(qū)塊鏈如何在沒有中心信任節(jié)點的情況下，快速證明數(shù)據(jù)是可靠正確的？典型的智能合約中的數(shù)據(jù)在區(qū)塊鏈上如何存取？ 來鑫通過給出代碼例子，用最通俗的語言，來闡釋了這些的問題。

區(qū)塊鏈為什么叫區(qū)塊鏈而不叫交易鏈？

區(qū)塊鏈是有序的向前引用的包含交易信息的區(qū)塊列表。每個挖礦節(jié)點將交易打包放到區(qū)塊中，然后分發(fā)到網(wǎng)絡中以達成共識，也就是說，達成共識的最小單元是區(qū)塊，而不是交易。其實如果需要做成交易鏈也是可以的，但是達成共識的次數(shù)就數(shù)量級的提升了，這樣區(qū)塊鏈的性能將會大打折扣。

區(qū)塊鏈節(jié)點中的數(shù)據(jù)都存在哪里？

在持久化方面，區(qū)塊鏈數(shù)據(jù)可以直接存儲在一個扁平的文件中，也可以存儲在簡單的數(shù)據(jù)庫系統(tǒng)中，比特幣和以太坊都區(qū)塊鏈數(shù)據(jù)存儲在 google的 LevelDb中。

比特幣中的區(qū)塊結構是怎樣的？

Version: 用于區(qū)分軟件版本號Previous Block Hash：是指向前一個區(qū)塊頭的 hash。在比特幣中，區(qū)塊頭的 hash一般都是臨時算出，并沒有包含在本區(qū)塊頭或者區(qū)塊中，但在持久化的時候可以作為索引存儲以提高性能

Nonce、Difficulty Target和 Timestamp : 用在 pow共識算法中。

Merkle Root： 是區(qū)塊中所有交易的指紋，merkle tree的樹根。交易在區(qū)塊鏈節(jié)點之間傳播，所有節(jié)點都按相同的算法（merkle tree）將交易組合起來，如此可以判斷交易是否完全一致,此外也用于輕量錢包中快速驗證一個交易是否存在于一個區(qū)塊中。

什么是 Merkle Tree 和 Merkle Proof？

如上圖，merkle Tree是一顆平衡樹，樹根也就是 Merkle Root存在區(qū)塊頭中。樹的構建過程是遞歸地的計算 Hash的過程，如：先是 Hash交易 a得到 Ha，Hash交易 b得到 Hb，再 Hash前兩個 Hash（也就是 Ha和 Hb）得到 Hab，其他節(jié)點也是同理遞歸，最終得到 Merkle Root。

Merkle tree在區(qū)塊鏈中有兩個作用：

1.僅僅看 merkle root就可以知道區(qū)塊中的所有交易是不是一樣的

2.對于輕量節(jié)點來說（不存儲所有的交易信息，只同步區(qū)塊頭）提供了快速驗證一個交易是否存在交易中的方法。

merkle proof從某處出發(fā)向上遍歷，算出 merkle Root的所需要經(jīng)過的路徑節(jié)點。在上圖的例子中，如果輕量錢包要驗證 Txb（紅色方框）是否已經(jīng)包含在區(qū)塊中，可以向全量節(jié)點請求 merkle Proof，用于證明 Txb的存在，過程為：

1.全量節(jié)點只要返回黃色部分的節(jié)點信息（Ha與 Hcd）

2.輕量節(jié)點執(zhí)行計算 Hash(Txb)=Hb à Hash(Ha + Hb)=Hab à Hash(Hab + Hcd)=Habcd，計算出來的 merkleRoot(也就是 Habcd)跟已知區(qū)塊頭中的 merkleRoot比較，如果一樣則認為交易確實已經(jīng)入塊。

在上圖的區(qū)塊中，僅僅存在少量的區(qū)塊。如果區(qū)塊所包含的交易很多，merkle proof僅僅需要帶 log2(N)個節(jié)點，此時 merkle proof的優(yōu)勢就會變得非常明顯。

以太坊中的 merkle tree

在比特幣中，系統(tǒng)底層不維護每個賬戶的余額，只有 UTXO（Unspent Transaction Outputs）。賬戶之間的轉(zhuǎn)賬通過交易完成，確切地說，比特幣用戶將 UTXO作為交易的輸入，可以花掉一個或者多個 UTXO。

一個 UTXO像一張現(xiàn)金紙幣，要么不使用，要么全部使用，而不能只花一部分。舉個例子來說，一個用戶有一個價值 1比特幣的 UTXO，如果他想轉(zhuǎn)賬 0.5給某人，那他可以創(chuàng)建一個交易，以這個價值 1比特幣的 UTXO為輸入，另外產(chǎn)生 0.5比特幣的 OTXO作為這個交易的輸出（找零給自己）。

比特幣這個公開底層系統(tǒng)本身不單獨維護每個賬戶的余額，不過比特幣錢包可以記錄每個用戶所擁有的 UTXO，這樣計算出用戶的余額。

以太坊相比比特幣，額外引入了賬號狀態(tài)數(shù)據(jù)，比如 nonce、余額 balance和合約數(shù)據(jù)，這些是區(qū)塊鏈的關鍵數(shù)據(jù)，具有以下特性：

隨著交易的入塊需要不斷高效地更新，所有的這些數(shù)據(jù)在不同節(jié)點之間能夠高效地驗證是一致的，狀態(tài)數(shù)據(jù)不斷更新的過程中，歷史版本的數(shù)據(jù)數(shù)據(jù)需要保留。

系統(tǒng)中的每個節(jié)點執(zhí)行完相同區(qū)塊和交易后，那么這些節(jié)點中對應的所有賬戶數(shù)據(jù)都是一樣的，賬戶列表相同，賬戶對應的余額等數(shù)據(jù)也相同?？偟膩碚f，這些賬戶數(shù)據(jù)就像狀態(tài)機的狀態(tài)，每個節(jié)點執(zhí)行相同區(qū)塊后，達到的狀態(tài)應該是完全一致的。但是，這個狀態(tài)并不是直接寫到區(qū)塊里面，因為這些數(shù)據(jù)都是可以由區(qū)塊和交易重新產(chǎn)生的，如果寫到區(qū)塊里面會增加區(qū)塊的大小，加重區(qū)塊同步的負擔。

如上所示，區(qū)塊頭中保存了三個 merkle tree的 root:

tansaction root: 跟比特幣中的 Merkle Root作用相同，相當于區(qū)塊中交易的指紋，用于快速驗 證交易是否相同以及證明某個交易的存在。

state root: 這顆樹是賬戶狀態(tài)（余額和 nonce等）存放的地方，除此之外，還保存著 storage root，也就是合約數(shù)據(jù)保存的地方。receipts root:區(qū)塊中合約相關的交易輸出的事件。

Merkle Patricia tree

在 Transaction Root中，用類似比特幣的二進制 merkle tree是能夠解決問題的，因為它更適用于處理隊列數(shù)據(jù)，一旦建好就不再修改。但是對于 state tree，情況就復雜多了，本質(zhì)上來說，狀態(tài)數(shù)據(jù)更像一個 map，包含著賬號和賬號狀態(tài)的映射關系。除此之外，state tree還需要經(jīng)常更新，經(jīng)常插入或者刪除，這樣重新計算 Root的性能就顯得尤其重要。

Trie是一種字典樹，用于存儲文本字符，并利用了單詞之間共享前綴的特點，所以也叫做前綴樹。Trie樹在有些時候是比較浪費空間的，如下所示，即使這顆樹只有兩個詞，如果這兩個詞很長，那么這顆樹的節(jié)點也會變得非常多，無論是對于存儲還是對于 cpu來說都是不可接受的。如下所示：

相比 Trie樹，Patricia Trie將那些公共的的路徑壓縮以節(jié)省空間和提高效率，如下所示：

以太坊中的 Merkle Patricia trie，顧名思義，它是 Patricia trie和 Merkle Tree的結合，即具有 merkle tree的特性，也具有 Patricia Trie的特征：

1.密碼學安全，每個節(jié)點都都是按 hash引用，hash用來在 LevelDb中找對應的存儲數(shù)據(jù)；

2.像 Patricia trie樹一樣，這些可以根據(jù) Path來找對應的節(jié)點以找到 value；

3.引入了多種節(jié)點類型：

a.空節(jié)點 (比如說當一顆樹剛剛創(chuàng)建為空的時候)

b.葉子節(jié)點，最普通的 [key, value]

c.擴展節(jié)點，跟葉子節(jié)點類似，不過值變成了指向別的節(jié)點的 hash,[key, hash]

d.分支節(jié)點，是一個長度為 17的列表，前 16元素為可能的十六進制字符，最后一個元素為 value(如果這是 path的終點的話)

舉個例子：

在上圖中的 trie包含了 4對 key value，需要注意的是，key是按照 16進制來顯示的，也就是 a7占用一個字節(jié)，11占用一個字節(jié)等等

1.第一層的 Node是擴展節(jié)點，4個 Key都有公有的前綴 a7,next node指向一個分支節(jié)點

2.第二層是一個分支節(jié)點，由于 key轉(zhuǎn)換成了十六進制，每個 branch最多有 16個分支。下標也作為 path的一部分用于 path查找。比如說下標為 1的元素中指向最左邊的葉子節(jié)點（key-end為 1355）,到葉子節(jié)點就完成了 key搜索：擴展節(jié)點中 a7 + 分支節(jié)點下標 1 + 葉子節(jié)點 1355 = a711355

3.葉子節(jié)點和擴展節(jié)點的區(qū)分。正如上面提到的，葉子節(jié)點和擴展節(jié)點都是兩個字段的節(jié)點，也就是 [key，value]，存儲中沒有專門字段用來標識類型。為了區(qū)分這兩種節(jié)點類型并節(jié)省空間，在 key中加入了 4bits（1 nibble）的 flags的前綴，用 flags的倒數(shù)第二低的位指示是葉子節(jié)點還是擴展節(jié)點。此外，加入了 4bits之后，key的長度還有可能不是偶數(shù)個 nibble（存儲中只能按字節(jié)存儲），為此，如果 key是奇數(shù)個 nibble，在 flags nibble之后再添加一個空的 nibble，并且用 flags的最低位表示是否有添加，詳見上圖左下角。

###更深入的 Merkle Patricia tree

更詳細的字段關系如下圖所示：

下面將通過代碼片段的形式，逐一驗證各個 trie的結構（前提條件是先在本地搭建起以太坊私有鏈）。

1.Transaction trie如下所示，在本地環(huán)境發(fā)送交易并使之入塊，查看區(qū)塊的交易列表，TransactionsRoot和 RawTransaction：

在 trie包中寫單測函數(shù)，key為交易在區(qū)塊中的 index，RLP編碼，value為簽名過的原始交易 RawTransaction：

運行輸出得到的 Hash，也即 transactionsRoot為：

2.State Trie

獲取最新的區(qū)塊的 stateRoot，以及打印出賬號 0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的余額

在 state包中寫單測函數(shù)，state trie的數(shù)據(jù)以 trie節(jié)點 hash為 key存在 leveldb中，所以整個 state trie的入口 key就是 stateRoot。state tree中存儲數(shù)據(jù)的 path為 account的 hash，value為 RLP編碼過的結構體數(shù)據(jù)。為了簡單起見和節(jié)省篇幅，這里省去了錯誤檢查。

運行輸出得到 0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的余額，跟 eth.getBalance接口得到的結果是一致的。

3.storage trie

如下合約，為了簡單起見，合約中省去了構造函數(shù)等不相關的內(nèi)容，部署后地址為：

獲取到當前最新塊的 stateRoot為 0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed。

在 state包中寫單測函數(shù)，首先獲以 0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed創(chuàng)建 trie，取獲取合約賬號 0x9ea9b9eeac924fd784b064dabf174a55113c4064的 storageRoot,之后再以這個 storageRoot創(chuàng)建 trie。在取合約內(nèi)部數(shù)據(jù)時，key為 hash過的 32字節(jié) index，value為 RLP編碼過的值。

運行輸出以下數(shù)據(jù) storedUint為 2018，跟合約里的數(shù)據(jù)是一致的。值得注意的是 storedString的數(shù)據(jù)后面多了一個十六進制的 26(十進制為 38)，是字符串長度 (19)的兩倍，更多的細節(jié)請參見 http://solidity.readthedocs.io/en/latest/miscellaneous.html#layout-of-state-variables-in-storage。

同時，更復雜的數(shù)據(jù)結構如變長數(shù)組、map等規(guī)則會更加復雜，同時這里也忽略了一些字段打包存儲等細節(jié)，但是都圍繞著 storageTrie，基本原理沒有改變。

文/來鑫

songjy