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* pindex, std::vector<bool>* signals=nullptr) const { return AbstractThresholdConditionChecker::GetStateStatisticsFor(pindex, dummy_params, signals); }
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) { // early exit; no need for LIMITED_WHILE
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 
224  // get statistics from end of previous period, then reset
225  BIP9Stats last_stats;
226  last_stats.period = period;
227  last_stats.threshold = threshold;
228  last_stats.count = last_stats.elapsed = 0;
229  last_stats.possible = (period >= threshold);
230  std::vector<bool> last_signals{};
231 
232  int prev_next_height = (prev == nullptr ? 0 : prev->nHeight + 1);
233  assert(exp_since <= prev_next_height);
234 
235  // mine (period-1) blocks and check state
236  for (int b = 1; b < period; ++b) {
237  const bool signal = (signalling_mask >> (b % 32)) & 1;
238  if (signal) ++blocks_sig;
239 
240  CBlockIndex* current_block = blocks.mine_block(signal);
241 
242  // verify that signalling attempt was interpreted correctly
243  assert(checker.Condition(current_block) == signal);
244 
245  // state and since don't change within the period
246  const ThresholdState state = checker.GetStateFor(current_block);
247  const int since = checker.GetStateSinceHeightFor(current_block);
248  assert(state == exp_state);
249  assert(since == exp_since);
250 
251  // check that after mining this block stats change as expected
252  std::vector<bool> signals;
253  const BIP9Stats stats = checker.GetStateStatisticsFor(current_block, &signals);
254  const BIP9Stats stats_no_signals = checker.GetStateStatisticsFor(current_block);
255  assert(stats.period == stats_no_signals.period && stats.threshold == stats_no_signals.threshold
256  && stats.elapsed == stats_no_signals.elapsed && stats.count == stats_no_signals.count
257  && stats.possible == stats_no_signals.possible);
258 
259  assert(stats.period == period);
260  assert(stats.threshold == threshold);
261  assert(stats.elapsed == b);
262  assert(stats.count == last_stats.count + (signal ? 1 : 0));
263  assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
264  last_stats = stats;
265 
266  assert(signals.size() == last_signals.size() + 1);
267  assert(signals.back() == signal);
268  last_signals.push_back(signal);
269  assert(signals == last_signals);
270  }
271 
272  if (exp_state == ThresholdState::STARTED) {
273  // double check that stats.possible is sane
274  if (blocks_sig >= threshold - 1) assert(last_stats.possible);
275  }
276 
277  // mine the final block
278  bool signal = (signalling_mask >> (period % 32)) & 1;
279  if (signal) ++blocks_sig;
280  CBlockIndex* current_block = blocks.mine_block(signal);
281  assert(checker.Condition(current_block) == signal);
282 
283  const BIP9Stats stats = checker.GetStateStatisticsFor(current_block);
284  assert(stats.period == period);
285  assert(stats.threshold == threshold);
286  assert(stats.elapsed == period);
287  assert(stats.count == blocks_sig);
288  assert(stats.possible == (stats.count + period >= stats.elapsed + threshold));
289 
290  // More interesting is whether the state changed.
291  const ThresholdState state = checker.GetStateFor(current_block);
292  const int since = checker.GetStateSinceHeightFor(current_block);
293 
294  // since is straightforward:
295  assert(since % period == 0);
296  assert(0 <= since && since <= current_block->nHeight + 1);
297  if (state == exp_state) {
298  assert(since == exp_since);
299  } else {
300  assert(since == current_block->nHeight + 1);
301  }
302 
303  // state is where everything interesting is
304  switch (state) {
306  assert(since == 0);
307  assert(exp_state == ThresholdState::DEFINED);
308  assert(current_block->GetMedianTimePast() < checker.m_begin);
309  break;
311  assert(current_block->GetMedianTimePast() >= checker.m_begin);
312  if (exp_state == ThresholdState::STARTED) {
313  assert(blocks_sig < threshold);
314  assert(current_block->GetMedianTimePast() < checker.m_end);
315  } else {
316  assert(exp_state == ThresholdState::DEFINED);
317  }
318  break;
320  if (exp_state == ThresholdState::LOCKED_IN) {
321  assert(current_block->nHeight + 1 < min_activation);
322  } else {
323  assert(exp_state == ThresholdState::STARTED);
324  assert(blocks_sig >= threshold);
325  }
326  break;
328  assert(always_active_test || min_activation <= current_block->nHeight + 1);
329  assert(exp_state == ThresholdState::ACTIVE || exp_state == ThresholdState::LOCKED_IN);
330  break;
332  assert(never_active_test || current_block->GetMedianTimePast() >= checker.m_end);
333  if (exp_state == ThresholdState::STARTED) {
334  assert(blocks_sig < threshold);
335  } else {
336  assert(exp_state == ThresholdState::FAILED);
337  }
338  break;
339  default:
340  assert(false);
341  }
342 
343  if (blocks.size() >= period * max_periods) {
344  // we chose the timeout (and block times) so that by the time we have this many blocks it's all over
346  }
347 
348  if (always_active_test) {
349  // "always active" has additional restrictions
350  assert(state == ThresholdState::ACTIVE);
351  assert(exp_state == ThresholdState::ACTIVE);
352  assert(since == 0);
353  } else if (never_active_test) {
354  // "never active" does too
355  assert(state == ThresholdState::FAILED);
356  assert(exp_state == ThresholdState::FAILED);
357  assert(since == 0);
358  } else {
359  // for signalled deployments, the initial state is always DEFINED
360  assert(since > 0 || state == ThresholdState::DEFINED);
361  assert(exp_since > 0 || exp_state == ThresholdState::DEFINED);
362  }
363 }
364 } // 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:164
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
AbstractThresholdConditionChecker::GetStateStatisticsFor
BIP9Stats GetStateStatisticsFor(const CBlockIndex *pindex, const Consensus::Params &params, std::vector< bool > *signalling_blocks=nullptr) const
Returns the numerical statistics of an in-progress BIP9 softfork in the period including pindex If pr...
Definition: versionbits.cpp:101
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:64
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:139
CBlockIndex::GetMedianTimePast
int64_t GetMedianTimePast() const
Definition: chain.h:290
CBlockIndex::nVersion
int32_t nVersion
block header
Definition: chain.h:204
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
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:164
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:151
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:566
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