src/coins.cpp

   1 // Copyright (c) 2012-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
   7 #include "memusage.h"
   8 #include "random.h"
   9
  10 #include <assert.h>
  11
  12 /**
  13  * calculate number of bytes for the bitmask, and its number of non-zero bytes
  14  * each bit in the bitmask represents the availability of one output, but the
  15  * availabilities of the first two outputs are encoded separately
  16  */
  17 void CCoins::CalcMaskSize(unsigned int &nBytes, unsigned int &nNonzeroBytes) const {
  18     unsigned int nLastUsedByte = 0;
  19     for (unsigned int b = 0; 2+b*8 < vout.size(); b++) {
  20         bool fZero = true;
  21         for (unsigned int i = 0; i < 8 && 2+b*8+i < vout.size(); i++) {
  22             if (!vout[2+b*8+i].IsNull()) {
  23                 fZero = false;
  24                 continue;
  25             }
  26         }
  27         if (!fZero) {
  28             nLastUsedByte = b + 1;
  29             nNonzeroBytes++;
  30         }
  31     }
  32     nBytes += nLastUsedByte;
  33 }
  34
  35 bool CCoins::Spend(uint32_t nPos)
  36 {
  37     if (nPos >= vout.size() || vout[nPos].IsNull())
  38         return false;
  39     vout[nPos].SetNull();
  40     Cleanup();
  41     return true;
  42 }
  43 bool CCoinsView::GetAnchorAt(const uint256 &rt, libzerocash::IncrementalMerkleTree &tree) const { return false; }
  44 bool CCoinsView::GetSerial(const uint256 &serial) const { return false; }
  45 bool CCoinsView::GetCoins(const uint256 &txid, CCoins &coins) const { return false; }
  46 bool CCoinsView::HaveCoins(const uint256 &txid) const { return false; }
  47 uint256 CCoinsView::GetBestBlock() const { return uint256(); }
  48 uint256 CCoinsView::GetBestAnchor() const { return uint256(); };
  49 bool CCoinsView::BatchWrite(CCoinsMap &mapCoins,
  50                             const uint256 &hashBlock,
  51                             const uint256 &hashAnchor,
  52                             CAnchorsMap &mapAnchors,
  53                             CSerialsMap &mapSerials) { return false; }
  54 bool CCoinsView::GetStats(CCoinsStats &stats) const { return false; }
  55
  56
  57 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
  58
  59 bool CCoinsViewBacked::GetAnchorAt(const uint256 &rt, libzerocash::IncrementalMerkleTree &tree) const { return base->GetAnchorAt(rt, tree); }
  60 bool CCoinsViewBacked::GetSerial(const uint256 &serial) const { return base->GetSerial(serial); }
  61 bool CCoinsViewBacked::GetCoins(const uint256 &txid, CCoins &coins) const { return base->GetCoins(txid, coins); }
  62 bool CCoinsViewBacked::HaveCoins(const uint256 &txid) const { return base->HaveCoins(txid); }
  63 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
  64 uint256 CCoinsViewBacked::GetBestAnchor() const { return base->GetBestAnchor(); }
  65 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
  66 bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins,
  67                                   const uint256 &hashBlock,
  68                                   const uint256 &hashAnchor,
  69                                   CAnchorsMap &mapAnchors,
  70                                   CSerialsMap &mapSerials) { return base->BatchWrite(mapCoins, hashBlock, hashAnchor, mapAnchors, mapSerials); }
  71 bool CCoinsViewBacked::GetStats(CCoinsStats &stats) const { return base->GetStats(stats); }
  72
  73 CCoinsKeyHasher::CCoinsKeyHasher() : salt(GetRandHash()) {}
  74
  75 CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), hasModifier(false), cachedCoinsUsage(0) { }
  76
  77 CCoinsViewCache::~CCoinsViewCache()
  78 {
  79     assert(!hasModifier);
  80 }
  81
  82 size_t CCoinsViewCache::DynamicMemoryUsage() const {
  83     return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
  84 }
  85
  86 CCoinsMap::const_iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
  87     CCoinsMap::iterator it = cacheCoins.find(txid);
  88     if (it != cacheCoins.end())
  89         return it;
  90     CCoins tmp;
  91     if (!base->GetCoins(txid, tmp))
  92         return cacheCoins.end();
  93     CCoinsMap::iterator ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())).first;
  94     tmp.swap(ret->second.coins);
  95     if (ret->second.coins.IsPruned()) {
  96         // The parent only has an empty entry for this txid; we can consider our
  97         // version as fresh.
  98         ret->second.flags = CCoinsCacheEntry::FRESH;
  99     }
 100     cachedCoinsUsage += memusage::DynamicUsage(ret->second.coins);
 101     return ret;
 102 }
 103
 104
 105 bool CCoinsViewCache::GetAnchorAt(const uint256 &rt, libzerocash::IncrementalMerkleTree &tree) const {
 106     CAnchorsMap::const_iterator it = cacheAnchors.find(rt);
 107     if (it != cacheAnchors.end()) {
 108         if (it->second.entered) {
 109             tree.setTo(it->second.tree);
 110             return true;
 111         } else {
 112             return false;
 113         }
 114     }
 115
 116     CAnchorsCacheEntry entry;
 117     if (!base->GetAnchorAt(rt, tree)) {
 118         return false;
 119     }
 120
 121     entry.entered = true;
 122     entry.tree.setTo(tree);
 123     cacheAnchors.insert(std::make_pair(rt, entry));
 124
 125     return true;
 126 }
 127
 128 bool CCoinsViewCache::GetSerial(const uint256 &serial) const {
 129     CSerialsMap::iterator it = cacheSerials.find(serial);
 130     if (it != cacheSerials.end())
 131         return it->second.entered;
 132
 133     CSerialsCacheEntry entry;
 134     bool tmp = base->GetSerial(serial);
 135     entry.entered = tmp;
 136
 137     cacheSerials.insert(std::make_pair(serial, entry));
 138
 139     // TODO: cache usage
 140
 141     return tmp;
 142 }
 143
 144 void CCoinsViewCache::PushAnchor(const libzerocash::IncrementalMerkleTree &tree) {
 145     std::vector<unsigned char> newrt_v(32);
 146     tree.getRootValue(newrt_v);
 147     uint256 newrt(newrt_v);
 148
 149     auto currentRoot = GetBestAnchor();
 150
 151     // We don't want to overwrite an anchor we already have.
 152     // This occurs when a block doesn't modify mapAnchors at all,
 153     // because there are no pours. We could get around this a
 154     // different way (make all blocks modify mapAnchors somehow)
 155     // but this is simpler to reason about.
 156     if (currentRoot != newrt) {
 157         CAnchorsMap::iterator ret = cacheAnchors.insert(std::make_pair(newrt, CAnchorsCacheEntry())).first;
 158
 159         ret->second.entered = true;
 160         ret->second.tree.setTo(tree);
 161         ret->second.flags = CAnchorsCacheEntry::DIRTY;
 162
 163         hashAnchor = newrt;
 164     }
 165 }
 166
 167 void CCoinsViewCache::PopAnchor(const uint256 &newrt) {
 168     auto currentRoot = GetBestAnchor();
 169
 170     // Blocks might not change the commitment tree, in which
 171     // case restoring the "old" anchor during a reorg must
 172     // have no effect.
 173     if (currentRoot != newrt) {
 174         CAnchorsMap::iterator ret = cacheAnchors.insert(std::make_pair(currentRoot, CAnchorsCacheEntry())).first;
 175
 176         ret->second.entered = false;
 177         ret->second.flags = CAnchorsCacheEntry::DIRTY;
 178
 179         hashAnchor = newrt;
 180     }
 181 }
 182
 183 void CCoinsViewCache::SetSerial(const uint256 &serial, bool spent) {
 184     std::pair<CSerialsMap::iterator, bool> ret = cacheSerials.insert(std::make_pair(serial, CSerialsCacheEntry()));
 185     ret.first->second.entered = spent;
 186     ret.first->second.flags |= CSerialsCacheEntry::DIRTY;
 187 }
 188
 189 bool CCoinsViewCache::GetCoins(const uint256 &txid, CCoins &coins) const {
 190     CCoinsMap::const_iterator it = FetchCoins(txid);
 191     if (it != cacheCoins.end()) {
 192         coins = it->second.coins;
 193         return true;
 194     }
 195     return false;
 196 }
 197
 198 CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) {
 199     assert(!hasModifier);
 200     std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry()));
 201     size_t cachedCoinUsage = 0;
 202     if (ret.second) {
 203         if (!base->GetCoins(txid, ret.first->second.coins)) {
 204             // The parent view does not have this entry; mark it as fresh.
 205             ret.first->second.coins.Clear();
 206             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 207         } else if (ret.first->second.coins.IsPruned()) {
 208             // The parent view only has a pruned entry for this; mark it as fresh.
 209             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 210         }
 211     } else {
 212         cachedCoinUsage = memusage::DynamicUsage(ret.first->second.coins);
 213     }
 214     // Assume that whenever ModifyCoins is called, the entry will be modified.
 215     ret.first->second.flags |= CCoinsCacheEntry::DIRTY;
 216     return CCoinsModifier(*this, ret.first, cachedCoinUsage);
 217 }
 218
 219 const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
 220     CCoinsMap::const_iterator it = FetchCoins(txid);
 221     if (it == cacheCoins.end()) {
 222         return NULL;
 223     } else {
 224         return &it->second.coins;
 225     }
 226 }
 227
 228 bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
 229     CCoinsMap::const_iterator it = FetchCoins(txid);
 230     // We're using vtx.empty() instead of IsPruned here for performance reasons,
 231     // as we only care about the case where a transaction was replaced entirely
 232     // in a reorganization (which wipes vout entirely, as opposed to spending
 233     // which just cleans individual outputs).
 234     return (it != cacheCoins.end() && !it->second.coins.vout.empty());
 235 }
 236
 237 uint256 CCoinsViewCache::GetBestBlock() const {
 238     if (hashBlock.IsNull())
 239         hashBlock = base->GetBestBlock();
 240     return hashBlock;
 241 }
 242
 243
 244 uint256 CCoinsViewCache::GetBestAnchor() const {
 245     if (hashAnchor.IsNull())
 246         hashAnchor = base->GetBestAnchor();
 247     return hashAnchor;
 248 }
 249
 250 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
 251     hashBlock = hashBlockIn;
 252 }
 253
 254 bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins,
 255                                  const uint256 &hashBlockIn,
 256                                  const uint256 &hashAnchorIn,
 257                                  CAnchorsMap &mapAnchors,
 258                                  CSerialsMap &mapSerials) {
 259     assert(!hasModifier);
 260     for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end();) {
 261         if (it->second.flags & CCoinsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 262             CCoinsMap::iterator itUs = cacheCoins.find(it->first);
 263             if (itUs == cacheCoins.end()) {
 264                 if (!it->second.coins.IsPruned()) {
 265                     // The parent cache does not have an entry, while the child
 266                     // cache does have (a non-pruned) one. Move the data up, and
 267                     // mark it as fresh (if the grandparent did have it, we
 268                     // would have pulled it in at first GetCoins).
 269                     assert(it->second.flags & CCoinsCacheEntry::FRESH);
 270                     CCoinsCacheEntry& entry = cacheCoins[it->first];
 271                     entry.coins.swap(it->second.coins);
 272                     cachedCoinsUsage += memusage::DynamicUsage(entry.coins);
 273                     entry.flags = CCoinsCacheEntry::DIRTY | CCoinsCacheEntry::FRESH;
 274                 }
 275             } else {
 276                 if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 277                     // The grandparent does not have an entry, and the child is
 278                     // modified and being pruned. This means we can just delete
 279                     // it from the parent.
 280                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 281                     cacheCoins.erase(itUs);
 282                 } else {
 283                     // A normal modification.
 284                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 285                     itUs->second.coins.swap(it->second.coins);
 286                     cachedCoinsUsage += memusage::DynamicUsage(itUs->second.coins);
 287                     itUs->second.flags |= CCoinsCacheEntry::DIRTY;
 288                 }
 289             }
 290         }
 291         CCoinsMap::iterator itOld = it++;
 292         mapCoins.erase(itOld);
 293     }
 294
 295     for (CAnchorsMap::iterator child_it = mapAnchors.begin(); child_it != mapAnchors.end();)
 296     {
 297         if (child_it->second.flags & CAnchorsCacheEntry::DIRTY) {
 298             CAnchorsMap::iterator parent_it = cacheAnchors.find(child_it->first);
 299
 300             if (parent_it == cacheAnchors.end()) {
 301                 if (child_it->second.entered) {
 302                     // Parent doesn't have an entry, but child has a new commitment root.
 303
 304                     CAnchorsCacheEntry& entry = cacheAnchors[child_it->first];
 305                     entry.entered = true;
 306                     entry.tree.setTo(child_it->second.tree);
 307                     entry.flags = CAnchorsCacheEntry::DIRTY;
 308
 309                     // TODO: cache usage
 310                 }
 311             } else {
 312                 if (parent_it->second.entered != child_it->second.entered) {
 313                     // The parent may have removed the entry.
 314                     parent_it->second.entered = child_it->second.entered;
 315                     parent_it->second.flags |= CAnchorsCacheEntry::DIRTY;
 316                 }
 317             }
 318         }
 319
 320         CAnchorsMap::iterator itOld = child_it++;
 321         mapAnchors.erase(itOld);
 322     }
 323
 324     for (CSerialsMap::iterator child_it = mapSerials.begin(); child_it != mapSerials.end();)
 325     {
 326         if (child_it->second.flags & CSerialsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 327             CSerialsMap::iterator parent_it = cacheSerials.find(child_it->first);
 328
 329             if (parent_it == cacheSerials.end()) {
 330                 if (child_it->second.entered) {
 331                     // Parent doesn't have an entry, but child has a SPENT serial.
 332                     // Move the spent serial up.
 333
 334                     CSerialsCacheEntry& entry = cacheSerials[child_it->first];
 335                     entry.entered = true;
 336                     entry.flags = CSerialsCacheEntry::DIRTY;
 337
 338                     // TODO: cache usage
 339                 }
 340             } else {
 341                 if (parent_it->second.entered != child_it->second.entered) {
 342                     parent_it->second.entered = child_it->second.entered;
 343                     parent_it->second.flags |= CSerialsCacheEntry::DIRTY;
 344                 }
 345             }
 346         }
 347         CSerialsMap::iterator itOld = child_it++;
 348         mapSerials.erase(itOld);
 349     }
 350
 351     hashAnchor = hashAnchorIn;
 352     hashBlock = hashBlockIn;
 353     return true;
 354 }
 355
 356 bool CCoinsViewCache::Flush() {
 357     bool fOk = base->BatchWrite(cacheCoins, hashBlock, hashAnchor, cacheAnchors, cacheSerials);
 358     cacheCoins.clear();
 359     cacheAnchors.clear();
 360     cacheSerials.clear();
 361     cachedCoinsUsage = 0;
 362     return fOk;
 363 }
 364
 365 unsigned int CCoinsViewCache::GetCacheSize() const {
 366     return cacheCoins.size();
 367 }
 368
 369 const CTxOut &CCoinsViewCache::GetOutputFor(const CTxIn& input) const
 370 {
 371     const CCoins* coins = AccessCoins(input.prevout.hash);
 372     assert(coins && coins->IsAvailable(input.prevout.n));
 373     return coins->vout[input.prevout.n];
 374 }
 375
 376 CAmount CCoinsViewCache::GetValueIn(const CTransaction& tx) const
 377 {
 378     if (tx.IsCoinBase())
 379         return 0;
 380
 381     CAmount nResult = 0;
 382     for (unsigned int i = 0; i < tx.vin.size(); i++)
 383         nResult += GetOutputFor(tx.vin[i]).nValue;
 384
 385     nResult += tx.GetPourValueIn();
 386
 387     return nResult;
 388 }
 389
 390 bool CCoinsViewCache::HavePourRequirements(const CTransaction& tx) const
 391 {
 392     BOOST_FOREACH(const CPourTx &pour, tx.vpour)
 393     {
 394         BOOST_FOREACH(const uint256& serial, pour.serials)
 395         {
 396             if (GetSerial(serial)) {
 397                 // If the serial is set, this transaction
 398                 // double-spends!
 399                 return false;
 400             }
 401         }
 402
 403         libzerocash::IncrementalMerkleTree tree(INCREMENTAL_MERKLE_TREE_DEPTH);
 404         if (!GetAnchorAt(pour.anchor, tree)) {
 405             // If we do not have the anchor for the pour,
 406             // it is invalid.
 407             return false;
 408         }
 409     }
 410
 411     return true;
 412 }
 413
 414 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
 415 {
 416     if (!tx.IsCoinBase()) {
 417         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 418             const COutPoint &prevout = tx.vin[i].prevout;
 419             const CCoins* coins = AccessCoins(prevout.hash);
 420             if (!coins || !coins->IsAvailable(prevout.n)) {
 421                 return false;
 422             }
 423         }
 424     }
 425     return true;
 426 }
 427
 428 double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight) const
 429 {
 430     if (tx.IsCoinBase())
 431         return 0.0;
 432     double dResult = 0.0;
 433     BOOST_FOREACH(const CTxIn& txin, tx.vin)
 434     {
 435         const CCoins* coins = AccessCoins(txin.prevout.hash);
 436         assert(coins);
 437         if (!coins->IsAvailable(txin.prevout.n)) continue;
 438         if (coins->nHeight < nHeight) {
 439             dResult += coins->vout[txin.prevout.n].nValue * (nHeight-coins->nHeight);
 440         }
 441     }
 442     return tx.ComputePriority(dResult);
 443 }
 444
 445 CCoinsModifier::CCoinsModifier(CCoinsViewCache& cache_, CCoinsMap::iterator it_, size_t usage) : cache(cache_), it(it_), cachedCoinUsage(usage) {
 446     assert(!cache.hasModifier);
 447     cache.hasModifier = true;
 448 }
 449
 450 CCoinsModifier::~CCoinsModifier()
 451 {
 452     assert(cache.hasModifier);
 453     cache.hasModifier = false;
 454     it->second.coins.Cleanup();
 455     cache.cachedCoinsUsage -= cachedCoinUsage; // Subtract the old usage
 456     if ((it->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 457         cache.cacheCoins.erase(it);
 458     } else {
 459         // If the coin still exists after the modification, add the new usage
 460         cache.cachedCoinsUsage += memusage::DynamicUsage(it->second.coins);
 461     }
 462 }