1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-present 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_CHAIN_H
7 #define BITCOIN_CHAIN_H
8 9 #include <arith_uint256.h>
10 #include <consensus/params.h>
11 #include <flatfile.h>
12 #include <kernel/cs_main.h>
13 #include <primitives/block.h>
14 #include <serialize.h>
15 #include <sync.h>
16 #include <uint256.h>
17 #include <util/time.h>
18 19 #include <algorithm>
20 #include <cassert>
21 #include <cstdint>
22 #include <string>
23 #include <vector>
24 25 /**
26 * Maximum amount of time that a block timestamp is allowed to exceed the
27 * current time before the block will be accepted.
28 */
29 static constexpr int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60;
30 31 /**
32 * Timestamp window used as a grace period by code that compares external
33 * timestamps (such as timestamps passed to RPCs, or wallet key creation times)
34 * to block timestamps. This should be set at least as high as
35 * MAX_FUTURE_BLOCK_TIME.
36 */
37 static constexpr int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME;
38 //! Init values for CBlockIndex nSequenceId when loaded from disk
39 static constexpr int32_t SEQ_ID_BEST_CHAIN_FROM_DISK = 0;
40 static constexpr int32_t SEQ_ID_INIT_FROM_DISK = 1;
41 42 enum BlockStatus : uint32_t {
43 //! Unused.
44 BLOCK_VALID_UNKNOWN = 0,
45 46 //! Reserved (was BLOCK_VALID_HEADER).
47 BLOCK_VALID_RESERVED = 1,
48 49 //! All parent headers found, difficulty matches, timestamp >= median previous. Implies all parents
50 //! are also at least TREE.
51 BLOCK_VALID_TREE = 2,
52 53 /**
54 * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
55 * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS.
56 *
57 * If a block's validity is at least VALID_TRANSACTIONS, CBlockIndex::nTx will be set. If a block and all previous
58 * blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_TRANSACTIONS,
59 * CBlockIndex::m_chain_tx_count will be set.
60 */
61 BLOCK_VALID_TRANSACTIONS = 3,
62 63 //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
64 //! Implies all previous blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_CHAIN.
65 BLOCK_VALID_CHAIN = 4,
66 67 //! Scripts & signatures ok. Implies all previous blocks back to the genesis block or an assumeutxo snapshot block
68 //! are at least VALID_SCRIPTS.
69 BLOCK_VALID_SCRIPTS = 5,
70 71 //! All validity bits.
72 BLOCK_VALID_MASK = BLOCK_VALID_RESERVED | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
73 BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
74 75 BLOCK_HAVE_DATA = 8, //!< full block available in blk*.dat
76 BLOCK_HAVE_UNDO = 16, //!< undo data available in rev*.dat
77 BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
78 79 BLOCK_FAILED_VALID = 32, //!< stage after last reached validness failed
80 BLOCK_FAILED_CHILD = 64, //!< Unused flag that was previously set when descending from failed block
81 82 BLOCK_OPT_WITNESS = 128, //!< block data in blk*.dat was received with a witness-enforcing client
83 84 BLOCK_STATUS_RESERVED = 256, //!< Unused flag that was previously set on assumeutxo snapshot blocks and their
85 //!< ancestors before they were validated, and unset when they were validated.
86 };
87 88 /** The block chain is a tree shaped structure starting with the
89 * genesis block at the root, with each block potentially having multiple
90 * candidates to be the next block. A blockindex may have multiple pprev pointing
91 * to it, but at most one of them can be part of the currently active branch.
92 */
93 class CBlockIndex
94 {
95 public:
96 //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
97 const uint256* phashBlock{nullptr};
98 99 //! pointer to the index of the predecessor of this block
100 CBlockIndex* pprev{nullptr};
101 102 //! pointer to the index of some further predecessor of this block
103 CBlockIndex* pskip{nullptr};
104 105 //! height of the entry in the chain. The genesis block has height 0
106 int nHeight{0};
107 108 //! Which # file this block is stored in (blk?????.dat)
109 int nFile GUARDED_BY(::cs_main){0};
110 111 //! Byte offset within blk?????.dat where this block's data is stored
112 unsigned int nDataPos GUARDED_BY(::cs_main){0};
113 114 //! Byte offset within rev?????.dat where this block's undo data is stored
115 unsigned int nUndoPos GUARDED_BY(::cs_main){0};
116 117 //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
118 arith_uint256 nChainWork{};
119 120 //! Number of transactions in this block. This will be nonzero if the block
121 //! reached the VALID_TRANSACTIONS level, and zero otherwise.
122 //! Note: in a potential headers-first mode, this number cannot be relied upon
123 unsigned int nTx{0};
124 125 //! (memory only) Number of transactions in the chain up to and including this block.
126 //! This value will be non-zero if this block and all previous blocks back
127 //! to the genesis block or an assumeutxo snapshot block have reached the
128 //! VALID_TRANSACTIONS level.
129 uint64_t m_chain_tx_count{0};
130 131 //! Verification status of this block. See enum BlockStatus
132 //!
133 //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot
134 //! load to avoid a spurious startup failure requiring -reindex.
135 //! @sa NeedsRedownload
136 //! @sa ActivateSnapshot
137 uint32_t nStatus GUARDED_BY(::cs_main){0};
138 139 //! block header
140 int32_t nVersion{0};
141 uint256 hashMerkleRoot{};
142 uint32_t nTime{0};
143 uint32_t nBits{0};
144 uint32_t nNonce{0};
145 146 //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
147 //! Initialized to SEQ_ID_INIT_FROM_DISK{1} when loading blocks from disk, except for blocks
148 //! belonging to the best chain which overwrite it to SEQ_ID_BEST_CHAIN_FROM_DISK{0}.
149 int32_t nSequenceId{SEQ_ID_INIT_FROM_DISK};
150 151 //! (memory only) Maximum nTime in the chain up to and including this block.
152 unsigned int nTimeMax{0};
153 154 explicit CBlockIndex(const CBlockHeader& block)
155 : nVersion{block.nVersion},
156 hashMerkleRoot{block.hashMerkleRoot},
157 nTime{block.nTime},
158 nBits{block.nBits},
159 nNonce{block.nNonce}
160 {
161 }
162 163 FlatFilePos GetBlockPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
164 {
165 AssertLockHeld(::cs_main);
166 FlatFilePos ret;
167 if (nStatus & BLOCK_HAVE_DATA) {
168 ret.nFile = nFile;
169 ret.nPos = nDataPos;
170 }
171 return ret;
172 }
173 174 FlatFilePos GetUndoPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
175 {
176 AssertLockHeld(::cs_main);
177 FlatFilePos ret;
178 if (nStatus & BLOCK_HAVE_UNDO) {
179 ret.nFile = nFile;
180 ret.nPos = nUndoPos;
181 }
182 return ret;
183 }
184 185 CBlockHeader GetBlockHeader() const
186 {
187 CBlockHeader block;
188 block.nVersion = nVersion;
189 if (pprev)
190 block.hashPrevBlock = pprev->GetBlockHash();
191 block.hashMerkleRoot = hashMerkleRoot;
192 block.nTime = nTime;
193 block.nBits = nBits;
194 block.nNonce = nNonce;
195 return block;
196 }
197 198 uint256 GetBlockHash() const
199 {
200 assert(phashBlock != nullptr);
201 return *phashBlock;
202 }
203 204 /**
205 * Check whether this block and all previous blocks back to the genesis block or an assumeutxo snapshot block have
206 * reached VALID_TRANSACTIONS and had transactions downloaded (and stored to disk) at some point.
207 *
208 * Does not imply the transactions are consensus-valid (ConnectTip might fail)
209 * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true)
210 *
211 * Note that this will be true for the snapshot base block, if one is loaded, since its m_chain_tx_count value will have
212 * been set manually based on the related AssumeutxoData entry.
213 */
214 bool HaveNumChainTxs() const { return m_chain_tx_count != 0; }
215 216 NodeSeconds Time() const
217 {
218 return NodeSeconds{std::chrono::seconds{nTime}};
219 }
220 221 int64_t GetBlockTime() const
222 {
223 return (int64_t)nTime;
224 }
225 226 int64_t GetBlockTimeMax() const
227 {
228 return (int64_t)nTimeMax;
229 }
230 231 static constexpr int nMedianTimeSpan = 11;
232 233 int64_t GetMedianTimePast() const
234 {
235 int64_t pmedian[nMedianTimeSpan];
236 int64_t* pbegin = &pmedian[nMedianTimeSpan];
237 int64_t* pend = &pmedian[nMedianTimeSpan];
238 239 const CBlockIndex* pindex = this;
240 for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
241 *(--pbegin) = pindex->GetBlockTime();
242 243 std::sort(pbegin, pend);
244 return pbegin[(pend - pbegin) / 2];
245 }
246 247 std::string ToString() const;
248 249 //! Check whether this block index entry is valid up to the passed validity level.
250 bool IsValid(enum BlockStatus nUpTo) const
251 EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
252 {
253 AssertLockHeld(::cs_main);
254 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
255 if (nStatus & BLOCK_FAILED_VALID)
256 return false;
257 return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
258 }
259 260 //! Raise the validity level of this block index entry.
261 //! Returns true if the validity was changed.
262 bool RaiseValidity(enum BlockStatus nUpTo) EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
263 {
264 AssertLockHeld(::cs_main);
265 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
266 if (nStatus & BLOCK_FAILED_VALID) return false;
267 268 if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
269 nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
270 return true;
271 }
272 return false;
273 }
274 275 //! Build the skiplist pointer for this entry.
276 void BuildSkip();
277 278 //! Efficiently find an ancestor of this block.
279 CBlockIndex* GetAncestor(int height);
280 const CBlockIndex* GetAncestor(int height) const;
281 282 CBlockIndex() = default;
283 ~CBlockIndex() = default;
284 285 protected:
286 //! CBlockIndex should not allow public copy construction because equality
287 //! comparison via pointer is very common throughout the codebase, making
288 //! use of copy a footgun. Also, use of copies do not have the benefit
289 //! of simplifying lifetime considerations due to attributes like pprev and
290 //! pskip, which are at risk of becoming dangling pointers in a copied
291 //! instance.
292 //!
293 //! We declare these protected instead of simply deleting them so that
294 //! CDiskBlockIndex can reuse copy construction.
295 CBlockIndex(const CBlockIndex&) = default;
296 CBlockIndex& operator=(const CBlockIndex&) = delete;
297 CBlockIndex(CBlockIndex&&) = delete;
298 CBlockIndex& operator=(CBlockIndex&&) = delete;
299 };
300 301 /** Compute how much work an nBits value corresponds to. */
302 arith_uint256 GetBitsProof(uint32_t bits);
303 304 /** Compute how much work a block index entry corresponds to. */
305 inline arith_uint256 GetBlockProof(const CBlockIndex& block) { return GetBitsProof(block.nBits); }
306 307 /** Compute how much work a block header corresponds to. */
308 inline arith_uint256 GetBlockProof(const CBlockHeader& header) { return GetBitsProof(header.nBits); }
309 310 /** Return the time it would take to redo the work difference between from and to, assuming the current hashrate corresponds to the difficulty at tip, in seconds. */
311 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
312 /** Find the forking point between two chain tips. */
313 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
314 315 316 /** Used to marshal pointers into hashes for db storage. */
317 class CDiskBlockIndex : public CBlockIndex
318 {
319 /** Historically CBlockLocator's version field has been written to disk
320 * streams as the client version, but the value has never been used.
321 *
322 * Hard-code to the highest client version ever written.
323 * SerParams can be used if the field requires any meaning in the future.
324 **/
325 static constexpr int DUMMY_VERSION = 259900;
326 327 public:
328 uint256 hashPrev;
329 330 CDiskBlockIndex()
331 {
332 hashPrev = uint256();
333 }
334 335 explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex)
336 {
337 hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
338 }
339 340 SERIALIZE_METHODS(CDiskBlockIndex, obj)
341 {
342 LOCK(::cs_main);
343 int _nVersion = DUMMY_VERSION;
344 READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED));
345 346 READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED));
347 READWRITE(VARINT(obj.nStatus));
348 READWRITE(VARINT(obj.nTx));
349 if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED));
350 if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos));
351 if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos));
352 353 // block header
354 READWRITE(obj.nVersion);
355 READWRITE(obj.hashPrev);
356 READWRITE(obj.hashMerkleRoot);
357 READWRITE(obj.nTime);
358 READWRITE(obj.nBits);
359 READWRITE(obj.nNonce);
360 }
361 362 uint256 ConstructBlockHash() const
363 {
364 CBlockHeader block;
365 block.nVersion = nVersion;
366 block.hashPrevBlock = hashPrev;
367 block.hashMerkleRoot = hashMerkleRoot;
368 block.nTime = nTime;
369 block.nBits = nBits;
370 block.nNonce = nNonce;
371 return block.GetHash();
372 }
373 374 uint256 GetBlockHash() = delete;
375 std::string ToString() = delete;
376 };
377 378 /** An in-memory indexed chain of blocks. */
379 class CChain
380 {
381 private:
382 std::vector<CBlockIndex*> vChain;
383 384 public:
385 CChain() = default;
386 CChain(const CChain&) = delete;
387 CChain& operator=(const CChain&) = delete;
388 389 /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
390 CBlockIndex* Genesis() const
391 {
392 return vChain.size() > 0 ? vChain[0] : nullptr;
393 }
394 395 /** Returns the index entry for the tip of this chain, or nullptr if none. */
396 CBlockIndex* Tip() const
397 {
398 return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
399 }
400 401 /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
402 CBlockIndex* operator[](int nHeight) const
403 {
404 if (nHeight < 0 || nHeight >= (int)vChain.size())
405 return nullptr;
406 return vChain[nHeight];
407 }
408 409 /** Efficiently check whether a block is present in this chain. */
410 bool Contains(const CBlockIndex& index) const
411 {
412 return (*this)[index.nHeight] == &index;
413 }
414 415 /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
416 CBlockIndex* Next(const CBlockIndex& index) const
417 {
418 if (Contains(index))
419 return (*this)[index.nHeight + 1];
420 else
421 return nullptr;
422 }
423 424 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
425 int Height() const
426 {
427 return int(vChain.size()) - 1;
428 }
429 430 /** Check whether this chain's tip exists, has enough work, and is recent. */
431 bool IsTipRecent(const arith_uint256& min_chain_work, std::chrono::seconds max_tip_age) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
432 {
433 const auto tip{Tip()};
434 return tip &&
435 tip->nChainWork >= min_chain_work &&
436 tip->Time() >= Now<NodeSeconds>() - max_tip_age;
437 }
438 439 /** Set/initialize a chain with a given tip. */
440 void SetTip(CBlockIndex& block);
441 442 /** Find the last common block between this chain and a block index entry. */
443 const CBlockIndex* FindFork(const CBlockIndex& index) const;
444 445 /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */
446 CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const;
447 };
448 449 /** Get a locator for a block index entry. */
450 CBlockLocator GetLocator(const CBlockIndex* index);
451 452 /** Construct a list of hash entries to put in a locator. */
453 std::vector<uint256> LocatorEntries(const CBlockIndex* index);
454 455 #endif // BITCOIN_CHAIN_H
456