以太坊采用基于賬戶(hù)的模式神年，系統(tǒng)中顯式地維護(hù)每個(gè)賬戶(hù)上有多少余額已维，今天看一下用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)account-based ledger

要完成的功能：

從 賬戶(hù)地址 到 賬戶(hù)狀態(tài) 的映射

addr -> state

addr：賬戶(hù)地址，以太坊中用的賬戶(hù)地址是160位瘤袖，也就是20個(gè)字節(jié)衣摩，一般表示成40個(gè)十六進(jìn)制的數(shù)（0～f）。

state：外部賬戶(hù)和合約賬戶(hù)的狀態(tài)捂敌，包括余額艾扮、交易次數(shù)、合約賬戶(hù)還包括代碼占婉、存儲(chǔ)泡嘴。

那么要設(shè)計(jì)什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這個(gè)映射呢？

數(shù)據(jù)結(jié)構(gòu)假設(shè)

以下是幾個(gè)思考的方案：

假設(shè)方案一：用哈希表實(shí)現(xiàn)

直觀上看逆济，像一個(gè)很典型的key-value pair酌予，給出一個(gè)賬戶(hù)地址，要找到相應(yīng)的賬戶(hù)狀態(tài)奖慌。

所以一個(gè)直觀的想法：用哈希表實(shí)現(xiàn)抛虫。

系統(tǒng)中的全節(jié)點(diǎn)維護(hù)一個(gè)哈希表，每次有一個(gè)新的賬戶(hù)简僧，插入到哈希表里面建椰，查詢(xún)賬戶(hù)的余額，就直接在哈希表中查詢(xún)岛马。如果不考慮哈希碰撞的話(huà)棉姐，基本上查詢(xún)的效率是常數(shù)時(shí)間內(nèi)完成的屠列，更新也是很容易在哈希表中更新的。

>>> 問(wèn)題：如果用這個(gè)哈希表要提供merkle proof怎么提供伞矩？

比如說(shuō)你要跟一個(gè)人簽合同笛洛，希望他能證明一下他有多少錢(qián)，怎么提供證明呢乃坤？

一種方法是 把哈希表中的元素組織成一個(gè)Merkle tree苛让，然后算出一個(gè)根哈希值，這個(gè)根哈希值存在block header里侥袜，只要根哈希值是正確的蝌诡，就能保證底下的樹(shù)不會(huì)被篡改。

如果有新區(qū)塊發(fā)布怎么辦枫吧？

新區(qū)塊中包含新的交易，執(zhí)行這個(gè)交易必然會(huì)使哈希表的內(nèi)容發(fā)生變化宇色，發(fā)布下一個(gè)區(qū)塊的時(shí)候九杂，再重新把哈希表中的內(nèi)容組織成一個(gè)Merkle tree嗎？

這個(gè)代價(jià)太大了宣蠕。實(shí)際上例隆，真正發(fā)生變化的賬戶(hù)狀態(tài)只是一小部分，因?yàn)橹挥心莻€(gè)區(qū)塊里所關(guān)聯(lián)的賬戶(hù)才會(huì)發(fā)生變化抢蚀，大多數(shù)賬戶(hù)的狀態(tài)是不變的镀层。所以每次你都重新構(gòu)造一次Merkle tree，這個(gè)代價(jià)是很大的皿曲。

比特幣系統(tǒng)當(dāng)中難道不是每出現(xiàn)一個(gè)區(qū)塊也要重新構(gòu)造一個(gè)Merkle tree嗎唱逢？那個(gè)為什么沒(méi)有問(wèn)題？

那個(gè)Merkle tree是把區(qū)塊里包含的交易組織成一個(gè)Merkle tree屋休，那區(qū)塊中的交易每次發(fā)布一個(gè)新的區(qū)塊又有一系列新的交易坞古，所以比特幣中的Merkle tree是immutable的，每次發(fā)布一個(gè)新的區(qū)塊對(duì)應(yīng)一個(gè)Merkle tree劫樟，然后這棵Merkle tree構(gòu)建完之后是不會(huì)再改的痪枫，下次再發(fā)布一個(gè)新的區(qū)塊再構(gòu)建一個(gè)新的Merkle tree。

那區(qū)塊里有多少個(gè)交易呢叠艳？最多差不多4000個(gè)（按照1M字節(jié)奶陈，每個(gè)交易大概是250M字節(jié)左右），這個(gè)其實(shí)是一個(gè)上限附较，很多區(qū)塊的交易數(shù)目根本到不了4000個(gè)吃粒，有好多區(qū)塊就只有幾百個(gè)，甚至有可能還有更少的翅睛，所以每次發(fā)布一個(gè)區(qū)塊声搁，比特幣里構(gòu)建一個(gè)Merkle tree黑竞，是要把這幾百個(gè)到幾千個(gè)交易構(gòu)成一個(gè)Merkle tree。

這里如果采用這種方法會(huì)是什么情況疏旨？

是要把所有的以太坊賬戶(hù)一起構(gòu)成一個(gè)Merkle tree很魂，這個(gè)就比剛才講的幾百，幾千個(gè)交易要高出好幾個(gè)數(shù)量級(jí)檐涝，相當(dāng)于每次發(fā)布一個(gè)區(qū)塊要把所有的賬戶(hù)遍歷一遍構(gòu)建出一個(gè)Merkle tree遏匆，下次再有一個(gè)區(qū)塊，再把所有的賬戶(hù)遍歷一遍谁榜，再構(gòu)建出一個(gè)Merkle tree幅聘。

除了提供Merkle proof證明賬戶(hù)有多少錢(qián)之外，這個(gè)Merkle tree還有另外一個(gè)很重要的作用窃植，就是維護(hù)各個(gè)全節(jié)點(diǎn)之間狀態(tài)的一致性帝蒿，如果沒(méi)有根哈希值不去發(fā)不出來(lái)，每個(gè)節(jié)點(diǎn)就是在本地維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)巷怜，那怎么知道你的數(shù)據(jù)結(jié)構(gòu)的狀態(tài)跟別人的數(shù)據(jù)結(jié)構(gòu)的狀態(tài)是不是一致呢葛超，要各個(gè)全節(jié)點(diǎn)保持狀態(tài)的一致才行。這也是為什么比特幣中把根哈希值寫(xiě)在塊頭里的原因延塑，就是對(duì)于當(dāng)前區(qū)塊中包含哪些交易绣张，所有的全節(jié)點(diǎn)要有一個(gè)共識(shí)。

>>> 結(jié)論：不可行关带，因?yàn)槊看螛?gòu)建Merkle tree的代價(jià)太大

如果每個(gè)全節(jié)點(diǎn)在本地維護(hù)一個(gè)哈希表侥涵，然后需要構(gòu)建Merkle tree的時(shí)候構(gòu)建出Merkle tree來(lái)，然后根哈希值發(fā)到區(qū)塊頭里宋雏，這個(gè)方法是不行的芜飘。哈希表本身的效率是挺好的，插入好芭，更改效率都很好燃箭，但是每次構(gòu)建Merkle tree的代價(jià)太大了。

假設(shè)方案二：直接用一個(gè)Merkle tree把所有的賬戶(hù)都放進(jìn)去

不要哈希表了舍败，直接用一個(gè)Merkle tree把所有的賬戶(hù)都放進(jìn)去招狸，要改的時(shí)候直接在Merkle tree里改。因?yàn)槊總€(gè)區(qū)塊更新的只是一小部分賬戶(hù)邻薯，所以改的時(shí)候只是Merkle tree里的一小部分裙戏。

>>> 問(wèn)題1：Merkle tree沒(méi)有提供一個(gè)高效的查找、更新的方法

比特幣的Merkle tree是怎么構(gòu)建的厕诡？

就最底下一層是tx累榜，然后哈希值放到上面節(jié)點(diǎn)里，兩兩結(jié)合，然后再取一個(gè)哈希往上整壹罚。

他沒(méi)有提供一個(gè)快速查找葛作，更新的方法。

>>> 問(wèn)題2：直接把賬戶(hù)放到Merkle tree里猖凛，這個(gè)Merkle tree要不要排序赂蠢？

Sorted Merkle tree

如果不排序會(huì)怎么樣？

1辨泳、查找速度會(huì)慢虱岂。

2、還有一個(gè)問(wèn)題菠红，這些賬戶(hù)組成了這棵merkle tree第岖，葉節(jié)點(diǎn)是這些賬戶(hù)的信息，如果不規(guī)定這些賬戶(hù)在葉節(jié)點(diǎn)出現(xiàn)的順序试溯，那么這樣構(gòu)建出來(lái)的Merkle tree不是唯一的蔑滓。

比如，系統(tǒng)中有很多全節(jié)點(diǎn)耍共，每個(gè)全節(jié)點(diǎn)按照自己的某個(gè)順序烫饼，比如說(shuō)他聽(tīng)到某個(gè)交易的順序構(gòu)建一個(gè)Merkle tree，那么葉結(jié)點(diǎn)的順序是亂的试读，每個(gè)節(jié)點(diǎn)都是自己決定的，最后構(gòu)建出的Merkle tree是不一樣的荠耽，算出的根哈希值也是不一樣的

比特幣中的節(jié)點(diǎn)也是不排序的钩骇，那為什么比特幣就沒(méi)有問(wèn)題呢？

因?yàn)楸忍貛胖械拿總€(gè)全節(jié)點(diǎn)收到的交易的順序也是不一樣的铝量，理論上說(shuō)構(gòu)建的Merkle tree的根哈希值也是不一樣的倘屹。

但是比特幣中，每個(gè)節(jié)點(diǎn)在本地組裝一個(gè)候選區(qū)塊慢叨，這個(gè)節(jié)點(diǎn)自己決定哪些交易纽匙、以什么順序順序打包進(jìn)這個(gè)區(qū)塊里，然后通過(guò)挖礦去競(jìng)爭(zhēng)記賬權(quán)拍谐。如果他沒(méi)有搶到記賬權(quán)烛缔，他的任何決定其他人沒(méi)必要知道；只有他有記賬權(quán)轩拨，且發(fā)布區(qū)塊后最終成為被大家接受的區(qū)塊践瓷，那么，這個(gè)順序就是發(fā)布這個(gè)區(qū)塊的節(jié)點(diǎn)確定的亡蓉。

也就是說(shuō)晕翠，比特幣中雖然也沒(méi)用排序的Merkle tree，但是他那個(gè)順序是唯一的砍濒，是由發(fā)布區(qū)塊的那個(gè)節(jié)點(diǎn)確定的淋肾。

那為什么以太坊不能這樣做硫麻？

如果以太坊也這么做的話(huà)，需要把賬戶(hù)的狀態(tài)發(fā)布到區(qū)塊里樊卓。也可以說(shuō)是 每個(gè)全節(jié)點(diǎn)自己決定 怎么把賬戶(hù)組織成一個(gè)Merkle tree拿愧，算出跟哈希值、挖出礦简识，但要怎么讓別人知道這個(gè)順序赶掖，你得把他發(fā)布到區(qū)塊里。但發(fā)布的是所有賬戶(hù)的狀態(tài)七扰，不是交易奢赂，這兩者差好幾個(gè)數(shù)量級(jí)，比特幣發(fā)布一個(gè)區(qū)塊只需要幾百個(gè)/幾千個(gè)交易颈走。

>>> 結(jié)論：不可行膳灶，不排序的Merkle tree是不行的。

交易是必須要發(fā)布的立由，不發(fā)布別人就沒(méi)法知道轧钓，但賬戶(hù)狀態(tài)可以維護(hù)在本地，而且大部分賬戶(hù)狀態(tài)是不變的锐膜。一個(gè)區(qū)塊里的交易只能改很少的賬戶(hù)毕箍，大多數(shù)賬戶(hù)是不變的，而且重復(fù)發(fā)布道盏，每隔十幾秒發(fā)布一個(gè)新的區(qū)塊而柑，把所有狀態(tài)都打包發(fā)布一遍，下次再過(guò)十幾秒再發(fā)布一遍荷逞，這個(gè)是不可行媒咳。

假設(shè)方案三：用Sorted Merkle tree

>>> 問(wèn)題：新增一個(gè)賬戶(hù)怎么辦

產(chǎn)生一個(gè)賬戶(hù)的地址是隨機(jī)的，他的葉節(jié)點(diǎn)的位置很可能是插在中間的种远，那后面這些樹(shù)的結(jié)構(gòu)都得變涩澡。

新產(chǎn)生一個(gè)賬戶(hù)，對(duì)外發(fā)生了交互坠敷，我需要把他加入到我的數(shù)據(jù)結(jié)構(gòu)里妙同，這是沒(méi)錯(cuò)的，但問(wèn)題是常拓，這個(gè)加入的代價(jià)有多大渐溶？

可能大半棵Merkle tree需要重構(gòu)，這個(gè)代價(jià)太大了弄抬。

>>> 結(jié)論：不可行茎辐，用Sorted Merkle tree，插入、刪除代價(jià)都太大拖陆。

而且弛槐，區(qū)塊鏈?zhǔn)遣豢纱鄹牡模钦f(shuō)添東西容易依啰，刪東西難乎串。

其實(shí)以太坊中沒(méi)有顯式地刪除賬戶(hù)的操作，有的賬戶(hù)上就一點(diǎn)錢(qián)速警，就一兩個(gè)Wei叹誉，你也不能把他刪掉。

上面的方案都不行闷旧。

以太坊的數(shù)據(jù)結(jié)構(gòu)

那么以太坊中采用的方法是用一個(gè)叫MPT（Merkle Patricia Tree）的結(jié)構(gòu)长豁。

講這個(gè)之前先講一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。

【Trie】

來(lái)源于“retrieval”忙灼，檢索匠襟。

trie：字典樹(shù)，前綴樹(shù)该园。

也是一種key-value的數(shù)據(jù)對(duì)酸舍，一般來(lái)說(shuō)key用字符串用的比較多，比如說(shuō)一些單詞排成一個(gè)trie的數(shù)據(jù)結(jié)構(gòu)里初。

舉例：

general

genesis（區(qū)塊鏈的第一個(gè)區(qū)塊叫做genesis block,創(chuàng)世紀(jì)塊）

go

god

good

下圖就是一個(gè)trie的結(jié)構(gòu)啃勉，這幾個(gè)單詞都是以G開(kāi)頭的，然后第二個(gè)字母就開(kāi)始分裂了双妨，左邊是E璧亮，右邊是O，左邊這前兩個(gè)單詞都是N和E斥难，然后下面再分開(kāi)，R和S帘饶，然后是后三個(gè)字母哑诊，右邊這個(gè)分支，O這個(gè)分支及刻，Go就已經(jīng)結(jié)束了镀裤，從這個(gè)可以看到單詞可能在trie的中間節(jié)點(diǎn)結(jié)束，然后左邊是D缴饭，右邊是O暑劝，左邊變成了God，右邊下來(lái)是Good颗搂。

Trie樹(shù)可以利用字符串的公共前綴來(lái)節(jié)約存儲(chǔ)空間担猛。

如果系統(tǒng)中存在大量字符串且這些字符串基本沒(méi)有公共前綴，則相應(yīng)的trie樹(shù)將非常消耗內(nèi)存，這也是trie樹(shù)的一個(gè)缺點(diǎn)傅联。

Trie的特點(diǎn)

特點(diǎn)一：trie的每個(gè)節(jié)點(diǎn)的分叉數(shù)目先改，取決于 key值里 每個(gè)元素的 取值范圍

這個(gè)例子當(dāng)中，每個(gè)都是英文單詞蒸走，而且是小寫(xiě)的仇奶，所以每個(gè)節(jié)點(diǎn)的分叉數(shù)目最多是26個(gè)，加上一個(gè)結(jié)束標(biāo)志位（表示這個(gè)單詞到這個(gè)地方就結(jié)束了）比驻。

如英文字母的字典樹(shù)是一個(gè)26叉樹(shù)该溯，數(shù)字的字典樹(shù)是一個(gè)10叉樹(shù)。

在以太坊中地址是表示成40個(gè)十六進(jìn)制的數(shù)别惦，因此分叉數(shù)目（branching factor）是17（十六進(jìn)制的0~f狈茉，再加上結(jié)束標(biāo)志位）。

特點(diǎn)二：trie的查找速率步咪，取決于key的長(zhǎng)度

鍵值越長(zhǎng)论皆，查找需要訪(fǎng)問(wèn)內(nèi)存的次數(shù)就越多。

在這個(gè)例子當(dāng)中猾漫，不同的單詞鍵值長(zhǎng)度是不同的点晴。

在以太坊中，所有鍵值都是40悯周，因?yàn)榈刂范际?0位十六進(jìn)制的數(shù)粒督。

比特幣和以太坊的地址是不通用的，兩個(gè)地址的格式長(zhǎng)度都是不一樣的禽翼。

但有一點(diǎn)是類(lèi)似的屠橄，以太坊中的地址也是公鑰經(jīng)過(guò)轉(zhuǎn)換得來(lái)的。其實(shí)就是公鑰取哈希闰挡，然后前面的不要锐墙，只要后面這部分，就得到一個(gè)160bit的地址长酗。

特點(diǎn)三：只要兩個(gè)地址不一樣溪北，最后肯定映射到樹(shù)中的不同分支，所以trie是不會(huì)出現(xiàn)碰撞的

特點(diǎn)四：不同的節(jié)點(diǎn)夺脾，不論按照什么順序插入這些賬戶(hù)之拨，最后構(gòu)造出來(lái)的樹(shù)是一樣的

前面講Merkle tree，如果不排序的話(huà)咧叭，一個(gè)問(wèn)題是賬戶(hù)插入到Merkle tree 的順序不一樣蚀乔，得到的樹(shù)的結(jié)構(gòu)也不一樣。

那trie呢菲茬？

比如上圖中的這五個(gè)單詞吉挣，換一個(gè)順序插到這個(gè)樹(shù)里面派撕，得到的是一個(gè)不同的樹(shù)嗎？其實(shí)是一樣的听想，只要給定的輸入不變腥刹，無(wú)論輸入怎么打亂重排，最后插入到trie當(dāng)中汉买，得到的樹(shù)是一樣的衔峰。

特點(diǎn)五：更新操作的局部性很好

每次發(fā)布一個(gè)區(qū)塊，系統(tǒng)中絕大多數(shù)賬戶(hù)的狀態(tài)是不變的蛙粘，只有個(gè)別受到影響的賬戶(hù)才會(huì)變垫卤，所以更新操作的局部性很重要。

trie局部性呢出牧？

比如在上圖中穴肘，我要更新genesis這個(gè)key對(duì)應(yīng)的value（這個(gè)圖當(dāng)中只畫(huà)出了key，沒(méi)有畫(huà)出value）舔痕，只要訪(fǎng)問(wèn)genesis的那個(gè)分支评抚，其他分支不用訪(fǎng)問(wèn)的，也不用遍歷整棵樹(shù)伯复。

Tire的缺點(diǎn)：存儲(chǔ)浪費(fèi)

像左邊分支都只有一個(gè)子節(jié)點(diǎn)慨代，對(duì)于這種一脈單傳的情況，如果能把節(jié)點(diǎn)進(jìn)行合并啸如，那么可以減小存儲(chǔ)的開(kāi)銷(xiāo)侍匙，同時(shí)也提高了查找的效率，不用一次一個(gè)一個(gè)的往下找了叮雳。

那么就引入了Patricia tree想暗，也有人寫(xiě)成Patricia trie，是經(jīng)過(guò)路徑壓縮的前綴樹(shù)帘不，有時(shí)候也叫壓縮前綴樹(shù)说莫。

【Patricia tree】/【Patricia trie】

這個(gè)如果進(jìn)行路徑壓縮就變成下圖的樣子。

可以看到寞焙，G下面還是E和O進(jìn)行分叉唬滑，E下面之后跟的都是NE，再往下就是E和S分叉棺弊，然后后面都和在一起了，右邊都是一樣的擒悬。

這樣壓縮之后有什么好處模她？

直觀上看，這個(gè)高度明顯縮短了懂牧，訪(fǎng)問(wèn)內(nèi)存的次數(shù)會(huì)大大減少侈净，效率提高了尊勿。

注意：對(duì)于Patricia tree來(lái)說(shuō)，新插入一個(gè)單詞畜侦，原來(lái)壓縮的路徑可能需要擴(kuò)展開(kāi)元扔。

比如這個(gè)例子當(dāng)中，加入geometry旋膳，左邊的分支就不能那樣壓縮了澎语。

路徑壓縮在什么情況下效果比較好？

鍵值分布比較稀疏的時(shí)候验懊，路徑壓縮效果比較好擅羞。

比如說(shuō)，這個(gè)例子當(dāng)中是用英文單詞义图，假設(shè)每個(gè)單詞都很長(zhǎng)减俏，但是一共沒(méi)有幾個(gè)單詞，

舉個(gè)例子：

misunderstanding

decentralization（去中心化）

disintermediation（去中間商碱工，非中介化）（intermediaries：中間商）

這三個(gè)單詞插入到一個(gè)普通的trie里面就成了下圖的樣子

可以看到這樣的結(jié)構(gòu)效率是比較低的娃承，基本上是一條線(xiàn)了。

如果用Patricia tree的話(huà)怕篷，參考下圖

這個(gè)樹(shù)的高度明顯改善多了历筝。

所以鍵值分布比較稀疏的時(shí)候苔货，路徑壓縮效果比較好舱禽。

以太坊應(yīng)用中鍵值是不是稀疏呢？

以太坊應(yīng)用中鍵值是地址屋匕，地址是160位的蹂析，地址空間有2^160舔示，這是一個(gè)非常非常大的數(shù)。

如果你設(shè)計(jì)一個(gè)計(jì)算機(jī)程序的算法电抚，他需要進(jìn)行運(yùn)算的次數(shù)是2^160惕稻，那這個(gè)在我們所有人的有生之年都不可能算出來(lái)，全世界的以太坊的賬戶(hù)數(shù)目加在一起也遠(yuǎn)遠(yuǎn)沒(méi)有這么大蝙叛，跟這個(gè)數(shù)比俺祠，是微乎其微的。

為什么要弄這么稀疏借帘，不把地址長(zhǎng)度縮短一點(diǎn)蜘渣，這樣訪(fǎng)問(wèn)效率也快，也沒(méi)必要那么稀疏了肺然？

以太坊中普通賬戶(hù)跟比特幣的創(chuàng)建方法是一樣的蔫缸，沒(méi)有一個(gè)中央的節(jié)點(diǎn)，就每個(gè)用戶(hù)獨(dú)立創(chuàng)建賬戶(hù)际起。你在本地產(chǎn)生一個(gè)公私鑰對(duì)拾碌，就是一個(gè)賬戶(hù)吐葱。

那怎么防止兩個(gè)人的賬戶(hù)碰撞，產(chǎn)生的一樣呢校翔？

這種可能性是存在的弟跑，但是這個(gè)概率比地球爆炸還要小。

怎么達(dá)到這么小的概率防症，就是地址要足夠長(zhǎng)孟辑，分布足夠稀疏，才不會(huì)產(chǎn)生碰撞告希。

這個(gè)可能看上去有點(diǎn)浪費(fèi)扑浸，但是這是去中心化的系統(tǒng)防止賬戶(hù)沖突的唯一辦法。

所以他是非常稀疏的燕偶，這就是為什么在數(shù)據(jù)結(jié)構(gòu)中喝噪，要用Patricia tree。

【MPT】（Merkle Patricia tree）

>>> Merkle tree和Binary tree的區(qū)別

即區(qū)塊鏈與普通鏈表的區(qū)別：把普通指針換成了哈希指針指么。

>>> Merkle Patricia tree和Patricia tree的區(qū)別

也是 把普通指針換成了哈希指針酝惧。

所有的賬戶(hù)組織成一個(gè)Patricia tree，用路徑壓縮提高效率伯诬，然后把普通指針換成哈希指針晚唇，所以就可以計(jì)算出一個(gè)根哈希值。這個(gè)跟哈希值也是寫(xiě)在block header里面盗似。

比特幣的block header里只有一個(gè)根哈希值：交易樹(shù)哩陕，就是區(qū)塊里包含的交易組成的Merkle tree組成的根哈希值。

以太坊的block header里有三個(gè)根哈希值：交易樹(shù)赫舒、狀態(tài)樹(shù)悍及、收據(jù)樹(shù)。

現(xiàn)在講的是狀態(tài)樹(shù)接癌，賬戶(hù)狀態(tài)最后組織成了一個(gè)Merkle tree心赶，他的根哈希值。

這個(gè)根哈希值的作用：

1缺猛、防止篡改

只要根哈希值不變缨叫，整個(gè)樹(shù)的任何部分都沒(méi)有辦法被篡改，也就是說(shuō)每個(gè)賬戶(hù)的狀態(tài)都能保證他是沒(méi)有被篡改過(guò)的荔燎。

2耻姥、Merkle proof

（1）能證明賬戶(hù)的余額是多少

你這個(gè)賬戶(hù)所在的分支自己向上作為Merkle proof發(fā)給輕節(jié)點(diǎn)，輕節(jié)點(diǎn)可以驗(yàn)證你的賬戶(hù)上有多少錢(qián)有咨。

（2）能證明某個(gè)賬戶(hù)是不存在的

之前講過(guò)咏闪，Sorted Merkle tree的一個(gè)作用是能證明non-membership。

這里的證明方法跟Sorted Merkle tree類(lèi)似摔吏。

比如鸽嫂，給一個(gè)地址轉(zhuǎn)賬之前，驗(yàn)證一下全節(jié)點(diǎn)里有沒(méi)有這個(gè)賬戶(hù)信息征讲。說(shuō)的更直白一點(diǎn)据某，證明MPT中某個(gè)鍵值是不存在的。

如果存在的話(huà)诗箍，是在什么樣的分支癣籽，把這個(gè)分支作為Merkle proof發(fā)過(guò)去，可以證明他是不存在的滤祖。

Modified MPT

以太坊中用到的不是原生的MPT筷狼，是Modified MPT，就是對(duì)MPT做一些修改匠童，這些修改不是很本質(zhì)的修改埂材。

舉個(gè)例子（如下圖），有四個(gè)賬戶(hù)（右上角）汤求，為了簡(jiǎn)單起見(jiàn)俏险，地址都比較短，假設(shè)只有7位的地址扬绪，而不是40位竖独，賬戶(hù)狀態(tài)也只顯示出了余額，其他賬戶(hù)狀態(tài)沒(méi)有顯示出來(lái)挤牛。第一個(gè)賬戶(hù)有45個(gè)以太幣莹痢，第二個(gè)賬戶(hù)只有1WEI（這個(gè)是以太坊中最小的計(jì)量單位，1WEI基本上可以忽略不計(jì)）

這個(gè)例子當(dāng)中墓赴，節(jié)點(diǎn)分為三種竞膳。

1、Extension Node（擴(kuò)展節(jié)點(diǎn)）

如果這個(gè)樹(shù)中出現(xiàn)了路徑壓縮就會(huì)有一個(gè)Extension Node竣蹦。

這四個(gè)地址前兩位都是一樣的a7顶猜，所以他的Root（根節(jié)點(diǎn)）就是一個(gè)Extension Node。

shared nibble（nibble：16進(jìn)制數(shù)痘括，一個(gè)nibble就是一個(gè)16進(jìn)制數(shù)）长窄，這里共享的nibble是a7

2、Branch Node（分支節(jié)點(diǎn)）

這里第三位就分開(kāi)了纲菌，有1,7,f挠日，所以就跟了一個(gè)Branch Node。

3翰舌、Leaf Node（葉節(jié)點(diǎn)）

先說(shuō)1嚣潜，這個(gè)1之后就是1355，只有這一個(gè)地址椅贱，就跟了Leaf Node懂算。

這個(gè)7有兩個(gè)地址只冻，連著路徑壓縮d3。

然后再往下3和9分開(kāi)了计技，跟著一個(gè)Branch Node喜德。

下面兩個(gè)Leaf Node，都是7垮媒。

最后一個(gè)f舍悯，就跟著一個(gè)Leaf Node，9365睡雇。

這就是狀態(tài)樹(shù)萌衬。

另外，這個(gè)樹(shù)的根節(jié)點(diǎn)取哈希之后得到的一個(gè)根哈希值它抱，是要寫(xiě)在塊頭里的（左上角）秕豫。

他用的也是哈希指針。比如7這個(gè)位置抗愁，這里存的是下面這個(gè)節(jié)點(diǎn)（extension node）的哈希值馁蒂。如果是普通指針的話(huà)，7這個(gè)位置存的是下面這個(gè)節(jié)點(diǎn)的地址蜘腌。

每次發(fā)布一個(gè)新的區(qū)塊的時(shí)候沫屡，這個(gè)狀態(tài)樹(shù)中，有一些節(jié)點(diǎn)的值會(huì)發(fā)生變化撮珠，這些改變不是在原地改沮脖，而是新建一些分支，原來(lái)的狀態(tài)其實(shí)是保留下來(lái)的芯急。

下面這個(gè)例子當(dāng)中勺届，有兩個(gè)相鄰的區(qū)塊。

Block N Header：State Root就是狀態(tài)樹(shù)的根哈希值娶耍，下面（灰色）顯示的是這棵狀態(tài)樹(shù)免姿。

Block N+1 Header：這個(gè)是新的區(qū)塊的狀態(tài)樹(shù)。

可以看到榕酒，雖然每一個(gè)區(qū)塊都有一個(gè)狀態(tài)樹(shù)胚膊，但是這兩顆樹(shù)的大部分節(jié)點(diǎn)是共享的。

右邊這棵樹(shù)主要都是指向左邊這顆樹(shù)的節(jié)點(diǎn)想鹰，只有那些發(fā)生改變的節(jié)點(diǎn)是需要新建一個(gè)分支紊婉。

這個(gè)例子中，這個(gè)賬戶(hù)是一個(gè)合約賬戶(hù)辑舷，因?yàn)橛蠧ode喻犁，還有Storage。

合約賬戶(hù)的存儲(chǔ)也是由MPT保存下來(lái)的。

這個(gè)存儲(chǔ)其實(shí)也是一個(gè)Key Value Store肢础，維護(hù)的是從這個(gè)變量到這個(gè)變量取值的一個(gè)映射还栓，在以太坊當(dāng)中，也是用的一棵MPT传轰。

所以以太坊中的這個(gè)結(jié)構(gòu)是一個(gè)大的MPT蝙云，包含很多小的MPT，每一個(gè)合約賬戶(hù)的存儲(chǔ)都是一棵小的MPT路召。

上圖中這個(gè)賬戶(hù)的新的區(qū)塊里：

Nonce發(fā)生了變化。

Balance余額也發(fā)生了變化波材。

Code是不變的股淡，所以Codehash指向原來(lái)樹(shù)中那個(gè)節(jié)點(diǎn)。

Storage是變了（存儲(chǔ)下面這個(gè)叫存儲(chǔ)樹(shù)）廷区，在存儲(chǔ)樹(shù)中唯灵，大部分節(jié)點(diǎn)也是沒(méi)有改變。這個(gè)例子當(dāng)中隙轻，只有一個(gè)節(jié)點(diǎn)變了埠帕，這個(gè)整數(shù)變量從29變成了45，所以新建了一個(gè)分支玖绿。

所以敛瓷，系統(tǒng)中每個(gè)全節(jié)點(diǎn)需要維護(hù)的不是一棵MPT，而是每次出現(xiàn)一個(gè)區(qū)塊斑匪，都要新建一個(gè)MPT呐籽，只不過(guò)這些狀態(tài)樹(shù)中，大部分的節(jié)點(diǎn)是共享的蚀瘸，只有少部分發(fā)生變化的節(jié)點(diǎn)要新建分支狡蝶。

問(wèn)：為什么要保留歷史狀態(tài)，為什么不在原地直接改了贮勃？

系統(tǒng)當(dāng)中有時(shí)候會(huì)出現(xiàn)分叉贪惹，臨時(shí)性的分叉是很普遍的。

以太坊把出塊時(shí)間降低到十幾秒之后寂嘉，這種臨時(shí)性的分叉是常態(tài)奏瞬，因?yàn)閰^(qū)塊在網(wǎng)上傳播時(shí)間可能也需要十幾秒。

假設(shè)由有個(gè)分叉垫释，這兩個(gè)節(jié)點(diǎn)同時(shí)獲得記賬權(quán)（如下圖）丝格。

這兩個(gè)分叉最終上面那個(gè)勝出了，下面這個(gè)分叉的節(jié)點(diǎn)該怎么辦棵譬？

這個(gè)時(shí)候就要回滾（roll back）显蝌，就這個(gè)節(jié)點(diǎn)當(dāng)前的狀態(tài)，就接受了下面這個(gè)節(jié)點(diǎn)的狀態(tài)要取消掉，退回到上一個(gè)節(jié)點(diǎn)的狀態(tài)曼尊，然后沿著上面那條鏈往下推進(jìn)酬诀。

有時(shí)候可能要把當(dāng)前狀態(tài)退回到?jīng)]有處理到這個(gè)區(qū)塊中交易的前一個(gè)狀態(tài)。

那怎么實(shí)現(xiàn)回滾呢骆撇？

就是要維護(hù)這些歷史紀(jì)錄瞒御。

這個(gè)跟比特幣還不太一樣，如果是比特幣的話(huà)神郊，他的交易類(lèi)型比較簡(jiǎn)單肴裙，有的時(shí)候可以通過(guò)這種反向操作推算出前一個(gè)狀態(tài)。

比如涌乳，一個(gè)簡(jiǎn)單的轉(zhuǎn)賬交易（如下圖）蜻懦，A轉(zhuǎn)給B10個(gè)BTC，這個(gè)對(duì)賬戶(hù)余額有什么影響呢夕晓？

A的賬戶(hù)上少了10個(gè)比特幣宛乃，B的狀態(tài)多了10個(gè)比特幣。

假如這個(gè)狀態(tài)要回滾了蒸辆，退回到前一個(gè)狀態(tài)征炼，那就把B這個(gè)賬戶(hù)減少10個(gè)比特幣，把A這個(gè)賬戶(hù)加回去10個(gè)比特幣就行了躬贡。

簡(jiǎn)單的轉(zhuǎn)賬交易回滾其實(shí)是比較容易的谆奥。

以太坊中為什么不行？

因?yàn)橐蕴恢杏?b>智能合約逗宜。

智能合約是圖靈完備的雄右，編程功能是很強(qiáng)的。從理論上說(shuō)纺讲，可以實(shí)現(xiàn)很復(fù)雜的功能擂仍，跟比特幣簡(jiǎn)單的腳本還不太一樣。

所以以太坊中如果不保存前面的狀態(tài)熬甚，智能合約執(zhí)行完之后逢渔，想再推算出前面是什么狀態(tài)，這是不可能的乡括，所以要想支持回滾肃廓，必須保存歷史狀態(tài)。

以太坊中代碼的數(shù)據(jù)結(jié)構(gòu)

1诲泌、block header的結(jié)構(gòu)

ParentHash：父區(qū)塊的哈希值盲赊。是區(qū)塊鏈中前一個(gè)區(qū)塊的哈希值，不是區(qū)塊的塊頭的哈希值敷扫。

UncleHash：叔父區(qū)塊的哈希值哀蘑。后面講Ghost協(xié)議的時(shí)候，每個(gè)區(qū)塊還有叔父區(qū)塊。而且后面會(huì)看到绘迁，比較奇怪的一點(diǎn)是合溺，大多數(shù)人表面上看ParentHash，UncleHash是一個(gè)輩分的缀台，但是以太坊中不是這樣的棠赛，這個(gè)Uncle比Parent可能大好多輩分。

Coinbase：是挖出這個(gè)礦的這個(gè)區(qū)塊的礦工的地址膛腐。

--------- 下面這三個(gè)就是本講相關(guān)的三棵樹(shù)的根哈希睛约，以太坊中有三棵樹(shù)：狀態(tài)樹(shù)，交易數(shù)和收據(jù)樹(shù)哲身。

Root：狀態(tài)樹(shù)的根哈希值痰腮。

TxHash：交易樹(shù)的根哈希值（類(lèi)似比特幣中的那個(gè)根哈希值）。

ReceiptHash：收據(jù)樹(shù)的根哈希值律罢。

Bloom：提供一個(gè)高效的查詢(xún)，符合某種條件的交易的執(zhí)行結(jié)果（跟收據(jù)樹(shù)是相關(guān)的）棍丐。

Diffculty：挖礦難度（要根據(jù)需要調(diào)整）

--------- GasLimit和GasUsed是跟汽油費(fèi)相關(guān)的误辑，智能合約要消耗汽油費(fèi)，類(lèi)似于比特幣中的交易費(fèi)歌逢。

GasLimit：單個(gè)區(qū)塊允許的最多gas總量

GasUsed：該交易消耗的總gas數(shù)量

Time：區(qū)塊的大致的產(chǎn)生時(shí)間

---------?MixDigest和Nonce是跟挖礦過(guò)程相關(guān)的巾钉。

nonce：是挖礦時(shí)猜的那個(gè)隨機(jī)數(shù)（類(lèi)似于比特幣的挖礦），以太坊中的挖礦也是要猜很多個(gè)隨機(jī)數(shù)秘案，寫(xiě)在塊頭里的隨機(jī)數(shù)是最后找到的砰苍，符合難度要求的

MixDigest：混合摘要，從nonce這個(gè)隨機(jī)數(shù)經(jīng)過(guò)一些計(jì)算阱高，算出一個(gè)哈希值赚导。

2、區(qū)塊的結(jié)構(gòu)

對(duì)這節(jié)課來(lái)說(shuō)比較相關(guān)的就是前面三個(gè)域：header赤惊，uncles吼旧，transactions

header：就是指向block header的指針

uncles：是指向叔父區(qū)塊的header的指針。而且是個(gè)數(shù)組未舟，因?yàn)橐粋€(gè)區(qū)塊可以有多個(gè)叔父區(qū)塊

transactions：就是這個(gè)區(qū)塊中交易的列表

這個(gè)區(qū)塊在網(wǎng)上發(fā)布的時(shí)候圈暗，發(fā)布的就是這些信息，其實(shí)就是剛剛上面的前三項(xiàng)真正發(fā)布出去裕膀。

狀態(tài)樹(shù)中的value的存儲(chǔ)：RLP

狀態(tài)樹(shù)中保存的是（key员串，value)

key就是地址。講到現(xiàn)在昼扛，主要講的是鍵值寸齐，這個(gè)地址的管理方式。

那么這個(gè)value呢，這個(gè)賬戶(hù)的狀態(tài)呢访忿，是怎么存儲(chǔ)在狀態(tài)樹(shù)當(dāng)中的瞧栗？

實(shí)際上是要經(jīng)過(guò)一個(gè)序列化（RLP）的過(guò)程，然后再存儲(chǔ)海铆。

RLP：Recursive Length Prefix迹恐，遞歸長(zhǎng)度前綴，是一種序列化方法卧斟。特點(diǎn)是簡(jiǎn)單殴边，極簡(jiǎn)主義，越簡(jiǎn)單越好珍语。

Protocal buffer：簡(jiǎn)稱(chēng)Protobuf锤岸，是個(gè)很有名的做序列化的庫(kù)。

跟這些庫(kù)相比板乙，RLP的理念就是越簡(jiǎn)單越好是偷。

它只支持一種類(lèi)型：nested array bytes，嵌套數(shù)組字節(jié)募逞。一個(gè)一個(gè)字節(jié)組成的數(shù)組蛋铆，可以嵌套。

以太坊里的所有的其他類(lèi)型放接，比如整數(shù)刺啦，或者比較復(fù)雜的哈希表，最后都要變成nested array bytes纠脾。

所以實(shí)現(xiàn)RLP要比實(shí)現(xiàn)Protocal buffer簡(jiǎn)單很多玛瘸，因?yàn)殡y的東西，他都不做苟蹈，都推給應(yīng)用層了糊渊。