1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2018 The Bitcoin Core developers 3 // Distributed under the MIT software license, see the accompanying 4 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 6 #ifndef BITCOIN_COINS_H 7 #define BITCOIN_COINS_H 8 9 #include <primitives/transaction.h> 10 #include <compressor.h> 11 #include <core_memusage.h> 12 #include <crypto/siphash.h> 13 #include <memusage.h> 14 #include <serialize.h> 15 #include <uint256.h> 16 17 #include <assert.h> 18 #include <stdint.h> 19 20 #include <unordered_map> 21 22 /** 23 * A UTXO entry. 24 * 25 * Serialized format: 26 * - VARINT((coinbase ? 1 : 0) | (height << 1)) 27 * - the non-spent CTxOut (via CTxOutCompressor) 28 */ 29 class Coin 30 { 31 public: 32 //! unspent transaction output 33 CTxOut out; 34 35 //! whether containing transaction was a coinbase 36 unsigned int fCoinBase : 1; 37 38 //! at which height this containing transaction was included in the active block chain 39 uint32_t nHeight : 31; 40 41 //! construct a Coin from a CTxOut and height/coinbase information. Coin(CTxOut && outIn,int nHeightIn,bool fCoinBaseIn)42 Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {} Coin(const CTxOut & outIn,int nHeightIn,bool fCoinBaseIn)43 Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {} 44 Clear()45 void Clear() { 46 out.SetNull(); 47 fCoinBase = false; 48 nHeight = 0; 49 } 50 51 //! empty constructor Coin()52 Coin() : fCoinBase(false), nHeight(0) { } 53 IsCoinBase()54 bool IsCoinBase() const { 55 return fCoinBase; 56 } 57 58 template<typename Stream> Serialize(Stream & s)59 void Serialize(Stream &s) const { 60 assert(!IsSpent()); 61 uint32_t code = nHeight * 2 + fCoinBase; 62 ::Serialize(s, VARINT(code)); 63 ::Serialize(s, CTxOutCompressor(REF(out))); 64 } 65 66 template<typename Stream> Unserialize(Stream & s)67 void Unserialize(Stream &s) { 68 uint32_t code = 0; 69 ::Unserialize(s, VARINT(code)); 70 nHeight = code >> 1; 71 fCoinBase = code & 1; 72 ::Unserialize(s, CTxOutCompressor(out)); 73 } 74 IsSpent()75 bool IsSpent() const { 76 return out.IsNull(); 77 } 78 DynamicMemoryUsage()79 size_t DynamicMemoryUsage() const { 80 return memusage::DynamicUsage(out.scriptPubKey); 81 } 82 }; 83 84 class SaltedOutpointHasher 85 { 86 private: 87 /** Salt */ 88 const uint64_t k0, k1; 89 90 public: 91 SaltedOutpointHasher(); 92 93 /** 94 * This *must* return size_t. With Boost 1.46 on 32-bit systems the 95 * unordered_map will behave unpredictably if the custom hasher returns a 96 * uint64_t, resulting in failures when syncing the chain (#4634). 97 */ operator()98 size_t operator()(const COutPoint& id) const { 99 return SipHashUint256Extra(k0, k1, id.hash, id.n); 100 } 101 }; 102 103 struct CCoinsCacheEntry 104 { 105 Coin coin; // The actual cached data. 106 unsigned char flags; 107 108 enum Flags { 109 DIRTY = (1 << 0), // This cache entry is potentially different from the version in the parent view. 110 FRESH = (1 << 1), // The parent view does not have this entry (or it is pruned). 111 /* Note that FRESH is a performance optimization with which we can 112 * erase coins that are fully spent if we know we do not need to 113 * flush the changes to the parent cache. It is always safe to 114 * not mark FRESH if that condition is not guaranteed. 115 */ 116 }; 117 CCoinsCacheEntryCCoinsCacheEntry118 CCoinsCacheEntry() : flags(0) {} CCoinsCacheEntryCCoinsCacheEntry119 explicit CCoinsCacheEntry(Coin&& coin_) : coin(std::move(coin_)), flags(0) {} 120 }; 121 122 typedef std::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher> CCoinsMap; 123 124 /** Cursor for iterating over CoinsView state */ 125 class CCoinsViewCursor 126 { 127 public: CCoinsViewCursor(const uint256 & hashBlockIn)128 CCoinsViewCursor(const uint256 &hashBlockIn): hashBlock(hashBlockIn) {} ~CCoinsViewCursor()129 virtual ~CCoinsViewCursor() {} 130 131 virtual bool GetKey(COutPoint &key) const = 0; 132 virtual bool GetValue(Coin &coin) const = 0; 133 virtual unsigned int GetValueSize() const = 0; 134 135 virtual bool Valid() const = 0; 136 virtual void Next() = 0; 137 138 //! Get best block at the time this cursor was created GetBestBlock()139 const uint256 &GetBestBlock() const { return hashBlock; } 140 private: 141 uint256 hashBlock; 142 }; 143 144 /** Abstract view on the open txout dataset. */ 145 class CCoinsView 146 { 147 public: 148 /** Retrieve the Coin (unspent transaction output) for a given outpoint. 149 * Returns true only when an unspent coin was found, which is returned in coin. 150 * When false is returned, coin's value is unspecified. 151 */ 152 virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const; 153 154 //! Just check whether a given outpoint is unspent. 155 virtual bool HaveCoin(const COutPoint &outpoint) const; 156 157 //! Retrieve the block hash whose state this CCoinsView currently represents 158 virtual uint256 GetBestBlock() const; 159 160 //! Retrieve the range of blocks that may have been only partially written. 161 //! If the database is in a consistent state, the result is the empty vector. 162 //! Otherwise, a two-element vector is returned consisting of the new and 163 //! the old block hash, in that order. 164 virtual std::vector<uint256> GetHeadBlocks() const; 165 166 //! Do a bulk modification (multiple Coin changes + BestBlock change). 167 //! The passed mapCoins can be modified. 168 virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock); 169 170 //! Get a cursor to iterate over the whole state 171 virtual CCoinsViewCursor *Cursor() const; 172 173 //! As we use CCoinsViews polymorphically, have a virtual destructor ~CCoinsView()174 virtual ~CCoinsView() {} 175 176 //! Estimate database size (0 if not implemented) EstimateSize()177 virtual size_t EstimateSize() const { return 0; } 178 }; 179 180 181 /** CCoinsView backed by another CCoinsView */ 182 class CCoinsViewBacked : public CCoinsView 183 { 184 protected: 185 CCoinsView *base; 186 187 public: 188 CCoinsViewBacked(CCoinsView *viewIn); 189 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 190 bool HaveCoin(const COutPoint &outpoint) const override; 191 uint256 GetBestBlock() const override; 192 std::vector<uint256> GetHeadBlocks() const override; 193 void SetBackend(CCoinsView &viewIn); 194 bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; 195 CCoinsViewCursor *Cursor() const override; 196 size_t EstimateSize() const override; 197 }; 198 199 200 /** CCoinsView that adds a memory cache for transactions to another CCoinsView */ 201 class CCoinsViewCache : public CCoinsViewBacked 202 { 203 protected: 204 /** 205 * Make mutable so that we can "fill the cache" even from Get-methods 206 * declared as "const". 207 */ 208 mutable uint256 hashBlock; 209 mutable CCoinsMap cacheCoins; 210 211 /* Cached dynamic memory usage for the inner Coin objects. */ 212 mutable size_t cachedCoinsUsage; 213 214 public: 215 CCoinsViewCache(CCoinsView *baseIn); 216 217 /** 218 * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache. 219 */ 220 CCoinsViewCache(const CCoinsViewCache &) = delete; 221 222 // Standard CCoinsView methods 223 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 224 bool HaveCoin(const COutPoint &outpoint) const override; 225 uint256 GetBestBlock() const override; 226 void SetBestBlock(const uint256 &hashBlock); 227 bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; Cursor()228 CCoinsViewCursor* Cursor() const override { 229 throw std::logic_error("CCoinsViewCache cursor iteration not supported."); 230 } 231 232 /** 233 * Check if we have the given utxo already loaded in this cache. 234 * The semantics are the same as HaveCoin(), but no calls to 235 * the backing CCoinsView are made. 236 */ 237 bool HaveCoinInCache(const COutPoint &outpoint) const; 238 239 /** 240 * Return a reference to Coin in the cache, or a pruned one if not found. This is 241 * more efficient than GetCoin. 242 * 243 * Generally, do not hold the reference returned for more than a short scope. 244 * While the current implementation allows for modifications to the contents 245 * of the cache while holding the reference, this behavior should not be relied 246 * on! To be safe, best to not hold the returned reference through any other 247 * calls to this cache. 248 */ 249 const Coin& AccessCoin(const COutPoint &output) const; 250 251 /** 252 * Add a coin. Set potential_overwrite to true if a non-pruned version may 253 * already exist. 254 */ 255 void AddCoin(const COutPoint& outpoint, Coin&& coin, bool potential_overwrite); 256 257 /** 258 * Spend a coin. Pass moveto in order to get the deleted data. 259 * If no unspent output exists for the passed outpoint, this call 260 * has no effect. 261 */ 262 bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr); 263 264 /** 265 * Push the modifications applied to this cache to its base. 266 * Failure to call this method before destruction will cause the changes to be forgotten. 267 * If false is returned, the state of this cache (and its backing view) will be undefined. 268 */ 269 bool Flush(); 270 271 /** 272 * Removes the UTXO with the given outpoint from the cache, if it is 273 * not modified. 274 */ 275 void Uncache(const COutPoint &outpoint); 276 277 //! Calculate the size of the cache (in number of transaction outputs) 278 unsigned int GetCacheSize() const; 279 280 //! Calculate the size of the cache (in bytes) 281 size_t DynamicMemoryUsage() const; 282 283 /** 284 * Amount of bitcoins coming in to a transaction 285 * Note that lightweight clients may not know anything besides the hash of previous transactions, 286 * so may not be able to calculate this. 287 * 288 * @param[in] tx transaction for which we are checking input total 289 * @return Sum of value of all inputs (scriptSigs) 290 */ 291 CAmount GetValueIn(const CTransaction& tx) const; 292 293 //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view 294 bool HaveInputs(const CTransaction& tx) const; 295 296 private: 297 CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const; 298 }; 299 300 //! Utility function to add all of a transaction's outputs to a cache. 301 //! When check is false, this assumes that overwrites are only possible for coinbase transactions. 302 //! When check is true, the underlying view may be queried to determine whether an addition is 303 //! an overwrite. 304 // TODO: pass in a boolean to limit these possible overwrites to known 305 // (pre-BIP34) cases. 306 void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false); 307 308 //! Utility function to find any unspent output with a given txid. 309 //! This function can be quite expensive because in the event of a transaction 310 //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK 311 //! lookups to database, so it should be used with care. 312 const Coin& AccessByTxid(const CCoinsViewCache& cache, const uint256& txid); 313 314 #endif // BITCOIN_COINS_H 315