重磅！美图技术团队发布开源 Ethereum DPoS 实现

导读：目前以太坊采用 PoW 算法，并计划逐步替换成 PoS，是否有可能在以太坊上引入 DPoS 算法？美图区块链实验室在区块链方面做了很多的研究，共识算法是其中重点研究的一个方向，最近，美图技术团队在以太坊上成功实现 DPoS 算法，并通过本文对算法思路及源码进行了详细介绍。查看文末留言有惊喜。

本文介绍了近期美图区块链实验室在学习和研究过程中的一些成果。Ethereum是比较成熟和智能化的案例，对美图日后发展区块链技术有相当的借鉴性，因此选择其作为研究对象。

我们基于 Ethereum(1.7.3版本) 实现 DPoS 共识算法主要有两个⽬的, ⼀个是我们之前主要是通过看代码的⽅式来研究区块链的⼀些技术，修改代码可以进⼀步加深和巩固代码设计上的理解。另外⼀点是通过将修改的代码开源，吸引更多的⼈来关注这个项⽬，那么也算是对社区的⼀种回馈。

Github 地址: https://github.com/meitu/go-ethereum

共识算法

开始分析 DPoS 实现之前，先简单介绍一下当前几个主流的数字货币共识算法。下面罗列的只是一部分共识算法，还有其他许多算法没有提及，罗列的顺序以及时间序不代表算法的优劣。

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

算法可以简单描述如下:

PoW 不断穷举的方式找到满足条件的整数需要消耗大量的计算资源， 而算力纯粹是为了找到一个没有任何意义的随机数，这成为大家诟病 PoW 的重要原因之一，现在有一些团队正在尝试把这些算力结合到现实中的一些场景，比如 AI 模型计算等。PoW 另外一个问题就是性能低下，当前比特币的性能差不多在 7 qps 左右，以太坊大概是比特币的两倍。现在比较知名的 offchain的 代表 lightning 主要就是为了解决比特币的性能问题，还有就是 V 神正在做的 ethereum sharding 等

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 算法描述如下：

上面公式中唯一的变量只有左边的 t，同时变化范围在固定空间内(比如不超过 1h，那么 t 的取值区间只有 7200 个，找不到就退出)，这样就不再需要像 PoW 一样用穷举的方式来找随机数，也就不会存在消耗大量算力的问题。另外， 我们可以看到计算阈值时加上了用户余额，意味着如果用户拥有的资产越多，那么就找到正确随机数的概率也会越大。

PoS 在解决算力的同时也引入了潜在的攻击问题：

• Nothing at stake， 由于 PoS 不需要消耗太多算力，所以当出现分叉时，矿工为了利益最大化会选择同时在两个分叉进行挖矿，从而导致更多的分叉。而 PoW 是算力敏感的，矿工只能选择押注其中一条路径。

• 长距离攻击，在 PoW 中恶意节点即使拥有 51% 以上的算力，如果想篡改账本也是需要花费大量的成本。而 PoS 对于算力的要求很低，那么就存在被篡改的风险

• 币龄累积攻击，有些算法实现中除了考虑拥有的资产之外还加上了币龄，那么就有可能导致部分节点不需要持有 51% 的资产就可以产生攻击

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 算法 没有太本质的区别，唯一的区别就是把投票的过程变成一笔交易。家详解的介绍我们整体的流程以及具体的实现。

整体流程如下:

算法主要包含两个核心部分:

1. 块验证人选举

2. 块验证人调度

第一批块验证人由创世块指定，后续每个周期(周期由具体实现定义)都会在周期开始的第一个块重新选举。验证人选举过程如下:

1. 踢掉上个周期出块不足的验证人

2. 统计截止选举块(每个周期的第一块)产生时候选人的票数，选出票数最高的前 N 个作为验证人

3. 随机打乱验证人出块顺序，验证人根据随机后的结果顺序出块

验证人调度根据选举结果进行出块，其他节点根据选举结果验证出块顺序和选举结果是否一致，如果不一致则认为此块不合法，直接丢弃。

DPoS 实现

以太坊当前代码里面已经包含了几种共识算法的实现:

• PoW 在主网使用

• FakePow 在单元测试使用

• PoA(Proof of Authority) 在测试网络中使用

为了在代码中实现多种共识算法，以太坊抽象了一套共识算法接口，实现不同的共识算法只要实现几个接口即可。另外由于 DPoS 为了避免每次选举都从创世块开始回放历史数据，增加了几个全局状态树用来记录选举和投票的状态， 并把树对应的 root 存储到块头，其中包括：

• EpochTrie 记录每个周期的验证人列表

• VoteTrie 记录投票人对应验证人

• CandidateTrie 记录候选人列表

• DelegateTrie 记录验证人以及对应投票人的列表

• MintCntTrie 记录验证人在周期内的出块数目

接口

核心实现

我们先看看打包块的流程:

矿工会定时通过  CheckValidator 去检查当前的 validator 是否为当前节点，如果是的话则通过 CreateNewWork 来创建一个新的打块任务，CreateNewWork 主要包含三部分的内容：

• Prepare()，上面看到的共识算法需要实现的接口，主要是初始化块头基础信息

• CommitTransactions()， 主要是从 transaction pool 按照 gas price 将交易打包到块中

• Finalize()，将 prepare 和 CommitNewWork 内容打包成新块，同时里面还有包含出块奖励、选举、更新打块计数等功能 

最后 Seal 会对新块进行签名，之后再将新块广播到邻近的节点，其他节点接收到新块会根据块的签名以及选举结果来看新块是否应该由该验证人来出块。相对其他的共识算法来说，DPoS 的共识算法主要区别在于选举，所以可以重点来看这块实现:

我们在打包每个块之前都会调用 tryElect 来看看当前块是否是新周期的第一块，如果是第一块则需要触发选举。 整体的选举的实现比较简单，主要是做了三个事情:

1. 根据上个周期出块的情况把一些被选上但出块数达不到要求的候选人踢掉

2. 截止到上一块为止，选出票数最高的前 N 个候选人作为验证人

3. 打乱验证人顺序

接下来看看计票实现(忽略一些不重要的代码):

计票的逻辑也很简单:

1. 先找出候选人对应投票人的列表

2. 所有投票人的余额作为票数累积到候选人的总票数中

之前我们看到除了上面看到几个接口之外，共识算法接口还要求实现比如像 VerifyHeader()，VerifySeal()，VerifyUncles() 等几个验证接口，主要是当其他人接收到新块时会使用这几个方法分别来验证块头，内容以及叔块的信息是否符合验证规则。由于篇幅的关系这里不进行详细介绍。

成为候选人/投票

某个节点想要成为验证人，首先要成为候选人，接着其他人才能对这个候选人进行投票。不管是投票还是成为候选人，对于节点来说其实都是一笔交易，之前的交易主要是转账或者合约调用，因此现在多增加几种交易类型。

在一个新块打包时会执行所有块内的交易，如果发现交易类型不是之前的转账或者合约调用类型，那么会调用 applyDposMessage 进行处理。

可以看到投票/成为候选人跟我们传统的实现差别不大，本质还是对于数据的增删查改，只是在数据的更新上区块链会比普通的 KV 更加复杂和特殊一些。

测试

第一批创世验证人在 dpostestgenesis.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，而块本身并未插入链)。

• 由于以太坊一些实现机制上也相对复杂一些，开始对于设计细节了解不是特别深入，在调试过程中也会花费比较多的时间。另外就是单元测试庞大，在对代码修改过程中需要不断地理解和修正单元测试。

参考

[1] https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper

[2] https://github.com/ethereum/go-ethereum/pull/1889

[3] https://bitfury.com/content/downloads/pos-vs-pow-1.0.2.pdf

[4] https://bitshares.org/technology/delegated-proof-of-stake-consensus/

[5] https://github.com/ethereum/go-ethereum

[6] https://github.com/meitu/go-ethereum

留言点赞前五可获得《高可用架构第一卷》图书一本（价值108元）以及一个美图限量版抱枕

相关阅读：

只用200行Go代码写一个自己的区块链！

200行Go代码实现自己的区块链——区块生成与网络通信

200行Go代码实现区块链 —— 挖矿算法

区块链及比特币入门指南

新一代开源分布式账本项目R3 Corda 技术揭秘：基于JVM开发

超越比特币以太坊的区块链技术：石墨烯项目简介

特别推荐：

比特币、以太坊、ERC20、PoW、PoS、智能合约、闪电网络……

想深入了解及讨论这些话题？高可用架构在知识星球（小密圈）创建了区块链学习小组，共同学习区块链包括数字货币前沿技术，欢迎点击链接加入。

区块链学习小组

转载本文请注明出处，技术原创及架构实践文章，欢迎通过公众号菜单「联系我们」进行投稿。

高可用架构

改变互联网的构建方式

长按二维码 关注「高可用架构」公众号