1. 摘要
本文介紹以太坊區(qū)塊鏈的一些基本知識(shí)徒扶，包括：
區(qū)塊數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
以太坊的4棵樹(shù)
狀態(tài)樹(shù)
交易樹(shù)
收據(jù)樹(shù)
賬戶存儲(chǔ)樹(shù)
2. 區(qū)塊數(shù)據(jù)結(jié)構(gòu)
以太坊的區(qū)塊是由區(qū)塊頭慌申、交易列表和叔區(qū)塊三部分組成。其中區(qū)塊頭包含塊區(qū)號(hào)、塊哈希姨裸、父塊哈希等信息，其中State Root怨酝、Transaction Root傀缩、Receipt Root分別代表了狀態(tài)樹(shù)、交易樹(shù)和交易樹(shù)的哈希农猬。除了創(chuàng)世塊外赡艰，每個(gè)塊都有父塊，用Parent Hash連成一條區(qū)塊鏈斤葱。如下圖：
3. 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
1慷垮、Merkle 樹(shù)
Merkle Tree，也叫做哈希樹(shù)揍堕，顧名思義料身，就是存儲(chǔ)hash值的一棵樹(shù)。Merkle樹(shù)的葉子是數(shù)據(jù)塊的hash值衩茸。非葉節(jié)點(diǎn)是其對(duì)應(yīng)子節(jié)點(diǎn)串聯(lián)字符串的hash芹血。是一個(gè)把任意長(zhǎng)度的數(shù)據(jù)通過(guò)哈希函數(shù)映射成固定長(zhǎng)度數(shù)據(jù)，這個(gè)數(shù)據(jù)就叫hash值，將這些hash值放到一個(gè)List里面幔烛，就叫做Hash List啃擦。Merkle Tree可以看做Hash List的泛化。
1）Merkle Tree的原理
把數(shù)據(jù)分成小的數(shù)據(jù)塊饿悬，每個(gè)數(shù)據(jù)塊有相應(yīng)地哈希令蛉，把相鄰的兩個(gè)哈希合并成一個(gè)字符串，然后運(yùn)算這個(gè)字符串的哈希乡恕，得到了一個(gè)”子哈涎匝“。如果哈习烈耍總數(shù)是單數(shù)运杭，那么直接取最后一個(gè)哈希作為下個(gè)子哈希。這樣就可以得到數(shù)目更少的新一級(jí)哈希函卒。然后按照這種方式逐漸計(jì)算上去辆憔，最終必然形成一棵倒掛的樹(shù)，到了樹(shù)根的這個(gè)位置报嵌，就剩下一個(gè)根哈希了虱咧，我們把它叫做 Merkle Root。過(guò)程如下圖：
2）Merkel樹(shù)的意義
在p2p網(wǎng)絡(luò)锚国，下載之前腕巡，先從可信的源獲得文件的Merkle Tree樹(shù)根。一旦獲得了樹(shù)根血筑，就可以從其他從不可信的源獲取Merkle tree绘沉。通過(guò)可信的樹(shù)根來(lái)檢查接受到的Merkle Tree。如果Merkle Tree是損壞的或者虛假的豺总，就從其他源獲得另一個(gè)Merkle Tree车伞，直到獲得一個(gè)與可信樹(shù)根匹配的Merkle Tree。
2喻喳、Trie 樹(shù)
Trie樹(shù)另玖，又稱前綴樹(shù)或字典樹(shù)。利用字符串的公共前綴來(lái)減少查詢時(shí)間表伦，最大限度的減少無(wú)謂的字符串比較谦去，查詢效率比哈希樹(shù)高。典型應(yīng)用是用于統(tǒng)計(jì)蹦哼，排序和保存大量的字符串(不僅限于字符串)哪轿，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。如圖5
基本性質(zhì)：
1）根節(jié)點(diǎn)不包含字符翔怎，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符
2）從根節(jié)點(diǎn)到某一節(jié)點(diǎn)窃诉。路徑上經(jīng)過(guò)的字符連接起來(lái)杨耙，就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串
3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同
注：鍵不需要被顯式地保存在節(jié)點(diǎn)中。圖示中標(biāo)注出完整的單詞飘痛，只是為了演示trie的原理
3珊膜、Patricia樹(shù)
Patricia樹(shù)，或稱Patricia trie宣脉，壓縮前綴樹(shù)车柠，是一種更節(jié)省空間的Trie。對(duì)于基數(shù)樹(shù)的每個(gè)節(jié)點(diǎn)塑猖，如果該節(jié)點(diǎn)是唯一的兒子的話竹祷，就和父節(jié)點(diǎn)合并。
4羊苟，以太坊的樹(shù)
以太坊區(qū)塊數(shù)據(jù)有三棵樹(shù)塑陵，分別為狀態(tài)樹(shù)，交易樹(shù)和收據(jù)樹(shù)蜡励。整個(gè)以太坊系統(tǒng)中只有一棵狀態(tài)樹(shù)令花，記錄整個(gè)以太坊系統(tǒng)的所有賬戶狀態(tài)。每個(gè)區(qū)塊保存著一棵交易樹(shù)凉倚，記錄該區(qū)塊的交易情況兼都，一棵收據(jù)樹(shù)用來(lái)記錄該區(qū)塊的交易收據(jù)。
狀態(tài)樹(shù)采用Merkel-Patrica(MPT)樹(shù)稽寒，而交易樹(shù)和收據(jù)樹(shù)采用Merkel樹(shù)扮碧。
對(duì)于交易樹(shù)和收據(jù)樹(shù)來(lái)說(shuō)，一旦樹(shù)已經(jīng)建立杏糙，花多少時(shí)間來(lái)編輯這棵樹(shù)并不重要字支，因?yàn)闃?shù)一旦建立了锻弓，它就會(huì)永遠(yuǎn)存在并且不會(huì)改變邀层。所以交易樹(shù)和收據(jù)樹(shù)采用Merkel樹(shù)疤坝。
對(duì)于狀態(tài)樹(shù)伶贰，每個(gè)節(jié)點(diǎn)基本上包含了一個(gè)鍵值映射尿赚，其中的鍵是地址消别，而值包括賬戶的聲明调窍、余額嗜愈、隨機(jī)數(shù)nounce旧蛾、代碼以及每一個(gè)賬戶的存儲(chǔ)。不同于交易歷史記錄蠕嫁，狀態(tài)樹(shù)需要經(jīng)常地進(jìn)行更新：賬戶余額和賬戶的隨機(jī)數(shù)nonce經(jīng)常會(huì)更變锨天，更重要的是，新的賬戶會(huì)頻繁地插入剃毒，存儲(chǔ)的鍵也會(huì)經(jīng)常被插入以及刪除病袄。我們需要這樣的數(shù)據(jù)結(jié)構(gòu)搂赋，它能在一次插入、更新益缠、刪除操作后快速計(jì)算到樹(shù)根脑奠，而不需要重新計(jì)算整個(gè)樹(shù)的Hash。Patricia樹(shù)具有Trie樹(shù)快速查找特點(diǎn)幅慌，并且比Trie樹(shù)更加節(jié)省空間宋欺，所以以太坊中，對(duì)Merkel樹(shù)改造成Merkel-Patrica(MPT)樹(shù)胰伍。
賬戶存儲(chǔ)樹(shù)是保存與賬戶相關(guān)聯(lián)數(shù)據(jù)的結(jié)構(gòu)齿诞。該項(xiàng)只有合約賬戶才有，而在 EOA 中骂租， storageRoot 留空祷杈、 codeHash 則是一串空字符串的哈希值。
（1）狀態(tài)樹(shù)
狀態(tài)樹(shù)中有四種節(jié)點(diǎn)菩咨，分別是空節(jié)點(diǎn)吠式、葉子節(jié)點(diǎn)、擴(kuò)展節(jié)點(diǎn)和分支節(jié)點(diǎn)抽米。
空節(jié)點(diǎn)特占，簡(jiǎn)單的表示空，在代碼中是一個(gè)空串云茸。
葉子節(jié)點(diǎn)（leaf）是目，表示為[key,value]的一個(gè)鍵值對(duì)，其中key是key的一種特殊十六進(jìn)制編碼标捺，value是value的RLP編碼懊纳。
擴(kuò)展節(jié)點(diǎn)（extension），也是[key亡容，value]的一個(gè)鍵值對(duì)嗤疯，但是這里的value是其他節(jié)點(diǎn)的hash值，這個(gè)hash可以被用來(lái)查詢數(shù)據(jù)庫(kù)中的節(jié)點(diǎn)闺兢。也就是說(shuō)通過(guò)hash鏈接到其他節(jié)點(diǎn)茂缚。
分支節(jié)點(diǎn)（branch），因?yàn)镸PT樹(shù)中的key被編碼成一種特殊的16進(jìn)制的表示屋谭，再加上最后的value脚囊，所以分支節(jié)點(diǎn)是一個(gè)長(zhǎng)度為17的list，前16個(gè)元素對(duì)應(yīng)著key中的16個(gè)可能的十六進(jìn)制字符桐磁，如果有一個(gè)[key,value]對(duì)在這個(gè)分支節(jié)點(diǎn)終止悔耘，最后一個(gè)元素代表一個(gè)值，即分支節(jié)點(diǎn)既可以搜索路徑的終止也可以是路徑的中間節(jié)點(diǎn)我擂。
假如有四個(gè)賬戶衬以，賬戶1地址0x811344缓艳，余額1ETH；賬戶2地址0x879337泄鹏，余額2ETH郎任；賬戶3地址0x8fd365，余額3ETH备籽；賬戶4地址0x879397,余額4ETH舶治，存儲(chǔ)如下：
從圖中可以看出，狀態(tài)樹(shù)的存儲(chǔ)涉及3種編碼方式：
KeyBytes編碼
Hex編碼
Compact編碼
在完成Compact編碼后车猬，會(huì)通過(guò)折疊操作把子結(jié)點(diǎn)替換成子結(jié)點(diǎn)的hash值霉猛，然后以鍵值對(duì)的形式將所有結(jié)點(diǎn)存儲(chǔ)到LevelDBA數(shù)據(jù)庫(kù)中。下面詳細(xì)介紹上面3中編碼方式珠闰。
KeyBytes編碼
即原始關(guān)鍵字惜浅，比如圖中的0x811344、0x879337等伏嗜。每個(gè)字節(jié)中包含2個(gè)nibble（半字節(jié)坛悉，4 bits），每個(gè)nibble的數(shù)值范圍時(shí)0x0~0xF承绸。
Hex編碼
由于我們需要以nibble為單位進(jìn)行編碼并插入MPT裸影，因此需要把一個(gè)字節(jié)拆分成兩個(gè)，轉(zhuǎn)換為Hex編碼军熏。
Compact編碼
當(dāng)我們需要把內(nèi)存中MPT存儲(chǔ)到數(shù)據(jù)庫(kù)中時(shí)轩猩，還需要再把兩個(gè)字節(jié)合并為一個(gè)字節(jié)進(jìn)行存儲(chǔ)，這時(shí)候會(huì)碰到2個(gè)問(wèn)題：
關(guān)鍵字長(zhǎng)度為奇數(shù)荡澎，有一個(gè)字節(jié)無(wú)法合并
需要區(qū)分結(jié)點(diǎn)是擴(kuò)展結(jié)點(diǎn)還是葉子結(jié)點(diǎn)
為了解決這個(gè)問(wèn)題均践，以太坊設(shè)計(jì)了一種Compact編碼方式，具體規(guī)則如下：
擴(kuò)展結(jié)點(diǎn)摩幔，關(guān)鍵字長(zhǎng)度為偶數(shù)彤委，前面加00前綴
擴(kuò)展結(jié)點(diǎn)，關(guān)鍵字長(zhǎng)度為奇數(shù)或衡，前面加1前綴（前綴和第1個(gè)字節(jié)合并為一個(gè)字節(jié)）
葉子結(jié)點(diǎn)焦影，關(guān)鍵字長(zhǎng)度為偶數(shù)，前面加20前綴（因?yàn)槭荁ig Endian）
葉子結(jié)點(diǎn)薇宠，關(guān)鍵字長(zhǎng)度為奇數(shù)偷办，前面加3前綴（前綴和第1個(gè)字節(jié)合并為一個(gè)字節(jié)）
StateDB的存儲(chǔ)
StateDB中存儲(chǔ)了很多stateObject艰额，而每一個(gè)stateObject則代表了一個(gè)以太坊賬戶澄港，包含了賬戶的地址、余額柄沮、nonce回梧、合約代碼hash等狀態(tài)信息废岂。所有賬戶的當(dāng)前狀態(tài)在以太坊中被稱為“世界狀態(tài)”，在每次挖出或者接收到新區(qū)塊時(shí)需要更新世界狀態(tài)狱意。
為了能夠快速檢索和更新賬戶狀態(tài)湖苞，StateDB采用了兩級(jí)緩存機(jī)制，參見(jiàn)下圖：
第一級(jí)緩存以map的形式存儲(chǔ)stateObject
第二級(jí)緩存以MPT的形式存儲(chǔ)
第三級(jí)就是LevelDB上的持久化存儲(chǔ)
當(dāng)上一級(jí)緩存中沒(méi)有所需的數(shù)據(jù)時(shí)详囤，會(huì)從下一級(jí)緩存或者數(shù)據(jù)庫(kù)中進(jìn)行加載财骨。
（2）交易樹(shù)
從下圖中可以看出，MPT是以交易在區(qū)塊中的索引的RLP編碼作為key藏姐，存儲(chǔ)交易數(shù)據(jù)的RLP編碼隆箩。事實(shí)上交易在LeveDB中并不是單獨(dú)存儲(chǔ)的，而是存儲(chǔ)在區(qū)塊的Body中羔杨。在往LeveDB中存儲(chǔ)不同類型的鍵值對(duì)時(shí)捌臊，會(huì)在關(guān)鍵字中添加不同的前綴予以區(qū)分。
因此兜材，以b + block index + block hash作為關(guān)鍵字就可以唯一確定某個(gè)區(qū)塊的Body所在的位置理澎。另外，為了能夠快速查詢某筆交易的數(shù)據(jù)曙寡，在數(shù)據(jù)庫(kù)中還存儲(chǔ)了每筆交易的索引信息糠爬，稱為T(mén)xLookupEntry。TxLookupEntry中包含了block index和block hash用于定位區(qū)塊Body卵皂，同時(shí)還包含了該筆交易在區(qū)塊Body中的索引位置秩铆。
（3）收據(jù)樹(shù)
交易回執(zhí)的存儲(chǔ)和交易類似，區(qū)別是交易回執(zhí)是單獨(dú)存儲(chǔ)到LevelDB中的灯变，以r為前綴殴玛。另外，由于交易回執(zhí)和交易是一一對(duì)應(yīng)的添祸，因此也可以通過(guò)TxLookupEntry快速定位交易回執(zhí)所在的位置滚粟，加速交易回執(zhí)的查找。
（3）賬戶存儲(chǔ)樹(shù)
以太坊中有兩種賬戶類型：外部所有賬戶（Externally Owned Accounts 簡(jiǎn)稱 EOA）以及合約賬戶刃泌。我們用來(lái)互相收發(fā)以太幣凡壤、部署智能合約的賬戶就是 EOA 賬戶，而部署智能合約時(shí)自動(dòng)生成的賬戶則是合約賬戶耙替。每一個(gè)智能合約都有其獨(dú)一無(wú)二的以太坊賬戶亚侠。
賬戶狀態(tài)反映了一個(gè)以太坊賬戶的各項(xiàng)信息。例如俗扇，它存儲(chǔ)了當(dāng)前賬戶以太幣的余額信息硝烂、當(dāng)前賬戶發(fā)送過(guò)的交易數(shù)量...每一個(gè)賬戶都有賬戶狀態(tài)。
下面就來(lái)看看賬戶狀態(tài)中都包括什么：
<1> nonce
從此地址發(fā)送出去的交易數(shù)量（如果當(dāng)前為 EOA 賬戶）或者此賬號(hào)產(chǎn)生的合約創(chuàng)建操作（現(xiàn)在先別管合約創(chuàng)建操作是什么）铜幽。
<2> balance
此賬號(hào)所擁有的以太幣數(shù)量（以 Wei 計(jì)量）滞谢。
<3> storageRoot
賬戶存儲(chǔ)樹(shù)的根節(jié)點(diǎn)哈希值（稍后介紹賬戶存儲(chǔ)是什么）串稀。
<4> codeHash
對(duì)于合約賬戶，就是此賬戶存儲(chǔ) EVM 代碼的哈希值狮杨。對(duì)于 EOA 賬戶母截，此處留空。
賬戶狀態(tài)中不容忽視的一個(gè)細(xì)節(jié)是橄教，上述對(duì)象在內(nèi)的所有對(duì)象都可變（除了 codeHash）清寇。舉例來(lái)說(shuō)，當(dāng)一個(gè)賬戶向其他賬戶發(fā)送以太幣時(shí)护蝶，除了 nonce 會(huì)增加颗管，賬戶的余額也會(huì)相應(yīng)改變。
而 codeHash 的不可變性使得滓走，如果部署了有漏洞的智能合約垦江，也無(wú)法修復(fù)更新此合約。對(duì)應(yīng)的搅方，只能部署一個(gè)新合約（而有漏洞的版本會(huì)一直存在于區(qū)塊鏈上）比吭。這也是為什么使用 Truffle 進(jìn)行智能合約的開(kāi)發(fā)和部署十分必要，并且用 Solidity 編程時(shí)要遵循 最佳實(shí)踐 的要求姨涡。
賬戶存儲(chǔ)樹(shù)是保存與賬戶相關(guān)聯(lián)數(shù)據(jù)的結(jié)構(gòu)衩藤。該項(xiàng)只有合約賬戶才有，而在 EOA 中涛漂， storageRoot 留空赏表、 codeHash 則是一串空字符串的哈希值。所有智能合約的數(shù)據(jù)都以 32 字節(jié)映射的形式保存在賬戶存儲(chǔ)樹(shù)中匈仗。此處不再贅述賬戶狀態(tài)樹(shù)如何維持合約數(shù)據(jù)瓢剿。賬戶狀態(tài)中的 storageRoot 區(qū)域負(fù)責(zé)維持賬戶存儲(chǔ)樹(shù)根節(jié)點(diǎn)哈希值。
根據(jù)以太坊黃皮書(shū)，賬戶若是一個(gè)智能合約賬戶火架，則必定包含了 存儲(chǔ)樹(shù) （storageRoot）和 代碼存儲(chǔ) （codeHash）鉴象。
若我們繼續(xù)放大觀察存儲(chǔ)樹(shù)，即為上圖最左邊的樹(shù)何鸡。存儲(chǔ)樹(shù)保存了智能合約的變量數(shù)據(jù)纺弊，它維持著256位的變量數(shù)據(jù)索引與RLP 算法編碼過(guò)的256位數(shù)據(jù)本身。
為保證數(shù)據(jù)完整性骡男，這些數(shù)據(jù) 也被組織成一棵 MPT 樹(shù)的形式 淆游。該MPT樹(shù)的根節(jié)點(diǎn)哈希值稱為 存儲(chǔ)樹(shù) 。
存儲(chǔ)樹(shù)是賬戶狀態(tài)的一個(gè) 域 ，該值隨著合約的存儲(chǔ)區(qū)的增加稽犁、刪除、改動(dòng)而不斷變更骚亿。
代碼存儲(chǔ)是只讀的已亥，它是合約賬戶的所執(zhí)行的代碼，它在合約第一次創(chuàng)建完畢后就不可以再變更来屠。
5虑椎，總結(jié)
總結(jié)一下，以太坊有四種前綴樹(shù)：
（1）狀態(tài)樹(shù)包括了從地址到賬戶狀態(tài)之間的映射俱笛。狀態(tài)樹(shù)的根節(jié)點(diǎn)哈希值由區(qū)塊保存（在 stateRoot 字段）捆姜，它標(biāo)示了區(qū)塊創(chuàng)建時(shí)的當(dāng)前狀態(tài)。整個(gè)網(wǎng)絡(luò)中只有一個(gè)狀態(tài)樹(shù)迎膜。
狀態(tài)標(biāo)識(shí)了以太坊這臺(tái)分布式計(jì)算機(jī)的硬盤(pán)泥技。它是從地址到賬戶狀態(tài)的映射。
（2）交易樹(shù)包含了一個(gè)區(qū)塊中的所有交易信息磕仅。由區(qū)塊頭（在 transactionsRoot 區(qū)域）保存交易樹(shù)的根節(jié)點(diǎn)哈希值珊豹。每個(gè)區(qū)塊都有一棵交易樹(shù)。
交易標(biāo)示了系統(tǒng)中的狀態(tài)轉(zhuǎn)移榕订。它可以是資金的轉(zhuǎn)移店茶、消息調(diào)用或是合約的部署。
（3）交易收據(jù)樹(shù)包含了一個(gè)區(qū)塊中所有交易的收據(jù)信息劫恒。同樣由區(qū)塊頭（在 receiptsRoot 區(qū)域）保存交易收據(jù)樹(shù)的根節(jié)點(diǎn)哈希值贩幻；每個(gè)區(qū)塊都有對(duì)應(yīng)的交易收據(jù)樹(shù)。
（4）賬戶存儲(chǔ)樹(shù)保存了與某一智能合約相關(guān)的數(shù)據(jù)信息两嘴。由賬戶狀態(tài)保存賬戶存儲(chǔ)樹(shù)的根節(jié)點(diǎn)哈希值（在 storageRoot 字段）丛楚。每個(gè)賬戶都有一個(gè)賬戶存儲(chǔ)樹(shù)。
賬戶狀態(tài)保存著每個(gè)以太坊賬戶的狀態(tài)信息憔辫。賬戶狀態(tài)同樣保存著賬戶狀態(tài)樹(shù)的 storageRoot鸯檬，后者包含了該賬戶的存儲(chǔ)數(shù)據(jù)。
用一張圖總結(jié)而言：
