天天看點
傳回

重磅！美圖技術團隊釋出開源 ethereum dpos 實作

作者：美圖技術團隊

連結：https://zhuanlan.zhihu.com/p/38013479

來源：知乎

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

導語：目前以太坊采用 PoW 算法，并計劃逐漸替換成 PoS，是否有可能在以太坊上引入 DPoS 算法？美圖區塊鍊實驗室在區塊鍊方面做了很多的研究，共識算法是其中重點研究的一個方向，最近，美圖技術團隊在以太坊上成功實作 DPoS 算法，并通過本文對算法思路及源碼進行了詳細介紹。

本文介紹了近期美圖區塊鍊實驗室在學習和研究區塊鍊技術的過程中的一些成果。Ethereum是比較成熟和智能化的案例，對我們日後發展區塊鍊技術有相當的借鑒性，是以選擇其作為研究對象。

我們基于 Ethereum(1.7.3版本) 實作 DPoS 共識算法主要有兩個⽬的, ⼀個是我們之前主要是通過看代碼的⽅式來研究區塊鍊的⼀些技術，修改代碼可以進⼀步加深和鞏固代碼設計上的了解。另外⼀點是通過将修改的代碼開源，吸引更多的⼈來關注這個項⽬，那麼也算是對社群的⼀種回饋。

Github 位址: meitu/go-ethereum

共識算法

開始分析 DPoS 實作之前，先簡單介紹一下目前幾個主流的數字貨币共識算法。下面羅列的隻是一部分共識算法，還有其他許多算法沒有提及，羅列的順序以及時間序不代表算法的優劣。

1.PoW(Proof of Work)

  • 1993 年由 Cynthia Dwork 和 Moni Naor 提出，主要是用來解決垃圾郵件問題
  • 2009 年 Satoshi 使用 PoW 作為 bitcoin 的共識算法，PoW 成為區塊鍊第一個共識算法。随着 GPU 挖礦算法的出現, Satoshi 預期的每個 CPU 一票的機制被破壞
  • 2011年 萊特币(比特币的第一個山寨币)， 采用 scrypt(由一個黑客發明) ，特點是挖礦需要更多記憶體以及并行計算困難，相比 SHA256 更加能夠抵禦礦機， 但由于安全性上沒有經過嚴格的驗證是以并未大規模應用
  • 2013 年 primecoin 把算力用來尋找最大素數，解決算力浪費問題
  • 2015 年 etherum 使用 PoW 作為共識算法, 提出 dagger-hashimoto 的改良版本，具備記憶體難解性以及更好的抵抗 ASIC

算法可以簡單描述如下:

hash(B) ⩽ M/D (1), 其中 D ∈ [1, M], hash = sha256

// M 在不同算法裡面設定的可能會不一樣，我們這裡可以認為就是常量
// D 就是目标難度，D 值越大, M 為常量，那麼 M/D 就會越小，是以要使用 hash 找出小于這個值就會越難

PoW 不斷窮舉的方式找到滿足條件的整數需要消耗大量的計算資源， 而算力純粹是為了找到一個沒有任何意義的随機數，這成為大家诟病 PoW 的重要原因之一，現在有一些團隊正在嘗試把這些算力結合到現實中的一些場景，比如 AI 模型計算等。PoW 另外一個問題就是性能低下，目前比特币的性能差不多在 7 qps 左右，以太坊大概是比特币的兩倍。現在比較知名的 offchain的 代表 lightning 主要就是為了解決比特币的性能問題，還有就是 V 神正在做的 ethereum sharding 等。

2.PoS(Proof of Stake)

  • 2012 年 sunny king 提出 PoS 算法， 主要是為了解決 PoW 對于算力消耗過大的問題
  • 2013 年 peercoin 首個實作 PoS 的數字貨币但仍然保留 PoW。PoW 作為冷啟動階段使用，後續逐漸降低 PoW 權重。同時使用币齡(coin age) 來解決财富累積的問題，這個也引入新的問題(下面的提到的币齡累積問題)。
  • 2013 年 11 月 NXT 實作了首個純 PoS 的數字貨币
  • 2014 年 blackcoin 也使用 PoS 作為共識算法同時去掉了币齡

PoS 算法描述如下：

hash(hash(Bprev), A, t) ⩽ balance(A) * M/D 其中 hash = sha256

// M/D 和 PoW 的公式裡面的 M/D 是同一個意思
// Bpre 指的是上一塊的 hash 值
// 注意: 右邊變量乘上了使用者的餘額，意味着在 M/D 一樣的情況下，那麼餘額越大算出的機率就會越大

上面公式中唯一的變量隻有左邊的 t，同時變化範圍在固定空間内(比如不超過 1h，那麼 t 的取值區間隻有 7200 個，找不到就退出)，這樣就不再需要像 PoW 一樣用窮舉的方式來找随機數，也就不會存在消耗大量算力的問題。另外， 我們可以看到計算門檻值時加上了使用者餘額，意味着如果使用者擁有的資産越多，那麼就找到正确随機數的機率也會越大。

PoS 在解決算力的同時也引入了潛在的攻擊問題：

  • Nothing at stake， 由于 PoS 不需要消耗太多算力，是以當出現分叉時，礦工為了利益最大化會選擇同時在兩個分叉進行挖礦，進而導緻更多的分叉。而 PoW 是算力敏感的，礦工隻能選擇押注其中一條路徑。
  • 長距離攻擊，在 PoW 中惡意節點即使擁有 51% 以上的算力，如果想篡改賬本也是需要花費大量的成本。而 PoS 對于算力的要求很低，那麼就存在被篡改的風險
  • 币齡累積攻擊，有些算法實作中除了考慮擁有的資産之外還加上了币齡，那麼就有可能導緻部分節點不需要持有 51% 的資産就可以産生攻擊

3.DPoS(Delegated Proof of Stake)

  • 2014 年 4 月Bitshares 的首席開發者 Dan Larimer 提出 DPoS 算法并應用到 Bitshares， 截止到目前(2018年 5 月) 已經運作了 4 年左右
  • 2016 年7 月 Steemit 公司釋出 Steemit 項目以及今年的 EOS 測試網絡也都是使用 DPoS 作為共識算法

DPoS 被認為是 PoS 的改進版本，DPoS 通過每隔一段時間進行一次選舉，然後由這些選舉出來的節點來負責出塊和互相監督驗證，這樣就可以大大降低出塊以及塊确認的時間。這樣的選舉方式帶來的問題是出塊節點會比 PoW 以及 PoS 更加中心化。

DPoS 算法概要

目前以太坊的共識算法是 PoW，後續會逐漸過渡為 PoW + PoS。目前為了解決算力消耗過大和性能問題，我們做的一個嘗試是将共識算法從 PoW 修改為 DPoS。

DPoS 共識算法最大的特點是出塊人是由選舉産生而不是通過算随機數。算法設計上和中心化的投票選舉機制和 Bitshares 提出的 DPoS 算法 沒有太本質的差別，唯一的差別就是把投票的過程變成一筆交易。在下文中我将為大家詳解的介紹我們整體的流程以及具體的實作。

整體流程如下:

重磅！美圖技術團隊釋出開源 ethereum dpos 實作

算法實作主要包含兩個核心部分:

  1. 塊驗證人選舉
  2. 塊驗證人排程

第一批塊驗證人由創世塊指定，後續每個周期(周期由具體實作定義)都會在周期開始的第一個塊重新選舉。驗證人選舉過程如下:

  1. 踢掉上個周期出塊不足的驗證人
  2. 統計截止選舉塊(每個周期的第一塊)産生時候選人的票數，選出票數最高的前 N 個作為驗證人
  3. 随機打亂驗證人出塊順序，驗證人根據随機後的結果順序出塊

驗證人排程根據選舉結果進行出塊，其他節點根據選舉結果驗證出塊順序和選舉結果是否一緻，如果不一緻則認為此塊不合法，直接丢棄。

DPoS 實作

以太坊目前代碼裡面已經包含了幾種共識算法的實作:

  • PoW

     在主網使用

  • FakePow

     在單元測試使用

  • PoA(Proof of Authority)

     在測試網絡中使用

為了在代碼中實作多種共識算法，以太坊抽象了一套共識算法接口，實作不同的共識算法隻要實作幾個接口即可。另外由于 DPoS 為了避免每次選舉都從創世塊開始回放曆史資料，增加了幾個全局狀态樹用來記錄選舉和投票的狀态， 并把樹對應的 root 存儲到塊頭，其中包括：

  • EpochTrie 記錄每個周期的驗證人清單
  • VoteTrie 記錄投票人對應驗證人
  • CandidateTrie 記錄候選人清單
  • DelegateTrie 記錄驗證人以及對應投票人的清單
  • MintCntTrie 記錄驗證人在周期内的出塊數目

1.接口

type Engine interface {
    Author(header *types.Header) (common.Address, error)
  	// 驗證塊頭是否符合共識算法規則
    VerifyHeader(chain ChainReader, header *types.Header, seal bool) error
    // 批量驗證塊頭是否符合共識算法規則
    VerifyHeaders(chain ChainReader, headers []*types.Header, seals []bool) (chan<- struct{}, <-chan error)
    // 驗證叔塊是否符合共識算法規則, DPoS 沒有叔塊
    VerifyUncles(chain ChainReader, block *types.Block) error
	// 驗證塊内容是否符合共識算法規則
    VerifySeal(chain ChainReader, header *types.Header) error

    // 根據共識算法規則初始化塊頭資訊
    Prepare(chain ChainReader, header *types.Header) error
    // 塊内交易執行完成之後進行的相關更新操作(比如挖塊激勵等等)
    Finalize(chain ChainReader, header *types.Header, state *state.StateDB, txs []*types.Transaction, uncles []*types.Header, receipts []*types.Receipt, dposContext *types.DposContext) (*types.Block, error)

    // 根據 Prepare 和 Finalize 生成的塊内容以及共識算法産生一個新塊
    Seal(chain ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error)

    // 該共識算法對外提供的 API 接口
    APIs(chain ChainReader) []rpc.API
}

2.核心實作

我們先看看打包塊的流程:

重磅！美圖技術團隊釋出開源 ethereum dpos 實作

礦工會定時通過

CheckValidator

去檢查目前的 validator 是否為目前節點，如果是的話則通過

CreateNewWork

來建立一個新的打塊任務，

CreateNewWork

主要包含三部分的内容：

  • Prepare()

     ，上面看到的共識算法需要實作的接口，主要是初始化塊頭基礎資訊

  • CommitTransactions()

     ， 主要是從 transaction pool 按照 gas price 将交易打包到塊中

  • Finalize()

     ，将 prepare 和 CommitNewWork 内容打包成新塊，同時裡面還有包含出塊獎勵、選舉、更新打塊計數等功能

最後 Seal 會對新塊進行簽名，之後再将新塊廣播到鄰近的節點，其他節點接收到新塊會根據塊的簽名以及選舉結果來看新塊是否應該由該驗證人來出塊。相對其他的共識算法來說，DPoS 的共識算法主要差別在于選舉，是以可以重點來看這塊實作:

func (ec *EpochContext) tryElect(genesis, parent *types.Header) error {
    genesisEpoch := genesis.Time.Int64() / epochInterval
    prevEpoch := parent.Time.Int64() / epochInterval
    currentEpoch := ec.TimeStamp / epochInterval 
    ....
    // 根據目前塊和上一塊的時間計算目前塊和上一塊是否屬于同一個周期，
    // 如果是同一個周期，意味着目前塊不是周期的第一塊，不需要觸發選舉
    // 如果不是同一周期，說明目前塊是該周期的第一塊，則觸發選舉
    for i := prevEpoch; i < currentEpoch; i++ {
        // 如果前一個周期不是創世周期，觸發踢出候選人規則
        // 踢出規則主要是看上一周期是否存在候選人出塊少于特定門檻值(50%), 如果存在則踢出
        if !prevEpochIsGenesis && iter.Next() {
            if err := ec.kickoutCandidate(prevEpoch, prevEpochIsGenesis); err != nil {
                return err
            }
        }
        // 對候選人進行計票後按照票數由高到低來排序, 選出前 N 個
        // 這裡需要注意的是目前對于成為候選人沒有門檻限制很容易被惡意攻擊
        votes, err := ec.countVotes()
        if err != nil {
            return err
        }
        sort.Sort(candidates)
        if len(candidates) > epochSize {
            candidates = candidates[:epochSize]
        }
        
        // 打亂驗證人清單，由于使用 seed 是由父塊的 hash 以及目前周期編号組成，
        // 是以每個節點計算出來的驗證人清單也會一緻
        seed := int64(binary.LittleEndian.Uint32(crypto.Keccak512(parent.Hash().Bytes()))) + i
        r := rand.New(rand.NewSource(seed))
        for i := len(candidates) - 1; i > 0; i-- {
            j := int(r.Int31n(int32(i + 1)))
            candidates[i], candidates[j] = candidates[j], candidates[i]
        }
        sortedValidators := make([]common.Address, 0)
        for _, candidate := range candidates {
            sortedValidators = append(sortedValidators, candidate.address)
        }
    }
    return nil
}

我們在打包每個塊之前都會調用

tryElect

來看看目前塊是否是新周期的第一塊，如果是第一塊則需要觸發選舉。 整體的選舉的實作比較簡單，主要是做了三個事情:

  1. 根據上個周期出塊的情況把一些被選上但出塊數達不到要求的候選人踢掉
  2. 截止到上一塊為止，選出票數最高的前 N 個候選人作為驗證人
  3. 打亂驗證人順序

接下來看看計票實作(忽略一些不重要的代碼):

func (ec *EpochContext) countVotes() (votes map[common.Address]*big.Int, err error) {
    ...
    // 周遊候選人清單
    for existCandidate {
        candidate := iterCandidate.Value
        candidateAddr := common.BytesToAddress(candidate)
        delegateIterator := trie.NewIterator(delegateTrie.PrefixIterator(candidate))
        existDelegator := delegateIterator.Next()
		...
        // 周遊候選人對應的投票人清單
        for existDelegator {
            delegator := delegateIterator.Value
            score, ok := votes[candidateAddr]
            if !ok {
                score = new(big.Int)
            }
            delegatorAddr := common.BytesToAddress(delegator)
            // 擷取投票人的餘額作為票數累積到候選人的票數中
            weight := statedb.GetBalance(delegatorAddr)
            score.Add(score, weight)
            votes[candidateAddr] = score
            existDelegator = delegateIterator.Next()
        }
        existCandidate = iterCandidate.Next()
    }
    return votes, nil
}

計票的邏輯也很簡單:

  1. 先找出候選人對應投票人的清單
  2. 所有投票人的餘額作為票數累積到候選人的總票數中

之前我們看到除了上面看到幾個接口之外，共識算法接口還要求實作比如像

VerifyHeader()

，

VerifySeal()

，

VerifyUncles()

等幾個驗證接口，主要是當其他人接收到新塊時會使用這幾個方法分别來驗證塊頭，内容以及叔塊的資訊是否符合驗證規則。由于篇幅的關系這裡不進行詳細介紹。

3.成為候選人/投票

某個節點想要成為驗證人，首先要成為候選人，接着其他人才能對這個候選人進行投票。不管是投票還是成為候選人，對于節點來說其實都是一筆交易，之前的交易主要是轉賬或者合約調用，是以現在多增加幾種交易類型。

const (
    Binary TxType = iota // 之前的轉賬或者合約調用交易
    LoginCandidate       // 成為候選人
    LogoutCandidate		 // 退出候選人
    Delegate			 // 投票(授權)
    UnDelegate			  // 取消投票(授權)
)

type txdata struct {
    Type         TxType          `json:"type"   gencodec:"required"` 
    AccountNonce uint64          `json:"nonce"    gencodec:"required"`
    Price        *big.Int        `json:"gasPrice" gencodec:"required"`
    GasLimit     *big.Int        `json:"gas"      gencodec:"required"`
    Recipient    *common.Address `json:"to"       rlp:"nil"` // nil means contract creation
    Amount       *big.Int        `json:"value"    gencodec:"required"`
    Payload      []byte          `json:"input"    gencodec:"required"`

    // Signature values
    V *big.Int `json:"v" gencodec:"required"`
    R *big.Int `json:"r" gencodec:"required"`
    S *big.Int `json:"s" gencodec:"required"`

    // This is only used when marshaling to JSON.
    Hash *common.Hash `json:"hash" rlp:"-"`
}

在一個新塊打包時會執行所有塊内的交易，如果發現交易類型不是之前的轉賬或者合約調用類型，那麼會調用 `applyDposMessage` 進行處理。

func applyDposMessage(dposContext *types.DposContext, msg types.Message) error {
    switch msg.Type() {
    case types.LoginCandidate:
        dposContext.BecomeCandidate(msg.From().Bytes())
    case types.LogoutCandidate:
        dposContext.KickoutCandidate(msg.From().Bytes())
    case types.Delegate:
        dposContext.Delegate(msg.From().Bytes(), msg.To().Bytes())
    case types.UnDelegate:
        dposContext.UnDelegate(msg.From().Bytes(), msg.To().Bytes())
    default:
        return types.ErrInvalidType
    }
    return nil
}

func (d *DposContext) BecomeCandidate(candidate []byte) error {
    // 更新候選人樹即可
    return d.candidateTrie.TryUpdate(candidate, candidate)
}

func (d *DposContext) Delegate(delegator, candidate []byte) error {
    if !common.IsHexAddress(common.BytesToAddress(candidate).String()) {
        return ErrInvalidAddress
    }
    // 投票(授權)之前需要先檢查該賬号是否候選人
    if _, err := d.candidateTrie.TryGet(candidate); err != nil {
        return err
    }
    // 如果投票人之前已經給其他人投過票則先取消之前的投票
    oldCandidate, err := d.voteTrie.TryGet(delegator)
    if err != nil {
        if _, ok := err.(*trie.MissingNodeError); !ok {
            return err
        }
    }
    if oldCandidate != nil {
        d.delegateTrie.Delete(append(oldCandidate, delegator...))
    }
    // 更新候選人對應的授權清單
    if err = d.delegateTrie.TryUpdate(append(candidate, delegator...), delegator); err != nil {
        return err
    }
    return d.voteTrie.TryUpdate(delegator, candidate)
}

可以看到投票/成為候選人跟我們傳統的實作差别不大，本質還是對于資料的增删查改，隻是在資料的更新上區塊鍊會比普通的 KV 更加複雜和特殊一些。

測試 

$ cd go-ethereum && make geth
$ ./build/bin/geth init --datadir /path/to/datadir dpos_test_genesis.json
$ ./build/bin/geth --datadir /path/to/datadir --keystore /path/to/keystore console
$ personal.unlock($validator, $passwd, 0)
$ miner.setValidator($validator)
$ miner.start()
第一批創世驗證人在 dpos_test_genesis.json 修改，為了友善測試可以将驗證人數目(maxValidatorSize)調小

開發遇到的問題

  • fast sync 模式下不接收廣播的塊導緻節點之間一直無法互相同步新塊

以太坊同步有三種同步機制：

  1. full sync

     同步全量區塊并回放所有交易資料來構造全局狀态樹

  2. fast sync

     （預設） 同步全量區塊資料以及第 N 塊的全局狀态樹，同時隻回放從第 N 塊之後的交易資料。這個機制很像 Redis 的 RDB + AOF 機制，這種方式避免回放所帶來的性能問題(回放交易主要的性能瓶頸是在于随機 IO 讀寫)。

  3. light sync

     隻同步區塊頭部資訊不同步具體交易内容，主要是用于錢包實作 SPV 功能

fast sync 模式下會直接丢棄廣播的塊，隻有在進入 full sync 之後才會接收。如果我們同時以預設同步方式(fast sync)啟動多個節點，由于節點之間出塊的頻率一樣導緻所有節點都無法進入 full sync 模式，節點之間同步的塊都會被丢棄。解決方案是創始節點以 full sync 方式啟動，我們開源的代碼為了友善測試，預設也會使用 full sync。

  • 加入 DPoS 之後，區塊的存儲結構發生一些變化，之前一些驗證流程邏輯需要調整。比如驗證人是否合法理論上需要在

    VerifyHeader

     來做校驗 ，因為塊頭隻是存儲需要對應樹的 root, 而沒有具體的内容，需要等到新塊寫入 DB 之後再來校驗(注意這裡的寫入本地指的是塊資料寫入 KV，而塊本身并未插傳入連結)。
  • 由于以太坊一些實作機制上也相對複雜一些，開始對于設計細節了解不是特别深入，在調試過程中也會花費比較多的時間。另外就是單元測試龐大，在對代碼修改過程中需要不斷地了解和修正單元測試。

參考：

DPOS Consensus Algorithm - The Missing White Paper

eth/63 fast synchronization algorithm

pos vs pow

delegated proof of stake consensus

https://github.com/ethereum/go-ethereum

https://github.com/meitu/go-ethereum

https://zhuanlan.zhihu.com/p/38013479

區塊鍊 / 共識算法 Consensus Ethereum DPoS 美圖 開源 共識
上一篇: PBFT（拜占庭容錯)
下一篇: 交易校驗與交易腳本校驗與腳本交易腳本簽名哈希類型

繼續閱讀