源码剖析 EOS 共识算法 (DPOS+BFT) 代码逻辑

debugfuture · 2018年09月05日 · 830 次阅读

本文转自【引力区开发者社区】

EOS之所以有可能达成百万TPS并且不会分叉的性能目标,主要原因在于BM选择了基于授权证明+拜占庭容错的共识算法(DPOS+BFT),网络中关于这种算法的介绍文章不在少数,但是真正从源码角度剖析的文章可以说一篇也没有!本篇文章,我们将从源码的角度为您深度剖析EOS项目中DPOS-BFT算法背后的代码逻辑。

1、DPOS共识算法背景

首先我们先来简单理解一下为什么DPOS相比于POW算法,性能更优。我们通过类比人民代表大会制度与古希腊公民大会制度来说明这个问题:

古希腊公民大会制度

  • 概念:(ecclesia,亦可写作ekklesia) 是古希腊城邦和古罗马的最高权力机关。由王或议事会召集,全体成年男子(战时全体战士)参加,讨论、决定部落各项重大问题。通常用举手或喊声表决,并达成对国家重大事务的共识。
  • 优缺点:优点很明显,更加民主!但是缺点也很明显,共识效率是这种制度最大的钳制:对于小国寡民的情况,这种共识模型看起来很美好!很民主!但是,对于一个大国,这种制度就有了很大弊端,任何国家事务(事无巨细)都要组织少至千万,多至几亿的国民参与投票,效率何其低下

人民代表大会制度

  • 概念:这个概念大家都很了解,通过由民主选举产生、对人民负责并受人民监督的全国和地方各级人民代表大会,人民代表大会负责国家事务的最终决策。
  • 优缺点:这种制度极大的提升了共识的效率,通过民主投票的方式选举出一组人民代表参与最终的决策,使得最终决策的效率极大的提高(参与共识的人数变小,单单看统计票数的工作都能减小不少的工作量),不可避免的,这种模式中缺点也是存在的,一定程度上降低了民主程度

类比区块链世界的共识算法,优缺点何其相似:

  • POW<->古希腊公民大会制度:去中心化程度高,共识效率极低;
  • DPOS<->人民代表大会制度:共识效率显著提高,去中心化程度较低。

这一切的设计,都是从应用需求出发对区块链不可能三角做出的折衷方案:以民主程度换取共识效率!图1.1与1.2简单了展现了两者的关系。

图1.1 POW共识算法

图1.2 DPOS共识算法

2、EOS共识算法代码概述

相信很多阅读者已经对EOS所采用的DPOS+BFT共识算法有了初步的了解,这里我们先简单介绍一下,参考EOS项目白皮书:

  • EOS.IO软件采用目前为止唯一能够符合上述性能要求的去中心化共识算法,即授权委托证明(DPOS)。根据这种算法, EOS区块链上持有token的人可以通过投票系统持续选择区块生产者,任何人都可以成为块生产,只要他能说服token持有人以获得足够投票。
  • EOS.IO软件能够精确到每0.5秒生产一个区块,并且仅一个生产者被授权能在给定的时间点生产该区块。代码规定每轮生产126秒(共21个生产者,每个生产者6秒出12个区块)。在每轮开始时,根据token持有者的投票选出21个不同的块生产者。获选生产者按照代码规定的顺序轮流出块。

通过通读EOS代码,笔者将DPOS+BFT共识算法拆分成两个部分,方便大家理解:

  • 出块节点竞选:该功能主要依托于eosio.system系统合约进行:token持有者可以调用系统合约中的投票函数投票给自己信任的节点,投票结果将会保存在指定table中,智能合约每隔126个区块更新一次出块节点权限;
  • 生产区块:该功能主要依托于producer_plugin插件,注册成为候选出块节点在运行该插件时,时刻监听记录着节点获得投票情况的table,每过126个区块(1个epoch),判断一次自己获得的投票数量是否处在前21名,若处在,则在指定round生产区块,否则只同步不生产

本节最后,让我们看一下两个算法的具体类图,其中图2.1为出块节点竞选算法具体类图,图2.2为生产区块算法具体类图。我想这两张图对有编程基础的同学来说应该会有所助益,看不懂的同学不要着急,下面我们将详细讲解这两部分算法的具体代码

图2.1 出块节点竞选算法具体类图

图2.2 生产区块算法具体类图

1、算法总览

首先回顾一下前一篇我们给出的总类图,如图1.1所示,可以发现,EOS项目中整个出块节点竞选(DPOS)算法是依托系统合约实现的,简单来说,整个DPOS算法可以简化为两个进程来理解:主要分为投票与更新和监控票数后出块两部分。

图1.1 出块节点竞选类图

我们来看一下投票的总流程图,如图1.2所示,其中的关键文件有两个:

  • programs/cleos/main.cpp文件:该文件是cleos的源程序,主要负责投票信息的捕获
  • contracts/eosio.system/voting.cpp文件:由上述源程序中捕获的投票信息将送入eosio.system合约中,触发相应的函数,eosio.system合约中关于投票的函数实现位于voting.cpp中。

图1.2 出块节点竞选总流程图

接下来,我们详细看一下整个源码的实现过程。分为两部分介绍:

  • cleos中的源码;
  • voting中的源码。

2、cleos源码

programs/cleos/main.cpp定义了cleos的源程序,cleos是一个eos命令行工具,为用户提供一种通过命令行与区块链交互并且管理钱包的功能。其中涉及到与出块节点竞选相关的代码主要有四部分:

  • register_producer_subcommand结构:注册出块节点;
  • unregister_producer_subcommand结构:注销出块节点;
  • vote_producer_proxy_subcommand结构:通过代理节点投票;
  • vote_producers_subcommand结构:执行投票操作;
  • approve_producer_subcommand结构:增加待选出块节点;
  • unapprove_producer_subcommand结构:取消待选出块节点;
  • list_producers_subcommand结构:查询可选出块节点列表。

cleos中指令的执行是通过在main函数中声明相应的结构,每个结构中包含具体的构造函数,用以执行相应的功能逻辑,在这里,我们详细介绍投票功能的代码部分,其他部分感兴趣的朋友可以在开发群中讨论。

首先我们来看一下main函数中关于vote动作的定义,由于main函数很长,我们截选其中关于voting的部分,如图2.1所示:

图2.1 cleos功能初始化部分

简单来说,main函数主要通过add_subcommand()函数赋予的定义cleos工具主要选项的功能初始化voteproducer功能,然后通过图2.2中app.parse(argc, argv)函数捕获用户的输入,并调用相关的功能。

图2.2 cleos中捕获用户输入动作源码

当捕获到“system+voteproducer+详细参数”命令时,触发vote_producers_subcommand结构中的构造函数,如图2.3所示,构造函数首先初始化子命令,而后执行如下代码,将获取的参数发送给系统合约(eosio.system)中,并捕获智能合约执行结果返回给用户。图2.3 vote函数代码细节

send_actions({create_action({permission_level{voter_str,config::active_name}},config::system_account_name,N(voteproducer),act_payload)});

图2.3 vote函数代码细节

3、voting.cpp合约代码

之前我们讲过,具体投票的代码是由系统合约负责执行的,这部分代码实现位于contracts/eosio.system/voting.cpp中,首先我们罗列一下其中的关键函数并介绍一下含义与功能:

  • regproducer函数:注册出块节点账户;
  • unregprod函数;注销出块节点账户;
  • update_elected_producers:更新出块节点选举情况的全局状态;
  • stake2vote函数:为投票抵押代币;
  • voteproducer:投票函数
  • update_votes:更新投票结果;
  • regproxy:注册委托投票代理人;

和上文一样,我们只将最基础的投票函数做详细说明,包括voteproducer、stake2vote、update_votes和update_elected_producers四部分,其他功能感兴趣的朋友可以和我在开发者中讨论。

系统合约在接到cleos中捕获的投票命令之后,将会首先出发voteproducer函数,如图3.1所示,这一步很简单,首先判断投票人是否具有投票权限,若具备,则执行update_votes函数更新全局投票情况,反之则抛出异常。

图3.1 voteproducer代码

接着执行update_votes函数,我们做详细介绍:

  • 首先判断投票人类型,若为代理投票人,将会判断代理人是否具有对应的委托权限,不符则抛出异常,通过则向下继续执行;
  • 接着判断投票人是否具有投票权限,即是否进行用以投票的代币抵押,这里主要查询一个全局表_voters,该表中维护了所有用户的抵押信息。若没有抵押,则抛出异常。通过则向下继续执行;
  • 接着判断本次投票是否为首次投票,若是,则修改全局投票状态_gstate.total_activated_stake;
  • 接着进行投票操作,即读取用户提交的producer_deltas列表,并在出块节点的全局表中查找对应出块节点,并调整相应节点的投票情况;
  • 最后修改该用户的投票权重

图3.2 update_votes函数代码

至此,投票操作就已经完成,但是请注意,在代码中并没有涉及到节点更新刚刚修改后的全局变量值的操作!其实更新操作并非在cleos程序中进行,而是在nodeos程序中通过插件调取update_elected_producers函数来完成的:每过一个区块,或者是区块时间戳每更新一次,则执行一次该函数,完成全局变量的更新!具体代码如图3.3所示,系统将会在top_producers表中保留前21个节点信息,并使其成为出块节点,并调用std::sort()函数对这些节点排序,而后被选出来的出块节点之间进行共识的BFT算法就是参照这个排序顺序进行的

图3.3 update_elected_producers函数代码

接下来我们继续介绍DPOS+BFT的源码实现细节中生产区块过程所采用的BFT算法

1、算法总览

首先回顾一下前一篇我们给出的总类图,如图1.1所示,可以发现,EOS项目中整个超级节点之间生产区块所采用的共识算法为普通的拜占庭容错算法(BFT),该算法整体依托插件体系实现的,之所以采用这样的设计模式,主要有两层原因:

  • 防止部分恶意超级节点窜通作恶,包括修改账本信息等动作;
  • 防止区块链分叉。

图1.1 生产区块的BFT算法类图

我们来看一下区块生产的总流程图,如图1.2所示,其中的关键文件有4个:

  • programs/nodeos/main.cpp文件:该文件是nodeos的源程序,主要负责节点出块与接受区块等
  • plugins/producer_plugin/producer_plugin.cpp文件:这个插件主要负责了节点有关于生产区块、接受区块和同步区块的所有函数;
  • libraries/appbase/channel.cpp文件:该文件定义了EOS系统中的transaction、block等数据的交互通道
  • plugins/chain_plugin/chain_plugin.cpp文件:这个插件主要负责与EOS区块链数据之间的交互操作,如读取、写入、更新、删除等。

图1.2 出块节点竞选总流程图

接下来,我们详细看一下整个源码的实现过程。分为两部分介绍:

  • schedule_production_loop()函数源码;
  • start_block函数源码

2、schedule_production_loop()函数

我们知道,EOS的出块流程是周期性循环的,即每过126s,按照top_producers中节点重复一次出块流程,每个节点生产12个区块,通过上篇文章我们知道该DPOS算法是通过eosio.system系统合约实现的,并根据std::sort()函数按照选出的前21个超级节点的账户名首字母排序,而控制这21个出块节点的生产区块的具体函数就是plugins/produce_plugin/produce_plugin.cpp中的schedule_production_loop函数:nodeos程序根据全局时间(epoch)重复执行schedule_production_loop函数,以达到周期性出块的目的。

首先来看一下该函数,如图2.1所示:

总结下来,该函数的主要逻辑如下:

  • 通过chain_plugin插件调用controller函数,并重置时间
  • 调用start_block()函数,尝试打包新区块,返回start_block_result状态(该状态是enum枚举类,共有四种状态:succeeded、failed、waiting、exhausted)。
  • 根据返回的类型针对性的执行函数
    • failed:提示出块错误消息,挂起至同步状态
    • waiting:不做任何操作,保持同步状态;
    • succeeded:出块成功,若生产的区块不是exhausted状态(超过规定的出块时间),则调用maybe_produce_block函数尝试生产并发布区块;
    • 判断该节点是否有其他出块账户,若有,等待下次出块。
  • 监听出块节点动态,判断自己是否处在下一轮出块列表中。

通过这样的设置,nodeos节点就可以持续跟踪自己是否具有当前epoch的出块权限,若具有,则出块,反之则同步。其中有一个关键函数:start_block()函数下面持续展开。

3、start_block()函数

介绍一下该函数的逻辑:

  • 首先获取当前区块生产者;
  • 接着判断本地节点是否具有最新区块,同步是否完成;
  • 接着判断是否具有对应的私钥;
  • 正式出块,调用controller中的start_block函数,生产区块。
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册