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