Bitcoin Core  25.99.0
P2P Digital Currency
coinscache_sim.cpp
Go to the documentation of this file.
1 // Copyright (c) 2023 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 <crypto/sha256.h>
8 #include <test/fuzz/fuzz.h>
10 #include <test/fuzz/util.h>
11 
12 #include <assert.h>
13 #include <optional>
14 #include <memory>
15 #include <stdint.h>
16 #include <vector>
17 
18 namespace {
19 
21 constexpr uint32_t NUM_OUTPOINTS = 256;
23 constexpr uint32_t NUM_COINS = 256;
25 constexpr uint32_t MAX_CACHES = 4;
27 using coinidx_type = uint8_t;
28 
29 struct PrecomputedData
30 {
32  COutPoint outpoints[NUM_OUTPOINTS];
33 
35  Coin coins[NUM_COINS];
36 
37  PrecomputedData()
38  {
39  static const uint8_t PREFIX_O[1] = {'o'};
40  static const uint8_t PREFIX_S[1] = {'s'};
41  static const uint8_t PREFIX_M[1] = {'m'};
43  for (uint32_t i = 0; i < NUM_OUTPOINTS; ++i) {
44  uint32_t idx = (i * 1200U) >> 12; /* Map 3 or 4 entries to same txid. */
45  const uint8_t ser[4] = {uint8_t(idx), uint8_t(idx >> 8), uint8_t(idx >> 16), uint8_t(idx >> 24)};
46  CSHA256().Write(PREFIX_O, 1).Write(ser, sizeof(ser)).Finalize(outpoints[i].hash.begin());
47  outpoints[i].n = i;
48  }
49 
50  for (uint32_t i = 0; i < NUM_COINS; ++i) {
51  const uint8_t ser[4] = {uint8_t(i), uint8_t(i >> 8), uint8_t(i >> 16), uint8_t(i >> 24)};
52  uint256 hash;
53  CSHA256().Write(PREFIX_S, 1).Write(ser, sizeof(ser)).Finalize(hash.begin());
54  /* Convert hash to scriptPubkeys (of different lengths, so SanityCheck's cached memory
55  * usage check has a chance to detect mismatches). */
56  switch (i % 5U) {
57  case 0: /* P2PKH */
58  coins[i].out.scriptPubKey.resize(25);
59  coins[i].out.scriptPubKey[0] = OP_DUP;
60  coins[i].out.scriptPubKey[1] = OP_HASH160;
61  coins[i].out.scriptPubKey[2] = 20;
62  std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 3);
63  coins[i].out.scriptPubKey[23] = OP_EQUALVERIFY;
64  coins[i].out.scriptPubKey[24] = OP_CHECKSIG;
65  break;
66  case 1: /* P2SH */
67  coins[i].out.scriptPubKey.resize(23);
68  coins[i].out.scriptPubKey[0] = OP_HASH160;
69  coins[i].out.scriptPubKey[1] = 20;
70  std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 2);
71  coins[i].out.scriptPubKey[12] = OP_EQUAL;
72  break;
73  case 2: /* P2WPKH */
74  coins[i].out.scriptPubKey.resize(22);
75  coins[i].out.scriptPubKey[0] = OP_0;
76  coins[i].out.scriptPubKey[1] = 20;
77  std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 2);
78  break;
79  case 3: /* P2WSH */
80  coins[i].out.scriptPubKey.resize(34);
81  coins[i].out.scriptPubKey[0] = OP_0;
82  coins[i].out.scriptPubKey[1] = 32;
83  std::copy(hash.begin(), hash.begin() + 32, coins[i].out.scriptPubKey.begin() + 2);
84  break;
85  case 4: /* P2TR */
86  coins[i].out.scriptPubKey.resize(34);
87  coins[i].out.scriptPubKey[0] = OP_1;
88  coins[i].out.scriptPubKey[1] = 32;
89  std::copy(hash.begin(), hash.begin() + 32, coins[i].out.scriptPubKey.begin() + 2);
90  break;
91  }
92  /* Hash again to construct nValue and fCoinBase. */
93  CSHA256().Write(PREFIX_M, 1).Write(ser, sizeof(ser)).Finalize(hash.begin());
94  coins[i].out.nValue = CAmount(hash.GetUint64(0) % MAX_MONEY);
95  coins[i].fCoinBase = (hash.GetUint64(1) & 7) == 0;
96  coins[i].nHeight = 0; /* Real nHeight used in simulation is set dynamically. */
97  }
98  }
99 };
100 
101 enum class EntryType : uint8_t
102 {
103  /* This entry in the cache does not exist (so we'd have to look in the parent cache). */
104  NONE,
105 
106  /* This entry in the cache corresponds to an unspent coin. */
107  UNSPENT,
108 
109  /* This entry in the cache corresponds to a spent coin. */
110  SPENT,
111 };
112 
113 struct CacheEntry
114 {
115  /* Type of entry. */
116  EntryType entrytype;
117 
118  /* Index in the coins array this entry corresponds to (only if entrytype == UNSPENT). */
119  coinidx_type coinidx;
120 
121  /* nHeight value for this entry (so the coins[coinidx].nHeight value is ignored; only if entrytype == UNSPENT). */
122  uint32_t height;
123 };
124 
125 struct CacheLevel
126 {
127  CacheEntry entry[NUM_OUTPOINTS];
128 
129  void Wipe() {
130  for (uint32_t i = 0; i < NUM_OUTPOINTS; ++i) {
131  entry[i].entrytype = EntryType::NONE;
132  }
133  }
134 };
135 
143 class CoinsViewBottom final : public CCoinsView
144 {
145  std::map<COutPoint, Coin> m_data;
146 
147 public:
148  bool GetCoin(const COutPoint& outpoint, Coin& coin) const final
149  {
150  auto it = m_data.find(outpoint);
151  if (it == m_data.end()) {
152  if ((outpoint.n % 5) == 3) {
153  coin.Clear();
154  return true;
155  }
156  return false;
157  } else {
158  coin = it->second;
159  return true;
160  }
161  }
162 
163  bool HaveCoin(const COutPoint& outpoint) const final
164  {
165  return m_data.count(outpoint);
166  }
167 
168  uint256 GetBestBlock() const final { return {}; }
169  std::vector<uint256> GetHeadBlocks() const final { return {}; }
170  std::unique_ptr<CCoinsViewCursor> Cursor() const final { return {}; }
171  size_t EstimateSize() const final { return m_data.size(); }
172 
173  bool BatchWrite(CCoinsMap& data, const uint256&, bool erase) final
174  {
175  for (auto it = data.begin(); it != data.end(); it = erase ? data.erase(it) : std::next(it)) {
176  if (it->second.flags & CCoinsCacheEntry::DIRTY) {
177  if (it->second.coin.IsSpent() && (it->first.n % 5) != 4) {
178  m_data.erase(it->first);
179  } else if (erase) {
180  m_data[it->first] = std::move(it->second.coin);
181  } else {
182  m_data[it->first] = it->second.coin;
183  }
184  } else {
185  /* For non-dirty entries being written, compare them with what we have. */
186  auto it2 = m_data.find(it->first);
187  if (it->second.coin.IsSpent()) {
188  assert(it2 == m_data.end() || it2->second.IsSpent());
189  } else {
190  assert(it2 != m_data.end());
191  assert(it->second.coin.out == it2->second.out);
192  assert(it->second.coin.fCoinBase == it2->second.fCoinBase);
193  assert(it->second.coin.nHeight == it2->second.nHeight);
194  }
195  }
196  }
197  return true;
198  }
199 };
200 
201 } // namespace
202 
203 FUZZ_TARGET(coinscache_sim)
204 {
206  static const PrecomputedData data;
207 
209  CoinsViewBottom bottom;
211  std::vector<std::unique_ptr<CCoinsViewCache>> caches;
213  CacheLevel sim_caches[MAX_CACHES + 1];
215  uint32_t current_height = 1U;
216 
217  // Initialize bottom simulated cache.
218  sim_caches[0].Wipe();
219 
221  auto lookup = [&](uint32_t outpointidx, int sim_idx = -1) -> std::optional<std::pair<coinidx_type, uint32_t>> {
222  uint32_t cache_idx = sim_idx == -1 ? caches.size() : sim_idx;
223  while (true) {
224  const auto& entry = sim_caches[cache_idx].entry[outpointidx];
225  if (entry.entrytype == EntryType::UNSPENT) {
226  return {{entry.coinidx, entry.height}};
227  } else if (entry.entrytype == EntryType::SPENT) {
228  return std::nullopt;
229  };
230  if (cache_idx == 0) break;
231  --cache_idx;
232  }
233  return std::nullopt;
234  };
235 
237  auto flush = [&]() {
238  assert(caches.size() >= 1);
239  auto& cache = sim_caches[caches.size()];
240  auto& prev_cache = sim_caches[caches.size() - 1];
241  for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
242  if (cache.entry[outpointidx].entrytype != EntryType::NONE) {
243  prev_cache.entry[outpointidx] = cache.entry[outpointidx];
244  cache.entry[outpointidx].entrytype = EntryType::NONE;
245  }
246  }
247  };
248 
249  // Main simulation loop: read commands from the fuzzer input, and apply them
250  // to both the real cache stack and the simulation.
251  FuzzedDataProvider provider(buffer.data(), buffer.size());
252  LIMITED_WHILE(provider.remaining_bytes(), 10000) {
253  // Every operation (except "Change height") moves current height forward,
254  // so it functions as a kind of epoch, making ~all UTXOs unique.
255  ++current_height;
256  // Make sure there is always at least one CCoinsViewCache.
257  if (caches.empty()) {
258  caches.emplace_back(new CCoinsViewCache(&bottom, /*deterministic=*/true));
259  sim_caches[caches.size()].Wipe();
260  }
261 
262  // Execute command.
263  CallOneOf(
264  provider,
265 
266  [&]() { // GetCoin
267  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
268  // Look up in simulation data.
269  auto sim = lookup(outpointidx);
270  // Look up in real caches.
271  Coin realcoin;
272  auto real = caches.back()->GetCoin(data.outpoints[outpointidx], realcoin);
273  // Compare results.
274  if (!sim.has_value()) {
275  assert(!real || realcoin.IsSpent());
276  } else {
277  assert(real && !realcoin.IsSpent());
278  const auto& simcoin = data.coins[sim->first];
279  assert(realcoin.out == simcoin.out);
280  assert(realcoin.fCoinBase == simcoin.fCoinBase);
281  assert(realcoin.nHeight == sim->second);
282  }
283  },
284 
285  [&]() { // HaveCoin
286  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
287  // Look up in simulation data.
288  auto sim = lookup(outpointidx);
289  // Look up in real caches.
290  auto real = caches.back()->HaveCoin(data.outpoints[outpointidx]);
291  // Compare results.
292  assert(sim.has_value() == real);
293  },
294 
295  [&]() { // HaveCoinInCache
296  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
297  // Invoke on real cache (there is no equivalent in simulation, so nothing to compare result with).
298  (void)caches.back()->HaveCoinInCache(data.outpoints[outpointidx]);
299  },
300 
301  [&]() { // AccessCoin
302  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
303  // Look up in simulation data.
304  auto sim = lookup(outpointidx);
305  // Look up in real caches.
306  const auto& realcoin = caches.back()->AccessCoin(data.outpoints[outpointidx]);
307  // Compare results.
308  if (!sim.has_value()) {
309  assert(realcoin.IsSpent());
310  } else {
311  assert(!realcoin.IsSpent());
312  const auto& simcoin = data.coins[sim->first];
313  assert(simcoin.out == realcoin.out);
314  assert(simcoin.fCoinBase == realcoin.fCoinBase);
315  assert(realcoin.nHeight == sim->second);
316  }
317  },
318 
319  [&]() { // AddCoin (only possible_overwrite if necessary)
320  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
321  uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
322  // Look up in simulation data (to know whether we must set possible_overwrite or not).
323  auto sim = lookup(outpointidx);
324  // Invoke on real caches.
325  Coin coin = data.coins[coinidx];
326  coin.nHeight = current_height;
327  caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), sim.has_value());
328  // Apply to simulation data.
329  auto& entry = sim_caches[caches.size()].entry[outpointidx];
330  entry.entrytype = EntryType::UNSPENT;
331  entry.coinidx = coinidx;
332  entry.height = current_height;
333  },
334 
335  [&]() { // AddCoin (always possible_overwrite)
336  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
337  uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
338  // Invoke on real caches.
339  Coin coin = data.coins[coinidx];
340  coin.nHeight = current_height;
341  caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), true);
342  // Apply to simulation data.
343  auto& entry = sim_caches[caches.size()].entry[outpointidx];
344  entry.entrytype = EntryType::UNSPENT;
345  entry.coinidx = coinidx;
346  entry.height = current_height;
347  },
348 
349  [&]() { // SpendCoin (moveto = nullptr)
350  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
351  // Invoke on real caches.
352  caches.back()->SpendCoin(data.outpoints[outpointidx], nullptr);
353  // Apply to simulation data.
354  sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
355  },
356 
357  [&]() { // SpendCoin (with moveto)
358  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
359  // Look up in simulation data (to compare the returned *moveto with).
360  auto sim = lookup(outpointidx);
361  // Invoke on real caches.
362  Coin realcoin;
363  caches.back()->SpendCoin(data.outpoints[outpointidx], &realcoin);
364  // Apply to simulation data.
365  sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
366  // Compare *moveto with the value expected based on simulation data.
367  if (!sim.has_value()) {
368  assert(realcoin.IsSpent());
369  } else {
370  assert(!realcoin.IsSpent());
371  const auto& simcoin = data.coins[sim->first];
372  assert(simcoin.out == realcoin.out);
373  assert(simcoin.fCoinBase == realcoin.fCoinBase);
374  assert(realcoin.nHeight == sim->second);
375  }
376  },
377 
378  [&]() { // Uncache
379  uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
380  // Apply to real caches (there is no equivalent in our simulation).
381  caches.back()->Uncache(data.outpoints[outpointidx]);
382  },
383 
384  [&]() { // Add a cache level (if not already at the max).
385  if (caches.size() != MAX_CACHES) {
386  // Apply to real caches.
387  caches.emplace_back(new CCoinsViewCache(&*caches.back(), /*deterministic=*/true));
388  // Apply to simulation data.
389  sim_caches[caches.size()].Wipe();
390  }
391  },
392 
393  [&]() { // Remove a cache level.
394  // Apply to real caches (this reduces caches.size(), implicitly doing the same on the simulation data).
395  caches.back()->SanityCheck();
396  caches.pop_back();
397  },
398 
399  [&]() { // Flush.
400  // Apply to simulation data.
401  flush();
402  // Apply to real caches.
403  caches.back()->Flush();
404  },
405 
406  [&]() { // Sync.
407  // Apply to simulation data (note that in our simulation, syncing and flushing is the same thing).
408  flush();
409  // Apply to real caches.
410  caches.back()->Sync();
411  },
412 
413  [&]() { // Flush + ReallocateCache.
414  // Apply to simulation data.
415  flush();
416  // Apply to real caches.
417  caches.back()->Flush();
418  caches.back()->ReallocateCache();
419  },
420 
421  [&]() { // GetCacheSize
422  (void)caches.back()->GetCacheSize();
423  },
424 
425  [&]() { // DynamicMemoryUsage
426  (void)caches.back()->DynamicMemoryUsage();
427  },
428 
429  [&]() { // Change height
430  current_height = provider.ConsumeIntegralInRange<uint32_t>(1, current_height - 1);
431  }
432  );
433  }
434 
435  // Sanity check all the remaining caches
436  for (const auto& cache : caches) {
437  cache->SanityCheck();
438  }
439 
440  // Full comparison between caches and simulation data, from bottom to top,
441  // as AccessCoin on a higher cache may affect caches below it.
442  for (unsigned sim_idx = 1; sim_idx <= caches.size(); ++sim_idx) {
443  auto& cache = *caches[sim_idx - 1];
444  size_t cache_size = 0;
445 
446  for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
447  cache_size += cache.HaveCoinInCache(data.outpoints[outpointidx]);
448  const auto& real = cache.AccessCoin(data.outpoints[outpointidx]);
449  auto sim = lookup(outpointidx, sim_idx);
450  if (!sim.has_value()) {
451  assert(real.IsSpent());
452  } else {
453  assert(!real.IsSpent());
454  assert(real.out == data.coins[sim->first].out);
455  assert(real.fCoinBase == data.coins[sim->first].fCoinBase);
456  assert(real.nHeight == sim->second);
457  }
458  }
459 
460  // HaveCoinInCache ignores spent coins, so GetCacheSize() may exceed it. */
461  assert(cache.GetCacheSize() >= cache_size);
462  }
463 
464  // Compare the bottom coinsview (not a CCoinsViewCache) with sim_cache[0].
465  for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
466  Coin realcoin;
467  bool real = bottom.GetCoin(data.outpoints[outpointidx], realcoin);
468  auto sim = lookup(outpointidx, 0);
469  if (!sim.has_value()) {
470  assert(!real || realcoin.IsSpent());
471  } else {
472  assert(real && !realcoin.IsSpent());
473  assert(realcoin.out == data.coins[sim->first].out);
474  assert(realcoin.fCoinBase == data.coins[sim->first].fCoinBase);
475  assert(realcoin.nHeight == sim->second);
476  }
477  }
478 }
static constexpr CAmount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition: amount.h:26
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:230
Abstract view on the open txout dataset.
Definition: coins.h:174
virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const
Retrieve the Coin (unspent transaction output) for a given outpoint.
Definition: coins.cpp:13
virtual std::vector< uint256 > GetHeadBlocks() const
Retrieve the range of blocks that may have been only partially written.
Definition: coins.cpp:15
virtual bool HaveCoin(const COutPoint &outpoint) const
Just check whether a given outpoint is unspent.
Definition: coins.cpp:19
virtual size_t EstimateSize() const
Estimate database size (0 if not implemented)
Definition: coins.h:205
virtual std::unique_ptr< CCoinsViewCursor > Cursor() const
Get a cursor to iterate over the whole state.
Definition: coins.cpp:17
virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase=true)
Do a bulk modification (multiple Coin changes + BestBlock change).
Definition: coins.cpp:16
virtual uint256 GetBestBlock() const
Retrieve the block hash whose state this CCoinsView currently represents.
Definition: coins.cpp:14
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:36
uint32_t n
Definition: transaction.h:39
A hasher class for SHA-256.
Definition: sha256.h:14
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:707
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:681
CScript scriptPubKey
Definition: transaction.h:161
CAmount nValue
Definition: transaction.h:160
A UTXO entry.
Definition: coins.h:32
CTxOut out
unspent transaction output
Definition: coins.h:35
bool IsSpent() const
Either this coin never existed (see e.g.
Definition: coins.h:80
uint32_t nHeight
at which height this containing transaction was included in the active block chain
Definition: coins.h:41
unsigned int fCoinBase
whether containing transaction was a coinbase
Definition: coins.h:38
T ConsumeIntegralInRange(T min, T max)
constexpr uint64_t GetUint64(int pos) const
Definition: uint256.h:76
constexpr unsigned char * begin()
Definition: uint256.h:68
void resize(size_type new_size)
Definition: prevector.h:325
256-bit opaque blob.
Definition: uint256.h:106
std::unordered_map< COutPoint, CCoinsCacheEntry, SaltedOutpointHasher, std::equal_to< COutPoint >, PoolAllocator< std::pair< const COutPoint, CCoinsCacheEntry >, sizeof(std::pair< const COutPoint, CCoinsCacheEntry >)+sizeof(void *) *4, alignof(void *)> > CCoinsMap
PoolAllocator's MAX_BLOCK_SIZE_BYTES parameter here uses sizeof the data, and adds the size of 4 poin...
Definition: coins.h:149
static const CAmount SPENT
FUZZ_TARGET(coinscache_sim)
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
@ NONE
Definition: logging.h:39
@ OP_CHECKSIG
Definition: script.h:188
@ OP_EQUAL
Definition: script.h:144
@ OP_DUP
Definition: script.h:123
@ OP_HASH160
Definition: script.h:185
@ OP_1
Definition: script.h:81
@ OP_0
Definition: script.h:74
@ OP_EQUALVERIFY
Definition: script.h:145
@ DIRTY
DIRTY means the CCoinsCacheEntry is potentially different from the version in the parent cache.
Definition: coins.h:117
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition: util.h:36
assert(!tx.IsCoinBase())