Line data    Source code

       1             : // Copyright (c) 2020-2021 The Bitcoin Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #include <chain.h>
       6             : #include <chainparams.h>
       7             : #include <common/args.h>
       8             : #include <consensus/params.h>
       9             : #include <primitives/block.h>
      10             : #include <util/chaintype.h>
      11             : #include <versionbits.h>
      12             : 
      13             : #include <test/fuzz/FuzzedDataProvider.h>
      14             : #include <test/fuzz/fuzz.h>
      15             : #include <test/fuzz/util.h>
      16             : 
      17             : #include <cstdint>
      18             : #include <limits>
      19             : #include <memory>
      20             : #include <vector>
      21             : 
      22             : namespace {
      23             : class TestConditionChecker : public AbstractThresholdConditionChecker
      24             : {
      25             : private:
      26             :     mutable ThresholdConditionCache m_cache;
      27           0 :     const Consensus::Params dummy_params{};
      28             : 
      29             : public:
      30             :     const int64_t m_begin;
      31             :     const int64_t m_end;
      32             :     const int m_period;
      33             :     const int m_threshold;
      34             :     const int m_min_activation_height;
      35             :     const int m_bit;
      36             : 
      37           0 :     TestConditionChecker(int64_t begin, int64_t end, int period, int threshold, int min_activation_height, int bit)
      38           0 :         : m_begin{begin}, m_end{end}, m_period{period}, m_threshold{threshold}, m_min_activation_height{min_activation_height}, m_bit{bit}
      39           0 :     {
      40           0 :         assert(m_period > 0);
      41           0 :         assert(0 <= m_threshold && m_threshold <= m_period);
      42           0 :         assert(0 <= m_bit && m_bit < 32 && m_bit < VERSIONBITS_NUM_BITS);
      43           0 :         assert(0 <= m_min_activation_height);
      44           0 :     }
      45             : 
      46           0 :     bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const override { return Condition(pindex->nVersion); }
      47           0 :     int64_t BeginTime(const Consensus::Params& params) const override { return m_begin; }
      48           0 :     int64_t EndTime(const Consensus::Params& params) const override { return m_end; }
      49           0 :     int Period(const Consensus::Params& params) const override { return m_period; }
      50           0 :     int Threshold(const Consensus::Params& params) const override { return m_threshold; }
      51           0 :     int MinActivationHeight(const Consensus::Params& params) const override { return m_min_activation_height; }
      52             : 
      53           0 :     ThresholdState GetStateFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateFor(pindexPrev, dummy_params, m_cache); }
      54           0 :     int GetStateSinceHeightFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateSinceHeightFor(pindexPrev, dummy_params, m_cache); }
      55           0 :     BIP9Stats GetStateStatisticsFor(const CBlockIndex* pindex, std::vector<bool>* signals=nullptr) const { return AbstractThresholdConditionChecker::GetStateStatisticsFor(pindex, dummy_params, signals); }
      56             : 
      57           0 :     bool Condition(int32_t version) const
      58             :     {
      59           0 :         uint32_t mask = (uint32_t{1}) << m_bit;
      60           0 :         return (((version & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (version & mask) != 0);
      61             :     }
      62             : 
      63           0 :     bool Condition(const CBlockIndex* pindex) const { return Condition(pindex->nVersion); }
      64             : };
      65             : 
      66             : /** Track blocks mined for test */
      67             : class Blocks
      68             : {
      69             : private:
      70             :     std::vector<std::unique_ptr<CBlockIndex>> m_blocks;
      71             :     const uint32_t m_start_time;
      72             :     const uint32_t m_interval;
      73             :     const int32_t m_signal;
      74           2 :     const int32_t m_no_signal;
      75             : 
      76             : public:
      77           0 :     Blocks(uint32_t start_time, uint32_t interval, int32_t signal, int32_t no_signal)
      78           0 :         : m_start_time{start_time}, m_interval{interval}, m_signal{signal}, m_no_signal{no_signal} {}
      79             : 
      80           0 :     size_t size() const { return m_blocks.size(); }
      81             : 
      82           0 :     CBlockIndex* tip() const
      83             :     {
      84           0 :         return m_blocks.empty() ? nullptr : m_blocks.back().get();
      85             :     }
      86             : 
      87           0 :     CBlockIndex* mine_block(bool signal)
      88             :     {
      89           0 :         CBlockHeader header;
      90           0 :         header.nVersion = signal ? m_signal : m_no_signal;
      91           0 :         header.nTime = m_start_time + m_blocks.size() * m_interval;
      92           0 :         header.nBits = 0x1d00ffff;
      93             : 
      94           0 :         auto current_block = std::make_unique<CBlockIndex>(header);
      95           0 :         current_block->pprev = tip();
      96           0 :         current_block->nHeight = m_blocks.size();
      97           0 :         current_block->BuildSkip();
      98             : 
      99           0 :         return m_blocks.emplace_back(std::move(current_block)).get();
     100           0 :     }
     101             : };
     102             : 
     103             : std::unique_ptr<const CChainParams> g_params;
     104             : 
     105           0 : void initialize()
     106             : {
     107             :     // this is actually comparatively slow, so only do it once
     108           0 :     g_params = CreateChainParams(ArgsManager{}, ChainType::MAIN);
     109           0 :     assert(g_params != nullptr);
     110           0 : }
     111             : 
     112             : constexpr uint32_t MAX_START_TIME = 4102444800; // 2100-01-01
     113             : 
     114           4 : FUZZ_TARGET(versionbits, .init = initialize)
     115             : {
     116           0 :     const CChainParams& params = *g_params;
     117           0 :     const int64_t interval = params.GetConsensus().nPowTargetSpacing;
     118           0 :     assert(interval > 1); // need to be able to halve it
     119           0 :     assert(interval < std::numeric_limits<int32_t>::max());
     120             : 
     121           0 :     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
     122             : 
     123             :     // making period/max_periods larger slows these tests down significantly
     124           0 :     const int period = 32;
     125           0 :     const size_t max_periods = 16;
     126           0 :     const size_t max_blocks = 2 * period * max_periods;
     127             : 
     128           0 :     const int threshold = fuzzed_data_provider.ConsumeIntegralInRange(1, period);
     129           0 :     assert(0 < threshold && threshold <= period); // must be able to both pass and fail threshold!
     130             : 
     131             :     // too many blocks at 10min each might cause uint32_t time to overflow if
     132             :     // block_start_time is at the end of the range above
     133           0 :     assert(std::numeric_limits<uint32_t>::max() - MAX_START_TIME > interval * max_blocks);
     134             : 
     135           0 :     const int64_t block_start_time = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(params.GenesisBlock().nTime, MAX_START_TIME);
     136             : 
     137             :     // what values for version will we use to signal / not signal?
     138           0 :     const int32_t ver_signal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
     139           0 :     const int32_t ver_nosignal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
     140             : 
     141             :     // select deployment parameters: bit, start time, timeout
     142           0 :     const int bit = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, VERSIONBITS_NUM_BITS - 1);
     143             : 
     144           0 :     bool always_active_test = false;
     145           0 :     bool never_active_test = false;
     146             :     int64_t start_time;
     147             :     int64_t timeout;
     148           0 :     if (fuzzed_data_provider.ConsumeBool()) {
     149             :         // pick the timestamp to switch based on a block
     150             :         // note states will change *after* these blocks because mediantime lags
     151           0 :         int start_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
     152           0 :         int end_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
     153             : 
     154           0 :         start_time = block_start_time + start_block * interval;
     155           0 :         timeout = block_start_time + end_block * interval;
     156             : 
     157             :         // allow for times to not exactly match a block
     158           0 :         if (fuzzed_data_provider.ConsumeBool()) start_time += interval / 2;
     159           0 :         if (fuzzed_data_provider.ConsumeBool()) timeout += interval / 2;
     160           0 :     } else {
     161           0 :         if (fuzzed_data_provider.ConsumeBool()) {
     162           0 :             start_time = Consensus::BIP9Deployment::ALWAYS_ACTIVE;
     163           0 :             always_active_test = true;
     164           0 :         } else {
     165           0 :             start_time = Consensus::BIP9Deployment::NEVER_ACTIVE;
     166           0 :             never_active_test = true;
     167             :         }
     168           0 :         timeout = fuzzed_data_provider.ConsumeBool() ? Consensus::BIP9Deployment::NO_TIMEOUT : fuzzed_data_provider.ConsumeIntegral<int64_t>();
     169             :     }
     170           0 :     int min_activation = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * max_periods);
     171             : 
     172           0 :     TestConditionChecker checker(start_time, timeout, period, threshold, min_activation, bit);
     173             : 
     174             :     // Early exit if the versions don't signal sensibly for the deployment
     175           0 :     if (!checker.Condition(ver_signal)) return;
     176           0 :     if (checker.Condition(ver_nosignal)) return;
     177           0 :     if (ver_nosignal < 0) return;
     178             : 
     179             :     // TOP_BITS should ensure version will be positive and meet min
     180             :     // version requirement
     181           0 :     assert(ver_signal > 0);
     182           0 :     assert(ver_signal >= VERSIONBITS_LAST_OLD_BLOCK_VERSION);
     183             : 
     184             :     // Now that we have chosen time and versions, setup to mine blocks
     185           0 :     Blocks blocks(block_start_time, interval, ver_signal, ver_nosignal);
     186             : 
     187             :     /* Strategy:
     188             :      *  * we will mine a final period worth of blocks, with
     189             :      *    randomised signalling according to a mask
     190             :      *  * but before we mine those blocks, we will mine some
     191             :      *    randomised number of prior periods; with either all
     192             :      *    or no blocks in the period signalling
     193             :      *
     194             :      * We establish the mask first, then consume "bools" until
     195             :      * we run out of fuzz data to work out how many prior periods
     196             :      * there are and which ones will signal.
     197             :      */
     198             : 
     199             :     // establish the mask
     200           0 :     const uint32_t signalling_mask = fuzzed_data_provider.ConsumeIntegral<uint32_t>();
     201             : 
     202             :     // mine prior periods
     203           0 :     while (fuzzed_data_provider.remaining_bytes() > 0) { // early exit; no need for LIMITED_WHILE
     204             :         // all blocks in these periods either do or don't signal
     205           0 :         bool signal = fuzzed_data_provider.ConsumeBool();
     206           0 :         for (int b = 0; b < period; ++b) {
     207           0 :             blocks.mine_block(signal);
     208           0 :         }
     209             : 
     210             :         // don't risk exceeding max_blocks or times may wrap around
     211           0 :         if (blocks.size() + 2 * period > max_blocks) break;
     212             :     }
     213             :     // NOTE: fuzzed_data_provider may be fully consumed at this point and should not be used further
     214             : 
     215             :     // now we mine the final period and check that everything looks sane
     216             : 
     217             :     // count the number of signalling blocks
     218           0 :     int blocks_sig = 0;
     219             : 
     220             :     // get the info for the first block of the period
     221           0 :     CBlockIndex* prev = blocks.tip();
     222           0 :     const int exp_since = checker.GetStateSinceHeightFor(prev);
     223           0 :     const ThresholdState exp_state = checker.GetStateFor(prev);
     224             : 
     225             :     // get statistics from end of previous period, then reset
     226             :     BIP9Stats last_stats;
     227           0 :     last_stats.period = period;
     228           0 :     last_stats.threshold = threshold;
     229           0 :     last_stats.count = last_stats.elapsed = 0;
     230           0 :     last_stats.possible = (period >= threshold);
     231           0 :     std::vector<bool> last_signals{};
     232             : 
     233           0 :     int prev_next_height = (prev == nullptr ? 0 : prev->nHeight + 1);
     234           0 :     assert(exp_since <= prev_next_height);
     235             : 
     236             :     // mine (period-1) blocks and check state
     237           0 :     for (int b = 1; b < period; ++b) {
     238           0 :         const bool signal = (signalling_mask >> (b % 32)) & 1;
     239           0 :         if (signal) ++blocks_sig;
     240             : 
     241           0 :         CBlockIndex* current_block = blocks.mine_block(signal);
     242             : 
     243             :         // verify that signalling attempt was interpreted correctly
     244           0 :         assert(checker.Condition(current_block) == signal);
     245             : 
     246             :         // state and since don't change within the period
     247           0 :         const ThresholdState state = checker.GetStateFor(current_block);
     248           0 :         const int since = checker.GetStateSinceHeightFor(current_block);
     249           0 :         assert(state == exp_state);
     250           0 :         assert(since == exp_since);
     251             : 
     252             :         // check that after mining this block stats change as expected
     253           0 :         std::vector<bool> signals;
     254           0 :         const BIP9Stats stats = checker.GetStateStatisticsFor(current_block, &signals);
     255           0 :         const BIP9Stats stats_no_signals = checker.GetStateStatisticsFor(current_block);
     256           0 :         assert(stats.period == stats_no_signals.period && stats.threshold == stats_no_signals.threshold
     257             :                && stats.elapsed == stats_no_signals.elapsed && stats.count == stats_no_signals.count
     258             :                && stats.possible == stats_no_signals.possible);
     259             : 
     260           0 :         assert(stats.period == period);
     261           0 :         assert(stats.threshold == threshold);
     262           0 :         assert(stats.elapsed == b);
     263           0 :         assert(stats.count == last_stats.count + (signal ? 1 : 0));
     264           0 :         assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
     265           0 :         last_stats = stats;
     266             : 
     267           0 :         assert(signals.size() == last_signals.size() + 1);
     268           0 :         assert(signals.back() == signal);
     269           0 :         last_signals.push_back(signal);
     270           0 :         assert(signals == last_signals);
     271           0 :     }
     272             : 
     273           0 :     if (exp_state == ThresholdState::STARTED) {
     274             :         // double check that stats.possible is sane
     275           0 :         if (blocks_sig >= threshold - 1) assert(last_stats.possible);
     276           0 :     }
     277             : 
     278             :     // mine the final block
     279           0 :     bool signal = (signalling_mask >> (period % 32)) & 1;
     280           0 :     if (signal) ++blocks_sig;
     281           0 :     CBlockIndex* current_block = blocks.mine_block(signal);
     282           0 :     assert(checker.Condition(current_block) == signal);
     283             : 
     284           0 :     const BIP9Stats stats = checker.GetStateStatisticsFor(current_block);
     285           0 :     assert(stats.period == period);
     286           0 :     assert(stats.threshold == threshold);
     287           0 :     assert(stats.elapsed == period);
     288           0 :     assert(stats.count == blocks_sig);
     289           0 :     assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
     290             : 
     291             :     // More interesting is whether the state changed.
     292           0 :     const ThresholdState state = checker.GetStateFor(current_block);
     293           0 :     const int since = checker.GetStateSinceHeightFor(current_block);
     294             : 
     295             :     // since is straightforward:
     296           0 :     assert(since % period == 0);
     297           0 :     assert(0 <= since && since <= current_block->nHeight + 1);
     298           0 :     if (state == exp_state) {
     299           0 :         assert(since == exp_since);
     300           0 :     } else {
     301           0 :         assert(since == current_block->nHeight + 1);
     302             :     }
     303             : 
     304             :     // state is where everything interesting is
     305           0 :     switch (state) {
     306             :     case ThresholdState::DEFINED:
     307           0 :         assert(since == 0);
     308           0 :         assert(exp_state == ThresholdState::DEFINED);
     309           0 :         assert(current_block->GetMedianTimePast() < checker.m_begin);
     310           0 :         break;
     311             :     case ThresholdState::STARTED:
     312           0 :         assert(current_block->GetMedianTimePast() >= checker.m_begin);
     313           0 :         if (exp_state == ThresholdState::STARTED) {
     314           0 :             assert(blocks_sig < threshold);
     315           0 :             assert(current_block->GetMedianTimePast() < checker.m_end);
     316           0 :         } else {
     317           0 :             assert(exp_state == ThresholdState::DEFINED);
     318             :         }
     319           0 :         break;
     320             :     case ThresholdState::LOCKED_IN:
     321           0 :         if (exp_state == ThresholdState::LOCKED_IN) {
     322           0 :             assert(current_block->nHeight + 1 < min_activation);
     323           0 :         } else {
     324           0 :             assert(exp_state == ThresholdState::STARTED);
     325           0 :             assert(blocks_sig >= threshold);
     326             :         }
     327           0 :         break;
     328             :     case ThresholdState::ACTIVE:
     329           0 :         assert(always_active_test || min_activation <= current_block->nHeight + 1);
     330           0 :         assert(exp_state == ThresholdState::ACTIVE || exp_state == ThresholdState::LOCKED_IN);
     331           0 :         break;
     332             :     case ThresholdState::FAILED:
     333           0 :         assert(never_active_test || current_block->GetMedianTimePast() >= checker.m_end);
     334           0 :         if (exp_state == ThresholdState::STARTED) {
     335           0 :             assert(blocks_sig < threshold);
     336           0 :         } else {
     337           0 :             assert(exp_state == ThresholdState::FAILED);
     338             :         }
     339           0 :         break;
     340             :     default:
     341           0 :         assert(false);
     342             :     }
     343             : 
     344           0 :     if (blocks.size() >= period * max_periods) {
     345             :         // we chose the timeout (and block times) so that by the time we have this many blocks it's all over
     346           0 :         assert(state == ThresholdState::ACTIVE || state == ThresholdState::FAILED);
     347           0 :     }
     348             : 
     349           0 :     if (always_active_test) {
     350             :         // "always active" has additional restrictions
     351           0 :         assert(state == ThresholdState::ACTIVE);
     352           0 :         assert(exp_state == ThresholdState::ACTIVE);
     353           0 :         assert(since == 0);
     354           0 :     } else if (never_active_test) {
     355             :         // "never active" does too
     356           0 :         assert(state == ThresholdState::FAILED);
     357           0 :         assert(exp_state == ThresholdState::FAILED);
     358           0 :         assert(since == 0);
     359           0 :     } else {
     360             :         // for signalled deployments, the initial state is always DEFINED
     361           0 :         assert(since > 0 || state == ThresholdState::DEFINED);
     362           0 :         assert(exp_since > 0 || exp_state == ThresholdState::DEFINED);
     363             :     }
     364           0 : }
     365             : } // namespace