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