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

ETH 賬戶

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

狀態(tài)樹

• 作用

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

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

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

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

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

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

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

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

      
      
      image.png

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

    
    
    image.png

  • Merkle Patricia Trie(MPT) :

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

    
    
    image.png

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

  
  
  image.png

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

  • header

    
    
    image.png

  • block

    
    
    image.png

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

    
    
    image.png

交易樹

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

收據(jù)樹

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

布隆過濾器

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

GHOST 協(xié)議

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

  • 第一版

    • 規(guī)則
      • 規(guī)定E區(qū)塊在發(fā)布時可以將A、C、D叔父區(qū)塊包含進來，A、C、D叔父區(qū)塊可以得到出塊獎勵的7/8，而為了激勵E包含叔父區(qū)塊，規(guī)定E每包含一個叔父區(qū)塊可以額外得到1/32的出塊獎勵。為了防止E大量包含叔父區(qū)塊，規(guī)定一個區(qū)塊只能最多包含兩個叔父區(qū)塊，因此E在A、C、D中最多只能包含兩個區(qū)塊作為自己的出塊獎勵
    • 缺陷
      • 因為叔父區(qū)塊最多只能包含兩個，如圖出現(xiàn)3個怎么辦？

      • 礦工自私，故意不包含叔父區(qū)塊，導(dǎo)致叔父區(qū)塊7/8出塊獎勵沒了，而自己僅僅損失1/32。如果甲、乙兩個大型礦池存在競爭關(guān)系，那么他們可以采用故意不包含對方的叔父區(qū)塊，因為這樣對自己損失小而對對方損失大。

        
        
        image.png

  • 第二版

  • 規(guī)則

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

  • 缺點

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

      
      
      image.png

  • 第三版

    • 規(guī)則

      • M為該區(qū)塊鏈上一個區(qū)塊，F(xiàn)為其嚴格意義上的叔父，E為其嚴格意義上的“爺爺輩”。以太坊中規(guī)定，如果M包含F(xiàn)輩區(qū)塊，則F獲得7/8出塊獎勵；如果M包含E輩區(qū)塊，則F獲得6/8出塊獎勵，以此類推向前。直到包含A輩區(qū)塊，A獲得2/8出塊獎勵，再往前的“叔父區(qū)塊”，對于M來說就不再認可其為M的"叔父"了。 對于M來說，無論包含哪個輩分的“叔父”，得到的出塊獎勵都是1/32出塊獎勵, 也就是說，叔父區(qū)塊的定義是和當(dāng)前區(qū)塊在七代之內(nèi)有共同祖先才可（合法的叔父只有6輩）。

        
        
        image.png

  • 如果規(guī)定將下面整條鏈作為一個整體，給予出塊獎勵，這一定程度上鼓勵了分叉攻擊(降低了分叉攻擊的成本，因為即使攻擊失敗也有獎勵獲得)。因此，ETH系統(tǒng)中規(guī)定，只認可A區(qū)塊為叔父區(qū)塊，給予其補償，而其后的區(qū)塊全部作廢。

    
    
    image.png

ETH 挖礦算法

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

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

      
      
      image.png

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

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

  • 流程

    • 以太坊設(shè)計了兩個數(shù)組, 分別是 16M的cache和1G的dataset(兩個數(shù)組的大小是初始大小, 每隔30000個區(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ù)組第一個元素, 之后每個元素都通過前一個位置的元素的hash得到. 這樣每個元素和前一個元素都是有依賴關(guān)系的.dataset中的每個元素都是隨機一個索引, 根據(jù)索引從數(shù)組中取出一個元素, 然后對這個元素進行運算求出下一個索引, 然后重復(fù)256次, 得出的結(jié)果放在dataset的數(shù)組中.

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

  • 偽代碼

    
    
    image.png

  • mkcache

  • 分析

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

挖礦難度調(diào)整

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

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

    
    
    image.png

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

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

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

    
    
    image.png

• 難度炸彈代碼

  
  
  tz8jrpi6wq.jpg

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

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

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