EOS共识机制——BFT-DPoS

June 19, 2019

DPoS实现 #

DPoS（Delegated proof of stake），在EOS区块链中可以理解为：EOS代币持有者必须先抵押获得投票权，通过投票的方式选举，选出得票最高的21个BP（出块节点），21个BP轮流出块。

整个算法的实现是通过系统智能合约的方式，在文件eosio.system/voting.cpp中，看名称就知道这是一个投票相关的文件，使用Cleos工具输入cleos system可以列出系统合约相关操作：

shell

Subcommands:

  newaccount                  Create a new account on the blockchain with initial resources
  regproducer                 Register a new producer
  unregprod                   Unregister an existing producer
  voteproducer                Vote for a producer
  listproducers               List producers
  delegatebw                  Delegate bandwidth
  undelegatebw                Undelegate bandwidth
  listbw                      List delegated bandwidth
  bidname                     Name bidding
  bidnameinfo                 Get bidname info
  buyram                      Buy RAM
  sellram                     Sell RAM
  claimrewards                Claim producer rewards
  regproxy                    Register an account as a proxy (for voting)
  unregproxy                  Unregister an account as a proxy (for voting)
  canceldelay                 Cancel a delayed transaction
  rex                         Actions related to REX (the resource exchange)

我们主要关注 voteproducer，为节点投票的代码。在voting.cpp文件中可以找到对应的合约代码：

在CDT还没发布的时候，合约是和源代码放一起的，放在目录contracts中，新版本后系统合约单独有仓库https://github.com/EOSIO/eosio.contracts

c++

void system_contract::voteproducer( const account_name voter_name, const account_name proxy, const std::vector<account_name>& producers ) {
      require_auth( voter_name );
      update_votes( voter_name, proxy, producers, true );
   }

入参说明：

voter_name：投票者账号
proxy：代理账号
producers：想要投的节点，最多30个

然后是调用 update_votes，主要实现都在这里面，代码的实现还是比较简单的，加了注释：

c++

void system_contract::update_votes(const account_name voter_name, const account_name proxy,
                                       const std::vector<account_name> &producers, bool voting) {
        // validate input
        // 可以进行代理和直接投票两种操作，具体哪种操作是通过proxy和producers判断
        if (proxy) {
            eosio_assert(producers.size() == 0, "cannot vote for producers and proxy at same time");
            eosio_assert(voter_name != proxy, "cannot proxy to self");
            require_recipient(proxy);
        } else {
            eosio_assert(producers.size() <= 30, "attempt to vote for too many producers");
            for (size_t i = 1; i < producers.size(); ++i) {
                // 节点名称必须是有序排列好的
                eosio_assert(producers[i - 1] < producers[i], "producer votes must be unique and sorted");
            }
        }
        // 投票前必须将EOS抵押
        // 在通过`delegatebw`进行资源抵押后
        // 会在_voters保存记录
        auto voter = _voters.find(voter_name);
        eosio_assert(voter != _voters.end(), "user must stake before they can vote"); /// staking creates voter object
        eosio_assert(!proxy || !voter->is_proxy, "account registered as a proxy is not allowed to use a proxy");
        /**
         * The first time someone votes we calculate and set last_vote_weight, since they cannot unstake until
         * after total_activated_stake hits threshold, we can use last_vote_weight to determine that this is
         * their first vote and should consider their stake activated.
         */
        if (voter->last_vote_weight <= 0.0) {
            _gstate.total_activated_stake += voter->staked;
            if (_gstate.total_activated_stake >= min_activated_stake && _gstate.thresh_activated_stake_time == 0) {
                _gstate.thresh_activated_stake_time = current_time();
            }
        }
        // 计算投票权重
        // 通过抵押的EOS计算
        auto new_vote_weight = stake2vote(voter->staked);
        if (voter->is_proxy) {
            new_vote_weight += voter->proxied_vote_weight;
        }
        boost::container::flat_map<account_name, pair<double, bool /*new*/> > producer_deltas;
        if (voter->last_vote_weight > 0) {
            if (voter->proxy) {
                auto old_proxy = _voters.find(voter->proxy);
                eosio_assert(old_proxy != _voters.end(), "old proxy not found"); //data corruption
                _voters.modify(old_proxy, 0, [&](auto &vp) {
                    vp.proxied_vote_weight -= voter->last_vote_weight;
                });
                propagate_weight_change(*old_proxy);
            } else {
                // 如果之前有投票给其他节点
                // 这些节点的票数需要减少
                for (const auto &p : voter->producers) {
                    auto &d = producer_deltas[p];
                    d.first -= voter->last_vote_weight;
                    d.second = false;
                }
            }
        }
        if (proxy) {
            auto new_proxy = _voters.find(proxy);
            eosio_assert(new_proxy != _voters.end(),
                         "invalid proxy specified"); //if ( !voting ) { data corruption } else { wrong vote }
            eosio_assert(!voting || new_proxy->is_proxy, "proxy not found");
            if (new_vote_weight >= 0) {
                _voters.modify(new_proxy, 0, [&](auto &vp) {
                    vp.proxied_vote_weight += new_vote_weight;
                });
                propagate_weight_change(*new_proxy);
            }
        } else {
            if (new_vote_weight >= 0) {
                for (const auto &p : producers) {
                    auto &d = producer_deltas[p];
                    d.first += new_vote_weight;
                    d.second = true;
                }
            }
        }
        // 投票的节点票数增加
        for (const auto &pd : producer_deltas) {
            auto pitr = _producers.find(pd.first);
            if (pitr != _producers.end()) {
                eosio_assert(!voting || pitr->active() || !pd.second.second /* not from new set */,
                             "producer is not currently registered");
                _producers.modify(pitr, 0, [&](auto &p) {
                    p.total_votes += pd.second.first;
                    if (p.total_votes < 0) { // floating point arithmetics can give small negative numbers
                        p.total_votes = 0;
                    }
                    _gstate.total_producer_vote_weight += pd.second.first;
                    //eosio_assert( p.total_votes >= 0, "something bad happened" );
                });
            } else {
                eosio_assert(!pd.second.second /* not from new set */, "producer is not registered"); //data corruption
            }
        }
        // 保存更改
        _voters.modify(voter, 0, [&](auto &av) {
            av.last_vote_weight = new_vote_weight;
            av.producers = producers;
            av.proxy = proxy;
        });
    }

流程大概就是：

确保投票人已抵押
计算投票权重
减少之前投票过的节点票数
增加新节点票数

重点说下第二部分计算投票权重的算法stake2vote(voter->staked):

c++

double stake2vote(int64_t staked) {
        /// TODO subtract 2080 brings the large numbers closer to this decade
        double weight =
                int64_t((now() - (block_timestamp::block_timestamp_epoch / 1000)) / (seconds_per_day * 7)) / double(52);
        return double(staked) * std::pow(2, weight);
    }

入参staked是当前已抵押的数量，是CPU和NET抵押数量的总和。

可以看出权重值还跟时间有关系，block_timestamp_epoch值为946684800000(ms)，即2000年的时间戳，公式只有两个变量now()和staked，假如staked不变，now()越大权重值越大。也就是同样是抵押1000，现在去投票得到的权重会比你上周投票的权重值要大，但注意跨度必须是一周。这样设计能很好的提高投票的频率，保证选举的活性，尽量选出最好的BP。

一旦投票的过程实现了，只要根据票数做降序排列，前面21个就是出块节点了，总体来说DPoS的实现还是比较简单。

BFT算法代码分析 #

BFT（Byzantine Fault Tolerance），这里面主要作用是为了使21个BP达成一致的共识。

这里先通过简单的出块流程说明几组数字：21 个BP会按约定好的顺序，0.5 秒出一个块，每个BP一次连续出 6 个块也就是持续 3 秒，这里面BFT规定好必须要超过 2/3（15个） 的BP确认的区块，才能成为不可逆区块。

主要的核心代码在两个文件plugins/producer_plugin/producer_plugin.cpp和libraries/chain/controller.cpp，下面画了一张调用的流程图。

下面会根据上图每个点详细的走一遍，有些地方会贴上代码说明。首先我们找到节点程序启动的位置nodeos/main.cpp

c++

int main(int argc,char** argv)
{
...
 if(!app().initialize<chain_plugin, http_plugin, net_plugin, producer_plugin>(argc, argv))
         return INITIALIZE_FAIL;
...

这里就是开始的地方，来到producer_plugin，先是进行初始化，然后调用plugin_startup启动插件（顺便说一下EOS的一般功能都是做成插件的方式集成，你也可以开发一些插件在自己的节点上使用，例如已经有人开发了日志通过kafka的方式广播给业务系统）。

BP出块流程 #

上图的入口schedule_production_loop()函数会在这里启动，这是一个将会重复执行出块的函数，紧跟着进入start_block()函数，该函数主要尝试生产区块，然后将结果返回，因为该函数代码量有点大就不贴了。

这里先提出一个问题，前面说了节点是轮流出块，那么如何知道当前轮到谁出块呢？

答案是通过上一个区块的区块时间计算，得出一个区块时间，再通过区块时间计算出当前的出块节点。在正常的情况下，因为上一个区块的数据在所有的节点里都是一样的，所以大家计算得到的当前出块节点也是一样的，这样无需通讯就能达成共识。回到start_block()函数里，找到calculate_pending_block_time()函数计算区块时间：

c++

fc::time_point producer_plugin_impl::calculate_pending_block_time() const {
   const chain::controller& chain = chain_plug->chain();
   const fc::time_point now = fc::time_point::now();
   // chain.head_block_time()是最新区块的时间
   const fc::time_point base = std::max<fc::time_point>(now, chain.head_block_time());
   // 通过取模与差值计算
   // 令block_time值始终以 000 或 500 结尾
   const int64_t min_time_to_next_block = (config::block_interval_us) - (base.time_since_epoch().count() % (config::block_interval_us) );
   fc::time_point block_time = base + fc::microseconds(min_time_to_next_block);
   return block_time;
}
//其中`block_interval_ms`和`block_interval_us`常量在config.hpp文件：
const static int      block_interval_ms = 500;
const static int      block_interval_us = block_interval_ms*1000;

得到区块时间值block_time后，继续往下找到get_scheduled_producer(block_time)函数，使用该函数计算当前出块节点：

c++

producer_authority block_header_state::get_scheduled_producer(block_timestamp_type t) const {
        // t.slot是区块时间的另一种表示方式
        // 可以理解为给定的时间出块的个数 类似slot = t / 500
        // active_schedule.producers.size()是出块节点数量，21个
        // config::producer_repetitions是每个节点连续出块个数，12个
        // 通过取模的计算方式就可以求出给定时间出块索引值
        auto index = t.slot % (active_schedule.producers.size() * config::producer_repetitions);
        index /= config::producer_repetitions;
        return active_schedule.producers[index];
    }

我们再回到producer_plugin.start_block()函数，得到当前出块节点后，通过_producers.find(scheduled_producer.producer_name) != _producers.end()在_producers里面查找，如果找到了（即返回值不等于end()）表示当前轮到我们出块，接着调用controller.start_block()函数将交易池的交易捞出来放到新的区块，最后返回succeeded，回到schedule_production_loop()接收到结果后调用maybe_produce_block()函数进入produce_block()，在这里将会对新的区块进行finalize_block类似封口，再对区块进行签名，最后通过controller.commit_block()提交区块。

在commit_block()函数先把区块保存到本地数据库，然后将新的区块广播给其他节点，最后因为有新的区块加入到本地，重新计算不可逆区块，并同样广播出去。到此，就是BP出块的基本流程。

接收新的区块 #

新的区块广播出去后，其他BP会接收到新区块并作出相应的处理，继续看上面的流程图，看到第一个绿色的net_plugin块，接收新区块的代码位于plugins/net_plugin/net_plugin.cpp文件。

c++

void handle_message( const block_id_type& id, signed_block_ptr msg );

消息会被producer_plugin插件订阅，最终来到on_incoming_block()函数，先是对接收的区块进行了时间、ID等校验，毕竟这里是外部的一个区块，所以很有可能是恶意者提交的，在承认这个区块之前必须做一些必要的工作。校验完毕，进入push_block()，最后同样是调用commit_block()将新区块保存到本地，但和之前不同的是，需要对区块签名进行验签。

接收新的交易 #

节点除了接收新的区块外，还会接收其他节点广播的交易，接收新交易的代码位于plugins/net_plugin/net_plugin.cpp文件。

c++

handle_message(packed_transaction) -> bcast_transaction()

消息同样会被producer_plugin插件订阅，最终来到on_incoming_transaction_async()函数，进入交易池，等待出块时加入到新区块。

BFT实现 #

待续