coinscache_sim.cpp
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> 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[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 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, though coins whose output index 141 * is 3 (mod 5) always have GetCoin() succeed (but returning an IsSpent() coin unless a UTXO 142 * exists). Coins whose output index is 4 (mod 5) have GetCoin() always succeed after being spent. 143 * This exercises code paths with spent, non-DIRTY cache entries. 144 */ 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 { 207 /** Precomputed COutPoint and CCoins values. */ 208 static const PrecomputedData data; 209 210 /** Dummy coinsview instance (base of the hierarchy). */ 211 CoinsViewBottom bottom; 212 /** Real CCoinsViewCache objects. */ 213 std::vector<std::unique_ptr<CCoinsViewCache>> caches; 214 /** Simulated cache data (sim_caches[0] matches bottom, sim_caches[i+1] matches caches[i]). */ 215 CacheLevel sim_caches[MAX_CACHES + 1]; 216 /** Current height in the simulation. */ 217 uint32_t current_height = 1U; 218 219 // Initialize bottom simulated cache. 220 sim_caches[0].Wipe(); 221 222 /** Helper lookup function in the simulated cache stack. */ 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 238 /** Flush changes in top cache to the one below. */ 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 }