北京大學(xué)肖臻老師《區(qū)塊鏈技術(shù)與應(yīng)用》筆記 - ETH篇
北大肖臻《區(qū)塊鏈技術(shù)與應(yīng)用》公開課學(xué)習(xí)筆記
區(qū)塊鏈知識(shí)

ETH 賬戶

• ETH 維持賬戶的概念, 這種賬戶的概念和我們平時(shí)使用的賬戶概念相似, 這個(gè)ETH賬戶概念可以有效抵御雙花問題. 但是同時(shí)會(huì)產(chǎn)生重放攻擊的問題.
  • double spending attack(雙花攻擊, 支付方不誠(chéng)實(shí), 一筆錢花了兩次) : , 比特幣中使用UTXO交易模型抵御 double spending attack;
  • replay attack(重放攻擊 收款方不誠(chéng)實(shí), 復(fù)制這次交易, 收兩次錢) : , ETH中使用計(jì)數(shù)器(每筆交易中都有一個(gè)nonce字段, 用來記錄這是第多少比交易), 如果有人重放這次交易的話, 需要修改 nonce 字段, 但是如果修改了 nonce 字段, 那么這次交易的hash就會(huì)改變, 由于其他人沒有私鑰, 無法重新簽名, 所以這樣可以有效的抵御重放攻擊.
• 賬戶分類
  • 外部賬戶 (使用公私鑰控制的賬戶.)
    • balance (賬戶余額)
    • nonce (交易計(jì)數(shù))
  • 合約賬戶(不能主動(dòng)發(fā)起交易, 所有的交易只能由外部賬戶發(fā)起. 合約賬戶只能調(diào)用另一個(gè)合約)
  • ETH 添加合約賬戶, 是因?yàn)? ETH 使用了智能合約, 而使用合約需要一個(gè)穩(wěn)定的賬戶(BTC中沒有穩(wěn)定的賬戶), 不能使用某個(gè)賬戶簽訂完合約后, 又使用另一個(gè)賬戶去履行合約), 創(chuàng)建合約時(shí)候會(huì)返回一個(gè)地址, 通過地址可以調(diào)用合約, 調(diào)用過程代碼不變但是狀態(tài)會(huì)發(fā)生改變.
    • balance (賬戶余額)
    • nonce (合約的調(diào)用次數(shù))
    • code (代碼)
    • storage( 存儲(chǔ), 每個(gè)變量的值)

狀態(tài)樹

• 作用

  • 防篡改, 只要 Merkle Patricia Trie root hash 沒有改變, 整個(gè)樹的任何部分都無法篡改.
  • 通過提供自己賬戶所在的分支作為 merkle proof 提供給輕節(jié)點(diǎn), 輕節(jié)點(diǎn)可以驗(yàn)證賬戶的余額.
  • 可以證明某個(gè)收款賬戶是不存在的.

• ETH中使用MPT(Modified Merkle Patricia Trie)做的狀樹(address和state的映射關(guān)系, key是地址, value是賬戶狀態(tài)(將賬戶狀態(tài)序列化(RLP編碼 : Recursive Length Prefix)存儲(chǔ)在樹中));

  • 使用字典 : 無法提供 merkle proof, 因?yàn)槿绻峁﹎erkle proof, 需要將字典中的元素組織成 merkle tree, 然后將 merkle root hash 保存, 但是有個(gè)問題是每次有新的交易產(chǎn)生, 需要遍歷所有的用戶, 然后重新組織成merkle tree, 而用戶量是巨大的(BTC中的 merkle proof 用在block中, 每個(gè)block中大約有4000個(gè)交易, 而且組織完之后是不需要改變的, 區(qū)塊打包后不用改變)

  • 直接使用merkle tree : 沒有高效的查找和更新的方法. 而且如果這個(gè)merkle tree的葉子結(jié)點(diǎn)沒有排序, 那么每個(gè)人的生成的merkle tree是不唯一的, 算出的merkle root hash也不唯一(BTC中的merkle tree是獲得記賬權(quán)的節(jié)點(diǎn)說了算的);

  • 使用排序的 merkle tree : 新增一個(gè)賬戶發(fā)生交易的時(shí)候, 整個(gè)merkle tree 的結(jié)構(gòu)還是要改變的.

  • trie(字典樹, 前綴樹) :

    • trie中每個(gè)節(jié)點(diǎn)的分支數(shù)目取決于Key值中每個(gè)元素的取值范圍(圖例中最多26個(gè)英文字母分叉+一個(gè)結(jié)束標(biāo)志位);
    • trie查找效率取決于key的長(zhǎng)度符相。實(shí)際應(yīng)用中（以太坊地址長(zhǎng)度為160byte）榛做。;
    • trie中每個(gè)節(jié)點(diǎn)的分支數(shù)目取決于Key值中每個(gè)元素的取值范圍(圖例中最多26個(gè)英文字母分叉+一個(gè)結(jié)束標(biāo)志位);
    • 給定輸入纷闺，無論如何順序插入，構(gòu)造的trie都是一樣的
    • 更新操作局部性較好

    • 樹的高度太高, 對(duì)內(nèi)存不友好.

      
      
      image.png

  • Patricia trie(壓縮前綴樹) : 壓縮樹的高度(對(duì)于key分布稀疏的情況, 使用壓縮前綴樹和使用前綴樹的差別是很明顯的)

    
    
    image.png

  • Merkle Patricia Trie(MPT) :

  • Modified Merkle Patricia Trie : (ETH中使用 Modified Merkle Patricia Trie)

    
    
    image.png

• 發(fā)布新區(qū)塊, 狀態(tài)樹中的部分節(jié)點(diǎn)狀態(tài)會(huì)改變. 這種改變不是原地修改, 而是保留原本狀態(tài)并新建分支, 這樣方便回滾(分叉節(jié)點(diǎn)回滾回上一個(gè)狀態(tài)并拼接到最長(zhǎng)鏈后邊).

  
  
  image.png

• 數(shù)據(jù)結(jié)構(gòu)

  • header

    
    
    image.png

  • block

    
    
    image.png

  • 區(qū)塊在網(wǎng)絡(luò)上發(fā)布的時(shí)候的信息

    
    
    image.png

交易樹

• 只組織當(dāng)前發(fā)布的區(qū)塊的交易, 狀態(tài)樹需要把系統(tǒng)中所有賬戶的狀態(tài)都包含進(jìn)去,無論賬戶和當(dāng)前區(qū)塊是否有關(guān)系.
• 各個(gè)節(jié)點(diǎn)之間不同享節(jié)點(diǎn)
• 向輕節(jié)點(diǎn)提供 Merkle proof, 證明某個(gè)交易被打包到區(qū)塊中.

收據(jù)樹

• 只組織當(dāng)前發(fā)布的區(qū)塊的交易, 狀態(tài)樹需要把系統(tǒng)中所有賬戶的狀態(tài)都包含進(jìn)去, 無論賬戶和當(dāng)前區(qū)塊是否有關(guān)系.
• 各個(gè)節(jié)點(diǎn)之間不同享節(jié)點(diǎn)
• 向輕節(jié)點(diǎn)提供 Merkle proof, 證明某個(gè)交易的執(zhí)行結(jié)果.

布隆過濾器

• 可以證明某個(gè)元素一定不能在集合中/可能(發(fā)送hash碰撞, 會(huì)誤報(bào), 所以是可能)在集合中.
• 每個(gè)收據(jù)中包含一個(gè)布隆過濾器, 幾率交易的類型, 地址等其他信息, 發(fā)布的區(qū)塊在header中也有個(gè)總的布隆過濾器, 這個(gè)總的布隆過濾器是區(qū)塊中所有交易的所有布隆過濾器的并集.
• 使用布隆過濾器, 查找過去某個(gè)時(shí)間段內(nèi)的發(fā)生的和某個(gè)智能合約相關(guān)的所有交易, 先查詢哪個(gè)header的中總的布隆過濾器中包含要查找的交易類型, 如果塊頭的總布隆過濾器中不包含這個(gè)交易, 則表示一定沒有, 如果包含這個(gè)交易類型,在去查找區(qū)塊中所包含的交易所對(duì)應(yīng)的收據(jù)樹中的布隆過濾器.

GHOST 協(xié)議

• 因?yàn)镋TH中的出塊時(shí)間大幅度減少(15s), 但是導(dǎo)致頻繁的臨時(shí)分叉, 且分叉多, 這對(duì)于共識(shí)協(xié)議是個(gè)挑戰(zhàn), 所以使用了改善的 GHOST協(xié)議(對(duì)于非決策節(jié)點(diǎn), 也給予挖礦獎(jiǎng)勵(lì), 否則會(huì)大大降低礦工的挖礦積極性, 而礦工相對(duì)于大型礦池相比, 有天然的劣勢(shì)(礦池可能一直沿著自己挖出的區(qū)塊接著挖), ).
• 方案

  • 第一版

    • 規(guī)則
      • 規(guī)定E區(qū)塊在發(fā)布時(shí)可以將A守问、C、D叔父區(qū)塊包含進(jìn)來，A、C颖对、D叔父區(qū)塊可以得到出塊獎(jiǎng)勵(lì)的7/8，而為了激勵(lì)E包含叔父區(qū)塊磨隘，規(guī)定E每包含一個(gè)叔父區(qū)塊可以額外得到1/32的出塊獎(jiǎng)勵(lì)缤底。為了防止E大量包含叔父區(qū)塊，規(guī)定一個(gè)區(qū)塊只能最多包含兩個(gè)叔父區(qū)塊番捂，因此E在A个唧、C、D中最多只能包含兩個(gè)區(qū)塊作為自己的出塊獎(jiǎng)勵(lì)
    • 缺陷
      • 因?yàn)槭甯竻^(qū)塊最多只能包含兩個(gè)设预，如圖出現(xiàn)3個(gè)怎么辦徙歼？

      • 礦工自私，故意不包含叔父區(qū)塊鳖枕，導(dǎo)致叔父區(qū)塊7/8出塊獎(jiǎng)勵(lì)沒了魄梯，而自己僅僅損失1/32。如果甲宾符、乙兩個(gè)大型礦池存在競(jìng)爭(zhēng)關(guān)系酿秸，那么他們可以采用故意不包含對(duì)方的叔父區(qū)塊，因?yàn)檫@樣對(duì)自己損失小而對(duì)對(duì)方損失大魏烫。

        
        
        image.png

  • 第二版

  • 規(guī)則

    • F為E后面一個(gè)新的區(qū)塊允扇。因?yàn)橐?guī)定E最多只能包含兩個(gè)叔父區(qū)塊，所以假定E包含了C和D则奥。此時(shí)考润，F(xiàn)也可以將A認(rèn)為自己的的叔父區(qū)塊(實(shí)際上并非叔父輩的，而是爺爺輩的)读处。如果繼續(xù)往下挖糊治，F(xiàn)后的新區(qū)塊仍然可以包含B同輩的區(qū)塊(假定E、F未包含完)罚舱。這樣井辜，就有效地解決了上面提到的最初Ghost協(xié)議版本存在的缺陷。

  • 缺點(diǎn)

    • “叔父”這一定義隔多少代才好呢, 如果不限定, 只要一直出挖叔父區(qū)塊然后坐等收錢就行了, 不合理.

      
      
      image.png

  • 第三版

    • 規(guī)則

      • M為該區(qū)塊鏈上一個(gè)區(qū)塊管闷，F(xiàn)為其嚴(yán)格意義上的叔父粥脚，E為其嚴(yán)格意義上的“爺爺輩”。以太坊中規(guī)定包个，如果M包含F(xiàn)輩區(qū)塊刷允，則F獲得7/8出塊獎(jiǎng)勵(lì)；如果M包含E輩區(qū)塊，則F獲得6/8出塊獎(jiǎng)勵(lì)树灶，以此類推向前纤怒。直到包含A輩區(qū)塊，A獲得2/8出塊獎(jiǎng)勵(lì)天通，再往前的“叔父區(qū)塊”泊窘，對(duì)于M來說就不再認(rèn)可其為M的"叔父"了。 對(duì)于M來說像寒，無論包含哪個(gè)輩分的“叔父”烘豹，得到的出塊獎(jiǎng)勵(lì)都是1/32出塊獎(jiǎng)勵(lì), 也就是說，叔父區(qū)塊的定義是和當(dāng)前區(qū)塊在七代之內(nèi)有共同祖先才可（合法的叔父只有6輩）诺祸。

        
        
        image.png

  • 如果規(guī)定將下面整條鏈作為一個(gè)整體携悯，給予出塊獎(jiǎng)勵(lì)，這一定程度上鼓勵(lì)了分叉攻擊(降低了分叉攻擊的成本序臂，因?yàn)榧词构羰∫灿歇?jiǎng)勵(lì)獲得)。因此实束，ETH系統(tǒng)中規(guī)定奥秆，只認(rèn)可A區(qū)塊為叔父區(qū)塊，給予其補(bǔ)償咸灿，而其后的區(qū)塊全部作廢构订。

    
    
    image.png

ETH 挖礦算法

• 比特幣的挖礦算法需要專業(yè)的礦機(jī)進(jìn)行挖礦, 普通的計(jì)算機(jī)用戶難以參與, 導(dǎo)致挖礦中心化的局面產(chǎn)生, 與設(shè)計(jì)初衷的"去中心化"違背, 由此就誕生了ETH的ASIC Resistance挖礦算法. 還有人認(rèn)為使用礦機(jī)挖礦比使用通用計(jì)算機(jī)挖礦更安全, 因?yàn)槿绻腥诵枰l(fā)動(dòng)攻擊的時(shí)候, 需要購(gòu)買大量的礦機(jī)后參與挖礦然后才有可能發(fā)動(dòng)攻擊, 但是如果使用通用計(jì)算機(jī)挖礦, 那么很多科技公司可以在發(fā)動(dòng)攻擊時(shí)候使用自己的服務(wù)器去集中攻擊, 平時(shí)服務(wù)器還是正常使用.
• 萊特幣挖礦算法思想
  • 流程

    • seed位種子節(jié)點(diǎn), 通過對(duì)seed運(yùn)算出得出數(shù)組第一個(gè)元素, 之后每個(gè)元素都通過前一個(gè)位置的元素的hash得到. 這樣每個(gè)元素和前一個(gè)元素都是有依賴關(guān)系的.

      
      
      image.png

    • 求解puzzle的時(shí)候, 隨機(jī)一個(gè)索引, 根據(jù)索引從數(shù)組中取出一個(gè)元素, 然后對(duì)這個(gè)元素進(jìn)行運(yùn)算求出下一個(gè)索引, 然后重復(fù)這個(gè)過程.

      
      
      image.png
  • 分析
    • 如果數(shù)組足夠大, 礦工必須存儲(chǔ)這個(gè)數(shù)組, 而頻繁的訪問這個(gè)數(shù)組就涉及到大量的內(nèi)存讀取.從而實(shí)現(xiàn)對(duì)ASIC芯片不友好. 但是對(duì)于輕節(jié)點(diǎn)節(jié)點(diǎn)驗(yàn)證來說 一樣是不友好的, 驗(yàn)證的時(shí)候需要重復(fù)這個(gè)過程, 所以這個(gè)數(shù)組無法設(shè)置的過大, 只能是128K, 而128K對(duì)于礦機(jī)來說, 沒有起到應(yīng)有的作用.
• 以太坊挖礦算法思想

  • 流程

    • 以太坊設(shè)計(jì)了兩個(gè)數(shù)組, 分別是 16M的cache和1G的dataset(兩個(gè)數(shù)組的大小是初始大小, 每隔30000個(gè)區(qū)塊, newSeed = hash(seed), newCache.size = cache.size + cache.size * 1 / 128(增加128K), newDataSet.size = dataset.size + dataset.size * 1 / 128 (增加8M)). 在cache中通過hash(seed)得出數(shù)組第一個(gè)元素, 之后每個(gè)元素都通過前一個(gè)位置的元素的hash得到. 這樣每個(gè)元素和前一個(gè)元素都是有依賴關(guān)系的.dataset中的每個(gè)元素都是隨機(jī)一個(gè)索引, 根據(jù)索引從數(shù)組中取出一個(gè)元素, 然后對(duì)這個(gè)元素進(jìn)行運(yùn)算求出下一個(gè)索引, 然后重復(fù)256次, 得出的結(jié)果放在dataset的數(shù)組中.

      
      
      image.png
    • 求解puzzle的時(shí)候根據(jù)區(qū)塊block header 和其中的 nonce值計(jì)算一個(gè)初始hash, 根據(jù)hash值映射到數(shù)組中的索引A, 讀取A及A(A下一個(gè)索引)位置的元素, 然后對(duì)兩個(gè)數(shù)組進(jìn)行運(yùn)算, 得出下一個(gè)索引B和B, 循環(huán)執(zhí)行64次. 將最終得到的hash值與難度目標(biāo)閾值比較, 如果 result <= target求解puzzle成功, 否則更換nonce然后重復(fù)以上過程直到最終result <= target; 輕節(jié)點(diǎn)驗(yàn)證的時(shí)候, 是臨時(shí)計(jì)算出用到的dataset的元素.
      
      image.png

  • 偽代碼

    
    
    image.png

  • mkcache

  • 分析

    • 目前以太坊挖礦以GPU為主，可見其設(shè)計(jì)較為成功避矢，這與以太坊設(shè)計(jì)的挖礦算法(Ethash)所需要的大內(nèi)存具有很大關(guān)系悼瘾。

挖礦難度調(diào)整

• 難度調(diào)整算法

  • 難度最小值是 D0, 第0個(gè)區(qū)塊的難度就是D0;

    
    
    image.png

  • 自適應(yīng)難度調(diào)整, 基于父區(qū)塊的時(shí)間戳和本區(qū)塊的時(shí)間戳(單位是s).

    
    
    image.png
    
    
    image.png
  • 難度炸彈, 難度炸彈設(shè)計(jì)的目的是防止從Pow轉(zhuǎn)為Pos時(shí)候, 一部分礦工不轉(zhuǎn)換, 使ETH分叉, 使用難度炸彈后, 如果礦工不轉(zhuǎn)換到Pos, 那么難度炸彈的威力指數(shù)上升, 礦工挖礦難度大幅度提升.

  • 起初難度炸彈沒有減去300W的操作, 但是當(dāng)難度炸彈的威力體現(xiàn)出來的時(shí)候, 發(fā)現(xiàn)Pos的一些問題還沒有解決掉, 無法切換, 這時(shí)候通過減去300W的操作延遲難度炸彈的威力，為POS的實(shí)現(xiàn)爭(zhēng)取了一定的時(shí)間

    
    
    image.png

• 難度炸彈代碼

  
  
  tz8jrpi6wq.jpg

權(quán)益證明 (proof of state)

• 定義
  • 按照所占權(quán)益投票進(jìn)行共識(shí)達(dá)成审胸，類似于股份制有限共識(shí)按照股份多少投票亥宿，權(quán)益證明不需要挖礦. 這對(duì)于礦機(jī)廠商來說很不友好, 因?yàn)榈V機(jī)的開發(fā)周期長(zhǎng), 成本高, 如果礦機(jī)開發(fā)成功了, 以太坊改為使用權(quán)益證明達(dá)成共識(shí), 這對(duì)以礦機(jī)廠商來說很尷尬, 以太坊目前仍然是POW挖礦共識(shí)機(jī)制。在設(shè)計(jì)之初以太坊生成自己下一年就改成POS, 然后第二年說自己下一年就使用POS, 就這么一直騙砂沛，以太坊開發(fā)者就設(shè)想要從POW轉(zhuǎn)向POS烫扼，并為了防止有礦工不愿意轉(zhuǎn)埋下了一顆“難度炸彈”。但截至目前碍庵，以太坊仍然基于POW共識(shí)機(jī)制映企。
• 預(yù)挖礦(Pre-Mining) : 開發(fā)以太坊時(shí)，給開發(fā)者預(yù)留了一部分貨幣給開發(fā)者
• 預(yù)售(Pre-Sale) : 將預(yù)留的貨幣出售掉用于后續(xù)開發(fā)静浴，類似于拉風(fēng)投或眾籌.
• 分析
  • 使用Pow共識(shí)機(jī)制, 超級(jí)有錢的大戶可以購(gòu)買大量的礦機(jī), 然后集中攻擊一些小幣種, 使去區(qū)塊鏈賬本回滾, 從而讓用戶不在相信這種幣, 然后將這種幣扼殺.
  • 使用Pos共識(shí)機(jī)制, 只有擁有大量的幣的用戶才可以投票, 那么只能購(gòu)買大量的幣, 而購(gòu)買大量的幣會(huì)使幣的價(jià)格上漲.
    • 分析
      • 簡(jiǎn)單的共識(shí)機(jī)制, 會(huì)導(dǎo)致?lián)碛袔旁蕉嗟娜送诘V變得越簡(jiǎn)單.
      • 簡(jiǎn)單的共識(shí)機(jī)制, 會(huì)出現(xiàn)有的人兩邊下注(分叉時(shí)候, 兩邊都投票, 反正哪個(gè)下注成功都會(huì)有分紅)
        • 兩邊下注解決方案

          • 引入驗(yàn)證者validator堰氓，交點(diǎn)保證金。每挖出100個(gè)區(qū)塊作為epoch, 進(jìn)行兩次投票(prepare message 和 commit message), 然后只有每一輪投票都要超過三分之二的驗(yàn)證者通過才能通過苹享。 現(xiàn)在改為每50個(gè)區(qū)塊作為epoch,然后進(jìn)行一次投票, 這次投票作為上一輪的commit message同時(shí)作為下一輪的prepare message; 驗(yàn)證者可以得到獎(jiǎng)勵(lì), 亂投票/不作為會(huì)沒收保證金. 驗(yàn)證者的任期滿了會(huì)換屆, 然后保證金會(huì)被冷卻一段時(shí)間, 過一段時(shí)間沒有問題后保證金才能被取出來用作下一次保證金.