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 #include "version.h"
  10
  11 #include <assert.h>
  12
  13 /**
  14  * calculate number of bytes for the bitmask, and its number of non-zero bytes
  15  * each bit in the bitmask represents the availability of one output, but the
  16  * availabilities of the first two outputs are encoded separately
  17  */
  18 void CCoins::CalcMaskSize(unsigned int &nBytes, unsigned int &nNonzeroBytes) const {
  19     unsigned int nLastUsedByte = 0;
  20     for (unsigned int b = 0; 2+b*8 < vout.size(); b++) {
  21         bool fZero = true;
  22         for (unsigned int i = 0; i < 8 && 2+b*8+i < vout.size(); i++) {
  23             if (!vout[2+b*8+i].IsNull()) {
  24                 fZero = false;
  25                 continue;
  26             }
  27         }
  28         if (!fZero) {
  29             nLastUsedByte = b + 1;
  30             nNonzeroBytes++;
  31         }
  32     }
  33     nBytes += nLastUsedByte;
  34 }
  35
  36 bool CCoins::Spend(uint32_t nPos)
  37 {
  38     if (nPos >= vout.size() || vout[nPos].IsNull())
  39         return false;
  40     vout[nPos].SetNull();
  41     Cleanup();
  42     return true;
  43 }
  44 bool CCoinsView::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const { return false; }
  45 bool CCoinsView::GetNullifier(const uint256 &nullifier) const { return false; }
  46 bool CCoinsView::GetCoins(const uint256 &txid, CCoins &coins) const { return false; }
  47 bool CCoinsView::HaveCoins(const uint256 &txid) const { return false; }
  48 uint256 CCoinsView::GetBestBlock() const { return uint256(); }
  49 uint256 CCoinsView::GetBestAnchor() const { return uint256(); };
  50 bool CCoinsView::BatchWrite(CCoinsMap &mapCoins,
  51                             const uint256 &hashBlock,
  52                             const uint256 &hashAnchor,
  53                             CAnchorsMap &mapAnchors,
  54                             CNullifiersMap &mapNullifiers) { return false; }
  55 bool CCoinsView::GetStats(CCoinsStats &stats) const { return false; }
  56
  57
  58 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
  59
  60 bool CCoinsViewBacked::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const { return base->GetAnchorAt(rt, tree); }
  61 bool CCoinsViewBacked::GetNullifier(const uint256 &nullifier) const { return base->GetNullifier(nullifier); }
  62 bool CCoinsViewBacked::GetCoins(const uint256 &txid, CCoins &coins) const { return base->GetCoins(txid, coins); }
  63 bool CCoinsViewBacked::HaveCoins(const uint256 &txid) const { return base->HaveCoins(txid); }
  64 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
  65 uint256 CCoinsViewBacked::GetBestAnchor() const { return base->GetBestAnchor(); }
  66 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
  67 bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins,
  68                                   const uint256 &hashBlock,
  69                                   const uint256 &hashAnchor,
  70                                   CAnchorsMap &mapAnchors,
  71                                   CNullifiersMap &mapNullifiers) { return base->BatchWrite(mapCoins, hashBlock, hashAnchor, mapAnchors, mapNullifiers); }
  72 bool CCoinsViewBacked::GetStats(CCoinsStats &stats) const { return base->GetStats(stats); }
  73
  74 CCoinsKeyHasher::CCoinsKeyHasher() : salt(GetRandHash()) {}
  75
  76 CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), hasModifier(false), cachedCoinsUsage(0) { }
  77
  78 CCoinsViewCache::~CCoinsViewCache()
  79 {
  80     assert(!hasModifier);
  81 }
  82
  83 size_t CCoinsViewCache::DynamicMemoryUsage() const {
  84     return memusage::DynamicUsage(cacheCoins) +
  85            memusage::DynamicUsage(cacheAnchors) +
  86            memusage::DynamicUsage(cacheNullifiers) +
  87            cachedCoinsUsage;
  88 }
  89
  90 CCoinsMap::const_iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
  91     CCoinsMap::iterator it = cacheCoins.find(txid);
  92     if (it != cacheCoins.end())
  93         return it;
  94     CCoins tmp;
  95     if (!base->GetCoins(txid, tmp))
  96         return cacheCoins.end();
  97     CCoinsMap::iterator ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())).first;
  98     tmp.swap(ret->second.coins);
  99     if (ret->second.coins.IsPruned()) {
 100         // The parent only has an empty entry for this txid; we can consider our
 101         // version as fresh.
 102         ret->second.flags = CCoinsCacheEntry::FRESH;
 103     }
 104     cachedCoinsUsage += memusage::DynamicUsage(ret->second.coins);
 105     return ret;
 106 }
 107
 108
 109 bool CCoinsViewCache::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const {
 110     CAnchorsMap::const_iterator it = cacheAnchors.find(rt);
 111     if (it != cacheAnchors.end()) {
 112         if (it->second.entered) {
 113             tree = it->second.tree;
 114             return true;
 115         } else {
 116             return false;
 117         }
 118     }
 119
 120     if (!base->GetAnchorAt(rt, tree)) {
 121         return false;
 122     }
 123
 124     CAnchorsMap::iterator ret = cacheAnchors.insert(std::make_pair(rt, CAnchorsCacheEntry())).first;
 125     ret->second.entered = true;
 126     ret->second.tree = tree;
 127     cachedCoinsUsage += memusage::DynamicUsage(ret->second.tree);
 128
 129     return true;
 130 }
 131
 132 bool CCoinsViewCache::GetNullifier(const uint256 &nullifier) const {
 133     CNullifiersMap::iterator it = cacheNullifiers.find(nullifier);
 134     if (it != cacheNullifiers.end())
 135         return it->second.entered;
 136
 137     CNullifiersCacheEntry entry;
 138     bool tmp = base->GetNullifier(nullifier);
 139     entry.entered = tmp;
 140
 141     cacheNullifiers.insert(std::make_pair(nullifier, entry));
 142
 143     return tmp;
 144 }
 145
 146 void CCoinsViewCache::PushAnchor(const ZCIncrementalMerkleTree &tree) {
 147     uint256 newrt = tree.root();
 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 joinsplits. 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         auto insertRet = cacheAnchors.insert(std::make_pair(newrt, CAnchorsCacheEntry()));
 158         CAnchorsMap::iterator ret = insertRet.first;
 159
 160         ret->second.entered = true;
 161         ret->second.tree = tree;
 162         ret->second.flags = CAnchorsCacheEntry::DIRTY;
 163
 164         if (insertRet.second) {
 165             // An insert took place
 166             cachedCoinsUsage += memusage::DynamicUsage(ret->second.tree);
 167         }
 168
 169         hashAnchor = newrt;
 170     }
 171 }
 172
 173 void CCoinsViewCache::PopAnchor(const uint256 &newrt) {
 174     auto currentRoot = GetBestAnchor();
 175
 176     // Blocks might not change the commitment tree, in which
 177     // case restoring the "old" anchor during a reorg must
 178     // have no effect.
 179     if (currentRoot != newrt) {
 180         // Bring the current best anchor into our local cache
 181         // so that its tree exists in memory.
 182         {
 183             ZCIncrementalMerkleTree tree;
 184             assert(GetAnchorAt(currentRoot, tree));
 185         }
 186
 187         // Mark the anchor as unentered, removing it from view
 188         cacheAnchors[currentRoot].entered = false;
 189
 190         // Mark the cache entry as dirty so it's propagated
 191         cacheAnchors[currentRoot].flags = CAnchorsCacheEntry::DIRTY;
 192
 193         // Mark the new root as the best anchor
 194         hashAnchor = newrt;
 195     }
 196 }
 197
 198 void CCoinsViewCache::SetNullifier(const uint256 &nullifier, bool spent) {
 199     std::pair<CNullifiersMap::iterator, bool> ret = cacheNullifiers.insert(std::make_pair(nullifier, CNullifiersCacheEntry()));
 200     ret.first->second.entered = spent;
 201     ret.first->second.flags |= CNullifiersCacheEntry::DIRTY;
 202 }
 203
 204 bool CCoinsViewCache::GetCoins(const uint256 &txid, CCoins &coins) const {
 205     CCoinsMap::const_iterator it = FetchCoins(txid);
 206     if (it != cacheCoins.end()) {
 207         coins = it->second.coins;
 208         return true;
 209     }
 210     return false;
 211 }
 212
 213 CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) {
 214     assert(!hasModifier);
 215     std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry()));
 216     size_t cachedCoinUsage = 0;
 217     if (ret.second) {
 218         if (!base->GetCoins(txid, ret.first->second.coins)) {
 219             // The parent view does not have this entry; mark it as fresh.
 220             ret.first->second.coins.Clear();
 221             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 222         } else if (ret.first->second.coins.IsPruned()) {
 223             // The parent view only has a pruned entry for this; mark it as fresh.
 224             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 225         }
 226     } else {
 227         cachedCoinUsage = memusage::DynamicUsage(ret.first->second.coins);
 228     }
 229     // Assume that whenever ModifyCoins is called, the entry will be modified.
 230     ret.first->second.flags |= CCoinsCacheEntry::DIRTY;
 231     return CCoinsModifier(*this, ret.first, cachedCoinUsage);
 232 }
 233
 234 const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
 235     CCoinsMap::const_iterator it = FetchCoins(txid);
 236     if (it == cacheCoins.end()) {
 237         return NULL;
 238     } else {
 239         return &it->second.coins;
 240     }
 241 }
 242
 243 bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
 244     CCoinsMap::const_iterator it = FetchCoins(txid);
 245     // We're using vtx.empty() instead of IsPruned here for performance reasons,
 246     // as we only care about the case where a transaction was replaced entirely
 247     // in a reorganization (which wipes vout entirely, as opposed to spending
 248     // which just cleans individual outputs).
 249     return (it != cacheCoins.end() && !it->second.coins.vout.empty());
 250 }
 251
 252 uint256 CCoinsViewCache::GetBestBlock() const {
 253     if (hashBlock.IsNull())
 254         hashBlock = base->GetBestBlock();
 255     return hashBlock;
 256 }
 257
 258
 259 uint256 CCoinsViewCache::GetBestAnchor() const {
 260     if (hashAnchor.IsNull())
 261         hashAnchor = base->GetBestAnchor();
 262     return hashAnchor;
 263 }
 264
 265 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
 266     hashBlock = hashBlockIn;
 267 }
 268
 269 bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins,
 270                                  const uint256 &hashBlockIn,
 271                                  const uint256 &hashAnchorIn,
 272                                  CAnchorsMap &mapAnchors,
 273                                  CNullifiersMap &mapNullifiers) {
 274     assert(!hasModifier);
 275     for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end();) {
 276         if (it->second.flags & CCoinsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 277             CCoinsMap::iterator itUs = cacheCoins.find(it->first);
 278             if (itUs == cacheCoins.end()) {
 279                 if (!it->second.coins.IsPruned()) {
 280                     // The parent cache does not have an entry, while the child
 281                     // cache does have (a non-pruned) one. Move the data up, and
 282                     // mark it as fresh (if the grandparent did have it, we
 283                     // would have pulled it in at first GetCoins).
 284                     assert(it->second.flags & CCoinsCacheEntry::FRESH);
 285                     CCoinsCacheEntry& entry = cacheCoins[it->first];
 286                     entry.coins.swap(it->second.coins);
 287                     cachedCoinsUsage += memusage::DynamicUsage(entry.coins);
 288                     entry.flags = CCoinsCacheEntry::DIRTY | CCoinsCacheEntry::FRESH;
 289                 }
 290             } else {
 291                 if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 292                     // The grandparent does not have an entry, and the child is
 293                     // modified and being pruned. This means we can just delete
 294                     // it from the parent.
 295                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 296                     cacheCoins.erase(itUs);
 297                 } else {
 298                     // A normal modification.
 299                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 300                     itUs->second.coins.swap(it->second.coins);
 301                     cachedCoinsUsage += memusage::DynamicUsage(itUs->second.coins);
 302                     itUs->second.flags |= CCoinsCacheEntry::DIRTY;
 303                 }
 304             }
 305         }
 306         CCoinsMap::iterator itOld = it++;
 307         mapCoins.erase(itOld);
 308     }
 309
 310     for (CAnchorsMap::iterator child_it = mapAnchors.begin(); child_it != mapAnchors.end();)
 311     {
 312         if (child_it->second.flags & CAnchorsCacheEntry::DIRTY) {
 313             CAnchorsMap::iterator parent_it = cacheAnchors.find(child_it->first);
 314
 315             if (parent_it == cacheAnchors.end()) {
 316                 CAnchorsCacheEntry& entry = cacheAnchors[child_it->first];
 317                 entry.entered = child_it->second.entered;
 318                 entry.tree = child_it->second.tree;
 319                 entry.flags = CAnchorsCacheEntry::DIRTY;
 320
 321                 cachedCoinsUsage += memusage::DynamicUsage(entry.tree);
 322             } else {
 323                 if (parent_it->second.entered != child_it->second.entered) {
 324                     // The parent may have removed the entry.
 325                     parent_it->second.entered = child_it->second.entered;
 326                     parent_it->second.flags |= CAnchorsCacheEntry::DIRTY;
 327                 }
 328             }
 329         }
 330
 331         CAnchorsMap::iterator itOld = child_it++;
 332         mapAnchors.erase(itOld);
 333     }
 334
 335     for (CNullifiersMap::iterator child_it = mapNullifiers.begin(); child_it != mapNullifiers.end();)
 336     {
 337         if (child_it->second.flags & CNullifiersCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 338             CNullifiersMap::iterator parent_it = cacheNullifiers.find(child_it->first);
 339
 340             if (parent_it == cacheNullifiers.end()) {
 341                 CNullifiersCacheEntry& entry = cacheNullifiers[child_it->first];
 342                 entry.entered = child_it->second.entered;
 343                 entry.flags = CNullifiersCacheEntry::DIRTY;
 344             } else {
 345                 if (parent_it->second.entered != child_it->second.entered) {
 346                     parent_it->second.entered = child_it->second.entered;
 347                     parent_it->second.flags |= CNullifiersCacheEntry::DIRTY;
 348                 }
 349             }
 350         }
 351         CNullifiersMap::iterator itOld = child_it++;
 352         mapNullifiers.erase(itOld);
 353     }
 354
 355     hashAnchor = hashAnchorIn;
 356     hashBlock = hashBlockIn;
 357     return true;
 358 }
 359
 360 bool CCoinsViewCache::Flush() {
 361     bool fOk = base->BatchWrite(cacheCoins, hashBlock, hashAnchor, cacheAnchors, cacheNullifiers);
 362     cacheCoins.clear();
 363     cacheAnchors.clear();
 364     cacheNullifiers.clear();
 365     cachedCoinsUsage = 0;
 366     return fOk;
 367 }
 368
 369 unsigned int CCoinsViewCache::GetCacheSize() const {
 370     return cacheCoins.size();
 371 }
 372
 373 const CTxOut &CCoinsViewCache::GetOutputFor(const CTxIn& input) const
 374 {
 375     const CCoins* coins = AccessCoins(input.prevout.hash);
 376     assert(coins && coins->IsAvailable(input.prevout.n));
 377     return coins->vout[input.prevout.n];
 378 }
 379
 380 CAmount CCoinsViewCache::GetValueIn(const CTransaction& tx) const
 381 {
 382     if (tx.IsCoinBase())
 383         return 0;
 384
 385     CAmount nResult = 0;
 386     for (unsigned int i = 0; i < tx.vin.size(); i++)
 387         nResult += GetOutputFor(tx.vin[i]).nValue;
 388
 389     nResult += tx.GetJoinSplitValueIn();
 390
 391     return nResult;
 392 }
 393
 394 bool CCoinsViewCache::HaveJoinSplitRequirements(const CTransaction& tx) const
 395 {
 396     boost::unordered_map<uint256, ZCIncrementalMerkleTree, CCoinsKeyHasher> intermediates;
 397
 398     BOOST_FOREACH(const JSDescription &joinsplit, tx.vjoinsplit)
 399     {
 400         BOOST_FOREACH(const uint256& nullifier, joinsplit.nullifiers)
 401         {
 402             if (GetNullifier(nullifier)) {
 403                 // If the nullifier is set, this transaction
 404                 // double-spends!
 405                 return false;
 406             }
 407         }
 408
 409         ZCIncrementalMerkleTree tree;
 410         auto it = intermediates.find(joinsplit.anchor);
 411         if (it != intermediates.end()) {
 412             tree = it->second;
 413         } else if (!GetAnchorAt(joinsplit.anchor, tree)) {
 414             return false;
 415         }
 416
 417         BOOST_FOREACH(const uint256& commitment, joinsplit.commitments)
 418         {
 419             tree.append(commitment);
 420         }
 421
 422         intermediates.insert(std::make_pair(tree.root(), tree));
 423     }
 424
 425     return true;
 426 }
 427
 428 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
 429 {
 430     if (!tx.IsCoinBase()) {
 431         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 432             const COutPoint &prevout = tx.vin[i].prevout;
 433             const CCoins* coins = AccessCoins(prevout.hash);
 434             if (!coins || !coins->IsAvailable(prevout.n)) {
 435                 return false;
 436             }
 437         }
 438     }
 439     return true;
 440 }
 441
 442 double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight) const
 443 {
 444     if (tx.IsCoinBase())
 445         return 0.0;
 446     CAmount nTotalIn = 0;
 447     double dResult = 0.0;
 448     BOOST_FOREACH(const CTxIn& txin, tx.vin)
 449     {
 450         const CCoins* coins = AccessCoins(txin.prevout.hash);
 451         assert(coins);
 452         if (!coins->IsAvailable(txin.prevout.n)) continue;
 453         if (coins->nHeight < nHeight) {
 454             dResult += coins->vout[txin.prevout.n].nValue * (nHeight-coins->nHeight);
 455             nTotalIn += coins->vout[txin.prevout.n].nValue;
 456         }
 457     }
 458
 459     // If a transaction contains a joinsplit, we boost the priority of the transaction.
 460     // Joinsplits do not reveal any information about the value or age of a note, so we
 461     // cannot apply the priority algorithm used for transparent utxos.  Instead, we pick a
 462     // very large number and multiply it by the transaction's fee per 1000 bytes of data.
 463     // One trillion, 1000000000000, is equivalent to 1 ZEC utxo * 10000 blocks (~17 days).
 464     if (tx.vjoinsplit.size() > 0) {
 465         unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
 466         nTotalIn += tx.GetJoinSplitValueIn();
 467         CAmount fee = nTotalIn - tx.GetValueOut();
 468         CFeeRate feeRate(fee, nTxSize);
 469         CAmount feePerK = feeRate.GetFeePerK();
 470
 471         if (feePerK == 0) {
 472             feePerK = 1;
 473         }
 474
 475         dResult += 1000000000000 * double(feePerK);
 476         // We cast feePerK from int64_t to double because if feePerK is a large number, say
 477         // close to MAX_MONEY, the multiplication operation will result in an integer overflow.
 478         // The variable dResult should never overflow since a 64-bit double in C++ is typically
 479         // a double-precision floating-point number as specified by IEE 754, with a maximum
 480         // value DBL_MAX of 1.79769e+308.
 481     }
 482
 483     return tx.ComputePriority(dResult);
 484 }
 485
 486 CCoinsModifier::CCoinsModifier(CCoinsViewCache& cache_, CCoinsMap::iterator it_, size_t usage) : cache(cache_), it(it_), cachedCoinUsage(usage) {
 487     assert(!cache.hasModifier);
 488     cache.hasModifier = true;
 489 }
 490
 491 CCoinsModifier::~CCoinsModifier()
 492 {
 493     assert(cache.hasModifier);
 494     cache.hasModifier = false;
 495     it->second.coins.Cleanup();
 496     cache.cachedCoinsUsage -= cachedCoinUsage; // Subtract the old usage
 497     if ((it->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 498         cache.cacheCoins.erase(it);
 499     } else {
 500         // If the coin still exists after the modification, add the new usage
 501         cache.cachedCoinsUsage += memusage::DynamicUsage(it->second.coins);
 502     }
 503 }