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