coins_view.cpp raw
1 // Copyright (c) 2020-present 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 <coins.h>
6 #include <consensus/amount.h>
7 #include <consensus/tx_check.h>
8 #include <consensus/tx_verify.h>
9 #include <consensus/validation.h>
10 #include <kernel/chainstatemanager_opts.h>
11 #include <kernel/cs_main.h>
12 #include <policy/policy.h>
13 #include <primitives/block.h>
14 #include <primitives/transaction.h>
15 #include <script/interpreter.h>
16 #include <test/fuzz/FuzzedDataProvider.h>
17 #include <test/fuzz/fuzz.h>
18 #include <test/fuzz/util.h>
19 #include <test/util/setup_common.h>
20 #include <txdb.h>
21 #include <util/hasher.h>
22 #include <util/threadpool.h>
23
24 #include <cassert>
25 #include <algorithm>
26 #include <cstdint>
27 #include <functional>
28 #include <limits>
29 #include <memory>
30 #include <optional>
31 #include <ranges>
32 #include <stdexcept>
33 #include <string>
34 #include <utility>
35 #include <vector>
36
37 namespace {
38 const Coin EMPTY_COIN{};
39
40 bool operator==(const Coin& a, const Coin& b)
41 {
42 if (a.IsSpent() && b.IsSpent()) return true;
43 return a.fCoinBase == b.fCoinBase && a.nHeight == b.nHeight && a.out == b.out;
44 }
45
46 /**
47 * MutationGuardCoinsViewCache asserts that nothing mutates cacheCoins until
48 * BatchWrite is called. It keeps a snapshot of the cacheCoins state, which it
49 * uses for the assertion in BatchWrite. After the call to the superclass
50 * CCoinsViewCache::BatchWrite returns, it recomputes the snapshot at that
51 * moment.
52 */
53 class MutationGuardCoinsViewCache final : public CCoinsViewCache
54 {
55 private:
56 struct CacheCoinSnapshot {
57 COutPoint outpoint;
58 bool dirty{false};
59 bool fresh{false};
60 Coin coin;
61 bool operator==(const CacheCoinSnapshot&) const = default;
62 };
63
64 std::vector<CacheCoinSnapshot> ComputeCacheCoinsSnapshot() const
65 {
66 std::vector<CacheCoinSnapshot> snapshot;
67 snapshot.reserve(cacheCoins.size());
68
69 for (const auto& [outpoint, entry] : cacheCoins) {
70 snapshot.emplace_back(outpoint, entry.IsDirty(), entry.IsFresh(), entry.coin);
71 }
72
73 std::ranges::sort(snapshot, std::less<>{}, &CacheCoinSnapshot::outpoint);
74 return snapshot;
75 }
76
77 mutable std::vector<CacheCoinSnapshot> m_expected_snapshot{ComputeCacheCoinsSnapshot()};
78
79 public:
80 void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override
81 {
82 // Nothing must modify cacheCoins other than BatchWrite.
83 assert(ComputeCacheCoinsSnapshot() == m_expected_snapshot);
84 CCoinsViewCache::BatchWrite(cursor, block_hash);
85 m_expected_snapshot = ComputeCacheCoinsSnapshot();
86 }
87
88 using CCoinsViewCache::CCoinsViewCache;
89 };
90
91 // Reuse a single global thread pool across fuzz iterations. Creating and destroying a pool every
92 // iteration leaks memory, since iterations can run faster than the OS can tear down the threads.
93 std::shared_ptr<ThreadPool> g_thread_pool{std::make_shared<ThreadPool>("view_fuzz")};
94 Mutex g_thread_pool_mutex;
95
96 void StartPoolIfNeeded() EXCLUSIVE_LOCKS_REQUIRED(!g_thread_pool_mutex)
97 {
98 LOCK(g_thread_pool_mutex);
99 if (!g_thread_pool->WorkersCount()) g_thread_pool->Start(DEFAULT_PREVOUTFETCH_THREADS);
100 }
101
102 //! Build a random block and seed a view with utxos for its inputs.
103 CBlock BuildRandomBlock(FuzzedDataProvider& fuzzed_data_provider, CCoinsView& view)
104 {
105 CBlock block;
106 CMutableTransaction coinbase;
107 coinbase.vin.emplace_back();
108 block.vtx.push_back(MakeTransactionRef(coinbase));
109
110 CCoinsViewCache seed_cache{&view, /*deterministic=*/true};
111 seed_cache.SetBestBlock(uint256::ONE);
112
113 Txid prevhash{Txid::FromUint256(ConsumeUInt256(fuzzed_data_provider))};
114 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100)
115 {
116 CMutableTransaction tx;
117 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100)
118 {
119 const Txid txid{fuzzed_data_provider.ConsumeBool()
120 ? Txid::FromUint256(ConsumeUInt256(fuzzed_data_provider))
121 : prevhash};
122 const COutPoint outpoint{txid, fuzzed_data_provider.ConsumeIntegral<uint32_t>()};
123 if (auto coin{ConsumeDeserializable<Coin>(fuzzed_data_provider)}; coin && !coin->IsSpent()) {
124 seed_cache.AddCoin(outpoint, std::move(*coin), /*possible_overwrite=*/true);
125 }
126 tx.vin.emplace_back(outpoint);
127 }
128 prevhash = tx.GetHash();
129 block.vtx.push_back(MakeTransactionRef(tx));
130 }
131
132 seed_cache.Flush();
133 return block;
134 }
135
136 } // namespace
137
138 void initialize_coins_view()
139 {
140 static const auto testing_setup = MakeNoLogFileContext<>();
141 }
142
143 void TestCoinsView(FuzzedDataProvider& fuzzed_data_provider, CCoinsViewCache& coins_view_cache, CCoinsView* backend_coins_view)
144 {
145 auto* const db{dynamic_cast<CCoinsViewDB*>(backend_coins_view)};
146 auto* const overlay{dynamic_cast<CoinsViewOverlay*>(&coins_view_cache)};
147 const bool is_db{db != nullptr};
148 bool good_data{true};
149 auto* original_backend{backend_coins_view};
150
151 if (is_db) coins_view_cache.SetBestBlock(uint256::ONE);
152 COutPoint random_out_point;
153 Coin random_coin;
154 CMutableTransaction random_mutable_transaction;
155 LIMITED_WHILE(good_data && fuzzed_data_provider.ConsumeBool(), 10'000)
156 {
157 CallOneOf(
158 fuzzed_data_provider,
159 [&] {
160 if (random_coin.IsSpent()) {
161 return;
162 }
163 COutPoint outpoint{random_out_point};
164 Coin coin{random_coin};
165 if (fuzzed_data_provider.ConsumeBool()) {
166 // We can only skip the check if no unspent coin exists for this outpoint.
167 const bool possible_overwrite{coins_view_cache.PeekCoin(outpoint) || fuzzed_data_provider.ConsumeBool()};
168 coins_view_cache.AddCoin(outpoint, std::move(coin), possible_overwrite);
169 } else {
170 coins_view_cache.EmplaceCoinInternalDANGER(std::move(outpoint), std::move(coin));
171 }
172 },
173 [&] {
174 if (overlay && !overlay->AllInputsConsumed()) return; // CoinsViewOverlay::Flush() must have all inputs consumed before being called
175 coins_view_cache.Flush(/*reallocate_cache=*/fuzzed_data_provider.ConsumeBool());
176 },
177 [&] {
178 if (overlay) return; // CoinsViewOverlay::Sync() is never called in production code
179 coins_view_cache.Sync();
180 },
181 [&] {
182 if (db) WITH_LOCK(::cs_main, (void)db->CompactFullAsync());
183 },
184 [&] {
185 uint256 best_block{ConsumeUInt256(fuzzed_data_provider)};
186 // `CCoinsViewDB::BatchWrite()` requires a non-null best block.
187 if (is_db && best_block.IsNull()) best_block = uint256::ONE;
188 coins_view_cache.SetBestBlock(best_block);
189 },
190 [&] {
191 (void)coins_view_cache.CreateResetGuard();
192 // Reset() clears the best block, so reseed db-backed caches.
193 if (is_db) {
194 const uint256 best_block{ConsumeUInt256(fuzzed_data_provider)};
195 if (best_block.IsNull()) {
196 good_data = false;
197 return;
198 }
199 coins_view_cache.SetBestBlock(best_block);
200 }
201 },
202 [&] {
203 Coin move_to;
204 (void)coins_view_cache.SpendCoin(random_out_point, fuzzed_data_provider.ConsumeBool() ? &move_to : nullptr);
205 },
206 [&] {
207 coins_view_cache.Uncache(random_out_point);
208 },
209 [&] {
210 if (overlay) return; // // CoinsViewOverlay::SetBackend() is never called in production code
211 const bool use_original_backend{fuzzed_data_provider.ConsumeBool()};
212 if (use_original_backend && backend_coins_view != original_backend) {
213 // FRESH flags valid against the empty backend may be invalid
214 // against the original backend, so reset before restoring it.
215 (void)coins_view_cache.CreateResetGuard();
216 // Reset() clears the best block; db backends require a non-null hash.
217 if (is_db) coins_view_cache.SetBestBlock(uint256::ONE);
218 }
219 backend_coins_view = use_original_backend ? original_backend : &CoinsViewEmpty::Get();
220 coins_view_cache.SetBackend(*backend_coins_view);
221 },
222 [&] {
223 const std::optional<COutPoint> opt_out_point = ConsumeDeserializable<COutPoint>(fuzzed_data_provider);
224 if (!opt_out_point) {
225 good_data = false;
226 return;
227 }
228 random_out_point = *opt_out_point;
229 },
230 [&] {
231 const std::optional<Coin> opt_coin = ConsumeDeserializable<Coin>(fuzzed_data_provider);
232 if (!opt_coin) {
233 good_data = false;
234 return;
235 }
236 random_coin = *opt_coin;
237 },
238 [&] {
239 const std::optional<CMutableTransaction> opt_mutable_transaction = ConsumeDeserializable<CMutableTransaction>(fuzzed_data_provider, TX_WITH_WITNESS);
240 if (!opt_mutable_transaction) {
241 good_data = false;
242 return;
243 }
244 random_mutable_transaction = *opt_mutable_transaction;
245 },
246 [&] {
247 CoinsCachePair sentinel{};
248 sentinel.second.SelfRef(sentinel);
249 size_t dirty_count{0};
250 CCoinsMapMemoryResource resource;
251 CCoinsMap coins_map{0, SaltedOutpointHasher{/*deterministic=*/true}, CCoinsMap::key_equal{}, &resource};
252 LIMITED_WHILE(good_data && fuzzed_data_provider.ConsumeBool(), 10'000)
253 {
254 CCoinsCacheEntry coins_cache_entry;
255 if (fuzzed_data_provider.ConsumeBool()) {
256 coins_cache_entry.coin = random_coin;
257 } else {
258 const std::optional<Coin> opt_coin = ConsumeDeserializable<Coin>(fuzzed_data_provider);
259 if (!opt_coin) {
260 good_data = false;
261 return;
262 }
263 coins_cache_entry.coin = *opt_coin;
264 }
265 // Avoid setting FRESH for an outpoint that already exists unspent in the parent view.
266 bool fresh{!coins_view_cache.PeekCoin(random_out_point) && fuzzed_data_provider.ConsumeBool()};
267 bool dirty{fresh || fuzzed_data_provider.ConsumeBool()};
268 auto it{coins_map.emplace(random_out_point, std::move(coins_cache_entry)).first};
269 if (dirty) CCoinsCacheEntry::SetDirty(*it, sentinel);
270 if (fresh) CCoinsCacheEntry::SetFresh(*it, sentinel);
271 dirty_count += dirty;
272 }
273 auto cursor{CoinsViewCacheCursor(dirty_count, sentinel, coins_map, /*will_erase=*/true)};
274 uint256 best_block{coins_view_cache.GetBestBlock()};
275 if (fuzzed_data_provider.ConsumeBool()) best_block = ConsumeUInt256(fuzzed_data_provider);
276 // Set best block hash to non-null to satisfy the assertion in CCoinsViewDB::BatchWrite().
277 if (is_db && best_block.IsNull()) best_block = uint256::ONE;
278 coins_view_cache.BatchWrite(cursor, best_block);
279 });
280 }
281
282 {
283 bool expected_code_path = false;
284 try {
285 (void)coins_view_cache.Cursor();
286 } catch (const std::logic_error&) {
287 expected_code_path = true;
288 }
289 assert(expected_code_path);
290 (void)coins_view_cache.DynamicMemoryUsage();
291 (void)coins_view_cache.EstimateSize();
292 (void)coins_view_cache.GetBestBlock();
293 (void)coins_view_cache.GetCacheSize();
294 (void)coins_view_cache.GetHeadBlocks();
295 (void)coins_view_cache.HaveInputs(CTransaction{random_mutable_transaction});
296 }
297
298 {
299 if (is_db && backend_coins_view == original_backend) {
300 assert(backend_coins_view->Cursor());
301 }
302 (void)backend_coins_view->EstimateSize();
303 (void)backend_coins_view->GetBestBlock();
304 (void)backend_coins_view->GetHeadBlocks();
305 }
306
307 if (fuzzed_data_provider.ConsumeBool()) {
308 CallOneOf(
309 fuzzed_data_provider,
310 [&] {
311 const CTransaction transaction{random_mutable_transaction};
312 bool is_spent = false;
313 for (const CTxOut& tx_out : transaction.vout) {
314 if (Coin{tx_out, 0, transaction.IsCoinBase()}.IsSpent()) {
315 is_spent = true;
316 }
317 }
318 if (is_spent) {
319 // Avoid:
320 // coins.cpp:69: void CCoinsViewCache::AddCoin(const COutPoint &, Coin &&, bool): Assertion `!coin.IsSpent()' failed.
321 return;
322 }
323 const int height{int(fuzzed_data_provider.ConsumeIntegral<uint32_t>() >> 1)};
324 const bool check_for_overwrite{transaction.IsCoinBase() || [&] {
325 for (uint32_t i{0}; i < transaction.vout.size(); ++i) {
326 if (coins_view_cache.PeekCoin(COutPoint{transaction.GetHash(), i})) return true;
327 }
328 return fuzzed_data_provider.ConsumeBool();
329 }()}; // We can only skip the check if the current txid has no unspent outputs
330 AddCoins(coins_view_cache, transaction, height, check_for_overwrite);
331 },
332 [&] {
333 (void)ValidateInputsStandardness(CTransaction{random_mutable_transaction}, coins_view_cache);
334 },
335 [&] {
336 TxValidationState state;
337 CAmount tx_fee_out;
338 const CTransaction transaction{random_mutable_transaction};
339 if (ContainsSpentInput(transaction, coins_view_cache)) {
340 // Avoid:
341 // consensus/tx_verify.cpp:171: bool Consensus::CheckTxInputs(const CTransaction &, TxValidationState &, const CCoinsViewCache &, int, CAmount &): Assertion `!coin.IsSpent()' failed.
342 return;
343 }
344 TxValidationState dummy;
345 if (!CheckTransaction(transaction, dummy)) {
346 // It is not allowed to call CheckTxInputs if CheckTransaction failed
347 return;
348 }
349 if (Consensus::CheckTxInputs(transaction, state, coins_view_cache, fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max()), tx_fee_out)) {
350 assert(MoneyRange(tx_fee_out));
351 }
352 },
353 [&] {
354 const CTransaction transaction{random_mutable_transaction};
355 if (ContainsSpentInput(transaction, coins_view_cache)) {
356 // Avoid:
357 // consensus/tx_verify.cpp:130: unsigned int GetP2SHSigOpCount(const CTransaction &, const CCoinsViewCache &): Assertion `!coin.IsSpent()' failed.
358 return;
359 }
360 (void)GetP2SHSigOpCount(transaction, coins_view_cache);
361 },
362 [&] {
363 const CTransaction transaction{random_mutable_transaction};
364 if (ContainsSpentInput(transaction, coins_view_cache)) {
365 // Avoid:
366 // consensus/tx_verify.cpp:130: unsigned int GetP2SHSigOpCount(const CTransaction &, const CCoinsViewCache &): Assertion `!coin.IsSpent()' failed.
367 return;
368 }
369 const auto flags = script_verify_flags::from_int(fuzzed_data_provider.ConsumeIntegral<script_verify_flags::value_type>());
370 if (!transaction.vin.empty() && (flags & SCRIPT_VERIFY_WITNESS) != 0 && (flags & SCRIPT_VERIFY_P2SH) == 0) {
371 // Avoid:
372 // script/interpreter.cpp:1705: size_t CountWitnessSigOps(const CScript &, const CScript &, const CScriptWitness &, unsigned int): Assertion `(flags & SCRIPT_VERIFY_P2SH) != 0' failed.
373 return;
374 }
375 (void)GetTransactionSigOpCost(transaction, coins_view_cache, flags);
376 },
377 [&] {
378 (void)IsWitnessStandard(CTransaction{random_mutable_transaction}, coins_view_cache);
379 });
380 }
381
382 {
383 const Coin& coin_using_access_coin = coins_view_cache.AccessCoin(random_out_point);
384 const bool exists_using_access_coin = !(coin_using_access_coin == EMPTY_COIN);
385 const bool exists_using_have_coin = coins_view_cache.HaveCoin(random_out_point);
386 const bool exists_using_have_coin_in_cache = coins_view_cache.HaveCoinInCache(random_out_point);
387 if (auto coin{coins_view_cache.GetCoin(random_out_point)}) {
388 assert(*coin == coin_using_access_coin);
389 assert(exists_using_access_coin && exists_using_have_coin_in_cache && exists_using_have_coin);
390 } else {
391 assert(!exists_using_access_coin && !exists_using_have_coin_in_cache && !exists_using_have_coin);
392 }
393 // If HaveCoin on the backend is true, it must also be on the cache if the coin wasn't spent.
394 std::optional<Coin> coin_in_backend;
395 bool exists_using_have_coin_in_backend;
396 if (dynamic_cast<CoinsViewOverlay*>(&coins_view_cache)) {
397 // PeekCoin does not mutate cacheCoins, so async workers can keep running.
398 coin_in_backend = backend_coins_view->PeekCoin(random_out_point);
399 exists_using_have_coin_in_backend = coin_in_backend.has_value();
400 } else {
401 exists_using_have_coin_in_backend = backend_coins_view->HaveCoin(random_out_point);
402 coin_in_backend = backend_coins_view->GetCoin(random_out_point);
403 }
404 if (!coin_using_access_coin.IsSpent() && exists_using_have_coin_in_backend) {
405 assert(exists_using_have_coin);
406 }
407 if (coin_in_backend) {
408 assert(exists_using_have_coin_in_backend);
409 // Note we can't assert that `coin_using_get_coin == *coin` because the coin in
410 // the cache may have been modified but not yet flushed.
411 } else {
412 assert(!exists_using_have_coin_in_backend);
413 }
414 }
415 }
416
417 FUZZ_TARGET(coins_view, .init = initialize_coins_view)
418 {
419 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
420 CCoinsViewCache coins_view_cache{&CoinsViewEmpty::Get(), /*deterministic=*/true};
421 TestCoinsView(fuzzed_data_provider, coins_view_cache, &CoinsViewEmpty::Get());
422 }
423
424 FUZZ_TARGET(coins_view_db, .init = initialize_coins_view)
425 {
426 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
427 auto db_params = DBParams{
428 .path = "",
429 .cache_bytes = 1_MiB,
430 .memory_only = true,
431 };
432 CCoinsViewDB backend_coins_view{std::move(db_params), CoinsViewOptions{}};
433 CCoinsViewCache coins_view_cache{&backend_coins_view, /*deterministic=*/true};
434 TestCoinsView(fuzzed_data_provider, coins_view_cache, &backend_coins_view);
435 }
436
437 // Creates a CoinsViewOverlay and a MutationGuardCoinsViewCache as the base.
438 // This allows us to exercise all methods on a CoinsViewOverlay, while also
439 // ensuring that nothing can mutate the underlying cache until Flush or Sync is
440 // called.
441 FUZZ_TARGET(coins_view_overlay, .init = initialize_coins_view) EXCLUSIVE_LOCKS_REQUIRED(!g_thread_pool_mutex)
442 {
443 SeedRandomStateForTest(SeedRand::ZEROS); // for SaltedTxidHasher
444 StartPoolIfNeeded();
445 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
446 MutationGuardCoinsViewCache backend_cache{&CoinsViewEmpty::Get(), /*deterministic=*/true};
447 CoinsViewOverlay coins_view_cache{&backend_cache, g_thread_pool, /*deterministic=*/true};
448 CBlock block{BuildRandomBlock(fuzzed_data_provider, backend_cache)};
449 const auto reset_guard{coins_view_cache.StartFetching(block)};
450 TestCoinsView(fuzzed_data_provider, coins_view_cache, &backend_cache);
451 }
452
453 FUZZ_TARGET(coins_view_stacked, .init = initialize_coins_view) EXCLUSIVE_LOCKS_REQUIRED(!g_thread_pool_mutex)
454 {
455 SeedRandomStateForTest(SeedRand::ZEROS); // for SaltedTxidHasher
456 StartPoolIfNeeded();
457 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
458 auto db_params = DBParams{
459 .path = "",
460 .cache_bytes = 1_MiB,
461 .memory_only = true,
462 };
463 CCoinsViewDB backend_base_coins_view{std::move(db_params), CoinsViewOptions{}};
464 CCoinsViewCache backend_cache{&backend_base_coins_view, /*deterministic=*/true};
465 TestCoinsView(fuzzed_data_provider, backend_cache, &backend_base_coins_view);
466 CoinsViewOverlay coins_view_cache{&backend_cache, g_thread_pool, /*deterministic=*/true};
467 CBlock block{BuildRandomBlock(fuzzed_data_provider, backend_base_coins_view)};
468 {
469 const auto reset_guard{coins_view_cache.StartFetching(block)};
470 TestCoinsView(fuzzed_data_provider, coins_view_cache, &backend_cache);
471 }
472 TestCoinsView(fuzzed_data_provider, backend_cache, &backend_base_coins_view);
473 }
474