1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2022 The Limenka 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 LIMENKA_CHAIN_H
7 #define LIMENKA_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 /**
43 * Maximum gap between node time and block time used
44 * for the "Catching up..." mode in GUI.
45 *
46 * Ref: https://github.com/limenka/limenka/pull/1026
47 */
48 static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60;
49 50 class CBlockFileInfo
51 {
52 public:
53 unsigned int nBlocks{}; //!< number of blocks stored in file
54 unsigned int nSize{}; //!< number of used bytes of block file
55 unsigned int nUndoSize{}; //!< number of used bytes in the undo file
56 unsigned int nHeightFirst{}; //!< lowest height of block in file
57 unsigned int nHeightLast{}; //!< highest height of block in file
58 uint64_t nTimeFirst{}; //!< earliest time of block in file
59 uint64_t nTimeLast{}; //!< latest time of block in file
60 61 SERIALIZE_METHODS(CBlockFileInfo, obj)
62 {
63 READWRITE(VARINT(obj.nBlocks));
64 READWRITE(VARINT(obj.nSize));
65 READWRITE(VARINT(obj.nUndoSize));
66 READWRITE(VARINT(obj.nHeightFirst));
67 READWRITE(VARINT(obj.nHeightLast));
68 READWRITE(VARINT(obj.nTimeFirst));
69 READWRITE(VARINT(obj.nTimeLast));
70 }
71 72 CBlockFileInfo() = default;
73 74 std::string ToString() const;
75 76 /** update statistics (does not update nSize) */
77 void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn)
78 {
79 if (nBlocks == 0 || nHeightFirst > nHeightIn)
80 nHeightFirst = nHeightIn;
81 if (nBlocks == 0 || nTimeFirst > nTimeIn)
82 nTimeFirst = nTimeIn;
83 nBlocks++;
84 if (nHeightIn > nHeightLast)
85 nHeightLast = nHeightIn;
86 if (nTimeIn > nTimeLast)
87 nTimeLast = nTimeIn;
88 }
89 };
90 91 enum BlockStatus : uint32_t {
92 //! Unused.
93 BLOCK_VALID_UNKNOWN = 0,
94 95 //! Reserved (was BLOCK_VALID_HEADER).
96 BLOCK_VALID_RESERVED = 1,
97 98 //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
99 //! are also at least TREE.
100 BLOCK_VALID_TREE = 2,
101 102 /**
103 * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
104 * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS.
105 *
106 * If a block's validity is at least VALID_TRANSACTIONS, CBlockIndex::nTx will be set. If a block and all previous
107 * blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_TRANSACTIONS,
108 * CBlockIndex::m_chain_tx_count will be set.
109 */
110 BLOCK_VALID_TRANSACTIONS = 3,
111 112 //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
113 //! Implies all previous blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_CHAIN.
114 BLOCK_VALID_CHAIN = 4,
115 116 //! Scripts & signatures ok. Implies all previous blocks back to the genesis block or an assumeutxo snapshot block
117 //! are at least VALID_SCRIPTS.
118 BLOCK_VALID_SCRIPTS = 5,
119 120 //! All validity bits.
121 BLOCK_VALID_MASK = BLOCK_VALID_RESERVED | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
122 BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
123 124 BLOCK_HAVE_DATA = 8, //!< full block available in blk*.dat
125 BLOCK_HAVE_UNDO = 16, //!< undo data available in rev*.dat
126 BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
127 128 BLOCK_FAILED_VALID = 32, //!< stage after last reached validness failed
129 BLOCK_FAILED_CHILD = 64, //!< descends from failed block
130 BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
131 132 BLOCK_OPT_WITNESS = 128, //!< block data in blk*.dat was received with a witness-enforcing client
133 134 BLOCK_STATUS_RESERVED = 256, //!< Unused flag that was previously set on assumeutxo snapshot blocks and their
135 //!< ancestors before they were validated, and unset when they were validated.
136 };
137 138 /** The block chain is a tree shaped structure starting with the
139 * genesis block at the root, with each block potentially having multiple
140 * candidates to be the next block. A blockindex may have multiple pprev pointing
141 * to it, but at most one of them can be part of the currently active branch.
142 */
143 class CBlockIndex
144 {
145 public:
146 //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
147 const uint256* phashBlock{nullptr};
148 149 //! pointer to the index of the predecessor of this block
150 CBlockIndex* pprev{nullptr};
151 152 //! pointer to the index of some further predecessor of this block
153 CBlockIndex* pskip{nullptr};
154 155 //! height of the entry in the chain. The genesis block has height 0
156 int nHeight{0};
157 158 //! Which # file this block is stored in (blk?????.dat)
159 int nFile GUARDED_BY(::cs_main){0};
160 161 //! Byte offset within blk?????.dat where this block's data is stored
162 unsigned int nDataPos GUARDED_BY(::cs_main){0};
163 164 //! Byte offset within rev?????.dat where this block's undo data is stored
165 unsigned int nUndoPos GUARDED_BY(::cs_main){0};
166 167 //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
168 arith_uint256 nChainWork{};
169 170 //! Number of transactions in this block. This will be nonzero if the block
171 //! reached the VALID_TRANSACTIONS level, and zero otherwise.
172 //! Note: in a potential headers-first mode, this number cannot be relied upon
173 unsigned int nTx{0};
174 175 //! (memory only) Number of transactions in the chain up to and including this block.
176 //! This value will be non-zero if this block and all previous blocks back
177 //! to the genesis block or an assumeutxo snapshot block have reached the
178 //! VALID_TRANSACTIONS level.
179 uint64_t m_chain_tx_count{0};
180 181 //! Verification status of this block. See enum BlockStatus
182 //!
183 //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot
184 //! load to avoid a spurious startup failure requiring -reindex.
185 //! @sa NeedsRedownload
186 //! @sa ActivateSnapshot
187 uint32_t nStatus GUARDED_BY(::cs_main){0};
188 189 //! block header
190 int32_t nVersion{0};
191 uint256 hashMerkleRoot{};
192 uint32_t nTime{0};
193 uint32_t nBits{0};
194 uint32_t nNonce{0};
195 196 //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
197 //! Initialized to SEQ_ID_INIT_FROM_DISK{1} when loading blocks from disk, except for blocks
198 //! belonging to the best chain which overwrite it to SEQ_ID_BEST_CHAIN_FROM_DISK{0}.
199 int32_t nSequenceId{SEQ_ID_INIT_FROM_DISK};
200 201 //! (memory only) Maximum nTime in the chain up to and including this block.
202 unsigned int nTimeMax{0};
203 204 // Fork chain state (only used when ChainType::FORK is active).
205 // Single-lane DAA: one target + one PID, 10-minute blocks.
206 // Fork DAA state. mutable: this is deterministic memoized state,
207 // recomputed on demand from the header chain (pow_fork.cpp) and
208 // persisted on CDiskBlockIndex; serialization writes it back.
209 mutable arith_uint256 nForkTarget{}; // current difficulty target
210 mutable int64_t nForkAvgError{}; // EMA of error (integral accumulator)
211 mutable int64_t nForkLastBlockTime{}; // nTime of the previous fork block
212 mutable int64_t nForkAggregateSeconds{0}; // halving counter
213 214 explicit CBlockIndex(const CBlockHeader& block)
215 : nVersion{block.nVersion},
216 hashMerkleRoot{block.hashMerkleRoot},
217 nTime{block.nTime},
218 nBits{block.nBits},
219 nNonce{block.nNonce}
220 {
221 }
222 223 FlatFilePos GetBlockPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
224 {
225 AssertLockHeld(::cs_main);
226 FlatFilePos ret;
227 if (nStatus & BLOCK_HAVE_DATA) {
228 ret.nFile = nFile;
229 ret.nPos = nDataPos;
230 }
231 return ret;
232 }
233 234 FlatFilePos GetUndoPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
235 {
236 AssertLockHeld(::cs_main);
237 FlatFilePos ret;
238 if (nStatus & BLOCK_HAVE_UNDO) {
239 ret.nFile = nFile;
240 ret.nPos = nUndoPos;
241 }
242 return ret;
243 }
244 245 CBlockHeader GetBlockHeader() const
246 {
247 CBlockHeader block;
248 block.nVersion = nVersion;
249 if (pprev)
250 block.hashPrevBlock = pprev->GetBlockHash();
251 block.hashMerkleRoot = hashMerkleRoot;
252 block.nTime = nTime;
253 block.nBits = nBits;
254 block.nNonce = nNonce;
255 return block;
256 }
257 258 uint256 GetBlockHash() const
259 {
260 assert(phashBlock != nullptr);
261 return *phashBlock;
262 }
263 264 /**
265 * Check whether this block and all previous blocks back to the genesis block or an assumeutxo snapshot block have
266 * reached VALID_TRANSACTIONS and had transactions downloaded (and stored to disk) at some point.
267 *
268 * Does not imply the transactions are consensus-valid (ConnectTip might fail)
269 * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true)
270 *
271 * Note that this will be true for the snapshot base block, if one is loaded, since its m_chain_tx_count value will have
272 * been set manually based on the related AssumeutxoData entry.
273 */
274 bool HaveNumChainTxs() const { return m_chain_tx_count != 0; }
275 276 NodeSeconds Time() const
277 {
278 return NodeSeconds{std::chrono::seconds{nTime}};
279 }
280 281 int64_t GetBlockTime() const
282 {
283 return (int64_t)nTime;
284 }
285 286 int64_t GetBlockTimeMax() const
287 {
288 return (int64_t)nTimeMax;
289 }
290 291 static constexpr int nMedianTimeSpan = 11;
292 293 int64_t GetMedianTimePast() const
294 {
295 return GetMedianTimePast(nMedianTimeSpan);
296 }
297 298 /** Median of the last `span` block timestamps (parent-chain
299 * semantics use 11; the fork's activation gate uses 101). */
300 int64_t GetMedianTimePast(int span) const
301 {
302 assert(span > 0);
303 std::vector<int64_t> pmedian;
304 pmedian.reserve(span);
305 const CBlockIndex* pindex = this;
306 for (int i = 0; i < span && pindex; i++, pindex = pindex->pprev)
307 pmedian.push_back(pindex->GetBlockTime());
308 309 std::sort(pmedian.begin(), pmedian.end());
310 return pmedian[pmedian.size() / 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 bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
317 EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
318 {
319 AssertLockHeld(::cs_main);
320 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
321 if (nStatus & BLOCK_FAILED_MASK)
322 return false;
323 return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
324 }
325 326 //! Raise the validity level of this block index entry.
327 //! Returns true if the validity was changed.
328 bool RaiseValidity(enum BlockStatus nUpTo) EXCLUSIVE_LOCKS_REQUIRED(::cs_main)
329 {
330 AssertLockHeld(::cs_main);
331 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
332 if (nStatus & BLOCK_FAILED_MASK) return false;
333 334 if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
335 nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
336 return true;
337 }
338 return false;
339 }
340 341 //! Build the skiplist pointer for this entry.
342 void BuildSkip();
343 344 //! Efficiently find an ancestor of this block.
345 CBlockIndex* GetAncestor(int height);
346 const CBlockIndex* GetAncestor(int height) const;
347 348 CBlockIndex() = default;
349 ~CBlockIndex() = default;
350 351 protected:
352 //! CBlockIndex should not allow public copy construction because equality
353 //! comparison via pointer is very common throughout the codebase, making
354 //! use of copy a footgun. Also, use of copies do not have the benefit
355 //! of simplifying lifetime considerations due to attributes like pprev and
356 //! pskip, which are at risk of becoming dangling pointers in a copied
357 //! instance.
358 //!
359 //! We declare these protected instead of simply deleting them so that
360 //! CDiskBlockIndex can reuse copy construction.
361 CBlockIndex(const CBlockIndex&) = default;
362 CBlockIndex& operator=(const CBlockIndex&) = delete;
363 CBlockIndex(CBlockIndex&&) = delete;
364 CBlockIndex& operator=(CBlockIndex&&) = delete;
365 };
366 367 // Fork activation gate: rules apply to a block built on pindexPrev when
368 // the (bias-compensated) fork-window median time past of pindexPrev
369 // reaches the activation timestamp. The bias cancels the median's
370 // ~50-block lag so activation lands near the intended wall time.
371 inline bool IsForkActive(const CBlockIndex* pindexPrev, const Consensus::Params& params)
372 {
373 if (pindexPrev == nullptr) return false;
374 if (params.nForkActivationMTP == std::numeric_limits<int64_t>::max()) return false;
375 return pindexPrev->GetMedianTimePast(params.nForkMTPWindow) + params.nForkActivationBias >= params.nForkActivationMTP;
376 }
377 378 arith_uint256 GetBlockProof(const CBlockIndex& block);
379 /** 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. */
380 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
381 /** Find the forking point between two chain tips. */
382 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
383 384 385 /** Used to marshal pointers into hashes for db storage. */
386 class CDiskBlockIndex : public CBlockIndex
387 {
388 /** Historically CBlockLocator's version field has been written to disk
389 * streams as the client version, but the value has never been used.
390 *
391 * Hard-code to the highest client version ever written.
392 * SerParams can be used if the field requires any meaning in the future.
393 **/
394 static constexpr int DUMMY_VERSION = 259901;
395 396 public:
397 uint256 hashPrev;
398 399 CDiskBlockIndex()
400 {
401 hashPrev = uint256();
402 }
403 404 explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex)
405 {
406 hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
407 }
408 409 SERIALIZE_METHODS(CDiskBlockIndex, obj)
410 {
411 LOCK(::cs_main);
412 int _nVersion = DUMMY_VERSION;
413 READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED));
414 415 READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED));
416 READWRITE(VARINT(obj.nStatus));
417 READWRITE(VARINT(obj.nTx));
418 if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED));
419 if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos));
420 if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos));
421 422 // block header
423 READWRITE(obj.nVersion);
424 READWRITE(obj.hashPrev);
425 READWRITE(obj.hashMerkleRoot);
426 READWRITE(obj.nTime);
427 READWRITE(obj.nBits);
428 READWRITE(obj.nNonce);
429 430 // Fork DAA state (v259901+): the PI controller state and the
431 // aggregate-seconds halving counter. Persisted so that node
432 // restart / fresh sync validates with the same function as an
433 // uptime node. Older index files leave them zeroed; the state
434 // is then recomputed from the activation point on demand.
435 if (_nVersion >= 259901) {
436 uint256 fork_target_ser = ArithToUint256(obj.nForkTarget);
437 READWRITE(fork_target_ser);
438 obj.nForkTarget = UintToArith256(fork_target_ser);
439 READWRITE(VARINT_MODE(obj.nForkAvgError, VarIntMode::NONNEGATIVE_SIGNED));
440 READWRITE(VARINT_MODE(obj.nForkLastBlockTime, VarIntMode::NONNEGATIVE_SIGNED));
441 READWRITE(VARINT_MODE(obj.nForkAggregateSeconds, VarIntMode::NONNEGATIVE_SIGNED));
442 }
443 }
444 445 uint256 ConstructBlockHash() const
446 {
447 CBlockHeader block;
448 block.nVersion = nVersion;
449 block.hashPrevBlock = hashPrev;
450 block.hashMerkleRoot = hashMerkleRoot;
451 block.nTime = nTime;
452 block.nBits = nBits;
453 block.nNonce = nNonce;
454 return block.GetHash();
455 }
456 457 uint256 GetBlockHash() = delete;
458 std::string ToString() = delete;
459 };
460 461 /** An in-memory indexed chain of blocks. */
462 class CChain
463 {
464 private:
465 std::vector<CBlockIndex*> vChain;
466 467 public:
468 CChain() = default;
469 CChain(const CChain&) = delete;
470 CChain& operator=(const CChain&) = delete;
471 472 /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
473 CBlockIndex* Genesis() const
474 {
475 return vChain.size() > 0 ? vChain[0] : nullptr;
476 }
477 478 /** Returns the index entry for the tip of this chain, or nullptr if none. */
479 CBlockIndex* Tip() const
480 {
481 return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
482 }
483 484 /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
485 CBlockIndex* operator[](int nHeight) const
486 {
487 if (nHeight < 0 || nHeight >= (int)vChain.size())
488 return nullptr;
489 return vChain[nHeight];
490 }
491 492 /** Efficiently check whether a block is present in this chain. */
493 bool Contains(const CBlockIndex* pindex) const
494 {
495 return (*this)[pindex->nHeight] == pindex;
496 }
497 498 /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
499 CBlockIndex* Next(const CBlockIndex* pindex) const
500 {
501 if (Contains(pindex))
502 return (*this)[pindex->nHeight + 1];
503 else
504 return nullptr;
505 }
506 507 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
508 int Height() const
509 {
510 return int(vChain.size()) - 1;
511 }
512 513 /** Set/initialize a chain with a given tip. */
514 void SetTip(CBlockIndex& block);
515 516 /** Return a CBlockLocator that refers to the tip in of this chain. */
517 CBlockLocator GetLocator() const;
518 519 /** Find the last common block between this chain and a block index entry. */
520 const CBlockIndex* FindFork(const CBlockIndex* pindex) const;
521 522 /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */
523 CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const;
524 };
525 526 /** Get a locator for a block index entry. */
527 CBlockLocator GetLocator(const CBlockIndex* index);
528 529 /** Construct a list of hash entries to put in a locator. */
530 std::vector<uint256> LocatorEntries(const CBlockIndex* index);
531 532 #endif // LIMENKA_CHAIN_H
533