coinscache_sim.cpp raw
1 // Copyright (c) 2023 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 <coins.h>
6 #include <crypto/sha256.h>
7 #include <primitives/transaction.h>
8 #include <test/fuzz/fuzz.h>
9 #include <test/fuzz/FuzzedDataProvider.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
20 /** Number of distinct COutPoint values used in this test. */
21 constexpr uint32_t NUM_OUTPOINTS = 256;
22 /** Number of distinct Coin values used in this test (ignoring nHeight). */
23 constexpr uint32_t NUM_COINS = 256;
24 /** Maximum number CCoinsViewCache objects used in this test. */
25 constexpr uint32_t MAX_CACHES = 4;
26 /** Data type large enough to hold NUM_COINS-1. */
27 using coinidx_type = uint8_t;
28
29 struct PrecomputedData
30 {
31 //! Randomly generated COutPoint values.
32 COutPoint outpoints[NUM_OUTPOINTS];
33
34 //! Randomly generated Coin values.
35 Coin coins[NUM_COINS];
36
37 PrecomputedData()
38 {
39 static const uint8_t PREFIX_O[1] = {'o'}; /** Hash prefix for outpoint hashes. */
40 static const uint8_t PREFIX_S[1] = {'s'}; /** Hash prefix for coins scriptPubKeys. */
41 static const uint8_t PREFIX_M[1] = {'m'}; /** Hash prefix for coins nValue/fCoinBase. */
42
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[22] = 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
138 /** Class for the base of the hierarchy (roughly simulating a memory-backed CCoinsViewDB).
139 *
140 * The initial state consists of the empty UTXO set.
141 * Coins whose output index is 4 (mod 5) have GetCoin() always succeed after being spent.
142 * This exercises code paths with spent, non-DIRTY cache entries.
143 */
144 class CoinsViewBottom final : public CCoinsView
145 {
146 std::map<COutPoint, Coin> m_data;
147
148 public:
149 std::optional<Coin> GetCoin(const COutPoint& outpoint) const final
150 {
151 // TODO GetCoin shouldn't return spent coins
152 if (auto it = m_data.find(outpoint); it != m_data.end()) return it->second;
153 return std::nullopt;
154 }
155
156 bool HaveCoin(const COutPoint& outpoint) const final
157 {
158 return m_data.count(outpoint);
159 }
160
161 uint256 GetBestBlock() const final { return {}; }
162 std::vector<uint256> GetHeadBlocks() const final { return {}; }
163 std::unique_ptr<CCoinsViewCursor> Cursor() const final { return {}; }
164 size_t EstimateSize() const final { return m_data.size(); }
165
166 bool BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) final
167 {
168 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
169 if (it->second.IsDirty()) {
170 if (it->second.coin.IsSpent() && (it->first.n % 5) != 4) {
171 m_data.erase(it->first);
172 } else if (cursor.WillErase(*it)) {
173 m_data[it->first] = std::move(it->second.coin);
174 } else {
175 m_data[it->first] = it->second.coin;
176 }
177 } else {
178 /* For non-dirty entries being written, compare them with what we have. */
179 auto it2 = m_data.find(it->first);
180 if (it->second.coin.IsSpent()) {
181 assert(it2 == m_data.end() || it2->second.IsSpent());
182 } else {
183 assert(it2 != m_data.end());
184 assert(it->second.coin.out == it2->second.out);
185 assert(it->second.coin.fCoinBase == it2->second.fCoinBase);
186 assert(it->second.coin.nHeight == it2->second.nHeight);
187 }
188 }
189 }
190 return true;
191 }
192 };
193
194 } // namespace
195
196 FUZZ_TARGET(coinscache_sim)
197 {
198 /** Precomputed COutPoint and CCoins values. */
199 static const PrecomputedData data;
200
201 /** Dummy coinsview instance (base of the hierarchy). */
202 CoinsViewBottom bottom;
203 /** Real CCoinsViewCache objects. */
204 std::vector<std::unique_ptr<CCoinsViewCache>> caches;
205 /** Simulated cache data (sim_caches[0] matches bottom, sim_caches[i+1] matches caches[i]). */
206 CacheLevel sim_caches[MAX_CACHES + 1];
207 /** Current height in the simulation. */
208 uint32_t current_height = 1U;
209
210 // Initialize bottom simulated cache.
211 sim_caches[0].Wipe();
212
213 /** Helper lookup function in the simulated cache stack. */
214 auto lookup = [&](uint32_t outpointidx, int sim_idx = -1) -> std::optional<std::pair<coinidx_type, uint32_t>> {
215 uint32_t cache_idx = sim_idx == -1 ? caches.size() : sim_idx;
216 while (true) {
217 const auto& entry = sim_caches[cache_idx].entry[outpointidx];
218 if (entry.entrytype == EntryType::UNSPENT) {
219 return {{entry.coinidx, entry.height}};
220 } else if (entry.entrytype == EntryType::SPENT) {
221 return std::nullopt;
222 };
223 if (cache_idx == 0) break;
224 --cache_idx;
225 }
226 return std::nullopt;
227 };
228
229 /** Flush changes in top cache to the one below. */
230 auto flush = [&]() {
231 assert(caches.size() >= 1);
232 auto& cache = sim_caches[caches.size()];
233 auto& prev_cache = sim_caches[caches.size() - 1];
234 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
235 if (cache.entry[outpointidx].entrytype != EntryType::NONE) {
236 prev_cache.entry[outpointidx] = cache.entry[outpointidx];
237 cache.entry[outpointidx].entrytype = EntryType::NONE;
238 }
239 }
240 };
241
242 // Main simulation loop: read commands from the fuzzer input, and apply them
243 // to both the real cache stack and the simulation.
244 FuzzedDataProvider provider(buffer.data(), buffer.size());
245 LIMITED_WHILE(provider.remaining_bytes(), 10000) {
246 // Every operation (except "Change height") moves current height forward,
247 // so it functions as a kind of epoch, making ~all UTXOs unique.
248 ++current_height;
249 // Make sure there is always at least one CCoinsViewCache.
250 if (caches.empty()) {
251 caches.emplace_back(new CCoinsViewCache(&bottom, /*deterministic=*/true));
252 sim_caches[caches.size()].Wipe();
253 }
254
255 // Execute command.
256 CallOneOf(
257 provider,
258
259 [&]() { // GetCoin
260 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
261 // Look up in simulation data.
262 auto sim = lookup(outpointidx);
263 // Look up in real caches.
264 auto realcoin = caches.back()->GetCoin(data.outpoints[outpointidx]);
265 // Compare results.
266 if (!sim.has_value()) {
267 assert(!realcoin || realcoin->IsSpent());
268 } else {
269 assert(realcoin && !realcoin->IsSpent());
270 const auto& simcoin = data.coins[sim->first];
271 assert(realcoin->out == simcoin.out);
272 assert(realcoin->fCoinBase == simcoin.fCoinBase);
273 assert(realcoin->nHeight == sim->second);
274 }
275 },
276
277 [&]() { // HaveCoin
278 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
279 // Look up in simulation data.
280 auto sim = lookup(outpointidx);
281 // Look up in real caches.
282 auto real = caches.back()->HaveCoin(data.outpoints[outpointidx]);
283 // Compare results.
284 assert(sim.has_value() == real);
285 },
286
287 [&]() { // HaveCoinInCache
288 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
289 // Invoke on real cache (there is no equivalent in simulation, so nothing to compare result with).
290 (void)caches.back()->HaveCoinInCache(data.outpoints[outpointidx]);
291 },
292
293 [&]() { // AccessCoin
294 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
295 // Look up in simulation data.
296 auto sim = lookup(outpointidx);
297 // Look up in real caches.
298 const auto& realcoin = caches.back()->AccessCoin(data.outpoints[outpointidx]);
299 // Compare results.
300 if (!sim.has_value()) {
301 assert(realcoin.IsSpent());
302 } else {
303 assert(!realcoin.IsSpent());
304 const auto& simcoin = data.coins[sim->first];
305 assert(simcoin.out == realcoin.out);
306 assert(simcoin.fCoinBase == realcoin.fCoinBase);
307 assert(realcoin.nHeight == sim->second);
308 }
309 },
310
311 [&]() { // AddCoin (only possible_overwrite if necessary)
312 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
313 uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
314 // Look up in simulation data (to know whether we must set possible_overwrite or not).
315 auto sim = lookup(outpointidx);
316 // Invoke on real caches.
317 Coin coin = data.coins[coinidx];
318 coin.nHeight = current_height;
319 caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), sim.has_value());
320 // Apply to simulation data.
321 auto& entry = sim_caches[caches.size()].entry[outpointidx];
322 entry.entrytype = EntryType::UNSPENT;
323 entry.coinidx = coinidx;
324 entry.height = current_height;
325 },
326
327 [&]() { // AddCoin (always possible_overwrite)
328 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
329 uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
330 // Invoke on real caches.
331 Coin coin = data.coins[coinidx];
332 coin.nHeight = current_height;
333 caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), true);
334 // Apply to simulation data.
335 auto& entry = sim_caches[caches.size()].entry[outpointidx];
336 entry.entrytype = EntryType::UNSPENT;
337 entry.coinidx = coinidx;
338 entry.height = current_height;
339 },
340
341 [&]() { // SpendCoin (moveto = nullptr)
342 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
343 // Invoke on real caches.
344 caches.back()->SpendCoin(data.outpoints[outpointidx], nullptr);
345 // Apply to simulation data.
346 sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
347 },
348
349 [&]() { // SpendCoin (with moveto)
350 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
351 // Look up in simulation data (to compare the returned *moveto with).
352 auto sim = lookup(outpointidx);
353 // Invoke on real caches.
354 Coin realcoin;
355 caches.back()->SpendCoin(data.outpoints[outpointidx], &realcoin);
356 // Apply to simulation data.
357 sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
358 // Compare *moveto with the value expected based on simulation data.
359 if (!sim.has_value()) {
360 assert(realcoin.IsSpent());
361 } else {
362 assert(!realcoin.IsSpent());
363 const auto& simcoin = data.coins[sim->first];
364 assert(simcoin.out == realcoin.out);
365 assert(simcoin.fCoinBase == realcoin.fCoinBase);
366 assert(realcoin.nHeight == sim->second);
367 }
368 },
369
370 [&]() { // Uncache
371 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
372 // Apply to real caches (there is no equivalent in our simulation).
373 caches.back()->Uncache(data.outpoints[outpointidx]);
374 },
375
376 [&]() { // Add a cache level (if not already at the max).
377 if (caches.size() != MAX_CACHES) {
378 // Apply to real caches.
379 caches.emplace_back(new CCoinsViewCache(&*caches.back(), /*deterministic=*/true));
380 // Apply to simulation data.
381 sim_caches[caches.size()].Wipe();
382 }
383 },
384
385 [&]() { // Remove a cache level.
386 // Apply to real caches (this reduces caches.size(), implicitly doing the same on the simulation data).
387 caches.back()->SanityCheck();
388 caches.pop_back();
389 },
390
391 [&]() { // Flush.
392 // Apply to simulation data.
393 flush();
394 // Apply to real caches.
395 caches.back()->Flush();
396 },
397
398 [&]() { // Sync.
399 // Apply to simulation data (note that in our simulation, syncing and flushing is the same thing).
400 flush();
401 // Apply to real caches.
402 caches.back()->Sync();
403 },
404
405 [&]() { // Flush + ReallocateCache.
406 // Apply to simulation data.
407 flush();
408 // Apply to real caches.
409 caches.back()->Flush();
410 caches.back()->ReallocateCache();
411 },
412
413 [&]() { // GetCacheSize
414 (void)caches.back()->GetCacheSize();
415 },
416
417 [&]() { // DynamicMemoryUsage
418 (void)caches.back()->DynamicMemoryUsage();
419 },
420
421 [&]() { // Change height
422 current_height = provider.ConsumeIntegralInRange<uint32_t>(1, current_height - 1);
423 }
424 );
425 }
426
427 // Sanity check all the remaining caches
428 for (const auto& cache : caches) {
429 cache->SanityCheck();
430 }
431
432 // Full comparison between caches and simulation data, from bottom to top,
433 // as AccessCoin on a higher cache may affect caches below it.
434 for (unsigned sim_idx = 1; sim_idx <= caches.size(); ++sim_idx) {
435 auto& cache = *caches[sim_idx - 1];
436 size_t cache_size = 0;
437
438 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
439 cache_size += cache.HaveCoinInCache(data.outpoints[outpointidx]);
440 const auto& real = cache.AccessCoin(data.outpoints[outpointidx]);
441 auto sim = lookup(outpointidx, sim_idx);
442 if (!sim.has_value()) {
443 assert(real.IsSpent());
444 } else {
445 assert(!real.IsSpent());
446 assert(real.out == data.coins[sim->first].out);
447 assert(real.fCoinBase == data.coins[sim->first].fCoinBase);
448 assert(real.nHeight == sim->second);
449 }
450 }
451
452 // HaveCoinInCache ignores spent coins, so GetCacheSize() may exceed it.
453 assert(cache.GetCacheSize() >= cache_size);
454 }
455
456 // Compare the bottom coinsview (not a CCoinsViewCache) with sim_cache[0].
457 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
458 auto realcoin = bottom.GetCoin(data.outpoints[outpointidx]);
459 auto sim = lookup(outpointidx, 0);
460 if (!sim.has_value()) {
461 assert(!realcoin || realcoin->IsSpent());
462 } else {
463 assert(realcoin && !realcoin->IsSpent());
464 assert(realcoin->out == data.coins[sim->first].out);
465 assert(realcoin->fCoinBase == data.coins[sim->first].fCoinBase);
466 assert(realcoin->nHeight == sim->second);
467 }
468 }
469 }
470