Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2022 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 <sync.h>
15 : #include <uint256.h>
16 : #include <util/time.h>
17 :
18 : #include <vector>
19 :
20 : /**
21 : * Maximum amount of time that a block timestamp is allowed to exceed the
22 : * current network-adjusted time before the block will be accepted.
23 : */
24 : static constexpr int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60;
25 :
26 : /**
27 : * Timestamp window used as a grace period by code that compares external
28 : * timestamps (such as timestamps passed to RPCs, or wallet key creation times)
29 : * to block timestamps. This should be set at least as high as
30 : * MAX_FUTURE_BLOCK_TIME.
31 : */
32 : static constexpr int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME;
33 :
34 : /**
35 : * Maximum gap between node time and block time used
36 : * for the "Catching up..." mode in GUI.
37 : *
38 : * Ref: https://github.com/bitcoin/bitcoin/pull/1026
39 : */
40 : static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60;
41 :
42 : class CBlockFileInfo
43 : {
44 : public:
45 : unsigned int nBlocks; //!< number of blocks stored in file
46 : unsigned int nSize; //!< number of used bytes of block file
47 : unsigned int nUndoSize; //!< number of used bytes in the undo file
48 : unsigned int nHeightFirst; //!< lowest height of block in file
49 : unsigned int nHeightLast; //!< highest height of block in file
50 : uint64_t nTimeFirst; //!< earliest time of block in file
51 : uint64_t nTimeLast; //!< latest time of block in file
52 :
53 0 : SERIALIZE_METHODS(CBlockFileInfo, obj)
54 : {
55 0 : READWRITE(VARINT(obj.nBlocks));
56 0 : READWRITE(VARINT(obj.nSize));
57 0 : READWRITE(VARINT(obj.nUndoSize));
58 0 : READWRITE(VARINT(obj.nHeightFirst));
59 0 : READWRITE(VARINT(obj.nHeightLast));
60 0 : READWRITE(VARINT(obj.nTimeFirst));
61 0 : READWRITE(VARINT(obj.nTimeLast));
62 0 : }
63 :
64 2 : void SetNull()
65 : {
66 2 : nBlocks = 0;
67 2 : nSize = 0;
68 2 : nUndoSize = 0;
69 2 : nHeightFirst = 0;
70 2 : nHeightLast = 0;
71 2 : nTimeFirst = 0;
72 2 : nTimeLast = 0;
73 2 : }
74 :
75 2 : CBlockFileInfo()
76 : {
77 2 : SetNull();
78 2 : }
79 :
80 : std::string ToString() const;
81 :
82 : /** update statistics (does not update nSize) */
83 201 : void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn)
84 : {
85 201 : if (nBlocks == 0 || nHeightFirst > nHeightIn)
86 1 : nHeightFirst = nHeightIn;
87 201 : if (nBlocks == 0 || nTimeFirst > nTimeIn)
88 1 : nTimeFirst = nTimeIn;
89 201 : nBlocks++;
90 201 : if (nHeightIn > nHeightLast)
91 200 : nHeightLast = nHeightIn;
92 201 : if (nTimeIn > nTimeLast)
93 37 : nTimeLast = nTimeIn;
94 201 : }
95 : };
96 :
97 : enum BlockStatus : uint32_t {
98 : //! Unused.
99 : BLOCK_VALID_UNKNOWN = 0,
100 :
101 : //! Reserved (was BLOCK_VALID_HEADER).
102 : BLOCK_VALID_RESERVED = 1,
103 :
104 : //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
105 : //! are also at least TREE.
106 : BLOCK_VALID_TREE = 2,
107 :
108 : /**
109 : * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
110 : * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
111 : * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
112 : */
113 : BLOCK_VALID_TRANSACTIONS = 3,
114 :
115 : //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
116 : //! Implies all parents are either at least VALID_CHAIN, or are ASSUMED_VALID
117 : BLOCK_VALID_CHAIN = 4,
118 :
119 : //! Scripts & signatures ok. Implies all parents are either at least VALID_SCRIPTS, or are ASSUMED_VALID.
120 : BLOCK_VALID_SCRIPTS = 5,
121 :
122 : //! All validity bits.
123 : BLOCK_VALID_MASK = BLOCK_VALID_RESERVED | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
124 : BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
125 :
126 : BLOCK_HAVE_DATA = 8, //!< full block available in blk*.dat
127 : BLOCK_HAVE_UNDO = 16, //!< undo data available in rev*.dat
128 : BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
129 :
130 : BLOCK_FAILED_VALID = 32, //!< stage after last reached validness failed
131 : BLOCK_FAILED_CHILD = 64, //!< descends from failed block
132 : BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
133 :
134 : BLOCK_OPT_WITNESS = 128, //!< block data in blk*.dat was received with a witness-enforcing client
135 :
136 : /**
137 : * If ASSUMED_VALID is set, it means that this block has not been validated
138 : * and has validity status less than VALID_SCRIPTS. Also that it may have
139 : * descendant blocks with VALID_SCRIPTS set, because they can be validated
140 : * based on an assumeutxo snapshot.
141 : *
142 : * When an assumeutxo snapshot is loaded, the ASSUMED_VALID flag is added to
143 : * unvalidated blocks at the snapshot height and below. Then, as the background
144 : * validation progresses, and these blocks are validated, the ASSUMED_VALID
145 : * flags are removed. See `doc/design/assumeutxo.md` for details.
146 : *
147 : * This flag is only used to implement checks in CheckBlockIndex() and
148 : * should not be used elsewhere.
149 : */
150 : BLOCK_ASSUMED_VALID = 256,
151 : };
152 :
153 : /** The block chain is a tree shaped structure starting with the
154 : * genesis block at the root, with each block potentially having multiple
155 : * candidates to be the next block. A blockindex may have multiple pprev pointing
156 : * to it, but at most one of them can be part of the currently active branch.
157 : */
158 : class CBlockIndex
159 : {
160 : public:
161 : //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
162 18374 : const uint256* phashBlock{nullptr};
163 :
164 : //! pointer to the index of the predecessor of this block
165 18374 : CBlockIndex* pprev{nullptr};
166 :
167 : //! pointer to the index of some further predecessor of this block
168 18374 : CBlockIndex* pskip{nullptr};
169 :
170 : //! height of the entry in the chain. The genesis block has height 0
171 18374 : int nHeight{0};
172 :
173 : //! Which # file this block is stored in (blk?????.dat)
174 18374 : int nFile GUARDED_BY(::cs_main){0};
175 :
176 : //! Byte offset within blk?????.dat where this block's data is stored
177 18374 : unsigned int nDataPos GUARDED_BY(::cs_main){0};
178 :
179 : //! Byte offset within rev?????.dat where this block's undo data is stored
180 18374 : unsigned int nUndoPos GUARDED_BY(::cs_main){0};
181 :
182 : //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
183 18374 : arith_uint256 nChainWork{};
184 :
185 : //! Number of transactions in this block.
186 : //! Note: in a potential headers-first mode, this number cannot be relied upon
187 : //! Note: this value is faked during UTXO snapshot load to ensure that
188 : //! LoadBlockIndex() will load index entries for blocks that we lack data for.
189 : //! @sa ActivateSnapshot
190 18374 : unsigned int nTx{0};
191 :
192 : //! (memory only) Number of transactions in the chain up to and including this block.
193 : //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
194 : //! Change to 64-bit type before 2024 (assuming worst case of 60 byte transactions).
195 : //!
196 : //! Note: this value is faked during use of a UTXO snapshot because we don't
197 : //! have the underlying block data available during snapshot load.
198 : //! @sa AssumeutxoData
199 : //! @sa ActivateSnapshot
200 18374 : unsigned int nChainTx{0};
201 :
202 : //! Verification status of this block. See enum BlockStatus
203 : //!
204 : //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot
205 : //! load to avoid the block index being spuriously rewound.
206 : //! @sa NeedsRedownload
207 : //! @sa ActivateSnapshot
208 18374 : uint32_t nStatus GUARDED_BY(::cs_main){0};
209 :
210 : //! block header
211 13114 : int32_t nVersion{0};
212 13114 : uint256 hashMerkleRoot{};
213 13114 : uint32_t nTime{0};
214 13114 : uint32_t nBits{0};
215 13114 : uint32_t nNonce{0};
216 :
217 : //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
218 18374 : int32_t nSequenceId{0};
219 :
220 : //! (memory only) Maximum nTime in the chain up to and including this block.
221 18374 : unsigned int nTimeMax{0};
222 :
223 5260 : explicit CBlockIndex(const CBlockHeader& block)
224 5260 : : nVersion{block.nVersion},
225 5260 : hashMerkleRoot{block.hashMerkleRoot},
226 5260 : nTime{block.nTime},
227 5260 : nBits{block.nBits},
228 5260 : nNonce{block.nNonce}
229 : {
230 5260 : }
231 :
232 1 : FlatFilePos GetBlockPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
233 : {
234 1 : AssertLockHeld(::cs_main);
235 1 : FlatFilePos ret;
236 1 : if (nStatus & BLOCK_HAVE_DATA) {
237 1 : ret.nFile = nFile;
238 1 : ret.nPos = nDataPos;
239 1 : }
240 1 : return ret;
241 : }
242 :
243 200 : FlatFilePos GetUndoPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
244 : {
245 200 : AssertLockHeld(::cs_main);
246 200 : FlatFilePos ret;
247 200 : if (nStatus & BLOCK_HAVE_UNDO) {
248 0 : ret.nFile = nFile;
249 0 : ret.nPos = nUndoPos;
250 0 : }
251 200 : return ret;
252 : }
253 :
254 0 : CBlockHeader GetBlockHeader() const
255 : {
256 0 : CBlockHeader block;
257 0 : block.nVersion = nVersion;
258 0 : if (pprev)
259 0 : block.hashPrevBlock = pprev->GetBlockHash();
260 0 : block.hashMerkleRoot = hashMerkleRoot;
261 0 : block.nTime = nTime;
262 0 : block.nBits = nBits;
263 0 : block.nNonce = nNonce;
264 0 : return block;
265 : }
266 :
267 46646 : uint256 GetBlockHash() const
268 : {
269 46646 : assert(phashBlock != nullptr);
270 46646 : return *phashBlock;
271 : }
272 :
273 : /**
274 : * Check whether this block's and all previous blocks' transactions have been
275 : * downloaded (and stored to disk) at some point.
276 : *
277 : * Does not imply the transactions are consensus-valid (ConnectTip might fail)
278 : * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true)
279 : */
280 183104 : bool HaveTxsDownloaded() const { return nChainTx != 0; }
281 :
282 1205 : NodeSeconds Time() const
283 : {
284 1205 : return NodeSeconds{std::chrono::seconds{nTime}};
285 : }
286 :
287 606766 : int64_t GetBlockTime() const
288 : {
289 606766 : return (int64_t)nTime;
290 : }
291 :
292 0 : int64_t GetBlockTimeMax() const
293 : {
294 0 : return (int64_t)nTimeMax;
295 : }
296 :
297 : static constexpr int nMedianTimeSpan = 11;
298 :
299 53724 : int64_t GetMedianTimePast() const
300 : {
301 : int64_t pmedian[nMedianTimeSpan];
302 53724 : int64_t* pbegin = &pmedian[nMedianTimeSpan];
303 53724 : int64_t* pend = &pmedian[nMedianTimeSpan];
304 :
305 53724 : const CBlockIndex* pindex = this;
306 643854 : for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
307 590130 : *(--pbegin) = pindex->GetBlockTime();
308 :
309 53724 : std::sort(pbegin, pend);
310 53724 : return pbegin[(pend - pbegin) / 2];
311 : }
312 :
313 : std::string ToString() const;
314 :
315 : //! Check whether this block index entry is valid up to the passed validity level.
316 400 : bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
317 : EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
318 : {
319 400 : AssertLockHeld(::cs_main);
320 400 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
321 400 : if (nStatus & BLOCK_FAILED_MASK)
322 0 : return false;
323 400 : return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
324 400 : }
325 :
326 : //! @returns true if the block is assumed-valid; this means it is queued to be
327 : //! validated by a background chainstate.
328 182102 : bool IsAssumedValid() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
329 : {
330 182102 : AssertLockHeld(::cs_main);
331 182102 : return nStatus & BLOCK_ASSUMED_VALID;
332 : }
333 :
334 : //! Raise the validity level of this block index entry.
335 : //! Returns true if the validity was changed.
336 602 : bool RaiseValidity(enum BlockStatus nUpTo) EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
337 : {
338 602 : AssertLockHeld(::cs_main);
339 602 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
340 602 : if (nStatus & BLOCK_FAILED_MASK) return false;
341 :
342 602 : if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
343 : // If this block had been marked assumed-valid and we're raising
344 : // its validity to a certain point, there is no longer an assumption.
345 602 : if (nStatus & BLOCK_ASSUMED_VALID && nUpTo >= BLOCK_VALID_SCRIPTS) {
346 0 : nStatus &= ~BLOCK_ASSUMED_VALID;
347 0 : }
348 :
349 602 : nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
350 602 : return true;
351 : }
352 0 : return false;
353 602 : }
354 :
355 : //! Build the skiplist pointer for this entry.
356 : void BuildSkip();
357 :
358 : //! Efficiently find an ancestor of this block.
359 : CBlockIndex* GetAncestor(int height);
360 : const CBlockIndex* GetAncestor(int height) const;
361 :
362 26228 : CBlockIndex() = default;
363 : ~CBlockIndex() = default;
364 :
365 : protected:
366 : //! CBlockIndex should not allow public copy construction because equality
367 : //! comparison via pointer is very common throughout the codebase, making
368 : //! use of copy a footgun. Also, use of copies do not have the benefit
369 : //! of simplifying lifetime considerations due to attributes like pprev and
370 : //! pskip, which are at risk of becoming dangling pointers in a copied
371 : //! instance.
372 : //!
373 : //! We declare these protected instead of simply deleting them so that
374 : //! CDiskBlockIndex can reuse copy construction.
375 0 : CBlockIndex(const CBlockIndex&) = default;
376 : CBlockIndex& operator=(const CBlockIndex&) = delete;
377 : CBlockIndex(CBlockIndex&&) = delete;
378 : CBlockIndex& operator=(CBlockIndex&&) = delete;
379 : };
380 :
381 : arith_uint256 GetBlockProof(const CBlockIndex& block);
382 : /** 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. */
383 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
384 : /** Find the forking point between two chain tips. */
385 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
386 :
387 :
388 : /** Used to marshal pointers into hashes for db storage. */
389 : class CDiskBlockIndex : public CBlockIndex
390 : {
391 : /** Historically CBlockLocator's version field has been written to disk
392 : * streams as the client version, but the value has never been used.
393 : *
394 : * Hard-code to the highest client version ever written.
395 : * SerParams can be used if the field requires any meaning in the future.
396 : **/
397 : static constexpr int DUMMY_VERSION = 259900;
398 :
399 : public:
400 : uint256 hashPrev;
401 :
402 0 : CDiskBlockIndex()
403 : {
404 0 : hashPrev = uint256();
405 0 : }
406 :
407 0 : explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex)
408 : {
409 0 : hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
410 0 : }
411 :
412 0 : SERIALIZE_METHODS(CDiskBlockIndex, obj)
413 : {
414 0 : LOCK(::cs_main);
415 0 : int _nVersion = DUMMY_VERSION;
416 0 : READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED));
417 :
418 0 : READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED));
419 0 : READWRITE(VARINT(obj.nStatus));
420 0 : READWRITE(VARINT(obj.nTx));
421 0 : if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED));
422 0 : if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos));
423 0 : if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos));
424 :
425 : // block header
426 0 : READWRITE(obj.nVersion);
427 0 : READWRITE(obj.hashPrev);
428 0 : READWRITE(obj.hashMerkleRoot);
429 0 : READWRITE(obj.nTime);
430 0 : READWRITE(obj.nBits);
431 0 : READWRITE(obj.nNonce);
432 0 : }
433 :
434 0 : uint256 ConstructBlockHash() const
435 : {
436 0 : CBlockHeader block;
437 0 : block.nVersion = nVersion;
438 0 : block.hashPrevBlock = hashPrev;
439 0 : block.hashMerkleRoot = hashMerkleRoot;
440 0 : block.nTime = nTime;
441 0 : block.nBits = nBits;
442 0 : block.nNonce = nNonce;
443 0 : return block.GetHash();
444 : }
445 :
446 : uint256 GetBlockHash() = delete;
447 : std::string ToString() = delete;
448 : };
449 :
450 : /** An in-memory indexed chain of blocks. */
451 : class CChain
452 : {
453 : private:
454 : std::vector<CBlockIndex*> vChain;
455 :
456 : public:
457 1 : CChain() = default;
458 : CChain(const CChain&) = delete;
459 : CChain& operator=(const CChain&) = delete;
460 :
461 : /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
462 1202 : CBlockIndex* Genesis() const
463 : {
464 1202 : return vChain.size() > 0 ? vChain[0] : nullptr;
465 : }
466 :
467 : /** Returns the index entry for the tip of this chain, or nullptr if none. */
468 889772 : CBlockIndex* Tip() const
469 : {
470 889772 : return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
471 : }
472 :
473 : /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
474 801 : CBlockIndex* operator[](int nHeight) const
475 : {
476 801 : if (nHeight < 0 || nHeight >= (int)vChain.size())
477 201 : return nullptr;
478 600 : return vChain[nHeight];
479 801 : }
480 :
481 : /** Efficiently check whether a block is present in this chain. */
482 801 : bool Contains(const CBlockIndex* pindex) const
483 : {
484 801 : return (*this)[pindex->nHeight] == pindex;
485 : }
486 :
487 : /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
488 0 : CBlockIndex* Next(const CBlockIndex* pindex) const
489 : {
490 0 : if (Contains(pindex))
491 0 : return (*this)[pindex->nHeight + 1];
492 : else
493 0 : return nullptr;
494 0 : }
495 :
496 : /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
497 46049 : int Height() const
498 : {
499 46049 : return int(vChain.size()) - 1;
500 : }
501 :
502 : /** Set/initialize a chain with a given tip. */
503 : void SetTip(CBlockIndex& block);
504 :
505 : /** Return a CBlockLocator that refers to the tip in of this chain. */
506 : CBlockLocator GetLocator() const;
507 :
508 : /** Find the last common block between this chain and a block index entry. */
509 : const CBlockIndex* FindFork(const CBlockIndex* pindex) const;
510 :
511 : /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */
512 : CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const;
513 : };
514 :
515 : /** Get a locator for a block index entry. */
516 : CBlockLocator GetLocator(const CBlockIndex* index);
517 :
518 : /** Construct a list of hash entries to put in a locator. */
519 : std::vector<uint256> LocatorEntries(const CBlockIndex* index);
520 :
521 : #endif // BITCOIN_CHAIN_H
|
