??實(shí)際上，在比特幣系統(tǒng)中，所謂哈希指針只是一種形象的說(shuō)法，實(shí)際在用的時(shí)候，其實(shí)只有哈希，沒(méi)有指針。回顧之前學(xué)習(xí)過(guò)的Block Header的數(shù)據(jù)結(jié)構(gòu)，如下所示，我們可以得知， uint256 hashPrevBlock;這里表示的就是前一個(gè)區(qū)塊的哈希，實(shí)際上是沒(méi)有指針的。

class CBlockHeader

{

public:

//header

int32_t nVersion;//當(dāng)前使用的比特幣協(xié)議的版本號(hào)，沒(méi)法修改（4字節(jié)）

????uint256 hashPrevBlock;//前一個(gè)區(qū)塊塊頭哈希值（32字節(jié)），不能修改

????uint256 hashMerkleRoot;//Merkle Tree的根哈希值（32字節(jié)）；

??//通過(guò)修改Merkle Tree中鑄幣交易的CoinBase域當(dāng)作ExtraNonce來(lái)調(diào)整其根哈希值

????uint32_t nTime;//區(qū)塊產(chǎn)生時(shí)間，有一定調(diào)整余地（4字節(jié)）；

????????????????//比特幣系統(tǒng)并不要求非常精確的時(shí)間，這個(gè)時(shí)間可以在一定范圍內(nèi)調(diào)整

????uint32_t nBits;//挖礦后的目標(biāo)閾值編碼后的版本（4字節(jié)）;

????????????????????//只能按照協(xié)議中的要求定期進(jìn)行調(diào)整，不能隨便改

????uint32_t nNonce;//（4字節(jié)）單純靠調(diào)整nonce的值很大概率找不到符合難度要求的

}

?

?? 那么，如何找到前一個(gè)區(qū)塊的內(nèi)容呢？ 全結(jié)點(diǎn)一般是將這些區(qū)塊存儲(chǔ)在一個(gè) (Key,Value) 數(shù)據(jù)庫(kù)中，Key表示哈希值，Value表示區(qū)塊的內(nèi)容，有一個(gè)比較常用的 (Key,Value) 數(shù)據(jù)庫(kù)——LevelDB。所謂的區(qū)塊鏈?zhǔn)且粋€(gè)鏈表結(jié)構(gòu)，實(shí)際上是在 LevelDB 里面，用哈希值串起來(lái)的。只要掌握最后一個(gè)區(qū)塊的哈希值，用 LevelDB 查找 (Key,Value) ，就可以通過(guò)哈希值Key得到Value，就可以把最后一個(gè)區(qū)塊的內(nèi)容取出來(lái)。然后這個(gè)區(qū)塊的Block Header里面又有指向前一個(gè)區(qū)塊的哈希值，然后再去用 LevelDB 查找 (Key,Value) ，就可以找到前一個(gè)區(qū)塊的內(nèi)容，以此類推，就可以把整條區(qū)塊鏈都找出來(lái)。

??所以，在實(shí)際系統(tǒng)之中，所謂的哈希指針是只有哈希沒(méi)有指針的，或者也可以認(rèn)為哈希值本身就是指針。有些結(jié)點(diǎn)沒(méi)有保存區(qū)塊鏈整條鏈上的全部信息，只保存了最近的幾千個(gè)區(qū)塊的信息，如果需要用到前面區(qū)塊的信息，可以問(wèn)其他全結(jié)點(diǎn)要，哈希指針的性質(zhì)保證整個(gè)區(qū)塊鏈?zhǔn)遣豢纱鄹牡摹?/p>

?

2.區(qū)塊戀可能造成的問(wèn)題

??情侶兩個(gè)人合在一起買比特幣，然后將私鑰從中間截?cái)啵殖蓛刹糠?，每人保存其中的一段，如果兩個(gè)人分手了，當(dāng)初買的比特幣就被永久地所在區(qū)塊鏈上，誰(shuí)也取不出來(lái)。

?

可能造成的問(wèn)題：

（1）如果有一個(gè)人把私鑰丟失（或遺忘），都會(huì)導(dǎo)致比特幣無(wú)法取出。

（2）降低賬戶的安全性。

??比特幣系統(tǒng)中賬戶的安全性跟用戶所用的私鑰的長(zhǎng)度是相關(guān)的，用256位的私鑰就是因?yàn)檫@個(gè)長(zhǎng)度的私鑰用暴力破解的方式是不可行的，但是如果從中截?cái)?，就?huì)大大降低其安全性。

??假設(shè)其中一個(gè)人想要把比特幣取出來(lái)，那么只需要破解另外一半就可以，破解長(zhǎng)度為256的私鑰需要嘗試的可能性為2256，而破解128位的私鑰需要嘗試的可能性為2128，是指數(shù)級(jí)的減小。

??所以說(shuō)對(duì)于多個(gè)人共同持有的賬戶，不能用私鑰截?cái)嗟姆绞?，而?yīng)該使用多重簽名的方式來(lái)保障安全性。?在多重簽名（MULITISIG）中，每個(gè)人用到的私鑰都是獨(dú)立產(chǎn)生的，而且多重簽名還具有很多靈活性，如N個(gè)人中只給出M個(gè)人的簽名就可以驗(yàn)證通過(guò)。

?

（3）取不出來(lái)的錢將會(huì)永久被存在UTXO集合中，對(duì)礦工是不友好的。

??假設(shè)“區(qū)塊戀”的例子中的兩個(gè)情侶分手，不存在其中有人有使用暴力手段破解私鑰的情況，那么這些比特幣將會(huì)永遠(yuǎn)花不出去，礦工并不知道這對(duì)情侶已經(jīng)分手了，這些比特幣是取不出來(lái)的，所以他需要永遠(yuǎn)把錢保存在UTXO中，這個(gè)操作對(duì)全結(jié)點(diǎn)是不友好的。

?

3.分布式系統(tǒng)比較著名的不可能結(jié)論，從理論上證明，分布式系統(tǒng)中取得共識(shí)是不可能的，那么既然理論上已經(jīng)證明了是不可能的，實(shí)際上為什么又變得可能了呢？就是說(shuō)比特幣系統(tǒng)為什么能取得共識(shí)，為什么它能繞過(guò)分布式系統(tǒng)理論上證明的那些不可能結(jié)論？

??嚴(yán)格意義上說(shuō)，比特幣系統(tǒng)并沒(méi)有真正意義上的共識(shí)，因?yàn)槿〉玫墓沧R(shí)隨時(shí)都有可能被推翻，如出現(xiàn)分叉攻擊（本來(lái)你以為已經(jīng)取得某項(xiàng)共識(shí)，分叉攻擊之后，系統(tǒng)會(huì)回滾到前一個(gè)狀態(tài)，從理論上說(shuō)甚至有可能一直回滾到創(chuàng)世紀(jì)塊），按照分布式系統(tǒng)理論上的要求，共識(shí)一旦達(dá)成就不應(yīng)該再修改。從這個(gè)意義上說(shuō)，比特幣系統(tǒng)并沒(méi)有繞過(guò)分布式系統(tǒng)那些不可能的結(jié)論，因?yàn)樗](méi)有達(dá)到真正意義上的共識(shí)。理論和實(shí)際往往是有距離的，理論上的不可能只是在某種特定的模型下是不可能的，實(shí)際上把模型稍微改一改，這個(gè)不可能結(jié)論就不成立了。

??如何判斷遠(yuǎn)程數(shù)據(jù)中心的一臺(tái)服務(wù)器是不是已經(jīng)死機(jī)了。專家的看法是：分布式系統(tǒng)的理論已經(jīng)證明了，在異步環(huán)境中，不可能區(qū)分某個(gè)遠(yuǎn)程服務(wù)器到底是死機(jī)還是運(yùn)行緩慢。（所謂的異步環(huán)境是指通訊傳播的延遲是沒(méi)有上限的）但是實(shí)際上，我們可以給遠(yuǎn)程服務(wù)器的工作人員打個(gè)電話，讓他們看看這個(gè)服務(wù)器是不是死機(jī)了，如果死機(jī)幫忙重啟一下，這樣下來(lái)，這個(gè)理論上不可行的案例，實(shí)際上就變成可行的了?；蛘呓o服務(wù)器加一根電話線，進(jìn)行撥號(hào)上網(wǎng)，如果發(fā)現(xiàn)Internet執(zhí)行緩慢可以試一下電話線，兩根線一般不會(huì)出現(xiàn)同時(shí)擁堵的情況，這樣就可以確認(rèn)遠(yuǎn)程服務(wù)器是否死機(jī)。

?

4.比特幣的稀缺性

??為了獲得收益，挖礦的收益大于挖礦的開(kāi)銷，才是有利可圖的。所以，想要吸引到更多人來(lái)挖礦，要么增加挖礦的預(yù)期收益，要么降低挖礦的開(kāi)銷。

??比特幣的設(shè)計(jì)是非常巧妙的，我們之前計(jì)算過(guò)，每過(guò)大約四年時(shí)間，出塊獎(jiǎng)勵(lì)會(huì)減半一次，也就是說(shuō)比特幣的總數(shù)是恒定的。有些人說(shuō)這種總量恒定的東西是不適合作為貨幣的，以太坊就沒(méi)有出塊獎(jiǎng)勵(lì)定期減半的做法，有些加密貨幣甚至每過(guò)一段時(shí)間會(huì)自行通脹一次，因?yàn)橄∪钡臇|西是不適合做貨幣的。

??

5.量子計(jì)算

??最近幾年量子計(jì)算發(fā)展很快，有人產(chǎn)生這樣一種擔(dān)心：比特幣這種加密貨幣是建立在密碼學(xué)的基礎(chǔ)上的，將來(lái)量子計(jì)算技術(shù)發(fā)展起來(lái)以后，這些加密貨幣會(huì)不會(huì)變得不安全？

??傳說(shuō)中的量子計(jì)算機(jī)是非常強(qiáng)大的，可以破解現(xiàn)存的各種加密算法，但是這個(gè)擔(dān)心是不必要的。首先，量子計(jì)算機(jī)距離使用還有很長(zhǎng)一段時(shí)間，在比特幣的有生之年不一定能產(chǎn)生實(shí)質(zhì)性的威脅。而且，如果將來(lái)有一天量子計(jì)算真正強(qiáng)大到可以破壞現(xiàn)有的加密體系的話，首先受到?jīng)_擊的是傳統(tǒng)金融業(yè)，像網(wǎng)銀、網(wǎng)上支付等等都會(huì)變得不安全。所以，與其擔(dān)心量子計(jì)算對(duì)比特幣的沖擊還不如擔(dān)心量子計(jì)算對(duì)傳統(tǒng)金融業(yè)的沖擊，因?yàn)榇蠖鄶?shù)的錢都是存放在傳統(tǒng)金融體系中的，加密貨幣的總市值現(xiàn)代金融體系的很少一部分，而且將來(lái)還會(huì)有量子加密算法。

??第二，比特幣系統(tǒng)中并沒(méi)有把賬戶的公鑰直接暴露出來(lái)，而是用公鑰取哈希之后得到一個(gè)地址。比特幣中用的是非對(duì)稱加密體系，從私鑰可以推導(dǎo)出公鑰，所以只要將私鑰保管好，公鑰即使丟了也沒(méi)有關(guān)系，公鑰顯然不能推出私鑰。假設(shè)以后，量子技術(shù)發(fā)達(dá)了，可以通過(guò)公鑰推到得到私鑰，那么在比特幣系統(tǒng)中，還需要突破另一層保護(hù)機(jī)制，就是需要能夠從公鑰的哈希推算出公鑰，而這一點(diǎn)即使使用量子計(jì)算機(jī)也是無(wú)法完成的。加密跟取哈希是兩種不同性質(zhì)的操作，加密的目的是保證信息的安全性，以后還要解密，所以加密需要保證信息的完整性，加密過(guò)程不能丟失信息。而取哈希不一樣，取哈希一般情況下會(huì)造成信息的損失，哈希函數(shù)一般都是不可逆的，從哈希值是無(wú)法得到原來(lái)的輸入的。

??比特幣系統(tǒng)中哈希函數(shù)用的是SHA-256，即無(wú)論輸入有多大，輸出的都是256位的，這種情況如果可逆就會(huì)變成一個(gè)超級(jí)無(wú)敵的壓縮算法。所以，如果僅用來(lái)收錢的情況下，不建議把公鑰暴露在比特幣系統(tǒng)上，收錢的時(shí)候只需要提供公鑰的哈希提供的地址就可以，取錢的時(shí)候才需要提供公鑰，取錢的交易中需要公鑰和由私鑰產(chǎn)生的簽名。如果一個(gè)人想要偷A(chǔ)賬戶上的錢，他需要在A發(fā)布交易時(shí)實(shí)時(shí)破解從A的公鑰推導(dǎo)出A的私鑰，再實(shí)時(shí)產(chǎn)生一個(gè)跟A的交易競(jìng)爭(zhēng)的交易。即使這個(gè)人具有量子計(jì)算技術(shù)也很難在幾分鐘之內(nèi)就將私鑰破解，而且他發(fā)布的交易還需要搶在A發(fā)布交易的前面，因?yàn)槿绻贏發(fā)布交易之后，就會(huì)產(chǎn)生Double Spending。所以從比特幣安全的角度來(lái)看，比特幣系統(tǒng)中每個(gè)賬戶只取一次錢，花不完的錢轉(zhuǎn)給自己的其他賬戶，這樣做既提升了安全性，也提高了隱私保護(hù)的程度。

14-ETH-以太坊概述

1.以太坊相較比特幣做出的改進(jìn)

??比特幣稱為區(qū)塊鏈1.0，以太坊稱為區(qū)塊鏈2.0。

（1）出塊時(shí)間：

比特幣的出塊時(shí)間是十分鐘，以太坊的出塊時(shí)間是十幾秒，而且為了適應(yīng)新的出塊時(shí)間，以太坊還設(shè)計(jì)了一套基于GHOST協(xié)議的共識(shí)機(jī)制；

（2）Mining Puzzle：

比特幣的Mining Puzzle是計(jì)算密集型，比拼計(jì)算哈希值的算力，這樣造成的結(jié)果是挖礦設(shè)備的專業(yè)化，現(xiàn)在大家用的是ASIC芯片，很多人認(rèn)為這與區(qū)塊鏈去中心化的理念相悖，

以太坊設(shè)計(jì)的Mining Puzzle對(duì)內(nèi)存要求高，在一定程度上限ASIC芯片（ASIC Resistance）的使用；

（3）用權(quán)益證明來(lái)替代工作量證明：

以太坊中改成了權(quán)益證明（Proof of Stake），不挖礦了，改成了類似股份投票的方法，決定下一個(gè)區(qū)塊怎么產(chǎn)生。

?

2.以太坊增加的新功能

??智能合約（Smart Contract）。以太坊的一個(gè)特性就是增加了對(duì)去中心化的合約的支持。比特幣（BTC）最小計(jì)量單位是Satoshi（聰），以太坊（ETH）中的貨幣稱為以太（Ether），最小計(jì)量單位是Wei。

?

3.去中心化的合約

??現(xiàn)實(shí)社會(huì)中合約的有效性也是通過(guò)政府采取司法手段來(lái)維護(hù)的，使用技術(shù)手段把這些司法手段取代，就是智能合約的目的，如果合約中的內(nèi)容是可以通過(guò)代碼實(shí)現(xiàn)的，就可以將這樣的代碼放在區(qū)塊鏈上，通過(guò)合約的不可篡改性保證代碼正常運(yùn)行。

并非所有合同都能通過(guò)代碼實(shí)現(xiàn)的，也不是所有合同條款都可以量化的，但是有些邏輯比較清晰的合同是可以寫成智能合約的形式的。

?

4.去中心化的合約有什么好處？

??去中心化的貨幣有什么好處？比如跨國(guó)轉(zhuǎn)賬，傳統(tǒng)的方式交易費(fèi)非常昂貴而且轉(zhuǎn)賬時(shí)間非常長(zhǎng)，用加密貨幣（如BTC）則方便很多。

??那么，智能合約也有類似的應(yīng)用場(chǎng)景，若合同簽署方并非一個(gè)國(guó)家，來(lái)自世界各個(gè)國(guó)家，沒(méi)有統(tǒng)一的司法部門，若此時(shí)想要利用司法手段來(lái)維護(hù)合同的有效性會(huì)比較麻煩。用技術(shù)手段編寫無(wú)法修改的合約，所有人只能按照相關(guān)參與方執(zhí)行，無(wú)法違約，這是最好的。

?

15-ETH-帳戶

1.比特幣的賬戶模式

??比特幣系統(tǒng)是基于交易的賬本（Transaction Based Ledger），系統(tǒng)中并未顯示記錄每個(gè)賬戶上有多少錢，只能通過(guò)UTXO進(jìn)行推算（即在UTXO中查找該賬戶公鑰有多少輸入即可）。

??假設(shè)A轉(zhuǎn)給B錢的時(shí)候，需要說(shuō)明幣的來(lái)源。比特幣賬戶中，在前面一筆交易中收到的比特幣，在花的時(shí)候必須一次性全部花出去，不能只花一部分。

?

假設(shè)B收到A的5個(gè)比特幣，他只給C轉(zhuǎn)賬2個(gè)比特幣，若按上圖方式，其余3個(gè)比特幣會(huì)以交易費(fèi)（Transaction Fee）的形式給挖出區(qū)塊的礦工。

采用下圖的方式，將3個(gè)BTC轉(zhuǎn)給C，將剩余7個(gè)BTC轉(zhuǎn)到B的另一賬戶D上面。很多比特幣錢包就采用這種方式，每次轉(zhuǎn)賬就生成一個(gè)自己的新的地址，有利于隱私保護(hù)，但是仍然與日常生活有所不同。這是因?yàn)楸忍貛畔到y(tǒng)中沒(méi)有顯示的基于賬戶的交易的概念，在比特幣系統(tǒng)中，每個(gè)交易是單獨(dú)進(jìn)行處理的。

2.以太坊的賬戶模式

??以太坊系統(tǒng)則采用了基于賬戶的模型。系統(tǒng)中顯示記錄每個(gè)賬戶中以太幣的數(shù)量，轉(zhuǎn)賬是否合法只需要查看轉(zhuǎn)賬者賬戶中以太幣是否足夠即可，不用確切指出轉(zhuǎn)出的錢屬于哪一部分，同時(shí)也不需要每次全部轉(zhuǎn)賬。同時(shí)，也天然地防范了雙花攻擊。若出現(xiàn)Double Spending，無(wú)需說(shuō)明幣的來(lái)源，只需要扣兩次錢就好了。

? ? ? 但這種模式存在重放攻擊（Reply Attack）的缺陷。A向B轉(zhuǎn)賬10個(gè)ETH，過(guò)一段時(shí)間，B將A的交易重新發(fā)布，從而導(dǎo)致A賬戶被扣錢兩次。

在比特幣中會(huì)有重放攻擊嗎？不會(huì)，因?yàn)槭盏竭^(guò)的交易信息再?gòu)V播一次是很顯然的Double Spending。

??解決重放攻擊的方法：在每筆交易中添加一個(gè)Nonce（計(jì)數(shù)器），記錄該賬戶有史以來(lái)一共發(fā)布多少交易，轉(zhuǎn)賬時(shí)，Nonce作為交易的一部分，同時(shí)受到簽名的保護(hù)，從而防止本地篡改余額或進(jìn)行重放攻擊。

3.以太坊的賬戶類型

①外部賬戶：外部賬戶中有賬戶余額Balance和計(jì)數(shù)器Nonce（≠挖礦調(diào)整的Nonce）。

②合約賬戶：并非通過(guò)公私鑰對(duì)控制。合約賬戶不能主動(dòng)發(fā)起交易，若外部賬戶發(fā)起交易調(diào)動(dòng)了一個(gè)合約賬戶，該合約賬戶可以發(fā)起一個(gè)Message調(diào)用另外一個(gè)合約，但是不能自己主動(dòng)發(fā)起交易。合約賬戶除了Balance和Nonce之外還有代碼(Code)、相關(guān)狀態(tài)-存儲(chǔ)(Storage)，包括每個(gè)變量的取值。

??創(chuàng)建合約時(shí)候會(huì)返回一個(gè)地址，知道這個(gè)地址就可以調(diào)用這個(gè)合約。調(diào)用過(guò)程中，代碼不變但狀態(tài)會(huì)發(fā)生改變，存儲(chǔ)也會(huì)發(fā)生變化。

?

4.為什么創(chuàng)建以太坊，更換為基于賬戶的模型而不是沿襲比特幣系統(tǒng)？

??比特幣基于交易的模型隱私保護(hù)比較好，每次交易支持更換賬戶。

以太坊是為了支持智能合約，對(duì)于合約來(lái)說(shuō)，要求參與方的身份較為穩(wěn)定。如果地址變了，那投入到原來(lái)合約的錢也就找不見(jiàn)了。

?

16-ETH-狀態(tài)樹

一、什么是以太坊中的狀態(tài)樹

? ? ? ? 以太坊中采用的是一種基于賬戶的模式，想要實(shí)現(xiàn)這種模式需要完成從賬戶地址（Address）到賬戶狀態(tài)（State）的映射。以太坊中的賬戶地址是160位的，也就是20字節(jié)，一般將其表示為40個(gè)十六進(jìn)制的數(shù)。狀態(tài)是指外部賬戶和合約賬戶的狀態(tài)，包括余額，交易次數(shù)Nonce，對(duì)于合約賬戶還包括代碼和存儲(chǔ)。

?

二、實(shí)現(xiàn)從賬戶地址到賬戶狀態(tài)的映射

方案一、哈希表+Merkle tree

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

?

問(wèn)題：

1.?如果用這個(gè)哈希表要提供merkle proof怎么提供？比如說(shuō)你要跟一個(gè)人簽合同，希望他能證明一下他有多少錢，怎么提供證明呢？

類似比特幣系統(tǒng)中的做法，把哈希表中的元素組織成一個(gè)Merkle Tree，然后算出一個(gè)根哈希值，這個(gè)根哈希值存在Block Header里，只要根哈希值是正確的，就能保證底下的樹不會(huì)被篡改。

2.?比特幣系統(tǒng)中也是每出現(xiàn)一個(gè)區(qū)塊都要重新構(gòu)造一個(gè)Merkle tree，這為什么沒(méi)有問(wèn)題？

比特幣系統(tǒng)中的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é)左右），其實(shí)是一個(gè)上限。所以每次發(fā)布一個(gè)區(qū)塊，比特幣里要把這幾百個(gè)到幾千個(gè)交易構(gòu)成一個(gè)Merkle tree。

?

若以太坊中想要采取類似方法，需要把所有的以太坊賬戶一起構(gòu)成一個(gè)Merkle tree，量要高出好幾個(gè)數(shù)量級(jí)，相當(dāng)于每次發(fā)布一個(gè)區(qū)塊要把所有的賬戶遍歷一遍構(gòu)建出一個(gè)Merkle tree。

除了提供Merkle proof證明賬戶有多少錢之外，這個(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)的一致才行，這也是為什么比特幣中把根哈希值寫在塊頭里的原因，就是對(duì)于當(dāng)前區(qū)塊中包含哪些交易，所有的全節(jié)點(diǎn)要有一個(gè)共識(shí)。

? ? ? ? 綜上所述，哈希表本身的效率是挺好的，插入、更改效率都很好。但實(shí)際操作中，賬戶狀態(tài)發(fā)生變化的只是一小部分，大多數(shù)是不變的，所以每次都重新構(gòu)造一次Merkle tree的代價(jià)太大了。

方案二、不排序的Merkle tree

1.?直接用一個(gè)Merkle tree把所有的賬戶都放進(jìn)去，要修改賬戶狀態(tài)的時(shí)候直接在Merkle tree里改？

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

問(wèn)題②：直接把賬戶放到Merkle tree里，如果不排序，查找速度會(huì)慢，比特幣中如果證明一個(gè)交易在這個(gè)區(qū)塊中是不需要排序的，如果證明一個(gè)交易不在這個(gè)區(qū)塊中，是需要排序的，否則證明的代價(jià)就非常大了。

如果不排序還有一個(gè)問(wèn)題③：葉節(jié)點(diǎn)是這些賬戶的信息，如果不規(guī)定這些賬戶在葉節(jié)點(diǎn)出現(xiàn)的順序，那么這樣構(gòu)建出來(lái)的Merkle tree不是唯一的。

?

2.?比特幣中的節(jié)點(diǎn)也是不排序的，那為什么比特幣就沒(méi)有問(wè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)。只有他有記賬權(quán)，且發(fā)布區(qū)塊后最終成為被大家接受的區(qū)塊，這個(gè)順序是唯一的，是發(fā)布這個(gè)區(qū)塊的節(jié)點(diǎn)確定的。

?

3.?為什么以太坊不能這樣做？

因?yàn)槿绻惨@么做的話，需要把所有賬戶的狀態(tài)發(fā)布到區(qū)塊里，不是交易，個(gè)數(shù)差了很多個(gè)數(shù)量級(jí)。

賬戶狀態(tài)可以維護(hù)在本地，而且大部分賬戶狀態(tài)是不變的，一個(gè)區(qū)塊里的交易只能改很少的賬戶，且重復(fù)發(fā)布，每隔十幾秒發(fā)布一個(gè)新的區(qū)塊，把所有狀態(tài)都打包發(fā)布一遍，這個(gè)是不可行，剛才說(shuō)明了不排序的Merkle tree是不行的。

?

方案三、Sorted Merkle tree

也有問(wèn)題。如新增一個(gè)賬戶時(shí)，產(chǎn)生一個(gè)賬戶的地址是隨機(jī)的，他的葉節(jié)點(diǎn)的位置很可能是插在中間的，那后面這些樹的結(jié)構(gòu)都得變，插入，刪除代價(jià)都很大，每次更新都需要新產(chǎn)生一遍Merkle tree。

區(qū)塊鏈?zhǔn)遣豢纱鄹牡?，是說(shuō)添東西容易，刪東西難，其實(shí)以太坊中沒(méi)有顯式地刪除賬戶的操作，有的賬戶上就一點(diǎn)錢，就一兩個(gè)Wei，也不能把他刪掉。? ? ? ?

?

上面的方案都不行。那么以太坊中采用的方法是用一個(gè)叫MPT的結(jié)構(gòu)，在此之前先學(xué)習(xí)一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)——trie。

?

?

三、MPT結(jié)構(gòu)

1.Trie：字典樹（前綴樹）

也是一種(key,value)的樹，一般來(lái)說(shuō)key用字符串用的比較多，如將一些單詞排成一個(gè)trie的數(shù)據(jù)結(jié)構(gòu)。比如將general,genesis,god,go,good排列成trie的數(shù)據(jù)結(jié)構(gòu)如下圖。

2.Trie結(jié)構(gòu)的特點(diǎn)

①每個(gè)節(jié)點(diǎn)的分支數(shù)目取決于key值里每個(gè)元素的取值范圍。

在以太坊中，地址是表示成40個(gè)十六進(jìn)制的數(shù)，所以分叉數(shù)目（有時(shí)也叫做Branching Factor）是17，因?yàn)槭鞘M(jìn)制的0~f，再加上結(jié)束標(biāo)志位，所以是17。

?

②trie的查找速率取決于key的長(zhǎng)度，鍵值越長(zhǎng)，查找需要訪問(wèn)的次數(shù)就越多。

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

比特幣和以太坊的地址是不通用的，長(zhǎng)度不同（比特幣中的地址是用公鑰取哈希得到的256位的哈希值），以太坊中的地址是公鑰取哈希，只要后面這部分，就得到一個(gè)160bit的地址。

?

③trie是不會(huì)出現(xiàn)碰撞的：只要兩個(gè)地址不一樣，最后肯定映射到樹中的不同分支。

④trie構(gòu)造的樹不受輸入排序影響。

Merkle tree，如果不排序的話，一賬戶插入到Merkle tree 的順序不一樣，得到的樹的結(jié)構(gòu)也不一樣。

而trie，只要給定的輸入不變，無(wú)論輸入怎么打亂重排，得到的樹是一樣的。不同的節(jié)點(diǎn)，不論你怎么按照順序去插入這些賬戶，最后構(gòu)造出來(lái)的樹是一樣的。

?

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

?

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

比如在上圖中，左邊分支都只有一個(gè)子節(jié)點(diǎn)，如果能把節(jié)點(diǎn)進(jìn)行合并，可減小存儲(chǔ)的開(kāi)銷，同時(shí)提高查找的效率，不用一個(gè)個(gè)往下找。由此引入了Patricia tree。

?

3.Patricia tree（Patricia trie），經(jīng)過(guò)路徑壓縮的前綴樹，即壓縮前綴樹

將上圖的trie進(jìn)行路徑壓縮，結(jié)果如下圖。

壓縮后，縮短了樹的高度，訪問(wèn)內(nèi)存的次數(shù)則會(huì)大大減少，效率會(huì)明顯提高。

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

?

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

如英文單詞，每個(gè)單詞很長(zhǎng)，但是一共沒(méi)有幾個(gè)單詞。misunderstanding，decentralization（去中心化），disintermediation（非中間化）。用Patricia tree的話，參考下圖

?

這樣的結(jié)構(gòu)效率是比較低的，用Patricia tree的結(jié)果如下圖，這個(gè)樹的高度明顯改善。鍵值分布比較稀疏的時(shí)候，路徑壓縮效果比較好。如果應(yīng)用在以太坊中，鍵值則為地址，地址是160位的，所以地址空間有，這是一個(gè)非常非常大的數(shù)，如果設(shè)計(jì)一個(gè)計(jì)算機(jī)程序的算法，需要進(jìn)行運(yùn)算的次數(shù)是2^160，那這個(gè)在我們的有生之年都不可能算出來(lái)，全世界的以太坊的賬戶數(shù)目加在一起也遠(yuǎn)遠(yuǎn)沒(méi)有這么大，跟這個(gè)數(shù)比，是微乎其微的，所以以太坊的賬戶是非常非常稀疏的。

為什么設(shè)計(jì)地這么稀疏，不把地址長(zhǎng)度縮短一點(diǎn)，這樣訪問(wèn)效率也快，也沒(méi)必要那么稀疏了？ ?以太坊中普通賬戶的創(chuàng)建方法跟比特幣賬戶的創(chuàng)建方法是一樣的，沒(méi)有中央的節(jié)點(diǎn)，每個(gè)用戶獨(dú)立創(chuàng)建賬戶，在本地產(chǎn)生一個(gè)公私鑰對(duì)，就是一個(gè)賬戶。為了防止兩個(gè)人的賬戶碰撞（即產(chǎn)生的賬戶一樣），特將地址設(shè)計(jì)得足夠長(zhǎng)，分布足夠稀疏。這個(gè)可能看上去有點(diǎn)浪費(fèi)，但是這是去中心化的系統(tǒng)防止賬戶沖突的唯一辦法，所以在數(shù)據(jù)結(jié)構(gòu)中，要用Patricia tree。

?

4.MPT（Merkle Patricia tree）

（1）什么是Merkle Patricia tree

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

Merkel tree和Binary tree的區(qū)別：把普通指針換成了哈希指針。

在以太坊系統(tǒng)中，將所有賬戶組織成一個(gè)Patricia tree（用路徑壓縮提高效率），然后把普通指針換成哈希指針，計(jì)算出根哈希值，寫在Block Header里。

比特幣的Block Header里只有一個(gè)根哈希值，就是區(qū)塊里包含的交易組成的Merkle tree組成的根哈希值；以太坊中有三個(gè)，有一個(gè)交易組成的交易樹、用戶狀態(tài)組成狀態(tài)樹、和收據(jù)樹，狀態(tài)樹由賬戶狀態(tài)組成，他的根哈希值也是寫在Block Header里。

?

（2）根哈希值的作用

①防止篡改。根哈希值不發(fā)生變化，整個(gè)樹的任何部分都沒(méi)有辦法被篡改。

②Merkle Proof：證明賬戶的余額是多少。該賬戶所在的分支自己向上作Merkle Proof發(fā)給輕節(jié)點(diǎn)，輕節(jié)點(diǎn)可以驗(yàn)證該賬戶的余額。

③驗(yàn)證一個(gè)交易是不存在的。如果存在的話，把這個(gè)分支作為Merkle Proof發(fā)過(guò)去。

?

（3）以太坊中的MPT——Modified MPT

? ? ? ? 以太坊中用到的不是原生的MPT，是Modified MPT，這里對(duì)MPT做了一些修改，這些修改并非本質(zhì)的修改，如圖，樹中的根節(jié)點(diǎn)Root取哈希后得到的根哈希值會(huì)被寫在塊頭里，如圖左上角所示。另，圖中各個(gè)節(jié)點(diǎn)原本存放地址的位置在這里存放的都是哈希值，具體方式參考BTC-思考。

?

????????每次發(fā)布一個(gè)新的區(qū)塊的時(shí)候，這個(gè)狀態(tài)樹中，有一些節(jié)點(diǎn)的值會(huì)發(fā)生變化，這些改變不是在原地修改，而是新建一個(gè)分支，所以說(shuō)原來(lái)的狀態(tài)實(shí)際上是保留下來(lái)的，如下圖所示，以太坊中其實(shí)是一個(gè)大的MPT里面包含很多小的MPT，每個(gè)賬戶都有一個(gè)小的MPT。

?

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

以太坊將出塊時(shí)間降低到十幾秒，導(dǎo)致臨時(shí)性分叉成為常態(tài)（因?yàn)閰^(qū)塊在網(wǎng)上傳播時(shí)間可能也需要十幾秒）。假設(shè)有個(gè)分叉，這兩個(gè)節(jié)點(diǎn)同時(shí)獲得記賬權(quán)，上面的分叉勝出，成為最長(zhǎng)合法連，下面這個(gè)分叉的節(jié)點(diǎn)就要回滾（roll back）。也就是說(shuō)這個(gè)節(jié)點(diǎn)當(dāng)前的狀態(tài)（接受了下面這個(gè)節(jié)點(diǎn)的狀態(tài)）要取消，退回到之前的狀態(tài)，然后沿著上面那條合法鏈往下推進(jìn)。為了實(shí)現(xiàn)回滾，就要維護(hù)這些歷史紀(jì)錄。

比特幣系統(tǒng)中，交易類型較簡(jiǎn)單，有時(shí)可通過(guò)反向操作推算出前一個(gè)狀態(tài)。

以太坊中為什么不能直接回滾？因?yàn)橐蕴恢杏兄悄芎霞s，是圖靈完備的，編程功能是很強(qiáng)的，從理論上說(shuō)，可以實(shí)現(xiàn)很復(fù)雜的功能，跟比特幣簡(jiǎn)單的腳本不太一樣，所以以太坊中如果不保存前面的狀態(tài)，智能合約執(zhí)行完之后，想在推算出前面是什么狀態(tài)，這是不可能的，所以想支持回滾，必須保存歷史狀態(tài)。

?

?

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

1.塊頭Block Header的定義

Bloom

布隆過(guò)濾器，提供一種高效的查詢符合某種條件的交易的執(zhí)行結(jié)果（跟收據(jù)樹是相關(guān)的）

GasLimit

單個(gè)區(qū)塊允許的最多Gas總量（智能合約要消耗汽油費(fèi)，類似于比特幣中的交易費(fèi)）

GasUsed

該交易消耗的總Gas數(shù)量

?

?

?2.區(qū)塊Block的定義

3.External block

????????一個(gè)區(qū)塊真正在網(wǎng)上發(fā)布的時(shí)候就是發(fā)布這些信息。

?

狀態(tài)樹中保存的是（key,value)，key就是地址，前面主要講的是鍵值，這個(gè)地址的管理方式。value，即賬戶的狀態(tài)，是如何存儲(chǔ)在狀態(tài)樹當(dāng)中的？這需要經(jīng)過(guò)一個(gè)序列化（RLP：Recursive?Length Prefix）的過(guò)程，然后再存儲(chǔ)。

RLP是一種序列化方法，其特點(diǎn)是極簡(jiǎn)主義，越簡(jiǎn)單越好。

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

跟這些庫(kù)相比，RLP的理念就是越簡(jiǎn)單越好，只支持一種類型，nested array bytes（字節(jié)數(shù)組），即一個(gè)一個(gè)字節(jié)組成的數(shù)組（可以嵌套）。以太坊里的所有的其他類型，如整數(shù)和哈希表等，最后都要變成nested array bytes。所以，實(shí)現(xiàn)RLP要比實(shí)現(xiàn)Protocal buffer簡(jiǎn)單很多，因?yàn)殡y的東西都不做，都交給應(yīng)用層做。

?

?

?

?

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

一、以太坊中，三種基于樹的數(shù)據(jù)結(jié)構(gòu)——狀態(tài)樹、交易樹和收據(jù)樹。

所有的交易會(huì)組成一棵Merkle tree，叫交易樹，類似于比特幣系統(tǒng)中的Merkle tree。此外，以太坊中還增加了收據(jù)樹，每個(gè)交易執(zhí)行完之后會(huì)形成一個(gè)記錄這個(gè)其相關(guān)信息的收據(jù)，交易樹和收據(jù)樹上面的節(jié)點(diǎn)是一一對(duì)應(yīng)的。增加這個(gè)收據(jù)樹的目的是便于快速查詢執(zhí)行的結(jié)果（主要因?yàn)橐蕴坏闹悄芎霞s執(zhí)行過(guò)程比較復(fù)雜）。

?

從數(shù)據(jù)結(jié)構(gòu)上來(lái)看，交易樹和收據(jù)樹都是MPT（Merkle Patricia tree），BTC中是MT（Merkle tree）。以太坊中的三棵樹都用同樣的數(shù)據(jù)結(jié)構(gòu)，這樣代碼比較統(tǒng)一，便于管理，用MPT的一個(gè)好處是支持查找操作，可以通過(guò)鍵值從頂向下沿著這顆樹查找。在狀態(tài)樹中，查找的鍵值就是這個(gè)賬戶的地址，對(duì)于交易樹和收據(jù)樹來(lái)說(shuō)，查找的鍵值就是這個(gè)交易在發(fā)布的區(qū)塊里的序號(hào)，這個(gè)交易的排列順序是由發(fā)布區(qū)塊的那個(gè)節(jié)點(diǎn)決定的。

?

二、狀態(tài)樹、交易樹和收據(jù)樹的區(qū)別

（1）交易樹和收據(jù)樹都是只將當(dāng)前發(fā)布的區(qū)塊里的交易組織起來(lái)，狀態(tài)樹需要把系統(tǒng)中所有賬戶的狀態(tài)都要包含進(jìn)去。

?

（2）從數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)，多個(gè)區(qū)塊的狀態(tài)樹是共享節(jié)點(diǎn)的（新發(fā)布一個(gè)區(qū)塊的時(shí)候，只有該區(qū)塊中改變了狀態(tài)的節(jié)點(diǎn)需要新建一個(gè)分支，其他節(jié)點(diǎn)都是沿用原來(lái)狀態(tài)樹上的節(jié)點(diǎn)），相比之下，每個(gè)區(qū)塊的交易樹和收據(jù)樹都是獨(dú)立的，是不會(huì)共享節(jié)點(diǎn)的（一個(gè)區(qū)塊和另一個(gè)區(qū)塊發(fā)布的交易本身也認(rèn)為是獨(dú)立的）。

?

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

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

①向輕節(jié)點(diǎn)提供Merkle Proof。

②支持一些更加復(fù)雜的查詢操作。

比如，查詢過(guò)去十天當(dāng)中，所有與某個(gè)智能合約有關(guān)的交易（一種方法是把過(guò)去十天產(chǎn)生的所有區(qū)塊都掃描一遍，缺點(diǎn)：①?gòu)?fù)雜度較高；②存儲(chǔ)要大，保存整個(gè)集合的元素；③輕節(jié)點(diǎn)沒(méi)有交易列表，只有一個(gè)塊頭的信息，無(wú)法通過(guò)掃描所有交易列表來(lái)查詢）。

?

2.如何實(shí)現(xiàn)復(fù)雜的查詢操作

以太坊中引入了Bloom Filter布隆過(guò)濾器)，這種數(shù)據(jù)結(jié)構(gòu)可以支持比較高效的查找某個(gè)元素是不是在一個(gè)比較大的集合里。Bloom Filter給這個(gè)包含很多元素的集合計(jì)算出一個(gè)很緊湊的摘要（如一個(gè)128位的向量）。

例：如圖，給定一個(gè)數(shù)據(jù)集，含元素a、b、c，通過(guò)一個(gè)哈希函數(shù)H()對(duì)其進(jìn)行計(jì)算，將其映射到一個(gè)其初始全為0的128位的向量的某個(gè)位置，將該位置置為1。將所有元素處理完，就可以得到一個(gè)向量，則稱該向量為原集合的“摘要”。該“摘要”比原集合是要小很多。

假定想要查詢一個(gè)元素d是否在集合中，H(d)映射到向量中的位置處為0，不在；H(d)映射到向量中的位置處為1，有可能d在，有可能因哈希碰撞產(chǎn)生誤報(bào)。

所以使用Bloom Filter要注意，可能出現(xiàn)誤報(bào)false positive，不會(huì)出現(xiàn)漏報(bào)false negative。

?

Bloom Filter有各種各樣的變種，為解決這樣的哈希碰撞，有時(shí)候會(huì)用一組哈希函數(shù)，將某個(gè)待證明元素分別通過(guò)每個(gè)哈希函數(shù)映射到向量中的一個(gè)位置。一般來(lái)說(shuō)，不會(huì)所有的哈希函數(shù)都出現(xiàn)哈希碰撞。Bloom Filter的局限性是不支持刪除操作。比如把a(bǔ)刪掉了，對(duì)應(yīng)的向量1要不要改。若要支持刪除操作，則需要將向量中的值改成一個(gè)計(jì)數(shù)器，記錄該位置有多少元素映射過(guò)來(lái)，而且還需要考慮到計(jì)數(shù)器會(huì)不會(huì)溢出。

?

3.以太坊中Bloom Filter的用途

每個(gè)交易執(zhí)行完之后會(huì)形成一個(gè)包含Bloom Filter的收據(jù)，Bloom Filter用于記錄交易的類型、地址等信息。發(fā)布的區(qū)塊的塊頭里也有一個(gè)總的Bloom Filter，是這個(gè)區(qū)塊里所有交易的一個(gè)Bloom Filter的并集。

比如說(shuō)要查找過(guò)去十天發(fā)生的跟智能合約相關(guān)的交易，可以找一些有哪些區(qū)塊的塊頭的bloom filter有要的交易類型，如果有，再去查找區(qū)塊里面包含的交易所對(duì)應(yīng)的收據(jù)樹里面的那些Bloom Filter（就每個(gè)收據(jù)的bloom filter）看看哪個(gè)有，也可能都沒(méi)有，可能是false positive。如果是有的話，再找到相對(duì)應(yīng)的交易直接進(jìn)行一下確認(rèn)，好處是通過(guò)Bloom Filter的結(jié)構(gòu)能夠快速過(guò)濾掉大量無(wú)關(guān)的區(qū)塊。

?

四、以太坊的運(yùn)行過(guò)程

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

比特幣系統(tǒng)也可以認(rèn)為是一個(gè)交易驅(qū)動(dòng)的狀態(tài)機(jī)，比特幣中的狀態(tài)是UTXO（沒(méi)有被花掉的那些輸出），每次新發(fā)布一個(gè)區(qū)塊，會(huì)從UTXO里用掉一些輸出，又會(huì)增加一些新的輸出，發(fā)布的區(qū)塊會(huì)驅(qū)動(dòng)系統(tǒng)從當(dāng)前狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)。而且這兩個(gè)狀態(tài)機(jī)有一個(gè)共同的特點(diǎn)，就是狀態(tài)轉(zhuǎn)移都得是確定的，對(duì)一個(gè)給定的當(dāng)前狀態(tài)，一組給定的區(qū)塊中包含的交易，能確定性地轉(zhuǎn)移到下一個(gè)狀態(tài)。因?yàn)樗械娜?jié)點(diǎn)，所有的礦工，都要執(zhí)行同樣的狀態(tài)轉(zhuǎn)移，所以狀態(tài)轉(zhuǎn)移必須是確定性的。

?

問(wèn)題：

1、A轉(zhuǎn)賬到B，有沒(méi)有可能收款賬戶不包含在狀態(tài)樹中？

可能。因?yàn)橐蕴恢匈~戶可以節(jié)點(diǎn)自己產(chǎn)生，只有在產(chǎn)生交易時(shí)才會(huì)被系統(tǒng)知道。

?

2、可否將每個(gè)區(qū)塊中狀態(tài)樹更改為只包含和區(qū)塊中交易相關(guān)的賬戶狀態(tài)？

不能。①查找賬戶狀態(tài)很不方便；②因?yàn)樾枰朗湛钯~戶的狀態(tài)，才能給其添加金額，要向一個(gè)新創(chuàng)建賬戶轉(zhuǎn)賬，所有需要一直找到創(chuàng)世紀(jì)塊才能知道該賬戶為新建賬戶，系統(tǒng)中并未存儲(chǔ)，而區(qū)塊鏈?zhǔn)遣粩嘌娱L(zhǎng)的。

?

交易樹和收據(jù)樹的創(chuàng)建過(guò)程——代碼中的具體體現(xiàn)

鏈接：https://blog.csdn.net/YSL_Lsy_/article/details/126436571?spm=1001.2014.3001.5502

?

18-ETH-GHOST

一、以太坊的出塊時(shí)間及可能帶來(lái)的問(wèn)題

1.以太坊的出塊時(shí)間

以太坊將出塊時(shí)間降到了十幾秒，提高了系統(tǒng)的吞吐量（Throughput）、降低了反應(yīng)時(shí)間。比特幣和以太坊都是運(yùn)行在應(yīng)用層的共識(shí)協(xié)議，底層是一個(gè)P2P的Overlay Network，Overlay Network本身的傳輸時(shí)間比較長(zhǎng)（其拓?fù)鋮f(xié)議做flooding的時(shí)候沒(méi)有考慮實(shí)際的拓?fù)浣Y(jié)構(gòu)）。

問(wèn)題：發(fā)布區(qū)塊時(shí)，該區(qū)塊在網(wǎng)絡(luò)上傳到其他節(jié)點(diǎn)可能需要十幾秒，那么就有較大可能會(huì)有兩個(gè)節(jié)點(diǎn)（甚至多個(gè)），同時(shí)獲得記賬權(quán)，從而造成臨時(shí)性分叉。

?

2.以太坊與比特幣系統(tǒng)的平均出塊時(shí)間對(duì)比

對(duì)于比特幣系統(tǒng)來(lái)說(shuō)，平均出塊時(shí)間是600秒，足夠讓新發(fā)布的區(qū)塊傳播到網(wǎng)上的其他節(jié)點(diǎn)，但挖礦是個(gè)概率的過(guò)程，仍有兩個(gè)礦工同時(shí)獲得記賬權(quán)、同時(shí)發(fā)布區(qū)塊的可能，會(huì)帶來(lái)臨時(shí)性的分叉。

在以太坊中，這種臨時(shí)性的分叉會(huì)變成常態(tài)，而且分叉的數(shù)目也會(huì)變得更多，這對(duì)于共識(shí)協(xié)議來(lái)說(shuō)，是一個(gè)挑戰(zhàn)。

?

?

3.帶來(lái)的問(wèn)題

?

假定中間區(qū)塊勝出，則上下兩個(gè)區(qū)塊叫做Orphan Block或Stale Block，挖到這類區(qū)塊的礦工在里面有一個(gè)鑄幣交易，得到的出塊獎(jiǎng)勵(lì)最后等于作廢。對(duì)于比特幣來(lái)說(shuō)，這種臨時(shí)性的分叉不是很多，所以這么規(guī)定可以接受。

對(duì)于以太坊來(lái)說(shuō)，如果也將分叉區(qū)塊的出塊獎(jiǎng)勵(lì)作廢的話，則意味著這個(gè)礦工挖到的區(qū)塊有很大概率是白挖，對(duì)于個(gè)體礦工特別明顯。按照常理，礦工的收益應(yīng)該與算力成正比，礦池的收益也應(yīng)當(dāng)與礦池的總算力成正比。但大型礦池會(huì)出現(xiàn)Mining Centralization（挖礦集中化），即大型礦池所在的分叉更有可能成為最長(zhǎng)合法鏈，這促使別的礦工沿著最長(zhǎng)合法鏈繼續(xù)挖。這樣會(huì)使大型礦池出現(xiàn)惡性循環(huán)，越是大型礦池得到的收益越大，Mining Centralization更嚴(yán)重，有時(shí)候叫Centralization Bias，即中心化帶來(lái)的不成比例的優(yōu)勢(shì)。如果以太坊按照比特幣的共識(shí)機(jī)制就會(huì)有一定的問(wèn)題。

?

二、GHOST協(xié)議

為解決以太坊如果按照比特幣的共識(shí)機(jī)制產(chǎn)生的問(wèn)題，采用一個(gè)基于GHOST協(xié)議的共識(shí)機(jī)制，這個(gè)協(xié)議并非以太坊發(fā)明的，以太坊只是對(duì)該協(xié)議做了一些修改。

?

1.GHOST協(xié)議的核心思想

挖到礦的礦工發(fā)布一個(gè)區(qū)塊，即便這個(gè)區(qū)塊最后作廢了，也能得到一些出塊獎(jiǎng)勵(lì)，將作廢的區(qū)塊（Orphan Block或Stale Block）稱為Uncle Block。相對(duì)于最長(zhǎng)合法鏈的當(dāng)前區(qū)塊來(lái)說(shuō)，是他的叔父區(qū)塊，最長(zhǎng)合法鏈的下一個(gè)區(qū)塊在發(fā)布的時(shí)候可以把叔父區(qū)塊包含進(jìn)來(lái)，如下圖。

該協(xié)議的核心思想是：給予挖到礦但是沒(méi)有成為最長(zhǎng)合法鏈的那些礦工一種安慰。這樣有利于鼓勵(lì)系統(tǒng)中出現(xiàn)分叉后及時(shí)合并，相當(dāng)于最長(zhǎng)合法鏈上面的區(qū)塊將另外兩個(gè)分叉鏈給招安過(guò)來(lái)，這是GHOST協(xié)議最初的版本。

?

2.GHOST協(xié)議的缺陷

（1）Uncle Block的個(gè)數(shù)不能超過(guò)兩個(gè)

設(shè)計(jì)GHOST的目的是給Uncle Block一點(diǎn)好處，把它們合并過(guò)來(lái)，但是只能招安兩個(gè)。叔父區(qū)塊得到八分之七的出塊獎(jiǎng)勵(lì)是很高的，要是不限制的話，那么以太幣就太不值錢了。

?

（2）區(qū)塊傳播存在延遲

區(qū)塊D把區(qū)塊A作為叔父區(qū)塊的前提是：在挖這個(gè)區(qū)塊D的時(shí)候已經(jīng)知道區(qū)塊A這個(gè)叔父區(qū)塊的存在。

?

（3）受礦工主觀影響

如果這個(gè)礦工比較自私的話，有可能故意不包含叔父區(qū)塊。對(duì)叔父區(qū)塊來(lái)說(shuō)，7/8的出塊獎(jiǎng)勵(lì)是得不到的，對(duì)于他自己來(lái)說(shuō)，1/32的出塊獎(jiǎng)勵(lì)是得不到了，好像是損人不利己，但要從商業(yè)競(jìng)爭(zhēng)的角度講，這么做對(duì)這個(gè)礦工的損失是比較小的，對(duì)挖出叔父區(qū)塊的礦工的損失是比較大的。

?

3.改進(jìn)后的GHOST協(xié)議

決了礦池出于競(jìng)爭(zhēng)關(guān)系故意不把某個(gè)叔父區(qū)塊包含進(jìn)去的問(wèn)題。比如區(qū)塊D故意不包含區(qū)塊A，但是區(qū)塊E仍然可以包含區(qū)塊A。甚至有可能出現(xiàn)一個(gè)情況：挖到區(qū)塊A的礦工發(fā)現(xiàn)自己不在最長(zhǎng)合法鏈上，就沿著區(qū)塊D挖出了區(qū)塊E，然后就可以把自己的區(qū)塊A包含進(jìn)去。

?

也解決了出現(xiàn)第三個(gè)叔父區(qū)塊的問(wèn)題。把叔父的定義擴(kuò)展了，可能是隔著幾代的叔父。以太坊規(guī)定，叔父區(qū)塊可以得到7/8的出塊獎(jiǎng)勵(lì)。如果往前推一代，叔父區(qū)塊得到6/8的出塊獎(jiǎng)勵(lì)。合法的叔父只有6個(gè)輩分。

為什么設(shè)定合法的叔父必須在當(dāng)前區(qū)塊在七代以內(nèi)且有共同的祖先？

（1）如果不限制，全節(jié)點(diǎn)需要維護(hù)非常多的狀態(tài)（可能要記著隔著100代以前有哪些叔父區(qū)塊），新發(fā)布的區(qū)塊包含的叔父區(qū)塊，其他節(jié)點(diǎn)同樣也需要驗(yàn)證；

?

（2）設(shè)計(jì)最多隔著7代，且出塊獎(jiǎng)勵(lì)是逐漸遞減的，有利于鼓勵(lì)出現(xiàn)分叉之后，盡早合并，一出現(xiàn)分叉就馬上合并的時(shí)候能得到的出塊獎(jiǎng)勵(lì)是最多的。

?

叔父區(qū)塊的獎(jiǎng)勵(lì)叫做Uncle Reward，當(dāng)前區(qū)塊包含一個(gè)叔父區(qū)塊，就會(huì)得到1/32的出塊獎(jiǎng)勵(lì)，不論包含的是哪一個(gè)輩分的叔父。

?

4.改進(jìn)后的GHOST協(xié)議無(wú)法解決的問(wèn)題

主要是為了解決系統(tǒng)中出現(xiàn)的臨時(shí)性分叉（State Fork），規(guī)定最長(zhǎng)合法鏈的原則的目的是防止篡改，也是為了解決臨時(shí)性分叉。

如果這個(gè)分叉是別的原因造成的，比如由于對(duì)運(yùn)行的區(qū)塊鏈協(xié)議有不同的意見(jiàn)，那么這種方法是解決不了的，也就是說(shuō)，改進(jìn)后的GHOST協(xié)議仍然無(wú)法解決硬分叉。

?

例如，比特幣系統(tǒng)跟中心化的系統(tǒng)不一樣（中心化的系統(tǒng)發(fā)布一個(gè)新版本很容易），去中心化系統(tǒng)如果修改的話，會(huì)出現(xiàn)硬分叉。下圖的那兩條鏈如果不是因?yàn)閷?duì)當(dāng)前狀態(tài)有意見(jiàn)分歧，而是互相認(rèn)為對(duì)方是非法的，那么用這種方法是合并不了的。如果有礦工將這樣的區(qū)塊包含進(jìn)來(lái)，其他礦工會(huì)認(rèn)為這條鏈?zhǔn)欠欠ǖ?，還是不會(huì)沿著這條鏈繼續(xù)挖，因?yàn)椋杭词怪麈溩铋L(zhǎng)，但是包含非法交易。

三、以太坊中的獎(jiǎng)勵(lì)

區(qū)塊鏈和以太坊發(fā)布一個(gè)區(qū)塊能得到的獎(jiǎng)勵(lì)如下圖，叔父區(qū)塊得到八分之七的獎(jiǎng)勵(lì)只限于Block Reward，即7/8×3ETH。叔父區(qū)塊是得不到汽油費(fèi)的，但汽油費(fèi)所占的比例是非常小的，大部分是出塊獎(jiǎng)勵(lì)，跟比特幣的情況是類似的。

以太坊中沒(méi)有規(guī)定定期要把出塊獎(jiǎng)勵(lì)減半，比特幣那么規(guī)定是為了人為制造稀缺性，以太坊中五個(gè)以太幣降為三個(gè)以太幣，不是為了認(rèn)為制造稀缺性，實(shí)際上跟挖礦難度調(diào)整有關(guān)，2017年，挖礦難度炸彈被回調(diào)了300萬(wàn)個(gè)區(qū)塊，導(dǎo)致挖礦難度大幅度下降，為了維護(hù)公平性，也是為了使以太幣的供給量不要出現(xiàn)劇烈變化，所以降到了三個(gè)以太幣，這是一次性的，并沒(méi)有說(shuō)以后會(huì)不斷地下調(diào)。

?

比特幣一般當(dāng)作數(shù)字黃金，是用來(lái)儲(chǔ)值的；以太幣被比喻成石油，它是用來(lái)花的，用來(lái)消耗，然后可以執(zhí)行智能合約的。這個(gè)比喻不是完全的恰當(dāng)，因?yàn)槭突ㄍ曛缶蜎](méi)了，而以太坊中執(zhí)行智能合約要消耗的gas，只是從一個(gè)賬戶轉(zhuǎn)移到另外一個(gè)賬戶，發(fā)布智能合約的時(shí)候，要付出gas費(fèi)，執(zhí)行這個(gè)智能合約的礦工可以得到這個(gè)gas費(fèi)，所以這個(gè)比喻也不完全恰當(dāng)。

?

四、思考

1.把叔父區(qū)塊包含進(jìn)來(lái)的時(shí)候，叔父區(qū)塊的交易要不要執(zhí)行？

不應(yīng)該執(zhí)行，最長(zhǎng)合法鏈上的父區(qū)塊和他的叔父區(qū)塊包含的交易可能是沖突的，如果它們包含不同的交易，不同交易有可能不能都執(zhí)行。在以太坊中，雙花攻擊花兩次減兩次，但是有可能一個(gè)交易花了之后，另一個(gè)交易就沒(méi)法花了。叔父區(qū)塊本身不一定是非法的，但執(zhí)行完父區(qū)塊的交易，再去執(zhí)行叔父區(qū)塊的交易可能就變成非法的。

以太坊中只執(zhí)行在最長(zhǎng)合法鏈上的交易。而且根本就不檢查叔父區(qū)塊交易的合法性，只檢查叔父區(qū)塊是不是一個(gè)合法發(fā)布的區(qū)塊，即這個(gè)區(qū)塊是不是符合挖礦難度，也就是有沒(méi)有獲得記賬權(quán)。

?

2.叔父區(qū)塊能不能廣義化？

叔父區(qū)塊都是分叉之后第一個(gè)區(qū)塊。假定，將后面一連串的區(qū)塊認(rèn)為是叔父區(qū)塊，會(huì)造成一個(gè)后果：分叉攻擊的代價(jià)過(guò)低。正常意義上的分叉攻擊需要使分叉鏈長(zhǎng)度大于原來(lái)最長(zhǎng)合法鏈長(zhǎng)度才算成功，否則這些用來(lái)分叉攻擊的區(qū)塊會(huì)作廢，原本的出塊獎(jiǎng)勵(lì)也沒(méi)有了。如果將分叉鏈上的區(qū)塊認(rèn)為是叔父區(qū)塊的話，分叉攻擊不成還能作為叔父區(qū)塊獲得一些獎(jiǎng)勵(lì)。所以以太坊中規(guī)定，只有分叉后的第一個(gè)區(qū)塊可以得到Uncle Reward，后面的都不行。

五、以太坊中的真實(shí)情況

Etherscan.io可以實(shí)時(shí)查看以太坊的當(dāng)前狀態(tài)，右邊這個(gè)曲線顯示的是過(guò)去兩周的交易歷史，下面還包含最新挖出的區(qū)塊和最新的交易。

下圖所示為叔父區(qū)塊的幾種情況，這里的每一行對(duì)應(yīng)一個(gè)叔父區(qū)塊，第一列的Block Height就是區(qū)塊的序號(hào)，也就是Block Number，與表中不同輩分的叔父得到的Uncle Reward的數(shù)目相對(duì)應(yīng)。

下圖是兩個(gè)區(qū)塊的具體例子，左邊這個(gè)區(qū)塊包含了一個(gè)叔父區(qū)塊，倒數(shù)第二行uncle reward是2.25，應(yīng)該是距離為2的叔父。這個(gè)區(qū)塊得到的獎(jiǎng)勵(lì)，在倒數(shù)第三行，有三個(gè)部分組成，即3ETH出塊獎(jiǎng)勵(lì)、汽油費(fèi)和包含叔父區(qū)塊得到的三十二分之一的出塊獎(jiǎng)勵(lì)。

?

?