1、ETH-以太坊概述

比特幣和以太坊是兩種最主要的加密貨幣，比特幣被稱為區(qū)塊鏈1.0，以太坊被稱為區(qū)塊鏈2.0

以太坊在系統(tǒng)設(shè)計上針對比特幣運行過程中出現(xiàn)的問題進(jìn)行了改進(jìn)，比如：

1. 出塊時間，比特幣的區(qū)塊時間是10分鐘，以太坊的出塊時間大幅度降低到了十幾秒，而且為了適應(yīng)這種新的出塊時間，以太坊還設(shè)計了一套基于GHOST的共識機(jī)制
2. 以太坊的另一個改進(jìn)就是挖礦使用的mining puzzle，比特幣的mining puzzle是計算密集型的，比拼的是計算哈希值的算力，這樣造成的結(jié)果是挖礦設(shè)備的專業(yè)化，這樣跟以前宣揚的去中心化的理念是不符合的，所以以太坊設(shè)計的mining puzzle對內(nèi)存的要求就是很高的（memory hard mining puzzle），這樣設(shè)計的目的是限制了ASIC芯片的使用（ASIC resistance）
3. 將來以太坊還會有些革命性的改變，用權(quán)益證明（POS，proof of stake）來替代工作量證明（POW，proof of work）。權(quán)益證明就是不挖礦而是按照類似于股份投票的方法決定下一個區(qū)塊怎么產(chǎn)生
4. 除此之外，以太坊還增加了一個重要的功能，對智能合約（smart contract）的支持

1）、去中心化的貨幣/合約的概念

比特幣實現(xiàn)的是一種去中心化的貨幣，比特幣取得成功之后，很多人就開始思考：除了貨幣可以去中心化，還有什么可以去中心化？以太坊的一個特性就是增加了對去中心化的合約的支持

比特幣（BitCoin）：decentralized currency（去中心化的貨幣），符號是BTC，最小計量單位是Satoshi（一聰），1個比特幣等于1億聰，因為比特幣的創(chuàng)始人名為中本聰（Satoshi Nakamoto）

以太坊（Ethereum）：decentralized contract（去中心化的合約），符號是ETH，它的幣通俗地叫做以太，也叫Ether，最小計量單位是Wei（一偉），是為了致敬密碼學(xué)的先驅(qū)戴偉（Wei Dai）

去中心化的貨幣：

貨幣本來是應(yīng)該由政府發(fā)行的，貨幣的價值建立在政府公信力的基礎(chǔ)上，然后政府通過一些司法手段來維護(hù)貨幣的正常運行。比特幣的出現(xiàn)用技術(shù)手段把政府的這些職能給取代了，通過密碼學(xué)、共識機(jī)制來維護(hù)加密貨幣體系的正常運行

去中心化的合約：

現(xiàn)實生活中，合約的有效性也是應(yīng)該通過司法手段，通過政府來維護(hù)的，比如和人簽一個合同，這個合同如果出現(xiàn)糾紛，通過打官司/法院判決，法院先看一下這個合同是誰簽的，有沒有當(dāng)事人的合法簽名，合同當(dāng)中如何規(guī)定，是誰違反了合同，看看哪一方有錯，對于違約方按照合同中的條款應(yīng)該給予什么樣的處罰，這就是現(xiàn)實生活中的合同，通過司法手段維護(hù)合同的有效性。那么我們能不能也用技術(shù)手段這些司法手段給取代了，這就是以太坊智能合約的設(shè)計目的

如果合同中的內(nèi)容是可以通過程序代碼來實現(xiàn)出來的，那么就可以把代碼放到區(qū)塊鏈上，通過區(qū)塊鏈的不可篡改性來保證代碼的正確運行。當(dāng)然，不是所有的合同內(nèi)容都用編程語言來實現(xiàn)，也不是所有的合同條款都是可以被量化的，但是有一些邏輯比較簡單，比較清晰的合同是可以寫成智能合約的形式

2）、去中心化的貨幣/合約的好處

去中心化的貨幣的好處：

應(yīng)用場景舉例：跨國轉(zhuǎn)賬

比如說從美國轉(zhuǎn)一筆錢到埃及，用法幣（fait currency）是很麻煩的，時間很長，要辦很多手續(xù)，交易費也貴，如果用比特幣轉(zhuǎn)賬，就會好很多，這是比特幣的一個優(yōu)勢。雖然說比特幣每十分鐘才出一個區(qū)塊，有各種各樣不是很完美的地方，但是用比特幣跨國轉(zhuǎn)賬還是比法幣要快很多

去中心化的合約的好處：

應(yīng)用場景舉例：跨國合同簽署

如果合同的簽署方是來自世界各地的，沒有一個統(tǒng)一的司法管轄權(quán)，這個時候用司法手段來維護(hù)合同的有效性比較困難。就像在網(wǎng)上弄一個眾籌，眾籌的參與方來自全國各地，彼此之間不認(rèn)識，打官司也不知道到哪兒去打。這種情況下，如果通過事先寫好的程序代碼來保證每個人都只能按照規(guī)則來執(zhí)行，這是一種比較好的解決方法

就算合同的參與方都在同一個司法管轄權(quán)之內(nèi)的，想通過司法手段來維護(hù)合同的執(zhí)行也是一個比較費時費力的過程，打官司要花好多時間和精力。就算官司贏了，也不一定能拿到錢，還得申請凍結(jié)對方資產(chǎn)，申請強(qiáng)制執(zhí)行之類的。所以最好是用技術(shù)手段保證合同的參與方從一開始就不能違約

智能合約的好處就在于這個代碼一旦發(fā)布到區(qū)塊鏈上，那么區(qū)塊鏈的不可篡改性，只能按照代碼中制定的規(guī)則來執(zhí)行

2、ETH-賬戶

1）、比特幣：基于交易的賬本

比特幣中是用的基于交易的賬本（transaction-based ledger），這種模式下，系統(tǒng)中并沒有顯式的記錄每個賬戶上有多少錢，要根據(jù)UTXO里的信息推算，包括想知道這個人一共總資產(chǎn)有多少個比特幣，就算一下這個人的所有賬戶，就是他有私鑰的那些賬戶在UTXO里面一共有多少個幣就可以了

這種模式的好處是隱私保護(hù)比較好，你有多少錢，可能連你自己都說不清楚，那別人就更不清楚了。但是這樣就帶來一個問題，就使用上比較別扭，跟我們的日常體驗不太一樣

比如，A要轉(zhuǎn)給B 10個比特幣，A要說明這10個幣的來源，其中7個幣是前面某個交易中收到的，另外3個幣是之前另外一個交易收到的，證明幣的來源的合法性。這和我們平時去銀行的體驗是不太一樣的，銀行是你存錢的時候要說明錢的來源，花錢的時候是不用說明每一筆錢是從哪兒來的

另外一個比較別扭的地方，在前面交易中收到一些幣，將來要花的時候，必須要一次性都花出去，不能只花一部分

A轉(zhuǎn)給B 10個比特幣，將來B要轉(zhuǎn)給C 3個比特幣，幣的來源是A轉(zhuǎn)給B的這個交易。如上圖這樣處理，剩下的7個比特幣會當(dāng)做交易費給花出去了

如上圖，這個時候必須要把剩下的7個比特幣轉(zhuǎn)回給自己

很多比特幣錢包可以自動生成接收余額的地址，每次交易換一個新地址，也是有利于隱私保護(hù)的，但同樣跟我們的日常生活習(xí)慣不太一樣。比如說，銀行當(dāng)中，別人轉(zhuǎn)給你10萬塊錢，你要把3萬塊錢轉(zhuǎn)出去，剩下7萬塊錢就不用管，就放在賬戶上就行了。問題在于比特幣系統(tǒng)中，沒有顯式的維護(hù)基于賬戶的交易概念

2）、以太坊：基于賬戶的賬本

以太坊采用的是基于賬戶的模型（account-based ledger），這種模型跟銀行賬戶是比較相似的，系統(tǒng)中要顯式的記錄每個賬戶上有多少個以太幣

比如，A要轉(zhuǎn)給B 10個以太幣，這個交易的合法性只要檢查一下A賬戶上有沒有足夠的錢就行了。比如A賬戶上有100個以太幣，要轉(zhuǎn)10個給B，這就沒問題，不用說明這100個以太幣中是具體把哪10個轉(zhuǎn)給了B，不用說明幣的來源，是來自之前哪個交易。將來B要轉(zhuǎn)給C 3個以太幣也是可以的，不用把剩下的轉(zhuǎn)給他自己，因為有顯式余額的概念，所以剩下的幣就直接放在賬戶上就行了。用于說明幣的來源的哈希指針也不用了

比特幣中面臨的挑戰(zhàn)是雙花攻擊（double spending attack），花錢的人不誠實，以前花過的錢想再花一次

基于賬戶模式的好處是對double spending attack有天然的防御作用，因為不用管幣的來源，每花掉一次錢，就從你的賬戶上扣掉，花兩次就扣兩次

以太坊中面臨的挑戰(zhàn)是重放攻擊（replay attack），收錢的人不誠實，別人已經(jīng)給他轉(zhuǎn)過錢了，他想再轉(zhuǎn)一次

A把自己轉(zhuǎn)給B 10個以太幣的轉(zhuǎn)賬交易發(fā)布到網(wǎng)絡(luò)上，過一段時間之后，這個交易被寫到區(qū)塊鏈里了，A就以為轉(zhuǎn)賬交易完成了。假設(shè)B是有惡意的，把這個交易在網(wǎng)上重新廣播一遍，其他節(jié)點以為是個新的轉(zhuǎn)賬就把A的錢扣了2次

解決方案：

加一個計數(shù)器（nonce），記錄一下這個賬戶有史以來一共發(fā)布過多少交易，然后轉(zhuǎn)賬的時候，交易次數(shù)要成為交易內(nèi)容的一部分，一起包含進(jìn)去，都是受到發(fā)布交易的簽名的保護(hù)

如上圖，A轉(zhuǎn)給B 10個以太幣，A一共發(fā)布過20個交易，這是第21個，所以寫上nonce=21，然后整個內(nèi)容寫上A的簽名

把這個交易發(fā)布到網(wǎng)上，因為有簽名的保護(hù)，所以nonce的值，別人是改不了的。系統(tǒng)中的每個節(jié)點維護(hù)A這個狀態(tài)，不僅要維護(hù)A賬戶上的錢（balance），還要維護(hù)nonce的值，一開始nonce=0，每次收到A發(fā)布的一個交易，nonce+1

這個節(jié)點一開始A的nonce=20，然后現(xiàn)在發(fā)布這個交易，這個節(jié)點一看，這個交易是合法的，是可以執(zhí)行的，同時更新一下nonce=21。以后如果有人重放這個交易，這個節(jié)點一看，這個nonce已經(jīng)是21了，已經(jīng)被執(zhí)行過了，就不會再執(zhí)行一遍了

3）、以太坊賬戶的分類

以太坊中有兩類賬戶：外部賬戶、合約賬戶

externally owned account（外部賬戶）：

外部賬戶是由公私鑰控制的，本地產(chǎn)生一個公私鑰對，私鑰掌握賬戶的控制權(quán)（類似于比特幣中的賬戶），也叫普通賬戶

外部賬戶的狀態(tài)：

• balance（賬戶余額）
• nonce（計數(shù)器）

smart contract account（合約賬戶）：

合約賬戶不是通過公私鑰對控制的

合約賬戶的狀態(tài)：

• balance（賬戶余額）
• nonce（計數(shù)器）
• code（代碼）
• storage（相關(guān)狀態(tài)存儲，包括每個變量的取值）

一個合約可以調(diào)用另外一個合約，所以要通過nonce值記錄一下調(diào)用的次數(shù)

合約賬戶不能主動發(fā)起一個交易，以太坊中規(guī)定，所有的交易只能由外部賬戶發(fā)起。外部賬戶發(fā)起一個交易如果調(diào)用了一個合約賬戶，這個合約賬戶可以發(fā)送一個message調(diào)用另外一個合約，但是他不能自己平白的發(fā)起一個交易

創(chuàng)建合約會返回一個地址，知道這個合約的地址，就可以調(diào)用這個合約，調(diào)用的過程當(dāng)中狀態(tài)會發(fā)生變化，代碼（code）不會變，存儲（storage）會變

4）、為什么要設(shè)計這樣一種新的賬戶模式？

以太坊的創(chuàng)始人叫Vitalik，是個19歲的小孩，他當(dāng)初創(chuàng)建以太坊的時候，比特幣已經(jīng)有比較成熟的代碼可以作為參考，為什么不用比特幣已有的代碼，而要另弄一套？為什么不直接在比特幣系統(tǒng)設(shè)計上改進(jìn)，比如改出塊時間、mining puzzle，為什么非要改賬戶體系？

比特幣基于交易模型的一個好處是隱私保護(hù)，但是以太坊要支持的是智能合約，對于合約來說，要求參與者有比較穩(wěn)定的身份

這跟日常生活當(dāng)中是比較類似的，比如說，你跟某個人簽個合同，如果說你跟他簽合同的時候，他是一個身份，簽完之后，他身份變了，你找不到了，那這就有問題了，也有可能突然冒出了另外一個人，說他當(dāng)初就是跟你一塊簽合同的，只不過換了一個身份，這就給合同的執(zhí)行帶來一些困難。將來出現(xiàn)糾紛的時候，你也是需要知道這個合同當(dāng)初是跟誰簽的

現(xiàn)在有人提出來用智能合約實現(xiàn)一些金融衍生品（financial derivative）

比如期權(quán)/期貨，往合約里投一筆錢，預(yù)測未來的價格走勢，如果預(yù)測正確，給你一些收益，把錢還給你。但問題是，如果你投錢的這個賬戶，投完錢就變了，那到時候怎么把錢還給你呢？

這個不光是對于外部賬戶有這個問題。合約賬戶的問題就更嚴(yán)重了，如果你投錢投到一個合約賬戶，投完之后合約賬戶的地址變了，找不到就麻煩了

所以以太坊創(chuàng)建這個系統(tǒng)的時候，考慮了過去的一些已有的模型的利弊得失，最終沒有采用比特幣中基于交易的模式，而是采用了基于賬戶模式

這個從目前的狀況來看，還是比較合適的一個決策，以太坊的賬戶是希望保持穩(wěn)定的，無論是個人賬戶還是合約賬戶。如果你有隱私保護(hù)的需要，同樣可以創(chuàng)建很多個賬戶，根據(jù)情況使用不同的賬戶進(jìn)行不同的交易

3、ETH-狀態(tài)樹

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

要完成的功能是從賬戶地址到賬戶狀態(tài)的映射：addr->state

addr：賬戶地址，以太坊中用的賬戶地址是160位，也就是20個字節(jié)，一般表示成40個十六進(jìn)制的數(shù)

state：外部賬戶和合約賬戶的狀態(tài)，包括余額、交易次數(shù)，合約賬戶還包括代碼、存儲

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

1）、思考如何組織賬戶的數(shù)據(jù)結(jié)構(gòu)？

1）方案一： 用哈希表實現(xiàn)

從直觀上看，像一個很典型的key-value pair，給出一個賬戶地址，要找到相應(yīng)的賬戶狀態(tài)，所以一個直觀的想法是用哈希表實現(xiàn)

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

問題：如果用這個哈希表要提供Merkle proof怎么提供？

比如說你要跟一個人簽合同，希望他能證明一下他有多少錢，怎么提供證明呢？

一種方法是把哈希表中的元素組織成一個Merkle Tree，然后算出一個根哈希值，這個根哈希值存在block header里，只要根哈希值是正確的，就能保證底下的樹不會被篡改

如果有新區(qū)塊發(fā)布怎么辦？新區(qū)塊中包含新的交易，執(zhí)行這個交易必然會使哈希表的內(nèi)容發(fā)生變化，發(fā)布下一個區(qū)塊的時候，再重新把哈希表中的內(nèi)容（key：賬戶地址，value：賬戶狀態(tài)）組織成一個Merkle Tree嗎？

這個代價太大了。實際上，真正發(fā)生變化的賬戶狀態(tài)只是一小部分，因為只有那個區(qū)塊里的交易所關(guān)聯(lián)的賬戶才會發(fā)生變化，大多數(shù)賬戶的狀態(tài)是不變的。所以每次都重新構(gòu)造一次Merkle Tree，這個代價是很大的

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

比特幣是把區(qū)塊里包含的交易組織成一個Merkle Tree，那區(qū)塊中的交易每次發(fā)布一個新的區(qū)塊又有一系列新的交易，所以比特幣中的Merkle Tree是immutable（不變的）的，每次發(fā)布一個新的區(qū)塊對應(yīng)一個Merkle Tree，然后這棵Merkle Tree構(gòu)建完之后是不會再改的，下次再發(fā)布一個新的區(qū)塊再構(gòu)建一個新的Merkle Tree

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

這里如果采用這種方法會是什么情況？

是要把所有的以太坊賬戶一起構(gòu)成一個Merkle Tree，這個就比剛才講的幾百、幾千個交易要高出好幾個數(shù)量級，相當(dāng)于每次發(fā)布一個區(qū)塊要把所有的賬戶遍歷一遍構(gòu)建出一個Merkle Tree，下次再有一個區(qū)塊，再把所有的賬戶遍歷一遍，再構(gòu)建出一個Merkle Tree

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

結(jié)論：不可行，因為每次構(gòu)建Merkle Tree的代價太大

如果每個全節(jié)點在本地維護(hù)一個哈希表，然后需要構(gòu)建Merkle Tree的時候構(gòu)建出Merkle Tree來，然后根哈希值放到區(qū)塊頭里，這個方法是不行的。哈希表本身的效率是挺好的，插入、更改效率都很好，但是每次構(gòu)建Merkle Tree的代價太大了

2）方案二：直接用一個Merkle Tree把所有的賬戶都放進(jìn)去

不要哈希表了，直接用一個Merkle Tree把所有的賬戶都放進(jìn)去，要改的時候直接在Merkle Tree里改。因為每個區(qū)塊更新的只是一小部分賬戶，所以改的時候只是Merkle Tree里的一小部分

問題1：Merkle Tree沒有提供一個高效的查找、更新的方法

比特幣中的Merkle Tree最底下一層是transaction，然后哈希值放到上面節(jié)點里，兩兩結(jié)合，然后再取一個哈希往上整。Merkle Tree沒有提供一個快速查找，更新的方法

問題2：直接把賬戶放到Merkle Tree里，這個Merkle Tree要不要排序？（Sorted Merkle Tree）

如果不排序會怎么樣？

1. 查找速度會慢
2. 這些賬戶組成了這棵Merkle Tree，葉節(jié)點是這些賬戶的信息，如果不規(guī)定這些賬戶在葉節(jié)點出現(xiàn)的順序，那么這樣構(gòu)建出來的Merkle Tree不是唯一的

系統(tǒng)中有很多全節(jié)點，每個全節(jié)點按照自己的某個順序，比如說他聽到某個交易的順序構(gòu)建一個Merkle Tree，那么葉結(jié)點的順序是亂的，每個節(jié)點都是自己決定的，最后構(gòu)建出的Merkle Tree是不一樣的，算出的根哈希值也是不一樣的

比特幣中的Merkle Tree也是不排序的，那為什么比特幣就沒有問題呢？

因為比特幣中的每個全節(jié)點收到的交易的順序也是不一樣的，理論上說構(gòu)建的Merkle Tree的根哈希值也是不一樣的

比特幣中，每個節(jié)點在本地組裝一個候選區(qū)塊，這個節(jié)點自己決定哪些交易、以什么順序打包進(jìn)這個區(qū)塊里，然后通過挖礦去競爭記賬權(quán)。如果他沒有搶到記賬權(quán)，他的任何決定其他人沒必要知道；只有他有記賬權(quán)，且發(fā)布區(qū)塊后最終成為被大家接受的區(qū)塊，那么，這個順序就是發(fā)布這個區(qū)塊的節(jié)點確定的

也就是說，比特幣中雖然也沒用排序的Merkle Tree，但是順序是唯一的，是由發(fā)布區(qū)塊的那個節(jié)點確定的

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

如果以太坊也這么做的話，需要把賬戶的狀態(tài)發(fā)布到區(qū)塊里。也可以說是每個全節(jié)點自己決定怎么把賬戶組織成一個Merkle Tree，算出跟哈希值、挖出礦，但要怎么讓別人知道這個順序，你得把這個Merkle Tree發(fā)布到區(qū)塊里。但發(fā)布的是所有賬戶的狀態(tài)，不是交易，這兩者差好幾個數(shù)量級，比特幣發(fā)布一個區(qū)塊只需要幾百、幾千個交易

結(jié)論：不可行，不排序的Merkle Tree是不行的

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

3）方案三：用Sorted Merkle Tree

問題：新增一個賬戶怎么辦？

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

新產(chǎn)生一個賬戶，對外發(fā)生了交互，我需要把他加入到我的數(shù)據(jù)結(jié)構(gòu)里，這是沒錯的，但問題是，這個加入的代價有多大？

可能大半棵Merkle Tree需要重構(gòu)，這個代價太大了

結(jié)論：不可行，用Sorted Merkle Tree，插入、刪除代價都太大

而且，區(qū)塊鏈?zhǔn)遣豢纱鄹牡?，是說加?xùn)|西容易，刪東西難。以太坊中沒有顯式地刪除賬戶的操作，有的賬戶上就一點錢，就一兩個Wei，也不能把他刪掉

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

1）Trie（字典樹，前綴樹）

以太坊中是用一個叫MPT（Merkle Patricia Tree）的結(jié)構(gòu)，講這個之前先講一個簡單的數(shù)據(jù)結(jié)構(gòu)

Trie也是一種key-value對，一般來說key用字符串用的比較多，比如說一些單詞排成一個Trie的數(shù)據(jù)結(jié)構(gòu)

舉例：general、genesis（創(chuàng)世紀(jì)塊，區(qū)塊鏈的第一個區(qū)塊）、go、god、good

上圖就是一個Trie的結(jié)構(gòu)，這幾個單詞都是以G開頭的，然后第二個字母就開始分裂了，左邊是E，右邊是O。左邊這前兩個單詞都是N和E，然后下面再分開，R和S，然后是后三個字母。右邊這個分支，O這個分支，Go就已經(jīng)結(jié)束了，從這個可以看到單詞可能在Trie的中間節(jié)點結(jié)束，然后左邊是D，右邊是O，左邊變成了God，右邊下來是Good

Trie樹可以利用字符串的公共前綴來節(jié)約存儲空間。如果系統(tǒng)中存在大量字符串且這些字符串基本沒有公共前綴，則相應(yīng)的Trie樹將非常消耗內(nèi)存，這也是Trie樹的一個缺點

特點1：Trie的每個節(jié)點的分叉數(shù)目取決于key值里每個元素的取值范圍

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

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

特點2：Trie的查找效率取決于key的長度。鍵值越長，查找需要訪問內(nèi)存的次數(shù)就越多

在這個例子當(dāng)中，不同的單詞鍵值長度是不同的

在以太坊中，所有鍵值都是40，因為地址都是40位十六進(jìn)制的數(shù)

比特幣和以太坊的地址是不通用的，兩個地址的格式長度都是不一樣的。但有一點是類似的，以太坊中的地址也是公鑰經(jīng)過轉(zhuǎn)換得來的。其實就是公鑰取哈希，然后前面的不要，只要后面這部分，就得到一個160bit的地址

特點3：只要兩個地址不一樣，最后肯定映射到樹中的不同分支，所以Trie是不會出現(xiàn)碰撞的

特點4：不同的節(jié)點，不論按照什么順序插入這些賬戶，最后構(gòu)造出來的樹是一樣的

前面講Merkle Tree，如果不排序的話，一個問題是賬戶插入到Merkle Tree 的順序不一樣，得到的樹的結(jié)構(gòu)也不一樣

那Trie呢？比如上圖中的這五個單詞，換一個順序插到這個樹里面，得到的是一個不同的樹嗎？其實是一樣的，只要給定的輸入不變，無論輸入怎么打亂重排，最后插入到Trie當(dāng)中，得到的樹是一樣的

特點5：更新操作的局部性很好

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

Trie的局部性呢？比如在上圖中，我要更新genesis這個key對應(yīng)的value（這個圖當(dāng)中只畫出了key，沒有畫出value），只要訪問genesis的那個分支，其他分支不用訪問的，也不用遍歷整棵樹

缺點：存儲浪費

比如在上圖中左邊分支都只有一個子節(jié)點，對于這種一脈單傳的情況，如果能把節(jié)點進(jìn)行合并，那么可以減小存儲的開銷，同時也提高了查找的效率，不用一次一個一個的往下找了

那么就引入了Patricia Tree，也有人寫成Patricia Trie，是經(jīng)過路徑壓縮的前綴樹，有時候也叫壓縮前綴樹

2）Patricia Tree/Patricia Trie

Trie中的例子進(jìn)行路徑壓縮就變成上圖的樣子?？梢钥吹剑珿下面還是E和O進(jìn)行分叉，E下面之后跟的都是NE，再往下就是E和S分叉，然后后面都和在一起了，右邊的分支也是一樣的

這樣壓縮之后有什么好處？直觀上看，這個高度明顯縮短了，訪問內(nèi)存的次數(shù)會大大減少，效率提高了

注意：對于Patricia Tree來說，新插入一個單詞時，原來壓縮的路徑可能需要擴(kuò)展開

比如這個例子中，加入geometry，左邊的分支就不能那樣壓縮了

路徑壓縮在什么情況下效果比較好？鍵值分布比較稀疏的時候，路徑壓縮效果比較好

比如說，這個例子當(dāng)中是用英文單詞，假設(shè)每個單詞都很長，但是一共沒有幾個單詞，舉例：misunderstanding、decentralization（去中心化的）、disintermediation（去中間商，非中介化，intermediaries：中間商）

這三個單詞插入到一個普通的Trie里面就成了下圖的樣子。可以看到這樣的結(jié)構(gòu)效率是比較低的，基本上是一條線了

如果用Patricia Tree的話，如下圖

這個樹的高度明顯縮短了。所以鍵值分布比較稀疏的時候，路徑壓縮效果比較好

以太坊中鍵值是不是稀疏的呢？

以太坊中鍵值是地址，地址是160位的，地址空間有$2^{160}$，這是一個非常非常大的數(shù)。如果設(shè)計一個計算機(jī)程序的算法，需要進(jìn)行運算的次數(shù)是$2^{160}$，那這個在所有人的有生之年都不可能算出來，全世界的以太坊的賬戶數(shù)目加在一起也遠(yuǎn)遠(yuǎn)沒有這么大，跟這個數(shù)比，是微乎其微的

為什么要弄這么稀疏，不把地址長度縮短一點，這樣訪問效率也快，也沒必要那么稀疏了？

以太坊中普通賬戶跟比特幣的創(chuàng)建方法是一樣的，沒有一個中央的節(jié)點，就每個用戶獨立創(chuàng)建賬戶。在本地產(chǎn)生一個公私鑰對，就是一個賬戶

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

這種可能性是存在的，但是這個概率比地球爆炸還要小。怎么達(dá)到這么小的概率，就是地址要足夠長，分布足夠稀疏，才不會產(chǎn)生碰撞。這個可能看上去有點浪費，但是這是去中心化的系統(tǒng)防止賬戶沖突的唯一辦法。所以以太坊地址分布非常稀疏的，所以比較適合使用Patricia Tree

3）MPT（Merkle Patricia Tree）

Merkle Tree和Binary Tree的區(qū)別：

就是區(qū)塊鏈與普通鏈表的區(qū)別，把普通指針換成了哈希指針

Merkle Patricia Tree和Patricia Tree的區(qū)別：

所有的賬戶組織成一個Patricia Tree，用路徑壓縮提高效率，然后把普通指針換成哈希指針，所以就可以計算出一個根哈希值。這個跟哈希值也是寫在block header里面

比特幣的block header里只有一個根哈希值：交易樹，就是區(qū)塊里包含的交易組成的Merkle Tree組成的根哈希值

以太坊的block header里有三個根哈希值：交易樹、狀態(tài)樹、收據(jù)樹

賬戶狀態(tài)最后組織成了一個Merkle Patricia Tree，狀態(tài)樹的根哈希值的作用：

作用1：防止篡改

只要根哈希值不變，整個樹的任何部分都沒有辦法被篡改，也就是說每個賬戶的狀態(tài)都能保證是沒有被篡改過的

作用2：Merkle proof

1）能證明賬戶的余額是多少

你這個賬戶所在的分支自己向上作為Merkle proof發(fā)給輕節(jié)點，輕節(jié)點可以驗證你的賬戶上有多少錢

2）能證明某個賬戶是不存在的

Sorted Merkle Tree的一個作用是能證明non-membership，這里的證明方法跟Sorted Merkle Tree類似

比如，給一個地址轉(zhuǎn)賬之前，驗證一下全節(jié)點里有沒有這個賬戶信息。說的更直白一點，證明MPT中某個鍵值是不存在的

如果存在的話，是在什么樣的分支，把這個分支作為Merkle proof發(fā)過去，可以證明他是不存在的

4）Modified MPT

以太坊中用到的不是原生的MPT，是Modified MPT，就是對MPT的結(jié)構(gòu)做一些修改，這些修改不是很本質(zhì)的修改

上圖是Modified MPT的案例，右上角有四個賬戶，為了簡單起見，賬戶地址都比較短，假設(shè)只有7位的地址，而不是40位，賬戶狀態(tài)也只顯示出了余額，其他賬戶狀態(tài)沒有顯示出來。第一個賬戶有45個以太幣，第二個賬戶只有1WEI（這個是以太坊中最小的計量單位，1WEI基本上可以忽略不計）

這個案例當(dāng)中，節(jié)點分為三種：

Extension Node（擴(kuò)展節(jié)點）：

如果這個樹中出現(xiàn)了路徑壓縮就會有一個Extension Node，這四個地址前兩位都是一樣的a7，所以Root（根節(jié)點）就是一個Extension Node，shared nibble（nibble：16進(jìn)制數(shù)，一個nibble就是一個16進(jìn)制數(shù)），這里共享的nibble是a7

Branch Node（分支節(jié)點）：

案例中第三位就分開了，有1、7、f，所以就跟了一個Branch Node

Leaf Node（葉節(jié)點）：

先說1，這個1之后就是1355，只有這一個地址，就跟了Leaf Node。這個7有兩個地址，連著路徑壓縮d3，然后再往下3和9分開了，跟著一個Branch Node，下面兩個Leaf Node，都是7。最后一個f，就跟著一個Leaf Node：9365

另外，這個樹的根節(jié)點取哈希之后得到的一個根哈希值，是要寫在塊頭里的（左上角）

用的也是哈希指針。比如7這個位置，這里存的是下面這個節(jié)點（extension node）的哈希值。如果是普通指針的話，7這個位置存的是下面這個節(jié)點的地址

每次發(fā)布一個新的區(qū)塊的時候，狀態(tài)樹中有一些節(jié)點的值會發(fā)生變化，這些改變不是在原地改，而是新建一些分支，原來的狀態(tài)其實是保留下來的

上面這個例子中，有兩個相鄰的區(qū)塊：

Block N Header：State Root就是狀態(tài)樹的根哈希值，下面顯示的是這棵狀態(tài)樹

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

可以看到，雖然每一個區(qū)塊都有一個狀態(tài)樹，但是這兩棵樹的大部分節(jié)點是共享的。右邊這棵樹主要都是指向左邊這棵樹的節(jié)點，只有那些發(fā)生改變的節(jié)點是需要新建一個分支

這個例子中，這個賬戶是一個合約賬戶，因為有Code，還有Storage合約賬戶的存儲也是由MPT保存下來的。這個存儲其實也是一個Key Value Store，維護(hù)的是從這個變量到這個變量取值的一個映射，在以太坊當(dāng)中，也是用的一棵MPT。所以以太坊中的這個結(jié)構(gòu)是一個大的MPT，包含很多小的MPT，每一個合約賬戶的存儲都是一棵小的MPT

上圖中這個賬戶的新的區(qū)塊里：Nonce和Balance發(fā)生了變化，Code是不變的，所以Codehash指向原來樹中那個節(jié)點，Storage是變了的（存儲下面這個叫存儲樹），在存儲樹中，大部分節(jié)點也是沒有改變。這個例子當(dāng)中，只有一個節(jié)點變了，這個整數(shù)變量從29變成了45，所以新建了一個分支

所以，系統(tǒng)中每個全節(jié)點需要維護(hù)的不是一棵MPT，而是每次出現(xiàn)一個區(qū)塊，都要新建一個MPT，只不過這些狀態(tài)樹中，大部分的節(jié)點是共享的，只有少部分發(fā)生變化的節(jié)點要新建分支

為什么要保留歷史狀態(tài)，為什么不在原地直接改了？

系統(tǒng)當(dāng)中有時候會出現(xiàn)分叉，臨時性的分叉是很普遍的。以太坊把出塊時間降低到十幾秒之后，這種臨時性的分叉是常態(tài)，因為區(qū)塊在網(wǎng)上傳播時間可能也需要十幾秒

如上圖，有個分叉，這兩個節(jié)點同時獲得記賬權(quán)。這兩個分叉最終上面那個勝出了，下面這個分叉的節(jié)點這個時候就要回滾（roll back），就是這個節(jié)點當(dāng)前的狀態(tài)，就接受了下面這個節(jié)點的狀態(tài)要取消掉，退回到上一個節(jié)點的狀態(tài)，然后沿著上面那條鏈往下推進(jìn)

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

那怎么實現(xiàn)回滾呢？

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

這個跟比特幣還不太一樣，如果是比特幣的話，交易類型比較簡單，有的時候可以通過這種反向操作推算出前一個狀態(tài)。如果是一個簡單的轉(zhuǎn)賬交易，A轉(zhuǎn)給B 10個比特幣，這個對賬戶余額有什么影響呢？A的賬戶上少了10個比特幣，B的狀態(tài)多了10個比特幣。假如這個狀態(tài)要回滾，退回到前一個狀態(tài)，那就把B這個賬戶減少10個比特幣，把A這個賬戶加回去10個比特幣就行了。簡單的轉(zhuǎn)賬交易回滾其實是比較容易的

以太坊中為什么不行？因為以太坊中有智能合約。智能合約是圖靈完備的，編程功能是很強(qiáng)的。從理論上說，可以實現(xiàn)很復(fù)雜的功能，跟比特幣簡單的腳本還不太一樣。以太坊中如果不保存前面的狀態(tài)，智能合約執(zhí)行完之后，想再推算出前面是什么狀態(tài)，這是不可能的，所以要想支持回滾，必須保存歷史狀態(tài)

3）、以太坊的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)

1）block header的結(jié)構(gòu)

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

extblock是區(qū)塊在網(wǎng)上發(fā)布的信息，就是block中的前三項會真正發(fā)布出去

4）、狀態(tài)樹中的value的存儲：RLP

狀態(tài)樹中保存的是key value pair對。key就是地址，前面主要講的是鍵值，這個地址的管理方式

那么這個value呢，這個賬戶的狀態(tài)呢，是怎么存儲在狀態(tài)樹當(dāng)中的呢？實際上是要經(jīng)過一個序列化（RLP）的過程，然后再存儲

RLP：Recursive Length Prefix，遞歸長度前綴，是一種序列化方法。特點是簡單，極簡主義，越簡單越好

Protocal buffer：簡稱Protobuf，是個很有名的做序列化的庫

跟這些庫相比，RLP的理念就是越簡單越好。它只支持一種類型：nested array bytes，嵌套數(shù)組字節(jié)。一個一個字節(jié)組成的數(shù)組，可以嵌套。以太坊里的所有的其他類型，比如整數(shù)或者比較復(fù)雜的哈希表，最后都要變成nested array bytes

所以實現(xiàn)RLP要比實現(xiàn)Protocal buffer簡單很多，因為難的東西，都推給應(yīng)用層了

4、ETH-交易樹和收據(jù)樹

1）、交易樹和收據(jù)樹

每次發(fā)布一個區(qū)塊的時候，區(qū)塊中所包含的交易會組織成一個交易樹，也是一棵Merkle Tree，跟比特幣中的情況是類似的

此外，以太坊還增加了一個收據(jù)樹，每個交易執(zhí)行完之后會形成一個收據(jù)，記錄交易的相關(guān)信息，交易樹和收據(jù)樹上的節(jié)點是一一對應(yīng)的。由于以太坊智能合約執(zhí)行較為復(fù)雜，通過增加收據(jù)樹，便于快速查詢執(zhí)行結(jié)果

從數(shù)據(jù)結(jié)構(gòu)上，交易樹和收據(jù)樹都是MPT（Merkle Patricia Tree），而比特幣中都采用普通的Merkle Tree。以太坊中可能就僅僅是為了三棵樹代碼復(fù)用好所以這樣設(shè)計的

MPT的好處是支持查找操作，可以通過鍵值從頂向下沿著這個樹進(jìn)行查找。對于狀態(tài)樹來說，查找的鍵值就是這個賬戶的地址；對于交易樹和收據(jù)樹來說，查找的鍵值是這個交易在發(fā)布的區(qū)塊中的序號，交易的排列順序是由發(fā)布區(qū)塊的那個節(jié)點決定的

這三棵樹有一個重要的區(qū)別：交易樹和收據(jù)樹都是只把當(dāng)前發(fā)布的這個區(qū)塊里的交易組織起來的，而狀態(tài)樹是把系統(tǒng)中所有賬戶的狀態(tài)都要包含進(jìn)去，不管這些賬戶跟當(dāng)前區(qū)塊的交易有沒有什么關(guān)系

多個區(qū)塊的狀態(tài)樹是共享節(jié)點的，每次新發(fā)布一個區(qū)塊的時候，只有這個區(qū)塊中的交易改變了狀態(tài)的那些節(jié)點需要新建一個分支，其他節(jié)點都是沿用原來狀態(tài)樹上的節(jié)點。而每個區(qū)塊的交易樹和收據(jù)樹都是獨立的，是不會共享節(jié)點的，一個區(qū)塊跟另一個區(qū)塊發(fā)布的交易本身也認(rèn)為是獨立的

交易樹和收據(jù)樹的用途：

1. 向輕節(jié)點提供Merkle proof。像比特幣當(dāng)中，交易樹可以證明某個交易被打包到某個區(qū)塊里面，可以向輕節(jié)點提供這樣的Merkle proof，收據(jù)樹也是類似的，要證明某個交易的結(jié)果，也可以在收據(jù)樹里面提供一個Merkle proof
2. 以太坊還支持一些更加復(fù)雜的查詢操作。比如說，想找到過去十天當(dāng)中，所有跟某個智能合約有關(guān)的交易，一種方法是把過去十天產(chǎn)生的所有區(qū)塊都掃描一遍，看看其中有哪些交易是和智能合約相關(guān)的，但是這種方法的復(fù)雜度較高，而且對于輕節(jié)點來說，實際上，輕節(jié)點沒有交易列表，只有一個塊頭的信息，所以也沒有辦法通過掃描所有交易列表的方法來找到符合這個查詢條件的交易。與之類似的一些查詢，比如說，找到過去十天中所有的眾籌事件或者所有的發(fā)行新幣的事件，這些都是需要一個比較高效的方法才能支持

2）、bloom filter（布隆過濾器）

以太坊中引入了bloom filter，bloom filter支持比較高效的查找某個元素是不是在一個比較大的集合里面

比如說有一個集合，里面有很多元素，現(xiàn)在想知道某個指定的元素是不是在這個集合里

一個最笨的方法是，把這集合里面的元素遍歷一遍，看看有沒有想找的那個元素，這個復(fù)雜度是線性的，另外有一個前提是得有足夠得存儲來保存整個集合的元素，對于輕節(jié)點來說，輕節(jié)點沒有這個交易列表，沒有整個集合的元素信息，所以這種方法是用不了的

bloom filter用一個很巧妙的思想給這個大的、包含很多元素的集合計算出一個很緊湊的摘要

如上圖，這個例子當(dāng)中有一個（a,b,c）的集合，要計算出一個digest，底下是一個向量，這個向量初始的時候都是零

然后有一個哈希函數(shù)H，把每一個元素映射到向量中的某個位置。比如說a這個元素，取哈希之后，映射到相應(yīng)位置，把這個位置的元素從0變成1。然后，b和c也映射到相應(yīng)的位置。就是把每個元素都取哈希，找到向量中的對應(yīng)位置，然后把它置成1，所有元素都處理完了，得到這個向量就是原來集合的一個摘要，這個摘要比原來的集合要小很多，這個例子當(dāng)中用128bits就可以代表了

摘要的用處：比如說有一個元素d，想知道這個d元素是不是在這個集合里，但是這個集合本身我們不一定能夠保存下來

可以用這個哈希函數(shù)H對d取哈希值，取完之后發(fā)現(xiàn)映射到一個值為0的位置，說明d這個元素一定不在這集合里

假設(shè)取完哈希，映射到一個值為1的位置，有可能確實是集合中的元素，d=b，也有可能不在這個集合里，而是出現(xiàn)了哈希碰撞，恰好映射到了跟集合某個元素一樣的位置。所以用bloom filter要注意，有可能會出現(xiàn)false positive，但是不會出現(xiàn)false negative，就是可能出現(xiàn)誤報，但是不會出現(xiàn)漏報，元素在里面一定說在里面，元素不在里面也有可能說在里面（或者是說，bloom filter說某個元素在，可能會被誤判，bloom filter說某個元素不在，那么一定不在）

bloom filter有各種各樣的變種，比如說，解決這樣的哈希碰撞，有的bloom filter的設(shè)計用的不是一個哈希函數(shù)，而是一組哈希函數(shù)，每個哈希函數(shù)獨立的把這個元素映射到這個向量中的一個位置，用一組哈希函數(shù)的好處是如果出現(xiàn)哈希碰撞，那么一般來說，不會所有的哈希函數(shù)都出現(xiàn)哈希碰撞

bloom filter不支持刪除操作，比如把a(bǔ)刪掉了，對應(yīng)的向量1要不要改，如果改成0的話，集合中可能有另外一個元素也映射到這個位置（哈希碰撞是有可能的），所以簡單的bloom filter是不支持刪除操作的。如果要支持刪除操作，這個地方就不能是0和1了，得改成一個計數(shù)器，記錄這個位置有多少個元素映射過來，而且還要考慮到計數(shù)器會不會溢出，這樣數(shù)據(jù)結(jié)構(gòu)就復(fù)雜得多了，和當(dāng)初設(shè)計bloom filter的初衷是相違背的

3）、以太坊中bloom filter的用途

每個交易執(zhí)行完之后會形成一個收據(jù)，這個收據(jù)里面就包含一個bloom filter，記錄交易的類型、地址等其他信息，發(fā)布的區(qū)塊，在他的塊頭里也有一個總的bloom filter，這個總的bloom filter是這個區(qū)塊里所有交易的一個bloom filter的并集

比如說要查找過去十天發(fā)生的跟某個智能合約相關(guān)的交易，先查一下區(qū)塊的塊頭里的bloom filter有要找的交易類型，如果沒有，這個區(qū)塊就不是我們想要的，如果有，再去查找區(qū)塊里面包含的交易所對應(yīng)的收據(jù)樹里面的那些bloom filter，看看哪個有，也可能都沒有，因為有可能是false positive，如果是有的話，再找到相對應(yīng)的交易直接進(jìn)行一下確認(rèn)

好處是通過bloom filter的結(jié)構(gòu)能夠快速過濾掉大量無關(guān)的區(qū)塊，很多區(qū)塊一看塊頭的bloom filter就知道肯定沒有我們要的交易，然后剩下的一些少數(shù)的候選區(qū)塊，再仔細(xì)查看。比如說一個輕節(jié)點，只有塊頭信息，根據(jù)塊頭就已經(jīng)能夠過濾掉很多區(qū)塊了，剩下有可能是想要的區(qū)塊，再問全節(jié)點要進(jìn)一步的信息

4）、補(bǔ)充

狀態(tài)樹、交易樹、 收據(jù)樹三棵樹的根哈希值都是包括在塊頭里面的，以太坊的運行過程可以看作是一個交易驅(qū)動的狀態(tài)機(jī)（transaction-driven state machine）。這個狀態(tài)機(jī)的狀態(tài)是所有賬戶的狀態(tài)，就是狀態(tài)樹中包含的那些內(nèi)容，交易是每次發(fā)布區(qū)塊里包含的交易，通過執(zhí)行這些交易會驅(qū)動系統(tǒng)從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個狀態(tài)

比特幣也可以認(rèn)為是一個交易驅(qū)動的狀態(tài)機(jī)，比特幣中的狀態(tài)是UTXO（沒有被花掉的那些輸出），每次新發(fā)布一個區(qū)塊，會從UTXO里用掉一些輸出，又會增加一些新的輸出，所以發(fā)布的區(qū)塊會驅(qū)動狀態(tài)機(jī)從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個狀態(tài)

而且這兩個狀態(tài)機(jī)有一個共同的特點，就是狀態(tài)轉(zhuǎn)移都得是確定性的，對一個給定的當(dāng)前狀態(tài)、一組給定的交易（就是這個區(qū)塊中包含的交易），能夠確定性地轉(zhuǎn)移到下一個狀態(tài)，因為所有的全節(jié)點、所有的礦工，都要執(zhí)行同樣的狀態(tài)轉(zhuǎn)移，所以狀態(tài)轉(zhuǎn)移必須是確定性的

問題1：某人在以太坊發(fā)布一個交易，某個節(jié)點收到這個交易，轉(zhuǎn)賬交易A->B，有沒有可能這個收款人的地址從來沒聽說過？

以太坊和比特幣是一樣的，創(chuàng)建賬戶是不需要通知其他人的，只有這個賬戶第一次收到錢的時候，其他的節(jié)點才會知道這個賬戶的存在，這個時候要在狀態(tài)樹中新插入的一個節(jié)點，因為這個是新增加的賬戶

問題2：狀態(tài)樹、交易樹、收據(jù)樹的區(qū)別是，狀態(tài)樹要包含系統(tǒng)中所有賬戶的狀態(tài)，無論這些賬戶是否參與了當(dāng)前區(qū)塊的交易，那么能不能把狀態(tài)樹的設(shè)計改一下，改成每個區(qū)塊的狀態(tài)樹也只包含這個區(qū)塊中的交易相關(guān)的那些賬戶的狀態(tài)，這樣就跟交易樹和收據(jù)樹一致了，而且可以大幅度的削減每個區(qū)塊所對應(yīng)的狀態(tài)樹的大小，因為大部分的賬戶狀態(tài)是不會變的？

這樣設(shè)計的結(jié)果是每個區(qū)塊沒有一棵完整的狀態(tài)樹，只有當(dāng)前區(qū)塊中所包含的交易涉及到的賬戶的狀態(tài)

這么設(shè)計的一個問題就是，如果要想查找某個賬戶的狀態(tài)就不方便了。比如說有一個轉(zhuǎn)賬交易A轉(zhuǎn)給B 10個以太幣，要檢查A賬戶里是不是真的有10個以太幣，問題是最近一個區(qū)塊對應(yīng)的那個狀態(tài)樹可能沒有A這個賬戶，往前一直找，找到最近的一個包含A賬戶的區(qū)塊，才能知道A的賬戶余額是多少。如果A有較長的一段時間沒有發(fā)生交易，可能要從后往前，掃描很多個區(qū)塊，才能找到最近一次的賬戶狀態(tài)

還有一個更大的問題，就是A轉(zhuǎn)給B錢的時候，要知道A賬戶的狀態(tài)，才能知道A是不是有足夠的錢轉(zhuǎn)給B 10個以太幣，也要知道B賬戶的狀態(tài)，余額是多少，因為要往B賬戶余額里加10個以太幣，所以也要找B賬戶的狀態(tài)，而B賬戶有可能是個新建的賬戶，這個時候就要找到創(chuàng)世紀(jì)塊去，從當(dāng)前區(qū)塊一直找到創(chuàng)世紀(jì)塊，發(fā)現(xiàn)這個賬戶沒有，才知道原來是個新建的賬戶

5）、代碼中具體的數(shù)據(jù)結(jié)構(gòu)

交易樹和收據(jù)樹的創(chuàng)建過程，在NewBlock函數(shù)里創(chuàng)建了交易樹和收據(jù)樹，并且得到了他們的根哈希值

先看一下交易樹的代碼，首先判斷交易列表是否為空，如果是空的話，那么這個區(qū)塊里塊頭的交易樹的根哈希值就是一個空的哈希值，否則通過調(diào)用DeriveSha函數(shù)來得到交易樹的根哈希值，然后創(chuàng)建區(qū)塊的交易列表

中間這個代碼是收據(jù)樹，首先判斷一下收據(jù)列表是否為空，如果為空，塊頭里收據(jù)樹的根哈希值就是一個空的哈希值，如果不為空，通過調(diào)用DeriveSha函數(shù)來得到收據(jù)樹的根哈希值，然后創(chuàng)建塊頭里的bloom filter，每個交易執(zhí)行完之后會得到一個收據(jù)，所以交易列表的長度和收據(jù)列表的長度是一樣的

最下面這段代碼是叔父區(qū)塊的，首先判斷叔父列表是否為空，如果是的話，那么塊頭里叔父區(qū)塊的哈希值就是一個空的哈希值，否則，通過調(diào)用CalcUncleHash函數(shù)計算出哈希值，然后通過循壞構(gòu)建出區(qū)塊里的叔父數(shù)組

DeriveSha函數(shù)，前面NewBlock函數(shù)創(chuàng)建交易樹和收據(jù)樹的時候，調(diào)用的都是這個函數(shù)，這里創(chuàng)建的數(shù)據(jù)結(jié)構(gòu)是trie

而trie的數(shù)據(jù)結(jié)構(gòu)是一棵MPT，以太坊的三棵樹：交易樹、收據(jù)樹、狀態(tài)樹用的都是MPT

這是Receipt的數(shù)據(jù)結(jié)構(gòu)，每個交易執(zhí)行完之后形成的一個收據(jù)，記錄了這個交易的執(zhí)行結(jié)果

Bloom就是這個收據(jù)的bloom filter

Logs是個數(shù)組，每個收據(jù)可以包含多個Log，這些收據(jù)的bloom filter就是根據(jù)這些Log產(chǎn)生出來的

這是區(qū)塊塊頭的數(shù)據(jù)結(jié)構(gòu)，里面的Bloom域就是整個區(qū)塊的bloom filter，這個是由每個收據(jù)的bloom filter合并在一起得到的

這是剛剛的NewBlock函數(shù)，紅框里的代碼就是創(chuàng)建塊頭里的bloom filter，通過調(diào)用CreateBloom這個函數(shù)

這是相關(guān)的三個函數(shù)的代碼實現(xiàn)

CreateBloom函數(shù)的參數(shù)是這個區(qū)塊的所有收據(jù)，這個for循環(huán)對每個收據(jù)調(diào)用LogsBloom函數(shù)來生成這個收據(jù)的bloom filter，然后把這些bloom filter用Or操作合并起來得到整個區(qū)塊的bloom filter

LogsBloom函數(shù)的功能是生成每個收據(jù)的bloom filter，他的參數(shù)是這個收據(jù)的Log數(shù)組，剛才看過Receipt的數(shù)據(jù)結(jié)構(gòu)，每個Receipt里面包含一個Logs的數(shù)組，這個函數(shù)有兩層for循環(huán)，外層循環(huán)對Logs數(shù)組里的每一個Log進(jìn)行處理，首先把Log的地址取哈希后，加到bloom filter里面，這里的bloom9是bloom filter中用到的哈希函數(shù)，然后內(nèi)層循環(huán)把Log中包含的每個Topics加入到bloom filter里，這樣就得到了這個收據(jù)的bloom filter

bloom9是bloom filter中用到的哈希函數(shù)，這里的bloom9函數(shù)是把輸入映射到digest中的三個位置，把三個位置都置為1

第一行調(diào)用crypto里面的函數(shù)，生成一個256位的哈希值，b這個變量是個32個字節(jié)的哈希值

第二行的r是要返回的bloom filter，在這里初始化為0

接下來是個循環(huán)，把剛才生成的32個字節(jié)的哈希值取前六個字節(jié)，每兩個字節(jié)組成一組拼接在一起，然后and上2047，相當(dāng)于對2048取余，得到一個位于0到2047這個區(qū)間里的數(shù)，這樣做是因為以太坊中bloom filter的長度是2048位。這個循環(huán)的最后一行，把t左移這么多位然后合并到上一輪得到的bloom filter里，通過Or運算合并到前面的bloom filter里，經(jīng)過三輪循環(huán)，把三個位置置為1后，返回所創(chuàng)建的bloom filter

前面是生成bloom filter的過程，那么怎么查詢某個bloom filter里面是否包含了我們感興趣的topic呢?

這是通過調(diào)用BloomLookup函數(shù)來實現(xiàn)的，查一下bin的bloom filter里有沒有包含要找的第二個參數(shù)topic，首先用bloom9函數(shù)把topic轉(zhuǎn)化成一個bytesBacked，然后把他跟bloom filter取and操作，看看得到的結(jié)果是不是和bytesBacked相等。注意bloom filter里面可能包含除了我們要查找的topic之外其他的topic，所以要做一個and，然后再跟他自身比較，相當(dāng)于判斷一下我們要查找的這個topic在bloom filter中對應(yīng)的位置是不是都是1

對應(yīng)課程：

北京大學(xué)肖臻老師《區(qū)塊鏈技術(shù)與應(yīng)用》公開課文章來源地址http://www.zghlxwxcb.cn/news/detail-800444.html

到了這里，關(guān)于北京大學(xué)肖臻老師《區(qū)塊鏈技術(shù)與應(yīng)用》公開課筆記：以太坊原理（一）：以太坊概述、賬戶、狀態(tài)樹、交易樹和收據(jù)樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！