Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2020 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 <tinyformat.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 : * Ref: https://github.com/bitcoin/bitcoin/pull/1026
37 : */
38 : static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60;
39 :
40 : class CBlockFileInfo
41 : {
42 : public:
43 : unsigned int nBlocks; //!< number of blocks stored in file
44 : unsigned int nSize; //!< number of used bytes of block file
45 : unsigned int nUndoSize; //!< number of used bytes in the undo file
46 : unsigned int nHeightFirst; //!< lowest height of block in file
47 : unsigned int nHeightLast; //!< highest height of block in file
48 : uint64_t nTimeFirst; //!< earliest time of block in file
49 : uint64_t nTimeLast; //!< latest time of block in file
50 :
51 2067 : SERIALIZE_METHODS(CBlockFileInfo, obj)
52 : {
53 689 : READWRITE(VARINT(obj.nBlocks));
54 689 : READWRITE(VARINT(obj.nSize));
55 689 : READWRITE(VARINT(obj.nUndoSize));
56 689 : READWRITE(VARINT(obj.nHeightFirst));
57 689 : READWRITE(VARINT(obj.nHeightLast));
58 689 : READWRITE(VARINT(obj.nTimeFirst));
59 689 : READWRITE(VARINT(obj.nTimeLast));
60 689 : }
61 :
62 1100 : void SetNull() {
63 1100 : nBlocks = 0;
64 1100 : nSize = 0;
65 1100 : nUndoSize = 0;
66 1100 : nHeightFirst = 0;
67 1100 : nHeightLast = 0;
68 1100 : nTimeFirst = 0;
69 1100 : nTimeLast = 0;
70 1100 : }
71 :
72 2194 : CBlockFileInfo() {
73 1097 : SetNull();
74 2194 : }
75 :
76 : std::string ToString() const;
77 :
78 : /** update statistics (does not update nSize) */
79 45425 : void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) {
80 45425 : if (nBlocks==0 || nHeightFirst > nHeightIn)
81 301 : nHeightFirst = nHeightIn;
82 45425 : if (nBlocks==0 || nTimeFirst > nTimeIn)
83 301 : nTimeFirst = nTimeIn;
84 45425 : nBlocks++;
85 45425 : if (nHeightIn > nHeightLast)
86 42837 : nHeightLast = nHeightIn;
87 45425 : if (nTimeIn > nTimeLast)
88 14554 : nTimeLast = nTimeIn;
89 45425 : }
90 : };
91 :
92 : enum BlockStatus: uint32_t {
93 : //! Unused.
94 : BLOCK_VALID_UNKNOWN = 0,
95 :
96 : //! Reserved (was BLOCK_VALID_HEADER).
97 : BLOCK_VALID_RESERVED = 1,
98 :
99 : //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
100 : //! are also at least TREE.
101 : BLOCK_VALID_TREE = 2,
102 :
103 : /**
104 : * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
105 : * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
106 : * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
107 : */
108 : BLOCK_VALID_TRANSACTIONS = 3,
109 :
110 : //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
111 : //! Implies all parents are also at least CHAIN.
112 : BLOCK_VALID_CHAIN = 4,
113 :
114 : //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
115 : BLOCK_VALID_SCRIPTS = 5,
116 :
117 : //! All validity bits.
118 : BLOCK_VALID_MASK = BLOCK_VALID_RESERVED | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
119 : BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
120 :
121 : BLOCK_HAVE_DATA = 8, //!< full block available in blk*.dat
122 : BLOCK_HAVE_UNDO = 16, //!< undo data available in rev*.dat
123 : BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
124 :
125 : BLOCK_FAILED_VALID = 32, //!< stage after last reached validness failed
126 : BLOCK_FAILED_CHILD = 64, //!< descends from failed block
127 : BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
128 :
129 : BLOCK_OPT_WITNESS = 128, //!< block data in blk*.data was received with a witness-enforcing client
130 : };
131 :
132 : /** The block chain is a tree shaped structure starting with the
133 : * genesis block at the root, with each block potentially having multiple
134 : * candidates to be the next block. A blockindex may have multiple pprev pointing
135 : * to it, but at most one of them can be part of the currently active branch.
136 : */
137 44550 : class CBlockIndex
138 : {
139 : public:
140 : //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
141 4946013 : const uint256* phashBlock{nullptr};
142 :
143 : //! pointer to the index of the predecessor of this block
144 4946013 : CBlockIndex* pprev{nullptr};
145 :
146 : //! pointer to the index of some further predecessor of this block
147 4946013 : CBlockIndex* pskip{nullptr};
148 :
149 : //! height of the entry in the chain. The genesis block has height 0
150 4946013 : int nHeight{0};
151 :
152 : //! Which # file this block is stored in (blk?????.dat)
153 4946013 : int nFile{0};
154 :
155 : //! Byte offset within blk?????.dat where this block's data is stored
156 4946013 : unsigned int nDataPos{0};
157 :
158 : //! Byte offset within rev?????.dat where this block's undo data is stored
159 4946013 : unsigned int nUndoPos{0};
160 :
161 : //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
162 4946013 : arith_uint256 nChainWork{};
163 :
164 : //! Number of transactions in this block.
165 : //! Note: in a potential headers-first mode, this number cannot be relied upon
166 4946013 : 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 when necessary; won't happen before 2030
171 4946013 : unsigned int nChainTx{0};
172 :
173 : //! Verification status of this block. See enum BlockStatus
174 4946013 : uint32_t nStatus{0};
175 :
176 : //! block header
177 4876871 : int32_t nVersion{0};
178 4876871 : uint256 hashMerkleRoot{};
179 4876871 : uint32_t nTime{0};
180 4876871 : uint32_t nBits{0};
181 4876871 : uint32_t nNonce{0};
182 :
183 : //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
184 4946013 : int32_t nSequenceId{0};
185 :
186 : //! (memory only) Maximum nTime in the chain up to and including this block.
187 4946013 : unsigned int nTimeMax{0};
188 :
189 9703396 : CBlockIndex()
190 4826525 : {
191 9703396 : }
192 :
193 138284 : explicit CBlockIndex(const CBlockHeader& block)
194 69142 : : nVersion{block.nVersion},
195 69142 : hashMerkleRoot{block.hashMerkleRoot},
196 69142 : nTime{block.nTime},
197 69142 : nBits{block.nBits},
198 69142 : nNonce{block.nNonce}
199 69142 : {
200 138284 : }
201 :
202 105651 : FlatFilePos GetBlockPos() const {
203 105651 : FlatFilePos ret;
204 105651 : if (nStatus & BLOCK_HAVE_DATA) {
205 105540 : ret.nFile = nFile;
206 105540 : ret.nPos = nDataPos;
207 105540 : }
208 105651 : return ret;
209 : }
210 :
211 59479 : FlatFilePos GetUndoPos() const {
212 59479 : FlatFilePos ret;
213 59479 : if (nStatus & BLOCK_HAVE_UNDO) {
214 14577 : ret.nFile = nFile;
215 14577 : ret.nPos = nUndoPos;
216 14577 : }
217 59479 : return ret;
218 : }
219 :
220 172101 : CBlockHeader GetBlockHeader() const
221 : {
222 172101 : CBlockHeader block;
223 172101 : block.nVersion = nVersion;
224 172101 : if (pprev)
225 172101 : block.hashPrevBlock = pprev->GetBlockHash();
226 172101 : block.hashMerkleRoot = hashMerkleRoot;
227 172101 : block.nTime = nTime;
228 172101 : block.nBits = nBits;
229 172101 : block.nNonce = nNonce;
230 172101 : return block;
231 : }
232 :
233 2720885 : uint256 GetBlockHash() const
234 : {
235 2720885 : return *phashBlock;
236 : }
237 :
238 : /**
239 : * Check whether this block's and all previous blocks' transactions have been
240 : * downloaded (and stored to disk) at some point.
241 : *
242 : * Does not imply the transactions are consensus-valid (ConnectTip might fail)
243 : * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true)
244 : */
245 574950261 : bool HaveTxsDownloaded() const { return nChainTx != 0; }
246 :
247 4555244 : int64_t GetBlockTime() const
248 : {
249 4555244 : return (int64_t)nTime;
250 : }
251 :
252 170904 : int64_t GetBlockTimeMax() const
253 : {
254 170904 : return (int64_t)nTimeMax;
255 : }
256 :
257 : static constexpr int nMedianTimeSpan = 11;
258 :
259 379973 : int64_t GetMedianTimePast() const
260 : {
261 379973 : int64_t pmedian[nMedianTimeSpan];
262 379973 : int64_t* pbegin = &pmedian[nMedianTimeSpan];
263 : int64_t* pend = &pmedian[nMedianTimeSpan];
264 :
265 : const CBlockIndex* pindex = this;
266 4524295 : for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
267 4144322 : *(--pbegin) = pindex->GetBlockTime();
268 :
269 379973 : std::sort(pbegin, pend);
270 759946 : return pbegin[(pend - pbegin)/2];
271 379973 : }
272 :
273 0 : std::string ToString() const
274 : {
275 0 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
276 0 : pprev, nHeight,
277 0 : hashMerkleRoot.ToString(),
278 0 : GetBlockHash().ToString());
279 0 : }
280 :
281 : //! Check whether this block index entry is valid up to the passed validity level.
282 463130 : bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
283 : {
284 463130 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
285 463130 : if (nStatus & BLOCK_FAILED_MASK)
286 1788 : return false;
287 461342 : return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
288 463130 : }
289 :
290 : //! Raise the validity level of this block index entry.
291 : //! Returns true if the validity was changed.
292 138442 : bool RaiseValidity(enum BlockStatus nUpTo)
293 : {
294 138442 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
295 138442 : if (nStatus & BLOCK_FAILED_MASK)
296 0 : return false;
297 138442 : if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
298 138442 : nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
299 138442 : return true;
300 : }
301 0 : return false;
302 138442 : }
303 :
304 : //! Build the skiplist pointer for this entry.
305 : void BuildSkip();
306 :
307 : //! Efficiently find an ancestor of this block.
308 : CBlockIndex* GetAncestor(int height);
309 : const CBlockIndex* GetAncestor(int height) const;
310 : };
311 :
312 : arith_uint256 GetBlockProof(const CBlockIndex& block);
313 : /** 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. */
314 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
315 : /** Find the forking point between two chain tips. */
316 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
317 :
318 :
319 : /** Used to marshal pointers into hashes for db storage. */
320 : class CDiskBlockIndex : public CBlockIndex
321 : {
322 : public:
323 : uint256 hashPrev;
324 :
325 100692 : CDiskBlockIndex() {
326 50346 : hashPrev = uint256();
327 100692 : }
328 :
329 89100 : explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
330 44550 : hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
331 89100 : }
332 :
333 284688 : SERIALIZE_METHODS(CDiskBlockIndex, obj)
334 : {
335 94896 : int _nVersion = s.GetVersion();
336 94896 : if (!(s.GetType() & SER_GETHASH)) READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED));
337 :
338 94896 : READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED));
339 94896 : READWRITE(VARINT(obj.nStatus));
340 94896 : READWRITE(VARINT(obj.nTx));
341 94896 : if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED));
342 94896 : if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos));
343 94896 : if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos));
344 :
345 : // block header
346 94896 : READWRITE(obj.nVersion);
347 94896 : READWRITE(obj.hashPrev);
348 94896 : READWRITE(obj.hashMerkleRoot);
349 94896 : READWRITE(obj.nTime);
350 94896 : READWRITE(obj.nBits);
351 94896 : READWRITE(obj.nNonce);
352 94896 : }
353 :
354 50346 : uint256 GetBlockHash() const
355 : {
356 50346 : CBlockHeader block;
357 50346 : block.nVersion = nVersion;
358 50346 : block.hashPrevBlock = hashPrev;
359 50346 : block.hashMerkleRoot = hashMerkleRoot;
360 50346 : block.nTime = nTime;
361 50346 : block.nBits = nBits;
362 50346 : block.nNonce = nNonce;
363 50346 : return block.GetHash();
364 50346 : }
365 :
366 :
367 : std::string ToString() const
368 : {
369 : std::string str = "CDiskBlockIndex(";
370 : str += CBlockIndex::ToString();
371 : str += strprintf("\n hashBlock=%s, hashPrev=%s)",
372 : GetBlockHash().ToString(),
373 : hashPrev.ToString());
374 : return str;
375 : }
376 : };
377 :
378 : /** An in-memory indexed chain of blocks. */
379 2424 : class CChain {
380 : private:
381 : std::vector<CBlockIndex*> vChain;
382 :
383 : public:
384 : /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
385 333820 : CBlockIndex *Genesis() const {
386 333820 : return vChain.size() > 0 ? vChain[0] : nullptr;
387 : }
388 :
389 : /** Returns the index entry for the tip of this chain, or nullptr if none. */
390 193858664 : CBlockIndex *Tip() const {
391 193858664 : return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
392 : }
393 :
394 : /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
395 1215378 : CBlockIndex *operator[](int nHeight) const {
396 1215378 : if (nHeight < 0 || nHeight >= (int)vChain.size())
397 273928 : return nullptr;
398 941450 : return vChain[nHeight];
399 1215378 : }
400 :
401 : /** Efficiently check whether a block is present in this chain. */
402 704361 : bool Contains(const CBlockIndex *pindex) const {
403 704361 : return (*this)[pindex->nHeight] == pindex;
404 : }
405 :
406 : /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
407 168236 : CBlockIndex *Next(const CBlockIndex *pindex) const {
408 168236 : if (Contains(pindex))
409 168236 : return (*this)[pindex->nHeight + 1];
410 : else
411 0 : return nullptr;
412 168236 : }
413 :
414 : /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
415 1699806 : int Height() const {
416 1699806 : return vChain.size() - 1;
417 : }
418 :
419 : /** Set/initialize a chain with a given tip. */
420 : void SetTip(CBlockIndex *pindex);
421 :
422 : /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
423 : CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const;
424 :
425 : /** Find the last common block between this chain and a block index entry. */
426 : const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
427 :
428 : /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */
429 : CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const;
430 : };
431 :
432 : #endif // BITCOIN_CHAIN_H
|
