Branch data     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   [ +  -  +  -  :        126 :     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                 :        252 :     TestConditionChecker(int64_t begin, int64_t end, int period, int threshold, int min_activation_height, int bit)
      38                 :        126 :         : m_begin{begin}, m_end{end}, m_period{period}, m_threshold{threshold}, m_min_activation_height{min_activation_height}, m_bit{bit}
      39                 :        126 :     {
      40         [ +  - ]:        126 :         assert(m_period > 0);
      41   [ -  +  +  - ]:        126 :         assert(0 <= m_threshold && m_threshold <= m_period);
      42   [ +  -  -  +  :        126 :         assert(0 <= m_bit && m_bit < 32 && m_bit < VERSIONBITS_NUM_BITS);
                   +  - ]
      43         [ +  - ]:        126 :         assert(0 <= m_min_activation_height);
      44                 :        126 :     }
      45                 :            : 
      46                 :     119648 :     bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const override { return Condition(pindex->nVersion); }
      47                 :      33709 :     int64_t BeginTime(const Consensus::Params& params) const override { return m_begin; }
      48                 :      30046 :     int64_t EndTime(const Consensus::Params& params) const override { return m_end; }
      49                 :      39325 :     int Period(const Consensus::Params& params) const override { return m_period; }
      50                 :      37039 :     int Threshold(const Consensus::Params& params) const override { return m_threshold; }
      51                 :      30046 :     int MinActivationHeight(const Consensus::Params& params) const override { return m_min_activation_height; }
      52                 :            : 
      53                 :       3663 :     ThresholdState GetStateFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateFor(pindexPrev, dummy_params, m_cache); }
      54                 :       3663 :     int GetStateSinceHeightFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateSinceHeightFor(pindexPrev, dummy_params, m_cache); }
      55                 :       6993 :     BIP9Stats GetStateStatisticsFor(const CBlockIndex* pindex, std::vector<bool>* signals=nullptr) const { return AbstractThresholdConditionChecker::GetStateStatisticsFor(pindex, dummy_params, signals); }
      56                 :            : 
      57                 :     123442 :     bool Condition(int32_t version) const
      58                 :            :     {
      59                 :     123442 :         uint32_t mask = (uint32_t{1}) << m_bit;
      60         [ +  + ]:     123442 :         return (((version & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (version & mask) != 0);
      61                 :            :     }
      62                 :            : 
      63                 :       3552 :     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                 :        173 :     const int32_t m_no_signal;
      75                 :            : 
      76                 :            : public:
      77                 :        111 :     Blocks(uint32_t start_time, uint32_t interval, int32_t signal, int32_t no_signal)
      78                 :        111 :         : m_start_time{start_time}, m_interval{interval}, m_signal{signal}, m_no_signal{no_signal} {}
      79                 :            : 
      80                 :       1337 :     size_t size() const { return m_blocks.size(); }
      81                 :            : 
      82                 :      42895 :     CBlockIndex* tip() const
      83                 :            :     {
      84         [ +  + ]:      42895 :         return m_blocks.empty() ? nullptr : m_blocks.back().get();
      85                 :            :     }
      86                 :            : 
      87                 :      42784 :     CBlockIndex* mine_block(bool signal)
      88                 :            :     {
      89                 :      42784 :         CBlockHeader header;
      90         [ +  + ]:      42784 :         header.nVersion = signal ? m_signal : m_no_signal;
      91                 :      42784 :         header.nTime = m_start_time + m_blocks.size() * m_interval;
      92                 :      42784 :         header.nBits = 0x1d00ffff;
      93                 :            : 
      94                 :      42784 :         auto current_block = std::make_unique<CBlockIndex>(header);
      95         [ +  - ]:      42784 :         current_block->pprev = tip();
      96                 :      42784 :         current_block->nHeight = m_blocks.size();
      97         [ +  - ]:      42784 :         current_block->BuildSkip();
      98                 :            : 
      99         [ +  - ]:      42784 :         return m_blocks.emplace_back(std::move(current_block)).get();
     100                 :      42784 :     }
     101                 :            : };
     102                 :            : 
     103                 :            : std::unique_ptr<const CChainParams> g_params;
     104                 :            : 
     105                 :          1 : void initialize()
     106                 :            : {
     107                 :            :     // this is actually comparatively slow, so only do it once
     108         [ +  - ]:          1 :     g_params = CreateChainParams(ArgsManager{}, ChainType::MAIN);
     109         [ +  - ]:          1 :     assert(g_params != nullptr);
     110                 :          1 : }
     111                 :            : 
     112                 :            : constexpr uint32_t MAX_START_TIME = 4102444800; // 2100-01-01
     113                 :            : 
     114   [ +  -  -  + ]:        472 : FUZZ_TARGET(versionbits, .init = initialize)
     115                 :            : {
     116                 :        126 :     const CChainParams& params = *g_params;
     117                 :        126 :     const int64_t interval = params.GetConsensus().nPowTargetSpacing;
     118         [ +  - ]:        126 :     assert(interval > 1); // need to be able to halve it
     119         [ +  - ]:        126 :     assert(interval < std::numeric_limits<int32_t>::max());
     120                 :            : 
     121                 :        126 :     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
     122                 :            : 
     123                 :            :     // making period/max_periods larger slows these tests down significantly
     124                 :        126 :     const int period = 32;
     125                 :        126 :     const size_t max_periods = 16;
     126                 :        126 :     const size_t max_blocks = 2 * period * max_periods;
     127                 :            : 
     128                 :        126 :     const int threshold = fuzzed_data_provider.ConsumeIntegralInRange(1, period);
     129   [ -  +  +  - ]:        126 :     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         [ +  - ]:        126 :     assert(std::numeric_limits<uint32_t>::max() - MAX_START_TIME > interval * max_blocks);
     134                 :            : 
     135                 :        126 :     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                 :        126 :     const int32_t ver_signal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
     139                 :        126 :     const int32_t ver_nosignal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
     140                 :            : 
     141                 :            :     // select deployment parameters: bit, start time, timeout
     142                 :        126 :     const int bit = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, VERSIONBITS_NUM_BITS - 1);
     143                 :            : 
     144                 :        126 :     bool always_active_test = false;
     145                 :        126 :     bool never_active_test = false;
     146                 :            :     int64_t start_time;
     147                 :            :     int64_t timeout;
     148         [ +  + ]:        126 :     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                 :         85 :         int start_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
     152                 :         85 :         int end_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
     153                 :            : 
     154                 :         85 :         start_time = block_start_time + start_block * interval;
     155                 :         85 :         timeout = block_start_time + end_block * interval;
     156                 :            : 
     157                 :            :         // allow for times to not exactly match a block
     158         [ +  + ]:         85 :         if (fuzzed_data_provider.ConsumeBool()) start_time += interval / 2;
     159         [ +  + ]:         85 :         if (fuzzed_data_provider.ConsumeBool()) timeout += interval / 2;
     160                 :         85 :     } else {
     161         [ +  + ]:         41 :         if (fuzzed_data_provider.ConsumeBool()) {
     162                 :          8 :             start_time = Consensus::BIP9Deployment::ALWAYS_ACTIVE;
     163                 :          8 :             always_active_test = true;
     164                 :          8 :         } else {
     165                 :         33 :             start_time = Consensus::BIP9Deployment::NEVER_ACTIVE;
     166                 :         33 :             never_active_test = true;
     167                 :            :         }
     168         [ +  + ]:         41 :         timeout = fuzzed_data_provider.ConsumeBool() ? Consensus::BIP9Deployment::NO_TIMEOUT : fuzzed_data_provider.ConsumeIntegral<int64_t>();
     169                 :            :     }
     170                 :        126 :     int min_activation = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * max_periods);
     171                 :            : 
     172                 :        126 :     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   [ +  -  +  + ]:        126 :     if (!checker.Condition(ver_signal)) return;
     176   [ +  -  -  + ]:        116 :     if (checker.Condition(ver_nosignal)) return;
     177         [ +  + ]:        116 :     if (ver_nosignal < 0) return;
     178                 :            : 
     179                 :            :     // TOP_BITS should ensure version will be positive and meet min
     180                 :            :     // version requirement
     181         [ +  - ]:        111 :     assert(ver_signal > 0);
     182         [ +  - ]:        111 :     assert(ver_signal >= VERSIONBITS_LAST_OLD_BLOCK_VERSION);
     183                 :            : 
     184                 :            :     // Now that we have chosen time and versions, setup to mine blocks
     185         [ +  - ]:        111 :     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         [ +  - ]:        111 :     const uint32_t signalling_mask = fuzzed_data_provider.ConsumeIntegral<uint32_t>();
     201                 :            : 
     202                 :            :     // mine prior periods
     203   [ +  -  +  + ]:       1323 :     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         [ +  - ]:       1226 :         bool signal = fuzzed_data_provider.ConsumeBool();
     206         [ +  + ]:      40458 :         for (int b = 0; b < period; ++b) {
     207         [ +  - ]:      39232 :             blocks.mine_block(signal);
     208                 :      39232 :         }
     209                 :            : 
     210                 :            :         // don't risk exceeding max_blocks or times may wrap around
     211   [ +  -  +  + ]:       1226 :         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                 :        111 :     int blocks_sig = 0;
     219                 :            : 
     220                 :            :     // get the info for the first block of the period
     221         [ +  - ]:        111 :     CBlockIndex* prev = blocks.tip();
     222         [ +  - ]:        111 :     const int exp_since = checker.GetStateSinceHeightFor(prev);
     223         [ +  - ]:        111 :     const ThresholdState exp_state = checker.GetStateFor(prev);
     224                 :            : 
     225                 :            :     // get statistics from end of previous period, then reset
     226                 :            :     BIP9Stats last_stats;
     227                 :        111 :     last_stats.period = period;
     228                 :        111 :     last_stats.threshold = threshold;
     229                 :        111 :     last_stats.count = last_stats.elapsed = 0;
     230                 :        111 :     last_stats.possible = (period >= threshold);
     231                 :        111 :     std::vector<bool> last_signals{};
     232                 :            : 
     233         [ +  + ]:        111 :     int prev_next_height = (prev == nullptr ? 0 : prev->nHeight + 1);
     234         [ +  - ]:        111 :     assert(exp_since <= prev_next_height);
     235                 :            : 
     236                 :            :     // mine (period-1) blocks and check state
     237         [ +  + ]:       3552 :     for (int b = 1; b < period; ++b) {
     238                 :       3441 :         const bool signal = (signalling_mask >> (b % 32)) & 1;
     239         [ +  + ]:       3441 :         if (signal) ++blocks_sig;
     240                 :            : 
     241         [ +  - ]:       3441 :         CBlockIndex* current_block = blocks.mine_block(signal);
     242                 :            : 
     243                 :            :         // verify that signalling attempt was interpreted correctly
     244   [ +  -  +  - ]:       3441 :         assert(checker.Condition(current_block) == signal);
     245                 :            : 
     246                 :            :         // state and since don't change within the period
     247         [ +  - ]:       3441 :         const ThresholdState state = checker.GetStateFor(current_block);
     248         [ +  - ]:       3441 :         const int since = checker.GetStateSinceHeightFor(current_block);
     249         [ +  - ]:       3441 :         assert(state == exp_state);
     250         [ +  - ]:       3441 :         assert(since == exp_since);
     251                 :            : 
     252                 :            :         // check that after mining this block stats change as expected
     253                 :       3441 :         std::vector<bool> signals;
     254         [ +  - ]:       3441 :         const BIP9Stats stats = checker.GetStateStatisticsFor(current_block, &signals);
     255         [ +  - ]:       3441 :         const BIP9Stats stats_no_signals = checker.GetStateStatisticsFor(current_block);
     256   [ +  -  +  -  :       3441 :         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         [ +  - ]:       3441 :         assert(stats.period == period);
     261         [ +  - ]:       3441 :         assert(stats.threshold == threshold);
     262         [ +  - ]:       3441 :         assert(stats.elapsed == b);
     263         [ -  + ]:       3441 :         assert(stats.count == last_stats.count + (signal ? 1 : 0));
     264         [ -  + ]:       3441 :         assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
     265                 :       3441 :         last_stats = stats;
     266                 :            : 
     267         [ -  + ]:       3441 :         assert(signals.size() == last_signals.size() + 1);
     268   [ +  -  +  - ]:       3441 :         assert(signals.back() == signal);
     269         [ +  - ]:       3441 :         last_signals.push_back(signal);
     270   [ +  -  +  - ]:       3441 :         assert(signals == last_signals);
     271                 :       3441 :     }
     272                 :            : 
     273         [ +  + ]:        111 :     if (exp_state == ThresholdState::STARTED) {
     274                 :            :         // double check that stats.possible is sane
     275   [ +  +  +  - ]:         15 :         if (blocks_sig >= threshold - 1) assert(last_stats.possible);
     276                 :         15 :     }
     277                 :            : 
     278                 :            :     // mine the final block
     279                 :        111 :     bool signal = (signalling_mask >> (period % 32)) & 1;
     280         [ +  + ]:        111 :     if (signal) ++blocks_sig;
     281         [ +  - ]:        111 :     CBlockIndex* current_block = blocks.mine_block(signal);
     282   [ +  -  +  - ]:        111 :     assert(checker.Condition(current_block) == signal);
     283                 :            : 
     284         [ +  - ]:        111 :     const BIP9Stats stats = checker.GetStateStatisticsFor(current_block);
     285         [ +  - ]:        111 :     assert(stats.period == period);
     286         [ +  - ]:        111 :     assert(stats.threshold == threshold);
     287         [ +  - ]:        111 :     assert(stats.elapsed == period);
     288         [ +  - ]:        111 :     assert(stats.count == blocks_sig);
     289         [ +  - ]:        111 :     assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
     290                 :            : 
     291                 :            :     // More interesting is whether the state changed.
     292         [ +  - ]:        111 :     const ThresholdState state = checker.GetStateFor(current_block);
     293         [ +  - ]:        111 :     const int since = checker.GetStateSinceHeightFor(current_block);
     294                 :            : 
     295                 :            :     // since is straightforward:
     296         [ +  - ]:        111 :     assert(since % period == 0);
     297   [ -  +  +  - ]:        111 :     assert(0 <= since && since <= current_block->nHeight + 1);
     298         [ +  + ]:        111 :     if (state == exp_state) {
     299         [ +  - ]:         88 :         assert(since == exp_since);
     300                 :         88 :     } else {
     301         [ +  - ]:         23 :         assert(since == current_block->nHeight + 1);
     302                 :            :     }
     303                 :            : 
     304                 :            :     // state is where everything interesting is
     305   [ +  +  +  +  :        111 :     switch (state) {
                   +  - ]
     306                 :            :     case ThresholdState::DEFINED:
     307         [ +  - ]:          7 :         assert(since == 0);
     308         [ +  - ]:          7 :         assert(exp_state == ThresholdState::DEFINED);
     309   [ +  -  +  - ]:          7 :         assert(current_block->GetMedianTimePast() < checker.m_begin);
     310                 :          7 :         break;
     311                 :            :     case ThresholdState::STARTED:
     312   [ +  -  +  - ]:         16 :         assert(current_block->GetMedianTimePast() >= checker.m_begin);
     313         [ +  + ]:         16 :         if (exp_state == ThresholdState::STARTED) {
     314         [ +  - ]:          7 :             assert(blocks_sig < threshold);
     315   [ +  -  +  - ]:          7 :             assert(current_block->GetMedianTimePast() < checker.m_end);
     316                 :          7 :         } else {
     317         [ +  - ]:          9 :             assert(exp_state == ThresholdState::DEFINED);
     318                 :            :         }
     319                 :         16 :         break;
     320                 :            :     case ThresholdState::LOCKED_IN:
     321         [ +  + ]:          6 :         if (exp_state == ThresholdState::LOCKED_IN) {
     322         [ +  - ]:          3 :             assert(current_block->nHeight + 1 < min_activation);
     323                 :          3 :         } else {
     324         [ +  - ]:          3 :             assert(exp_state == ThresholdState::STARTED);
     325         [ +  - ]:          3 :             assert(blocks_sig >= threshold);
     326                 :            :         }
     327                 :          6 :         break;
     328                 :            :     case ThresholdState::ACTIVE:
     329   [ +  +  +  - ]:         43 :         assert(always_active_test || min_activation <= current_block->nHeight + 1);
     330   [ +  +  +  - ]:         43 :         assert(exp_state == ThresholdState::ACTIVE || exp_state == ThresholdState::LOCKED_IN);
     331                 :         43 :         break;
     332                 :            :     case ThresholdState::FAILED:
     333   [ +  +  +  -  :         39 :         assert(never_active_test || current_block->GetMedianTimePast() >= checker.m_end);
                   +  - ]
     334         [ +  + ]:         39 :         if (exp_state == ThresholdState::STARTED) {
     335         [ +  - ]:          5 :             assert(blocks_sig < threshold);
     336                 :          5 :         } else {
     337         [ +  - ]:         34 :             assert(exp_state == ThresholdState::FAILED);
     338                 :            :         }
     339                 :         39 :         break;
     340                 :            :     default:
     341                 :          0 :         assert(false);
     342                 :            :     }
     343                 :            : 
     344   [ +  -  +  + ]:        111 :     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   [ +  +  +  - ]:         40 :         assert(state == ThresholdState::ACTIVE || state == ThresholdState::FAILED);
     347                 :         40 :     }
     348                 :            : 
     349         [ +  + ]:        111 :     if (always_active_test) {
     350                 :            :         // "always active" has additional restrictions
     351         [ +  - ]:          8 :         assert(state == ThresholdState::ACTIVE);
     352         [ +  - ]:          8 :         assert(exp_state == ThresholdState::ACTIVE);
     353         [ +  - ]:          8 :         assert(since == 0);
     354         [ +  + ]:        111 :     } else if (never_active_test) {
     355                 :            :         // "never active" does too
     356         [ +  - ]:         18 :         assert(state == ThresholdState::FAILED);
     357         [ +  - ]:         18 :         assert(exp_state == ThresholdState::FAILED);
     358         [ +  - ]:         18 :         assert(since == 0);
     359                 :         18 :     } else {
     360                 :            :         // for signalled deployments, the initial state is always DEFINED
     361   [ +  +  +  - ]:         85 :         assert(since > 0 || state == ThresholdState::DEFINED);
     362   [ +  +  +  - ]:         85 :         assert(exp_since > 0 || exp_state == ThresholdState::DEFINED);
     363                 :            :     }
     364         [ -  + ]:        126 : }
     365                 :            : } // namespace