當前，區塊鏈技術大紅大紫，都說區塊鏈是公開透明的，不可篡改的且不依賴信任節點的系統。
那麼區塊鏈的數據是如何存儲的？區塊鏈如何在沒有中心信任節點的情況下，快速證明數據是可靠正確的？典型的智能合約中的數據在區塊鏈上如何存取？ 來鑫通過給出代碼例子，用最通俗的語言，來闡釋了這些的問題。
區塊鏈為什麼叫區塊鏈而不叫交易鏈？
區塊鏈是有序的向前引用的包含交易信息的區塊列表。每個挖礦節點將交易打包放到區塊中，然後分發到網絡中以達成共識，也就是說，達成共識的最小單元是區塊，而不是交易。其實如果需要做成交易鏈也是可以的，但是達成共識的次數就數量級的提升了，這樣區塊鏈的性能將會大打折扣。
區塊鏈節點中的數據都存在哪裡？
在持久化方面，區塊鏈數據可以直接存儲在一個扁平的文件中，也可以存儲在簡單的數據庫系統中，比特幣和以太坊都區塊鏈數據存儲在 google的 LevelDb中。
比特幣中的區塊結構是怎樣的？
Version: 用於區分軟件版本號Previous Block Hash：是指向前一個區塊頭的 hash。在比特幣中，區塊頭的 hash一般都是臨時算出，並沒有包含在本區塊頭或者區塊中，但在持久化的時候可以作為索引存儲以提高性能。
Nonce、Difficulty Target和 Timestamp : 用在 pow共識算法中。
Merkle Root： 是區塊中所有交易的指紋，merkle tree的樹根。交易在區塊鏈節點之間傳播，所有節點都按相同的算法（merkle tree）將交易組合起來，如此可以判斷交易是否完全一致,此外也用於輕量錢包中快速驗證一個交易是否存在於一個區塊中。
什麼是 Merkle Tree 和 Merkle Proof？
如上圖，merkle Tree是一顆平衡樹，樹根也就是 Merkle Root存在區塊頭中。樹的構建過程是遞歸地的計算 Hash的過程，如：先是 Hash交易 a得到 Ha，Hash交易 b得到 Hb，再 Hash前兩個 Hash（也就是 Ha和 Hb）得到 Hab，其他節點也是同理遞歸，最終得到 Merkle Root。
Merkle tree在區塊鏈中有兩個作用：
- 僅僅看 merkle root就可以知道區塊中的所有交易是不是一樣的
- 對於輕量節點來說（不存儲所有的交易信息，只同步區塊頭）提供了快速驗證一個交易是否存在交易中的方法。
merkle proof從某處出發向上遍歷，算出 merkle Root的所需要經過的路徑節點。在上圖的例子中，如果輕量錢包要驗證 Txb（紅色方框）是否已經包含在區塊中，可以向全量節點請求 merkle Proof，用於證明 Txb的存在，過程為：
- 全量節點只要返回黃色部分的節點信息（Ha與 Hcd）
- 輕量節點執行計算 Hash(Txb)=Hb à Hash(Ha + Hb)=Hab à Hash(Hab + Hcd)=Habcd，計算出來的 merkleRoot(也就是 Habcd)跟已知區塊頭中的 merkleRoot比較，如果一樣則認為交易確實已經入塊。
在上圖的區塊中，僅僅存在少量的區塊。如果區塊所包含的交易很多，merkle proof僅僅需要帶 log2(N)個節點，此時 merkle proof的優勢就會變得非常明顯。
以太坊中的 merkle tree
在比特幣中，系統底層不維護每個賬戶的餘額，只有 UTXO（Unspent Transaction Outputs）。賬戶之間的轉賬通過交易完成，確切地說，比特幣用戶將 UTXO作為交易的輸入，可以花掉一個或者多個 UTXO。
一個 UTXO像一張現金紙幣，要麼不使用，要麼全部使用，而不能只花一部分。舉個例子來說，一個用戶有一個價值 1比特幣的 UTXO，如果他想轉賬 0.5給某人，那他可以創建一個交易，以這個價值 1比特幣的 UTXO為輸入，另外產生 0.5比特幣的 OTXO作為這個交易的輸出（找零給自己）。
比特幣這個公開底層系統本身不單獨維護每個賬戶的餘額，不過比特幣錢包可以記錄每個用戶所擁有的 UTXO，這樣計算出用戶的餘額。
以太坊相比比特幣，額外引入了賬號狀態數據，比如 nonce、餘額 balance和合約數據，這些是區塊鏈的關鍵數據，具有以下特性：
隨著交易的入塊需要不斷高效地更新，所有的這些數據在不同節點之間能夠高效地驗證是一致的，狀態數據不斷更新的過程中，歷史版本的數據數據需要保留。
系統中的每個節點執行完相同區塊和交易後，那麼這些節點中對應的所有賬戶數據都是一樣的，賬戶列表相同，賬戶對應的餘額等數據也相同。總的來說，這些賬戶數據就像狀態機的狀態，每個節點執行相同區塊後，達到的狀態應該是完全一致的。但是，這個狀態並不是直接寫到區塊裡面，因為這些數據都是可以由區塊和交易重新產生的，如果寫到區塊裡面會增加區塊的大小，加重區塊同步的負擔。
如上所示，區塊頭中保存了三個 merkle tree的 root:
tansaction root: 跟比特幣中的 Merkle Root作用相同，相當於區塊中交易的指紋，用於快速驗 證交易是否相同以及證明某個交易的存在。
state root: 這顆樹是賬戶狀態（餘額和 nonce等）存放的地方，除此之外，還保存著 storage root，也就是合約數據保存的地方。receipts root:區塊中合約相關的交易輸出的事件。
Merkle Patricia tree
在 Transaction Root中，用類似比特幣的二進制 merkle tree是能夠解決問題的，因為它更適用於處理隊列數據，一旦建好就不再修改。但是對於 state tree，情況就複雜多了，本質上來說，狀態數據更像一個 map，包含著賬號和賬號狀態的映射關係。除此之外，state tree還需要經常更新，經常插入或者刪除，這樣重新計算 Root的性能就顯得尤其重要。
Trie是一種字典樹，用於存儲文本字符，並利用了單詞之間共享前綴的特點，所以也叫做前綴樹。Trie樹在有些時候是比較浪費空間的，如下所示，即使這顆樹只有兩個詞，如果這兩個詞很長，那麼這顆樹的節點也會變得非常多，無論是對於存儲還是對於 cpu來說都是不可接受的。如下所示：
相比 Trie樹，Patricia Trie將那些公共的的路徑壓縮以節省空間和提高效率，如下所示：
以太坊中的 Merkle Patricia trie，顧名思義，它是 Patricia trie和 Merkle Tree的結合，即具有 merkle tree的特性，也具有 Patricia Trie的特徵：
- 密碼學安全，每個節點都都是按 hash引用，hash用來在 LevelDb中找對應的存儲數據；
- 像 Patricia trie樹一樣，這些可以根據 Path來找對應的節點以找到 value；
- 引入了多種節點類型：
a.空節點 (比如說當一顆樹剛剛創建為空的時候)
b.葉子節點，最普通的 [key, value]
c.擴展節點，跟葉子節點類似，不過值變成了指向別的節點的 hash,[key, hash]
d.分支節點，是一個長度為 17的列表，前 16元素為可能的十六進制字符，最後一個元素為 value(如果這是 path的終點的話)
舉個例子：
在上圖中的 trie包含了 4對 key value，需要注意的是，key是按照 16進制來顯示的，也就是 a7佔用一個字節，11佔用一個字節等等
- 第一層的 Node是擴展節點，4個 Key都有公有的前綴 a7,next node指向一個分支節點
- 第二層是一個分支節點，由於 key轉換成了十六進制，每個 branch最多有 16個分支。下標也作為 path的一部分用於 path查找。比如說下標為 1的元素中指向最左邊的葉子節點（key-end為 1355）,到葉子節點就完成了 key搜索：擴展節點中 a7 + 分支節點下標 1 + 葉子節點 1355 = a711355
- 葉子節點和擴展節點的區分。正如上面提到的，葉子節點和擴展節點都是兩個字段的節點，也就是 [key，value]，存儲中沒有專門字段用來標識類型。為了區分這兩種節點類型並節省空間，在 key中加入了 4bits（1 nibble）的 flags的前綴，用 flags的倒數第二低的位指示是葉子節點還是擴展節點。此外，加入了 4bits之後，key的長度還有可能不是偶數個 nibble（存儲中只能按字節存儲），為此，如果 key是奇數個 nibble，在 flags nibble之後再添加一個空的 nibble，並且用 flags的最低位表示是否有添加，詳見上圖左下角。
###更深入的 Merkle Patricia tree
更詳細的字段關係如下圖所示：
下面將通過代碼片段的形式，逐一驗證各個 trie的結構（前提條件是先在本地搭建起以太坊私有鏈）。
1.Transaction trie如下所示，在本地環境發送交易並使之入塊，查看區塊的交易列表，TransactionsRoot和 RawTransaction：
> eth.getBlock(49).transactions
["0xdf648e4ce9bed9d3b0b35d969056ac496207692f96bd13327807e920e97a1b2f"]
> eth.getBlock(49).transactionsRoot
"0x1a65885367afcc561411fe68ed870e4952b11477ad5314de1ae8f26d48a03724"
>eth.getRawTransaction("0xdf648e4ce9bed9d3b0b35d969056ac496207692f96bd13327807e920e97a1b2f")
"0xf86505850430e2340083015f90947b04e3fe46e1cd9939bf572307fdc076478b5252018042a0e9893deacc678345ea700e714b84ce31ffe4a50267c324436fab2c48906871ada03704497c029452a1b19b1f4876e958ec7e873600408d89a8bf46e53c6e5f921e"
在 trie包中寫單測函數，key為交易在區塊中的 index，RLP編碼，value為簽名過的原始交易 RawTransaction：
func TestMyTrieCalculateTxTree(t *testing.T) {
var trie Trie
keybuf := new(bytes.Buffer)
rlp.Encode(keybuf, uint(0))
valueBytes, _ :=
hexutil.Decode("0xf86505850430e2340083015f90947b04e3fe46e1cd9939bf572307fdc076478b5252018042a0e9893deacc678345ea700e714b84ce31ffe4a50267c324436fab2c48906871ada03704497c029452a1b19b1f4876e958ec7e873600408d89a8bf46e53c6e5f921e")
trie.Update(keybuf.Bytes(), valueBytes)
t.Logf("Got Root:%s", trie.Hash().String())
}
運行輸出得到的 Hash，
也即 transactionsRoot為：
0x1a65885367afcc561411fe68ed870e4952b11477ad5314de1ae8f26d48a03724，跟 eth.getBlock(49).transactionsRoot得到的是一致的。 $ go test -v -run TestMyTrieCalculateTxTree === RUN TestMyTrieCalculateTxTree --- PASS: TestMyTrieCalculateTxTree (0.00s) my_trie_test.go:18: Got Root:0x1a65885367afcc561411fe68ed870e4952b11477ad5314de1ae8f26d48a03724 PASS ok github.com/ethereum/go-ethereum/trie 0.036s
2.State Trie
獲取最新的區塊的 stateRoot，以及打印出賬號 0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的餘額
> eth.getBlock(eth.blockNumber).stateRoot
"0xccc450ac770b0a644b81a8c0729733cf06d19f177e04fe664e1562dc3a620d60"
> eth.getBalance("0x08e5f4cc4d1b04c450d00693c95ae58825f6a307")
在 state包中寫單測函數，state trie的數據以 trie節點 hash為 key存在 leveldb中，所以整個 state trie的入口 key就是 stateRoot。state tree中存儲數據的 path為 account的 hash，value為 RLP編碼過的結構體數據。為了簡單起見和節省篇幅，這裡省去了錯誤檢查。
func TestMyTrieCalculateStateTree(t *testing.T) {
ldb, _ := ethdb.NewLDBDatabase("/Users/peace/ethereum/geth/chaindata", 0, 0)
tr, _ := trie.New(common.HexToHash("0xccc450ac770b0a644b81a8c0729733cf06d19f177e04fe664e1562dc3a620d60"),
trie.NewDatabase(ldb))
accBytes, _ := hexutil.Decode("0x08e5f4cc4d1b04c450d00693c95ae58825f6a307")
keyBytes := crypto.Keccak256Hash(accBytes).Bytes()
valueBytes, _ := tr.TryGet(keyBytes)
var acc Account
rlp.DecodeBytes(valueBytes, &acc)
t.Logf("balance:%d", acc.Balance)
}
運行輸出得到
0x08e5f4cc4d1b04c450d00693c95ae58825f6a307的餘額，跟 eth.getBalance接口得到的結果是一致的。
peaces-MacBook-Air:state peace$ go test -v -run TestMyTrieCalculateStateTree === RUN TestMyTrieCalculateStateTree --- PASS: TestMyTrieCalculateStateTree (0.01s) my_state_test.go:25: balance:23229575729235784806170618 PASS ok github.com/ethereum/go-ethereum/core/state 0.051s
3.storage trie
如下合約，為了簡單起見，合約中省去了構造函數等不相關的內容，部署後地址為：
0x9ea9b9eeac924fd784b064dabf174a55113c4064。
pragma solidity ^0.4.0;
contract testStorage {
uint storeduint = 2018;
string storedstring = 'Onething, OneWorld!';
}
獲取到當前最新塊的 stateRoot為
0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed。
> eth.getBlock(eth.blockNumber).stateRoot "0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed"
在 state包中寫單測函數，首先獲以 0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed創建 trie，
取獲取合約賬號
0x9ea9b9eeac924fd784b064dabf174a55113c4064的 storageRoot,之後再以這個 storageRoot創建 trie。
在取合約內部數據時，key為 hash過的 32字節 index，value為 RLP編碼過的值。
func TestMyTrieGetStorageData(t *testing.T) {
ldb, _ := ethdb.NewLDBDatabase("/Users/peace/ethereum/geth/chaindata", 0, 0)
statTr, _ :=
trie.New(common.HexToHash("0x86bce3794034cddb3126ec488d38cb3ee840eeff4e64c3afe0ec5a5ca8b5f6ed"),
trie.NewDatabase(ldb))
accBytes, _ := hexutil.Decode("0x9ea9b9eeac924fd784b064dabf174a55113c4064")
accKeyBytes := crypto.Keccak256Hash(accBytes).Bytes()
accValueBytes, _ := statTr.TryGet(accKeyBytes)
var acc Account
rlp.DecodeBytes(accValueBytes, &acc)
t.Logf("storageRoot:%s", acc.Root.String())
storageTr, _ := trie.New(common.HexToHash(acc.Root.String()),
trie.NewDatabase(ldb))
index0KeyBytes, _ := hexutil.Decode("0x0000000000000000000000000000000000000000000000000000000000000000")
index0ValuesBytes, _ := storageTr.TryGet(crypto.Keccak256Hash(index0KeyBytes).Bytes())
var storedUint uint
rlp.DecodeBytes(index0ValuesBytes, &storedUint)
t.Logf("storedUint: %d", storedUint)
index1KeyBytes, _ := hexutil.Decode("0x0000000000000000000000000000000000000000000000000000000000000001")
index1ValuesBytes, _ := storageTr.TryGet(crypto.Keccak256Hash(index1KeyBytes).Bytes())
t.Logf("raw bytes: %s", hexutil.Encode(index1ValuesBytes))
var storedString string
rlp.DecodeBytes(index1ValuesBytes, &storedString)
t.Logf("storedString: %s", storedString)
}
運行輸出以下數據 storedUint為 2018，跟合約裡的數據是一致的。值得注意的是 storedString的數據後面多了一個十六進制的 26(十進制為 38)，是字符串長度 (19)的兩倍，
更多的細節請參見
http://solidity.readthedocs.io/en/latest/miscellaneous.html#layout-of-state-variables-in-storage。
同時，更復雜的數據結構如變長數組、map等規則會更加複雜，同時這裡也忽略了一些字段打包存儲等細節，但是都圍繞著 storageTrie，基本原理沒有改變。
go test -v -run TestMyTrieGetStorageData === RUN TestMyTrieGetStorageData --- PASS: TestMyTrieGetStorageData (0.01s) my_state_test.go:41: storageRoot:0x3fa426aa67fff5c38788fe04e4f9815652d0b259a44efed794c309577ddc2057 my_state_test.go:49: storedUint: 2018 my_state_test.go:53: raw bytes: 0xa04f6e657468696e672c204f6e65576f726c642100000000000000000000000026 my_state_test.go:56: storedString: Onething, OneWorld!& PASS ok github.com/ethereum/go-ethereum/core/state 0.047s
原文轉載自迅雷鏈公眾號【微信號xunleilian】
