src/test/coins_tests.cpp

   1 // Copyright (c) 2014 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 "random.h"
   7 #include "uint256.h"
   8 #include "test/test_bitcoin.h"
   9 #include "consensus/validation.h"
  10 #include "main.h"
  11 #include "undo.h"
  12
  13 #include <vector>
  14 #include <map>
  15
  16 #include <boost/test/unit_test.hpp>
  17 #include "zcash/IncrementalMerkleTree.hpp"
  18
  19 namespace
  20 {
  21 class CCoinsViewTest : public CCoinsView
  22 {
  23     uint256 hashBestBlock_;
  24     uint256 hashBestAnchor_;
  25     std::map<uint256, CCoins> map_;
  26     std::map<uint256, ZCIncrementalMerkleTree> mapAnchors_;
  27     std::map<uint256, bool> mapSerials_;
  28
  29 public:
  30     CCoinsViewTest() {
  31         hashBestAnchor_ = ZCIncrementalMerkleTree::empty_root();
  32     }
  33
  34     bool GetAnchorAt(const uint256& rt, ZCIncrementalMerkleTree &tree) const {
  35         if (rt == ZCIncrementalMerkleTree::empty_root()) {
  36             ZCIncrementalMerkleTree new_tree;
  37             tree = new_tree;
  38             return true;
  39         }
  40
  41         std::map<uint256, ZCIncrementalMerkleTree>::const_iterator it = mapAnchors_.find(rt);
  42         if (it == mapAnchors_.end()) {
  43             return false;
  44         } else {
  45             tree = it->second;
  46             return true;
  47         }
  48     }
  49
  50     bool GetSerial(const uint256 &serial) const
  51     {
  52         std::map<uint256, bool>::const_iterator it = mapSerials_.find(serial);
  53
  54         if (it == mapSerials_.end()) {
  55             return false;
  56         } else {
  57             // The map shouldn't contain any false entries.
  58             assert(it->second);
  59             return true;
  60         }
  61     }
  62
  63     uint256 GetBestAnchor() const { return hashBestAnchor_; }
  64
  65     bool GetCoins(const uint256& txid, CCoins& coins) const
  66     {
  67         std::map<uint256, CCoins>::const_iterator it = map_.find(txid);
  68         if (it == map_.end()) {
  69             return false;
  70         }
  71         coins = it->second;
  72         if (coins.IsPruned() && insecure_rand() % 2 == 0) {
  73             // Randomly return false in case of an empty entry.
  74             return false;
  75         }
  76         return true;
  77     }
  78
  79     bool HaveCoins(const uint256& txid) const
  80     {
  81         CCoins coins;
  82         return GetCoins(txid, coins);
  83     }
  84
  85     uint256 GetBestBlock() const { return hashBestBlock_; }
  86
  87     bool BatchWrite(CCoinsMap& mapCoins,
  88                     const uint256& hashBlock,
  89                     const uint256& hashAnchor,
  90                     CAnchorsMap& mapAnchors,
  91                     CSerialsMap& mapSerials)
  92     {
  93         for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) {
  94             map_[it->first] = it->second.coins;
  95             if (it->second.coins.IsPruned() && insecure_rand() % 3 == 0) {
  96                 // Randomly delete empty entries on write.
  97                 map_.erase(it->first);
  98             }
  99             mapCoins.erase(it++);
 100         }
 101         for (CAnchorsMap::iterator it = mapAnchors.begin(); it != mapAnchors.end(); ) {
 102             if (it->second.entered) {
 103                 std::map<uint256, ZCIncrementalMerkleTree>::iterator ret =
 104                     mapAnchors_.insert(std::make_pair(it->first, ZCIncrementalMerkleTree())).first;
 105
 106                 ret->second = it->second.tree;
 107             } else {
 108                 mapAnchors_.erase(it->first);
 109             }
 110             mapAnchors.erase(it++);
 111         }
 112         for (CSerialsMap::iterator it = mapSerials.begin(); it != mapSerials.end(); ) {
 113             if (it->second.entered) {
 114                 mapSerials_[it->first] = true;
 115             } else {
 116                 mapSerials_.erase(it->first);
 117             }
 118             mapSerials.erase(it++);
 119         }
 120         mapCoins.clear();
 121         mapAnchors.clear();
 122         mapSerials.clear();
 123         hashBestBlock_ = hashBlock;
 124         hashBestAnchor_ = hashAnchor;
 125         return true;
 126     }
 127
 128     bool GetStats(CCoinsStats& stats) const { return false; }
 129 };
 130
 131 class CCoinsViewCacheTest : public CCoinsViewCache
 132 {
 133 public:
 134     CCoinsViewCacheTest(CCoinsView* base) : CCoinsViewCache(base) {}
 135
 136     void SelfTest() const
 137     {
 138         // Manually recompute the dynamic usage of the whole data, and compare it.
 139         size_t ret = memusage::DynamicUsage(cacheCoins);
 140         for (CCoinsMap::iterator it = cacheCoins.begin(); it != cacheCoins.end(); it++) {
 141             ret += memusage::DynamicUsage(it->second.coins);
 142         }
 143         BOOST_CHECK_EQUAL(memusage::DynamicUsage(*this), ret);
 144     }
 145
 146 };
 147
 148 }
 149
 150 uint256 appendRandomCommitment(ZCIncrementalMerkleTree &tree)
 151 {
 152     libzcash::SpendingKey k = libzcash::SpendingKey::random();
 153     libzcash::PaymentAddress addr = k.address();
 154
 155     libzcash::Note note(addr.a_pk, 0, uint256(), uint256());
 156
 157     auto cm = note.cm();
 158     tree.append(cm);
 159     return cm;
 160 }
 161
 162 BOOST_FIXTURE_TEST_SUITE(coins_tests, BasicTestingSetup)
 163
 164 BOOST_AUTO_TEST_CASE(serials_test)
 165 {
 166     CCoinsViewTest base;
 167     CCoinsViewCacheTest cache(&base);
 168
 169     uint256 myserial = GetRandHash();
 170
 171     BOOST_CHECK(!cache.GetSerial(myserial));
 172     cache.SetSerial(myserial, true);
 173     BOOST_CHECK(cache.GetSerial(myserial));
 174     cache.Flush();
 175
 176     CCoinsViewCacheTest cache2(&base);
 177
 178     BOOST_CHECK(cache2.GetSerial(myserial));
 179     cache2.SetSerial(myserial, false);
 180     BOOST_CHECK(!cache2.GetSerial(myserial));
 181     cache2.Flush();
 182
 183     CCoinsViewCacheTest cache3(&base);
 184
 185     BOOST_CHECK(!cache3.GetSerial(myserial));
 186 }
 187
 188 BOOST_AUTO_TEST_CASE(anchors_flush_test)
 189 {
 190     CCoinsViewTest base;
 191     uint256 newrt;
 192     {
 193         CCoinsViewCacheTest cache(&base);
 194         ZCIncrementalMerkleTree tree;
 195         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 196         appendRandomCommitment(tree);
 197
 198         newrt = tree.root();
 199
 200         cache.PushAnchor(tree);
 201         cache.Flush();
 202     }
 203
 204     {
 205         CCoinsViewCacheTest cache(&base);
 206         ZCIncrementalMerkleTree tree;
 207         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 208
 209         // Get the cached entry.
 210         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 211
 212         uint256 check_rt = tree.root();
 213
 214         BOOST_CHECK(check_rt == newrt);
 215     }
 216 }
 217
 218 BOOST_AUTO_TEST_CASE(chained_pours)
 219 {
 220     CCoinsViewTest base;
 221     CCoinsViewCacheTest cache(&base);
 222
 223     ZCIncrementalMerkleTree tree;
 224
 225     CPourTx ptx1;
 226     ptx1.anchor = tree.root();
 227     ptx1.commitments[0] = appendRandomCommitment(tree);
 228     ptx1.commitments[1] = appendRandomCommitment(tree);
 229
 230     // Although it's not possible given our assumptions, if
 231     // two pours create the same treestate twice, we should
 232     // still be able to anchor to it.
 233     CPourTx ptx1b;
 234     ptx1b.anchor = tree.root();
 235     ptx1b.commitments[0] = ptx1.commitments[0];
 236     ptx1b.commitments[1] = ptx1.commitments[1];
 237
 238     CPourTx ptx2;
 239     CPourTx ptx3;
 240
 241     ptx2.anchor = tree.root();
 242     ptx3.anchor = tree.root();
 243
 244     ptx2.commitments[0] = appendRandomCommitment(tree);
 245     ptx2.commitments[1] = appendRandomCommitment(tree);
 246
 247     ptx3.commitments[0] = appendRandomCommitment(tree);
 248     ptx3.commitments[1] = appendRandomCommitment(tree);
 249
 250     {
 251         CMutableTransaction mtx;
 252         mtx.vpour.push_back(ptx2);
 253
 254         BOOST_CHECK(!cache.HavePourRequirements(mtx));
 255     }
 256
 257     {
 258         // ptx2 is trying to anchor to ptx1 but ptx1
 259         // appears afterwards -- not a permitted ordering
 260         CMutableTransaction mtx;
 261         mtx.vpour.push_back(ptx2);
 262         mtx.vpour.push_back(ptx1);
 263
 264         BOOST_CHECK(!cache.HavePourRequirements(mtx));
 265     }
 266
 267     {
 268         CMutableTransaction mtx;
 269         mtx.vpour.push_back(ptx1);
 270         mtx.vpour.push_back(ptx2);
 271
 272         BOOST_CHECK(cache.HavePourRequirements(mtx));
 273     }
 274
 275     {
 276         CMutableTransaction mtx;
 277         mtx.vpour.push_back(ptx1);
 278         mtx.vpour.push_back(ptx2);
 279         mtx.vpour.push_back(ptx3);
 280
 281         BOOST_CHECK(cache.HavePourRequirements(mtx));
 282     }
 283
 284     {
 285         CMutableTransaction mtx;
 286         mtx.vpour.push_back(ptx1);
 287         mtx.vpour.push_back(ptx1b);
 288         mtx.vpour.push_back(ptx2);
 289         mtx.vpour.push_back(ptx3);
 290
 291         BOOST_CHECK(cache.HavePourRequirements(mtx));
 292     }
 293 }
 294
 295 BOOST_AUTO_TEST_CASE(anchors_test)
 296 {
 297     // TODO: These tests should be more methodical.
 298     //       Or, integrate with Bitcoin's tests later.
 299
 300     CCoinsViewTest base;
 301     CCoinsViewCacheTest cache(&base);
 302
 303     BOOST_CHECK(cache.GetBestAnchor() == ZCIncrementalMerkleTree::empty_root());
 304
 305     {
 306         ZCIncrementalMerkleTree tree;
 307
 308         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 309         BOOST_CHECK(cache.GetBestAnchor() == tree.root());
 310         appendRandomCommitment(tree);
 311         appendRandomCommitment(tree);
 312         appendRandomCommitment(tree);
 313         appendRandomCommitment(tree);
 314         appendRandomCommitment(tree);
 315         appendRandomCommitment(tree);
 316         appendRandomCommitment(tree);
 317
 318         ZCIncrementalMerkleTree save_tree_for_later;
 319         save_tree_for_later = tree;
 320
 321         uint256 newrt = tree.root();
 322         uint256 newrt2;
 323
 324         cache.PushAnchor(tree);
 325         BOOST_CHECK(cache.GetBestAnchor() == newrt);
 326
 327         {
 328             ZCIncrementalMerkleTree confirm_same;
 329             BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), confirm_same));
 330
 331             BOOST_CHECK(confirm_same.root() == newrt);
 332         }
 333
 334         appendRandomCommitment(tree);
 335         appendRandomCommitment(tree);
 336
 337         newrt2 = tree.root();
 338
 339         cache.PushAnchor(tree);
 340         BOOST_CHECK(cache.GetBestAnchor() == newrt2);
 341
 342         ZCIncrementalMerkleTree test_tree;
 343         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), test_tree));
 344
 345         BOOST_CHECK(tree.root() == test_tree.root());
 346
 347         {
 348             ZCIncrementalMerkleTree test_tree2;
 349             cache.GetAnchorAt(newrt, test_tree2);
 350
 351             BOOST_CHECK(test_tree2.root() == newrt);
 352         }
 353
 354         {
 355             cache.PopAnchor(newrt);
 356             ZCIncrementalMerkleTree obtain_tree;
 357             assert(!cache.GetAnchorAt(newrt2, obtain_tree)); // should have been popped off
 358             assert(cache.GetAnchorAt(newrt, obtain_tree));
 359
 360             assert(obtain_tree.root() == newrt);
 361         }
 362     }
 363 }
 364
 365 static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
 366
 367 // This is a large randomized insert/remove simulation test on a variable-size
 368 // stack of caches on top of CCoinsViewTest.
 369 //
 370 // It will randomly create/update/delete CCoins entries to a tip of caches, with
 371 // txids picked from a limited list of random 256-bit hashes. Occasionally, a
 372 // new tip is added to the stack of caches, or the tip is flushed and removed.
 373 //
 374 // During the process, booleans are kept to make sure that the randomized
 375 // operation hits all branches.
 376 BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
 377 {
 378     // Various coverage trackers.
 379     bool removed_all_caches = false;
 380     bool reached_4_caches = false;
 381     bool added_an_entry = false;
 382     bool removed_an_entry = false;
 383     bool updated_an_entry = false;
 384     bool found_an_entry = false;
 385     bool missed_an_entry = false;
 386
 387     // A simple map to track what we expect the cache stack to represent.
 388     std::map<uint256, CCoins> result;
 389
 390     // The cache stack.
 391     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
 392     std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
 393     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 394
 395     // Use a limited set of random transaction ids, so we do test overwriting entries.
 396     std::vector<uint256> txids;
 397     txids.resize(NUM_SIMULATION_ITERATIONS / 8);
 398     for (unsigned int i = 0; i < txids.size(); i++) {
 399         txids[i] = GetRandHash();
 400     }
 401
 402     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
 403         // Do a random modification.
 404         {
 405             uint256 txid = txids[insecure_rand() % txids.size()]; // txid we're going to modify in this iteration.
 406             CCoins& coins = result[txid];
 407             CCoinsModifier entry = stack.back()->ModifyCoins(txid);
 408             BOOST_CHECK(coins == *entry);
 409             if (insecure_rand() % 5 == 0 || coins.IsPruned()) {
 410                 if (coins.IsPruned()) {
 411                     added_an_entry = true;
 412                 } else {
 413                     updated_an_entry = true;
 414                 }
 415                 coins.nVersion = insecure_rand();
 416                 coins.vout.resize(1);
 417                 coins.vout[0].nValue = insecure_rand();
 418                 *entry = coins;
 419             } else {
 420                 coins.Clear();
 421                 entry->Clear();
 422                 removed_an_entry = true;
 423             }
 424         }
 425
 426         // Once every 1000 iterations and at the end, verify the full cache.
 427         if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
 428             for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
 429                 const CCoins* coins = stack.back()->AccessCoins(it->first);
 430                 if (coins) {
 431                     BOOST_CHECK(*coins == it->second);
 432                     found_an_entry = true;
 433                 } else {
 434                     BOOST_CHECK(it->second.IsPruned());
 435                     missed_an_entry = true;
 436                 }
 437             }
 438             BOOST_FOREACH(const CCoinsViewCacheTest *test, stack) {
 439                 test->SelfTest();
 440             }
 441         }
 442
 443         if (insecure_rand() % 100 == 0) {
 444             // Every 100 iterations, change the cache stack.
 445             if (stack.size() > 0 && insecure_rand() % 2 == 0) {
 446                 stack.back()->Flush();
 447                 delete stack.back();
 448                 stack.pop_back();
 449             }
 450             if (stack.size() == 0 || (stack.size() < 4 && insecure_rand() % 2)) {
 451                 CCoinsView* tip = &base;
 452                 if (stack.size() > 0) {
 453                     tip = stack.back();
 454                 } else {
 455                     removed_all_caches = true;
 456                 }
 457                 stack.push_back(new CCoinsViewCacheTest(tip));
 458                 if (stack.size() == 4) {
 459                     reached_4_caches = true;
 460                 }
 461             }
 462         }
 463     }
 464
 465     // Clean up the stack.
 466     while (stack.size() > 0) {
 467         delete stack.back();
 468         stack.pop_back();
 469     }
 470
 471     // Verify coverage.
 472     BOOST_CHECK(removed_all_caches);
 473     BOOST_CHECK(reached_4_caches);
 474     BOOST_CHECK(added_an_entry);
 475     BOOST_CHECK(removed_an_entry);
 476     BOOST_CHECK(updated_an_entry);
 477     BOOST_CHECK(found_an_entry);
 478     BOOST_CHECK(missed_an_entry);
 479 }
 480
 481 BOOST_AUTO_TEST_CASE(coins_coinbase_spends)
 482 {
 483     CCoinsViewTest base;
 484     CCoinsViewCacheTest cache(&base);
 485
 486     // Create coinbase transaction
 487     CMutableTransaction mtx;
 488     mtx.vin.resize(1);
 489     mtx.vin[0].scriptSig = CScript() << OP_1;
 490     mtx.vin[0].nSequence = 0;
 491     mtx.vout.resize(1);
 492     mtx.vout[0].nValue = 500;
 493     mtx.vout[0].scriptPubKey = CScript() << OP_1;
 494
 495     CTransaction tx(mtx);
 496
 497     BOOST_CHECK(tx.IsCoinBase());
 498
 499     CValidationState state;
 500     UpdateCoins(tx, state, cache, 100);
 501
 502     // Create coinbase spend
 503     CMutableTransaction mtx2;
 504     mtx2.vin.resize(1);
 505     mtx2.vin[0].prevout = COutPoint(tx.GetHash(), 0);
 506     mtx2.vin[0].scriptSig = CScript() << OP_1;
 507     mtx2.vin[0].nSequence = 0;
 508
 509     {
 510         CTransaction tx2(mtx2);
 511         BOOST_CHECK(NonContextualCheckInputs(tx2, state, cache, false, SCRIPT_VERIFY_NONE, false, Params().GetConsensus()));
 512     }
 513
 514     mtx2.vout.resize(1);
 515     mtx2.vout[0].nValue = 500;
 516     mtx2.vout[0].scriptPubKey = CScript() << OP_1;
 517
 518     {
 519         CTransaction tx2(mtx2);
 520         BOOST_CHECK(!NonContextualCheckInputs(tx2, state, cache, false, SCRIPT_VERIFY_NONE, false, Params().GetConsensus()));
 521         BOOST_CHECK(state.GetRejectReason() == "bad-txns-coinbase-spend-has-transparent-outputs");
 522     }
 523 }
 524
 525 BOOST_AUTO_TEST_SUITE_END()