當(dāng)前，區(qū)塊鏈技術(shù)大紅大紫，都說區(qū)塊鏈?zhǔn)枪_透明的，不可篡改的且不依賴信任節(jié)點(diǎn)的系統(tǒng)。

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

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

區(qū)塊鏈?zhǔn)怯行虻南蚯耙玫陌灰仔畔⒌膮^(qū)塊列表。每個(gè)挖礦節(jié)點(diǎn)將交易打包放到區(qū)塊中，然后分發(fā)到網(wǎng)絡(luò)中以達(dá)成共識，也就是說，達(dá)成共識的最小單元是區(qū)塊，而不是交易。其實(shí)如果需要做成交易鏈也是可以的，但是達(dá)成共識的次數(shù)就數(shù)量級的提升了，這樣區(qū)塊鏈的性能將會(huì)大打折扣。

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

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

比特幣中的區(qū)塊結(jié)構(gòu)是怎樣的？

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

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

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

什么是 Merkle Tree 和 Merkle Proof？

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

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

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

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

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

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

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

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

以太坊中的 merkle tree

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

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

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

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

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

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

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

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

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

Merkle Patricia tree

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

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

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

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

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

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

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

a.空節(jié)點(diǎn) (比如說當(dāng)一顆樹剛剛創(chuàng)建為空的時(shí)候)

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

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

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

舉個(gè)例子：

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

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

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

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

###更深入的 Merkle Patricia tree

更詳細(xì)的字段關(guān)系如下圖所示：

下面將通過代碼片段的形式，逐一驗(yàn)證各個(gè) trie的結(jié)構(gòu)（前提條件是先在本地搭建起以太坊私有鏈）。

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

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

運(yùn)行輸出得到的 Hash，也即 transactionsRoot為：

2.State Trie

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

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

運(yùn)行輸出得到 0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的余額，跟 eth.getBalance接口得到的結(jié)果是一致的。

3.storage trie

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

獲取到當(dāng)前最新塊的 stateRoot為 0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed。

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

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

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

文/來鑫

songjy