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
  10 #include <vector>
  11 #include <map>
  12
  13 #include <boost/test/unit_test.hpp>
  14 #include "zcash/IncrementalMerkleTree.hpp"
  15
  16 namespace
  17 {
  18 class CCoinsViewTest : public CCoinsView
  19 {
  20     uint256 hashBestBlock_;
  21     uint256 hashBestAnchor_;
  22     std::map<uint256, CCoins> map_;
  23     std::map<uint256, ZCIncrementalMerkleTree> mapAnchors_;
  24     std::map<uint256, bool> mapSerials_;
  25
  26 public:
  27     bool GetAnchorAt(const uint256& rt, ZCIncrementalMerkleTree &tree) const {
  28         if (rt.IsNull()) {
  29             ZCIncrementalMerkleTree new_tree;
  30             tree = new_tree;
  31             return true;
  32         }
  33
  34         std::map<uint256, ZCIncrementalMerkleTree>::const_iterator it = mapAnchors_.find(rt);
  35         if (it == mapAnchors_.end()) {
  36             return false;
  37         } else {
  38             tree = it->second;
  39             return true;
  40         }
  41     }
  42
  43     bool GetSerial(const uint256 &serial) const
  44     {
  45         std::map<uint256, bool>::const_iterator it = mapSerials_.find(serial);
  46
  47         if (it == mapSerials_.end()) {
  48             return false;
  49         } else {
  50             // The map shouldn't contain any false entries.
  51             assert(it->second);
  52             return true;
  53         }
  54     }
  55
  56     uint256 GetBestAnchor() const { return hashBestAnchor_; }
  57
  58     bool GetCoins(const uint256& txid, CCoins& coins) const
  59     {
  60         std::map<uint256, CCoins>::const_iterator it = map_.find(txid);
  61         if (it == map_.end()) {
  62             return false;
  63         }
  64         coins = it->second;
  65         if (coins.IsPruned() && insecure_rand() % 2 == 0) {
  66             // Randomly return false in case of an empty entry.
  67             return false;
  68         }
  69         return true;
  70     }
  71
  72     bool HaveCoins(const uint256& txid) const
  73     {
  74         CCoins coins;
  75         return GetCoins(txid, coins);
  76     }
  77
  78     uint256 GetBestBlock() const { return hashBestBlock_; }
  79
  80     bool BatchWrite(CCoinsMap& mapCoins,
  81                     const uint256& hashBlock,
  82                     const uint256& hashAnchor,
  83                     CAnchorsMap& mapAnchors,
  84                     CSerialsMap& mapSerials)
  85     {
  86         for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) {
  87             map_[it->first] = it->second.coins;
  88             if (it->second.coins.IsPruned() && insecure_rand() % 3 == 0) {
  89                 // Randomly delete empty entries on write.
  90                 map_.erase(it->first);
  91             }
  92             mapCoins.erase(it++);
  93         }
  94         for (CAnchorsMap::iterator it = mapAnchors.begin(); it != mapAnchors.end(); ) {
  95             if (it->second.entered) {
  96                 std::map<uint256, ZCIncrementalMerkleTree>::iterator ret =
  97                     mapAnchors_.insert(std::make_pair(it->first, ZCIncrementalMerkleTree())).first;
  98
  99                 ret->second = it->second.tree;
 100             } else {
 101                 mapAnchors_.erase(it->first);
 102             }
 103             mapAnchors.erase(it++);
 104         }
 105         for (CSerialsMap::iterator it = mapSerials.begin(); it != mapSerials.end(); ) {
 106             if (it->second.entered) {
 107                 mapSerials_[it->first] = true;
 108             } else {
 109                 mapSerials_.erase(it->first);
 110             }
 111             mapSerials.erase(it++);
 112         }
 113         mapCoins.clear();
 114         mapAnchors.clear();
 115         mapSerials.clear();
 116         hashBestBlock_ = hashBlock;
 117         hashBestAnchor_ = hashAnchor;
 118         return true;
 119     }
 120
 121     bool GetStats(CCoinsStats& stats) const { return false; }
 122 };
 123
 124 class CCoinsViewCacheTest : public CCoinsViewCache
 125 {
 126 public:
 127     CCoinsViewCacheTest(CCoinsView* base) : CCoinsViewCache(base) {}
 128
 129     void SelfTest() const
 130     {
 131         // Manually recompute the dynamic usage of the whole data, and compare it.
 132         size_t ret = memusage::DynamicUsage(cacheCoins);
 133         for (CCoinsMap::iterator it = cacheCoins.begin(); it != cacheCoins.end(); it++) {
 134             ret += memusage::DynamicUsage(it->second.coins);
 135         }
 136         BOOST_CHECK_EQUAL(memusage::DynamicUsage(*this), ret);
 137     }
 138
 139 };
 140
 141 }
 142
 143 BOOST_AUTO_TEST_CASE(serials_test)
 144 {
 145     CCoinsViewTest base;
 146     CCoinsViewCacheTest cache(&base);
 147
 148     uint256 myserial = GetRandHash();
 149
 150     BOOST_CHECK(!cache.GetSerial(myserial));
 151     cache.SetSerial(myserial, true);
 152     BOOST_CHECK(cache.GetSerial(myserial));
 153     cache.Flush();
 154
 155     CCoinsViewCacheTest cache2(&base);
 156
 157     BOOST_CHECK(cache2.GetSerial(myserial));
 158     cache2.SetSerial(myserial, false);
 159     BOOST_CHECK(!cache2.GetSerial(myserial));
 160     cache2.Flush();
 161
 162     CCoinsViewCacheTest cache3(&base);
 163
 164     BOOST_CHECK(!cache3.GetSerial(myserial));
 165 }
 166
 167 void appendRandomCommitment(ZCIncrementalMerkleTree &tree)
 168 {
 169     Address addr = Address::CreateNewRandomAddress();
 170     Coin coin(addr.getPublicAddress(), 100);
 171
 172     tree.append(uint256(coin.getCoinCommitment().getCommitmentValue()));
 173 }
 174
 175 BOOST_AUTO_TEST_CASE(anchors_flush_test)
 176 {
 177     CCoinsViewTest base;
 178     uint256 newrt;
 179     {
 180         CCoinsViewCacheTest cache(&base);
 181         ZCIncrementalMerkleTree tree;
 182         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 183         appendRandomCommitment(tree);
 184
 185         newrt = tree.root();
 186
 187         cache.PushAnchor(tree);
 188         cache.Flush();
 189     }
 190
 191     {
 192         CCoinsViewCacheTest cache(&base);
 193         ZCIncrementalMerkleTree tree;
 194         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 195
 196         // Get the cached entry.
 197         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 198
 199         uint256 check_rt = tree.root();
 200
 201         BOOST_CHECK(check_rt == newrt);
 202     }
 203 }
 204
 205 BOOST_AUTO_TEST_CASE(anchors_test)
 206 {
 207     // TODO: These tests should be more methodical.
 208     //       Or, integrate with Bitcoin's tests later.
 209
 210     CCoinsViewTest base;
 211     CCoinsViewCacheTest cache(&base);
 212
 213     BOOST_CHECK(cache.GetBestAnchor() == uint256());
 214
 215     {
 216         ZCIncrementalMerkleTree tree;
 217
 218         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), tree));
 219         appendRandomCommitment(tree);
 220         appendRandomCommitment(tree);
 221         appendRandomCommitment(tree);
 222         appendRandomCommitment(tree);
 223         appendRandomCommitment(tree);
 224         appendRandomCommitment(tree);
 225         appendRandomCommitment(tree);
 226
 227         ZCIncrementalMerkleTree save_tree_for_later;
 228         save_tree_for_later = tree;
 229
 230         uint256 newrt = tree.root();
 231         uint256 newrt2;
 232
 233         cache.PushAnchor(tree);
 234         BOOST_CHECK(cache.GetBestAnchor() == newrt);
 235
 236         {
 237             ZCIncrementalMerkleTree confirm_same;
 238             BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), confirm_same));
 239
 240             BOOST_CHECK(confirm_same.root() == newrt);
 241         }
 242
 243         appendRandomCommitment(tree);
 244         appendRandomCommitment(tree);
 245
 246         newrt2 = tree.root();
 247
 248         cache.PushAnchor(tree);
 249         BOOST_CHECK(cache.GetBestAnchor() == newrt2);
 250
 251         ZCIncrementalMerkleTree test_tree;
 252         BOOST_CHECK(cache.GetAnchorAt(cache.GetBestAnchor(), test_tree));
 253
 254         BOOST_CHECK(tree.root() == test_tree.root());
 255
 256         {
 257             ZCIncrementalMerkleTree test_tree2;
 258             cache.GetAnchorAt(newrt, test_tree2);
 259
 260             BOOST_CHECK(test_tree2.root() == newrt);
 261         }
 262
 263         {
 264             cache.PopAnchor(newrt);
 265             ZCIncrementalMerkleTree obtain_tree;
 266             assert(!cache.GetAnchorAt(newrt2, obtain_tree)); // should have been popped off
 267             assert(cache.GetAnchorAt(newrt, obtain_tree));
 268
 269             assert(obtain_tree.root() == newrt);
 270         }
 271     }
 272 }
 273
 274 BOOST_FIXTURE_TEST_SUITE(coins_tests, BasicTestingSetup)
 275
 276 static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
 277
 278 // This is a large randomized insert/remove simulation test on a variable-size
 279 // stack of caches on top of CCoinsViewTest.
 280 //
 281 // It will randomly create/update/delete CCoins entries to a tip of caches, with
 282 // txids picked from a limited list of random 256-bit hashes. Occasionally, a
 283 // new tip is added to the stack of caches, or the tip is flushed and removed.
 284 //
 285 // During the process, booleans are kept to make sure that the randomized
 286 // operation hits all branches.
 287 BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
 288 {
 289     // Various coverage trackers.
 290     bool removed_all_caches = false;
 291     bool reached_4_caches = false;
 292     bool added_an_entry = false;
 293     bool removed_an_entry = false;
 294     bool updated_an_entry = false;
 295     bool found_an_entry = false;
 296     bool missed_an_entry = false;
 297
 298     // A simple map to track what we expect the cache stack to represent.
 299     std::map<uint256, CCoins> result;
 300
 301     // The cache stack.
 302     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
 303     std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
 304     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 305
 306     // Use a limited set of random transaction ids, so we do test overwriting entries.
 307     std::vector<uint256> txids;
 308     txids.resize(NUM_SIMULATION_ITERATIONS / 8);
 309     for (unsigned int i = 0; i < txids.size(); i++) {
 310         txids[i] = GetRandHash();
 311     }
 312
 313     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
 314         // Do a random modification.
 315         {
 316             uint256 txid = txids[insecure_rand() % txids.size()]; // txid we're going to modify in this iteration.
 317             CCoins& coins = result[txid];
 318             CCoinsModifier entry = stack.back()->ModifyCoins(txid);
 319             BOOST_CHECK(coins == *entry);
 320             if (insecure_rand() % 5 == 0 || coins.IsPruned()) {
 321                 if (coins.IsPruned()) {
 322                     added_an_entry = true;
 323                 } else {
 324                     updated_an_entry = true;
 325                 }
 326                 coins.nVersion = insecure_rand();
 327                 coins.vout.resize(1);
 328                 coins.vout[0].nValue = insecure_rand();
 329                 *entry = coins;
 330             } else {
 331                 coins.Clear();
 332                 entry->Clear();
 333                 removed_an_entry = true;
 334             }
 335         }
 336
 337         // Once every 1000 iterations and at the end, verify the full cache.
 338         if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
 339             for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
 340                 const CCoins* coins = stack.back()->AccessCoins(it->first);
 341                 if (coins) {
 342                     BOOST_CHECK(*coins == it->second);
 343                     found_an_entry = true;
 344                 } else {
 345                     BOOST_CHECK(it->second.IsPruned());
 346                     missed_an_entry = true;
 347                 }
 348             }
 349             BOOST_FOREACH(const CCoinsViewCacheTest *test, stack) {
 350                 test->SelfTest();
 351             }
 352         }
 353
 354         if (insecure_rand() % 100 == 0) {
 355             // Every 100 iterations, change the cache stack.
 356             if (stack.size() > 0 && insecure_rand() % 2 == 0) {
 357                 stack.back()->Flush();
 358                 delete stack.back();
 359                 stack.pop_back();
 360             }
 361             if (stack.size() == 0 || (stack.size() < 4 && insecure_rand() % 2)) {
 362                 CCoinsView* tip = &base;
 363                 if (stack.size() > 0) {
 364                     tip = stack.back();
 365                 } else {
 366                     removed_all_caches = true;
 367                 }
 368                 stack.push_back(new CCoinsViewCacheTest(tip));
 369                 if (stack.size() == 4) {
 370                     reached_4_caches = true;
 371                 }
 372             }
 373         }
 374     }
 375
 376     // Clean up the stack.
 377     while (stack.size() > 0) {
 378         delete stack.back();
 379         stack.pop_back();
 380     }
 381
 382     // Verify coverage.
 383     BOOST_CHECK(removed_all_caches);
 384     BOOST_CHECK(reached_4_caches);
 385     BOOST_CHECK(added_an_entry);
 386     BOOST_CHECK(removed_an_entry);
 387     BOOST_CHECK(updated_an_entry);
 388     BOOST_CHECK(found_an_entry);
 389     BOOST_CHECK(missed_an_entry);
 390 }
 391
 392 BOOST_AUTO_TEST_SUITE_END()