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