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