Bitcoin Core  22.99.0
P2P Digital Currency
versionbits.cpp
Go to the documentation of this file.
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 <consensus/params.h>
8 #include <primitives/block.h>
9 #include <util/system.h>
10 #include <versionbits.h>
11 
13 #include <test/fuzz/fuzz.h>
14 #include <test/fuzz/util.h>
15 
16 #include <cstdint>
17 #include <limits>
18 #include <memory>
19 #include <vector>
20 
21 namespace {
23 {
24 private:
25  mutable ThresholdConditionCache m_cache;
26  const Consensus::Params dummy_params{};
27 
28 public:
29  const int64_t m_begin;
30  const int64_t m_end;
31  const int m_period;
32  const int m_threshold;
33  const int m_min_activation_height;
34  const int m_bit;
35 
36  TestConditionChecker(int64_t begin, int64_t end, int period, int threshold, int min_activation_height, int bit)
37  : m_begin{begin}, m_end{end}, m_period{period}, m_threshold{threshold}, m_min_activation_height{min_activation_height}, m_bit{bit}
38  {
39  assert(m_period > 0);
40  assert(0 <= m_threshold && m_threshold <= m_period);
41  assert(0 <= m_bit && m_bit < 32 && m_bit < VERSIONBITS_NUM_BITS);
42  assert(0 <= m_min_activation_height);
43  }
44 
45  bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const override { return Condition(pindex->nVersion); }
46  int64_t BeginTime(const Consensus::Params& params) const override { return m_begin; }
47  int64_t EndTime(const Consensus::Params& params) const override { return m_end; }
48  int Period(const Consensus::Params& params) const override { return m_period; }
49  int Threshold(const Consensus::Params& params) const override { return m_threshold; }
50  int MinActivationHeight(const Consensus::Params& params) const override { return m_min_activation_height; }
51 
52  ThresholdState GetStateFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateFor(pindexPrev, dummy_params, m_cache); }
53  int GetStateSinceHeightFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateSinceHeightFor(pindexPrev, dummy_params, m_cache); }
54  BIP9Stats GetStateStatisticsFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateStatisticsFor(pindexPrev, dummy_params); }
55 
56  bool Condition(int32_t version) const
57  {
58  uint32_t mask = ((uint32_t)1) << m_bit;
59  return (((version & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (version & mask) != 0);
60  }
61 
62  bool Condition(const CBlockIndex* pindex) const { return Condition(pindex->nVersion); }
63 };
64 
66 class Blocks
67 {
68 private:
69  std::vector<std::unique_ptr<CBlockIndex>> m_blocks;
70  const uint32_t m_start_time;
71  const uint32_t m_interval;
72  const int32_t m_signal;
73  const int32_t m_no_signal;
74 
75 public:
76  Blocks(uint32_t start_time, uint32_t interval, int32_t signal, int32_t no_signal)
77  : m_start_time{start_time}, m_interval{interval}, m_signal{signal}, m_no_signal{no_signal} {}
78 
79  size_t size() const { return m_blocks.size(); }
80 
81  CBlockIndex* tip() const
82  {
83  return m_blocks.empty() ? nullptr : m_blocks.back().get();
84  }
85 
86  CBlockIndex* mine_block(bool signal)
87  {
88  CBlockHeader header;
89  header.nVersion = signal ? m_signal : m_no_signal;
90  header.nTime = m_start_time + m_blocks.size() * m_interval;
91  header.nBits = 0x1d00ffff;
92 
93  auto current_block = std::make_unique<CBlockIndex>(header);
94  current_block->pprev = tip();
95  current_block->nHeight = m_blocks.size();
96  current_block->BuildSkip();
97 
98  return m_blocks.emplace_back(std::move(current_block)).get();
99  }
100 };
101 
102 std::unique_ptr<const CChainParams> g_params;
103 
104 void initialize()
105 {
106  // this is actually comparatively slow, so only do it once
108  assert(g_params != nullptr);
109 }
110 
111 constexpr uint32_t MAX_START_TIME = 4102444800; // 2100-01-01
112 
113 FUZZ_TARGET_INIT(versionbits, initialize)
114 {
115  const CChainParams& params = *g_params;
116  const int64_t interval = params.GetConsensus().nPowTargetSpacing;
117  assert(interval > 1); // need to be able to halve it
118  assert(interval < std::numeric_limits<int32_t>::max());
119 
120  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
121 
122  // making period/max_periods larger slows these tests down significantly
123  const int period = 32;
124  const size_t max_periods = 16;
125  const size_t max_blocks = 2 * period * max_periods;
126 
127  const int threshold = fuzzed_data_provider.ConsumeIntegralInRange(1, period);
128  assert(0 < threshold && threshold <= period); // must be able to both pass and fail threshold!
129 
130  // too many blocks at 10min each might cause uint32_t time to overflow if
131  // block_start_time is at the end of the range above
132  assert(std::numeric_limits<uint32_t>::max() - MAX_START_TIME > interval * max_blocks);
133 
134  const int64_t block_start_time = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(params.GenesisBlock().nTime, MAX_START_TIME);
135 
136  // what values for version will we use to signal / not signal?
137  const int32_t ver_signal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
138  const int32_t ver_nosignal = fuzzed_data_provider.ConsumeIntegral<int32_t>();
139 
140  // select deployment parameters: bit, start time, timeout
141  const int bit = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, VERSIONBITS_NUM_BITS - 1);
142 
143  bool always_active_test = false;
144  bool never_active_test = false;
145  int64_t start_time;
146  int64_t timeout;
147  if (fuzzed_data_provider.ConsumeBool()) {
148  // pick the timestamp to switch based on a block
149  // note states will change *after* these blocks because mediantime lags
150  int start_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
151  int end_block = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * (max_periods - 3));
152 
153  start_time = block_start_time + start_block * interval;
154  timeout = block_start_time + end_block * interval;
155 
156  // allow for times to not exactly match a block
157  if (fuzzed_data_provider.ConsumeBool()) start_time += interval / 2;
158  if (fuzzed_data_provider.ConsumeBool()) timeout += interval / 2;
159  } else {
160  if (fuzzed_data_provider.ConsumeBool()) {
162  always_active_test = true;
163  } else {
165  never_active_test = true;
166  }
167  timeout = fuzzed_data_provider.ConsumeBool() ? Consensus::BIP9Deployment::NO_TIMEOUT : fuzzed_data_provider.ConsumeIntegral<int64_t>();
168  }
169  int min_activation = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, period * max_periods);
170 
171  TestConditionChecker checker(start_time, timeout, period, threshold, min_activation, bit);
172 
173  // Early exit if the versions don't signal sensibly for the deployment
174  if (!checker.Condition(ver_signal)) return;
175  if (checker.Condition(ver_nosignal)) return;
176  if (ver_nosignal < 0) return;
177 
178  // TOP_BITS should ensure version will be positive and meet min
179  // version requirement
180  assert(ver_signal > 0);
182 
183  // Now that we have chosen time and versions, setup to mine blocks
184  Blocks blocks(block_start_time, interval, ver_signal, ver_nosignal);
185 
186  /* Strategy:
187  * * we will mine a final period worth of blocks, with
188  * randomised signalling according to a mask
189  * * but before we mine those blocks, we will mine some
190  * randomised number of prior periods; with either all
191  * or no blocks in the period signalling
192  *
193  * We establish the mask first, then consume "bools" until
194  * we run out of fuzz data to work out how many prior periods
195  * there are and which ones will signal.
196  */
197 
198  // establish the mask
199  const uint32_t signalling_mask = fuzzed_data_provider.ConsumeIntegral<uint32_t>();
200 
201  // mine prior periods
202  while (fuzzed_data_provider.remaining_bytes() > 0) {
203  // all blocks in these periods either do or don't signal
204  bool signal = fuzzed_data_provider.ConsumeBool();
205  for (int b = 0; b < period; ++b) {
206  blocks.mine_block(signal);
207  }
208 
209  // don't risk exceeding max_blocks or times may wrap around
210  if (blocks.size() + 2 * period > max_blocks) break;
211  }
212  // NOTE: fuzzed_data_provider may be fully consumed at this point and should not be used further
213 
214  // now we mine the final period and check that everything looks sane
215 
216  // count the number of signalling blocks
217  int blocks_sig = 0;
218 
219  // get the info for the first block of the period
220  CBlockIndex* prev = blocks.tip();
221  const int exp_since = checker.GetStateSinceHeightFor(prev);
222  const ThresholdState exp_state = checker.GetStateFor(prev);
223  BIP9Stats last_stats = checker.GetStateStatisticsFor(prev);
224 
225  int prev_next_height = (prev == nullptr ? 0 : prev->nHeight + 1);
226  assert(exp_since <= prev_next_height);
227 
228  // mine (period-1) blocks and check state
229  for (int b = 1; b < period; ++b) {
230  const bool signal = (signalling_mask >> (b % 32)) & 1;
231  if (signal) ++blocks_sig;
232 
233  CBlockIndex* current_block = blocks.mine_block(signal);
234 
235  // verify that signalling attempt was interpreted correctly
236  assert(checker.Condition(current_block) == signal);
237 
238  // state and since don't change within the period
239  const ThresholdState state = checker.GetStateFor(current_block);
240  const int since = checker.GetStateSinceHeightFor(current_block);
241  assert(state == exp_state);
242  assert(since == exp_since);
243 
244  // GetStateStatistics may crash when state is not STARTED
245  if (state != ThresholdState::STARTED) continue;
246 
247  // check that after mining this block stats change as expected
248  const BIP9Stats stats = checker.GetStateStatisticsFor(current_block);
249  assert(stats.period == period);
250  assert(stats.threshold == threshold);
251  assert(stats.elapsed == b);
252  assert(stats.count == last_stats.count + (signal ? 1 : 0));
253  assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
254  last_stats = stats;
255  }
256 
257  if (exp_state == ThresholdState::STARTED) {
258  // double check that stats.possible is sane
259  if (blocks_sig >= threshold - 1) assert(last_stats.possible);
260  }
261 
262  // mine the final block
263  bool signal = (signalling_mask >> (period % 32)) & 1;
264  if (signal) ++blocks_sig;
265  CBlockIndex* current_block = blocks.mine_block(signal);
266  assert(checker.Condition(current_block) == signal);
267 
268  // GetStateStatistics is safe on a period boundary
269  // and has progressed to a new period
270  const BIP9Stats stats = checker.GetStateStatisticsFor(current_block);
271  assert(stats.period == period);
272  assert(stats.threshold == threshold);
273  assert(stats.elapsed == 0);
274  assert(stats.count == 0);
275  assert(stats.possible == true);
276 
277  // More interesting is whether the state changed.
278  const ThresholdState state = checker.GetStateFor(current_block);
279  const int since = checker.GetStateSinceHeightFor(current_block);
280 
281  // since is straightforward:
282  assert(since % period == 0);
283  assert(0 <= since && since <= current_block->nHeight + 1);
284  if (state == exp_state) {
285  assert(since == exp_since);
286  } else {
287  assert(since == current_block->nHeight + 1);
288  }
289 
290  // state is where everything interesting is
291  switch (state) {
293  assert(since == 0);
294  assert(exp_state == ThresholdState::DEFINED);
295  assert(current_block->GetMedianTimePast() < checker.m_begin);
296  break;
298  assert(current_block->GetMedianTimePast() >= checker.m_begin);
299  if (exp_state == ThresholdState::STARTED) {
300  assert(blocks_sig < threshold);
301  assert(current_block->GetMedianTimePast() < checker.m_end);
302  } else {
303  assert(exp_state == ThresholdState::DEFINED);
304  }
305  break;
307  if (exp_state == ThresholdState::LOCKED_IN) {
308  assert(current_block->nHeight + 1 < min_activation);
309  } else {
310  assert(exp_state == ThresholdState::STARTED);
311  assert(blocks_sig >= threshold);
312  }
313  break;
315  assert(always_active_test || min_activation <= current_block->nHeight + 1);
316  assert(exp_state == ThresholdState::ACTIVE || exp_state == ThresholdState::LOCKED_IN);
317  break;
319  assert(never_active_test || current_block->GetMedianTimePast() >= checker.m_end);
320  if (exp_state == ThresholdState::STARTED) {
321  assert(blocks_sig < threshold);
322  } else {
323  assert(exp_state == ThresholdState::FAILED);
324  }
325  break;
326  default:
327  assert(false);
328  }
329 
330  if (blocks.size() >= period * max_periods) {
331  // we chose the timeout (and block times) so that by the time we have this many blocks it's all over
333  }
334 
335  if (always_active_test) {
336  // "always active" has additional restrictions
337  assert(state == ThresholdState::ACTIVE);
338  assert(exp_state == ThresholdState::ACTIVE);
339  assert(since == 0);
340  } else if (never_active_test) {
341  // "never active" does too
342  assert(state == ThresholdState::FAILED);
343  assert(exp_state == ThresholdState::FAILED);
344  assert(since == 0);
345  } else {
346  // for signalled deployments, the initial state is always DEFINED
347  assert(since > 0 || state == ThresholdState::DEFINED);
348  assert(exp_since > 0 || exp_state == ThresholdState::DEFINED);
349  }
350 }
351 } // namespace
ThresholdState::STARTED
@ STARTED
block.h
TestConditionChecker
Definition: versionbits_tests.cpp:32
VERSIONBITS_TOP_MASK
static const int32_t VERSIONBITS_TOP_MASK
What bitmask determines whether versionbits is in use.
Definition: versionbits.h:18
TestConditionChecker::GetStateSinceHeightFor
int GetStateSinceHeightFor(const CBlockIndex *pindexPrev) const
Definition: versionbits_tests.cpp:45
ThresholdState::ACTIVE
@ ACTIVE
assert
assert(!tx.IsCoinBase())
TestConditionChecker::Condition
bool Condition(const CBlockIndex *pindex, const Consensus::Params &params) const override
Definition: versionbits_tests.cpp:42
CBlockHeader::nBits
uint32_t nBits
Definition: block.h:28
nHeight
unsigned int nHeight
Definition: mempool_eviction.cpp:14
CBlockHeader
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:20
TestConditionChecker::Threshold
int Threshold(const Consensus::Params &params) const override
Definition: versionbits_tests.cpp:41
CBlockHeader::nVersion
int32_t nVersion
Definition: block.h:24
TestConditionChecker::GetStateFor
ThresholdState GetStateFor(const CBlockIndex *pindexPrev) const
Definition: versionbits_tests.cpp:44
CBlockIndex::nHeight
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: chain.h:150
util.h
CChainParams
CChainParams defines various tweakable parameters of a given instance of the Bitcoin system.
Definition: chainparams.h:69
Consensus::BIP9Deployment::NO_TIMEOUT
static constexpr int64_t NO_TIMEOUT
Constant for nTimeout very far in the future.
Definition: params.h:53
AbstractThresholdConditionChecker::GetStateFor
ThresholdState GetStateFor(const CBlockIndex *pindexPrev, const Consensus::Params &params, ThresholdConditionCache &cache) const
Returns the state for pindex A based on parent pindexPrev B.
Definition: versionbits.cpp:8
CChainParams::GetConsensus
const Consensus::Params & GetConsensus() const
Definition: chainparams.h:82
VERSIONBITS_TOP_BITS
static const int32_t VERSIONBITS_TOP_BITS
What bits to set in version for versionbits blocks.
Definition: versionbits.h:16
chainparams.h
ThresholdConditionCache
std::map< const CBlockIndex *, ThresholdState > ThresholdConditionCache
Definition: versionbits.h:38
TestConditionChecker::Period
int Period(const Consensus::Params &params) const override
Definition: versionbits_tests.cpp:40
Consensus::Params::nPowTargetSpacing
int64_t nPowTargetSpacing
Definition: params.h:103
Consensus::Params
Parameters that influence chain consensus.
Definition: params.h:70
initialize
void initialize()
Definition: fuzz.cpp:36
AbstractThresholdConditionChecker::GetStateSinceHeightFor
int GetStateSinceHeightFor(const CBlockIndex *pindexPrev, const Consensus::Params &params, ThresholdConditionCache &cache) const
Returns the height since when the ThresholdState has started for pindex A based on parent pindexPrev ...
Definition: versionbits.cpp:130
CBlockIndex::GetMedianTimePast
int64_t GetMedianTimePast() const
Definition: chain.h:272
CBlockIndex::nVersion
int32_t nVersion
block header
Definition: chain.h:190
ThresholdState::DEFINED
@ DEFINED
BIP9Stats::count
int count
Number of blocks with the version bit set since the beginning of the current period.
Definition: versionbits.h:49
FuzzedDataProvider.h
Consensus::BIP9Deployment::NEVER_ACTIVE
static constexpr int64_t NEVER_ACTIVE
Special value for nStartTime indicating that the deployment is never active.
Definition: params.h:64
versionbits.h
CBlockHeader::nTime
uint32_t nTime
Definition: block.h:27
BIP9Stats::threshold
int threshold
Number of blocks with the version bit set required to activate the softfork.
Definition: versionbits.h:45
CChainParams::GenesisBlock
const CBlock & GenesisBlock() const
Definition: chainparams.h:95
AbstractThresholdConditionChecker
Abstract class that implements BIP9-style threshold logic, and caches results.
Definition: versionbits.h:57
TestConditionChecker::BeginTime
int64_t BeginTime(const Consensus::Params &params) const override
Definition: versionbits_tests.cpp:38
ThresholdState::FAILED
@ FAILED
AbstractThresholdConditionChecker::MinActivationHeight
virtual int MinActivationHeight(const Consensus::Params &params) const
Definition: versionbits.h:62
CBaseChainParams::MAIN
static const std::string MAIN
Chain name strings.
Definition: chainparamsbase.h:22
AbstractThresholdConditionChecker::GetStateStatisticsFor
BIP9Stats GetStateStatisticsFor(const CBlockIndex *pindex, const Consensus::Params &params) const
Returns the numerical statistics of an in-progress BIP9 softfork in the current period.
Definition: versionbits.cpp:101
BIP9Stats
Display status of an in-progress BIP9 softfork.
Definition: versionbits.h:41
system.h
VERSIONBITS_NUM_BITS
static const int32_t VERSIONBITS_NUM_BITS
Total bits available for versionbits.
Definition: versionbits.h:20
BIP9Stats::elapsed
int elapsed
Number of blocks elapsed since the beginning of the current period.
Definition: versionbits.h:47
ArgsManager
Definition: system.h:158
fuzz.h
FuzzedDataProvider
Definition: FuzzedDataProvider.h:31
TestConditionChecker::EndTime
int64_t EndTime(const Consensus::Params &params) const override
Definition: versionbits_tests.cpp:39
params.h
ThresholdState::LOCKED_IN
@ LOCKED_IN
BIP9Stats::possible
bool possible
False if there are not enough blocks left in this period to pass activation threshold.
Definition: versionbits.h:51
VERSIONBITS_LAST_OLD_BLOCK_VERSION
static const int32_t VERSIONBITS_LAST_OLD_BLOCK_VERSION
What block version to use for new blocks (pre versionbits)
Definition: versionbits.h:14
FUZZ_TARGET_INIT
#define FUZZ_TARGET_INIT(name, init_fun)
Definition: fuzz.h:34
BIP9Stats::period
int period
Length of blocks of the BIP9 signalling period.
Definition: versionbits.h:43
ThresholdState
ThresholdState
BIP 9 defines a finite-state-machine to deploy a softfork in multiple stages.
Definition: versionbits.h:27
CBlockIndex
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: chain.h:137
CreateChainParams
std::unique_ptr< const CChainParams > CreateChainParams(const ArgsManager &args, const std::string &chain)
Creates and returns a std::unique_ptr<CChainParams> of the chosen chain.
Definition: chainparams.cpp:541
Consensus::BIP9Deployment::ALWAYS_ACTIVE
static constexpr int64_t ALWAYS_ACTIVE
Special value for nStartTime indicating that the deployment is always active.
Definition: params.h:59