1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2014 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.
6 #ifndef BITCOIN_CHAIN_H
7 #define BITCOIN_CHAIN_H
9 #include "arith_uint256.h"
10 #include "primitives/block.h"
12 #include "tinyformat.h"
17 #include <boost/foreach.hpp>
24 ADD_SERIALIZE_METHODS
;
26 template <typename Stream
, typename Operation
>
27 inline void SerializationOp(Stream
& s
, Operation ser_action
, int nType
, int nVersion
) {
28 READWRITE(VARINT(nFile
));
29 READWRITE(VARINT(nPos
));
36 CDiskBlockPos(int nFileIn
, unsigned int nPosIn
) {
41 friend bool operator==(const CDiskBlockPos
&a
, const CDiskBlockPos
&b
) {
42 return (a
.nFile
== b
.nFile
&& a
.nPos
== b
.nPos
);
45 friend bool operator!=(const CDiskBlockPos
&a
, const CDiskBlockPos
&b
) {
49 void SetNull() { nFile
= -1; nPos
= 0; }
50 bool IsNull() const { return (nFile
== -1); }
52 std::string
ToString() const
54 return strprintf("CBlockDiskPos(nFile=%i, nPos=%i)", nFile
, nPos
);
61 BLOCK_VALID_UNKNOWN
= 0,
63 //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
64 BLOCK_VALID_HEADER
= 1,
66 //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
67 //! are also at least TREE.
71 * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
72 * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
73 * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
75 BLOCK_VALID_TRANSACTIONS
= 3,
77 //! Outputs do not overspend inputs, no double spends, coinbase output ok, immature coinbase spends, BIP30.
78 //! Implies all parents are also at least CHAIN.
79 BLOCK_VALID_CHAIN
= 4,
81 //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
82 BLOCK_VALID_SCRIPTS
= 5,
84 //! All validity bits.
85 BLOCK_VALID_MASK
= BLOCK_VALID_HEADER
| BLOCK_VALID_TREE
| BLOCK_VALID_TRANSACTIONS
|
86 BLOCK_VALID_CHAIN
| BLOCK_VALID_SCRIPTS
,
88 BLOCK_HAVE_DATA
= 8, //! full block available in blk*.dat
89 BLOCK_HAVE_UNDO
= 16, //! undo data available in rev*.dat
90 BLOCK_HAVE_MASK
= BLOCK_HAVE_DATA
| BLOCK_HAVE_UNDO
,
92 BLOCK_FAILED_VALID
= 32, //! stage after last reached validness failed
93 BLOCK_FAILED_CHILD
= 64, //! descends from failed block
94 BLOCK_FAILED_MASK
= BLOCK_FAILED_VALID
| BLOCK_FAILED_CHILD
,
97 /** The block chain is a tree shaped structure starting with the
98 * genesis block at the root, with each block potentially having multiple
99 * candidates to be the next block. A blockindex may have multiple pprev pointing
100 * to it, but at most one of them can be part of the currently active branch.
105 //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
106 const uint256
* phashBlock
;
108 //! pointer to the index of the predecessor of this block
111 //! pointer to the index of some further predecessor of this block
114 //! height of the entry in the chain. The genesis block has height 0
117 //! Which # file this block is stored in (blk?????.dat)
120 //! Byte offset within blk?????.dat where this block's data is stored
121 unsigned int nDataPos
;
123 //! Byte offset within rev?????.dat where this block's undo data is stored
124 unsigned int nUndoPos
;
126 //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
127 arith_uint256 nChainWork
;
129 //! Number of transactions in this block.
130 //! Note: in a potential headers-first mode, this number cannot be relied upon
133 //! (memory only) Number of transactions in the chain up to and including this block.
134 //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
135 //! Change to 64-bit type when necessary; won't happen before 2030
136 unsigned int nChainTx
;
138 //! Verification status of this block. See enum BlockStatus
139 unsigned int nStatus
;
143 uint256 hashMerkleRoot
;
148 //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
149 uint32_t nSequenceId
;
160 nChainWork
= arith_uint256();
167 hashMerkleRoot
= uint256();
178 CBlockIndex(const CBlockHeader
& block
)
182 nVersion
= block
.nVersion
;
183 hashMerkleRoot
= block
.hashMerkleRoot
;
186 nNonce
= block
.nNonce
;
189 CDiskBlockPos
GetBlockPos() const {
191 if (nStatus
& BLOCK_HAVE_DATA
) {
198 CDiskBlockPos
GetUndoPos() const {
200 if (nStatus
& BLOCK_HAVE_UNDO
) {
207 CBlockHeader
GetBlockHeader() const
210 block
.nVersion
= nVersion
;
212 block
.hashPrevBlock
= pprev
->GetBlockHash();
213 block
.hashMerkleRoot
= hashMerkleRoot
;
216 block
.nNonce
= nNonce
;
220 uint256
GetBlockHash() const
225 int64_t GetBlockTime() const
227 return (int64_t)nTime
;
230 enum { nMedianTimeSpan
=11 };
232 int64_t GetMedianTimePast() const
234 int64_t pmedian
[nMedianTimeSpan
];
235 int64_t* pbegin
= &pmedian
[nMedianTimeSpan
];
236 int64_t* pend
= &pmedian
[nMedianTimeSpan
];
238 const CBlockIndex
* pindex
= this;
239 for (int i
= 0; i
< nMedianTimeSpan
&& pindex
; i
++, pindex
= pindex
->pprev
)
240 *(--pbegin
) = pindex
->GetBlockTime();
242 std::sort(pbegin
, pend
);
243 return pbegin
[(pend
- pbegin
)/2];
246 std::string
ToString() const
248 return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
250 hashMerkleRoot
.ToString(),
251 GetBlockHash().ToString());
254 //! Check whether this block index entry is valid up to the passed validity level.
255 bool IsValid(enum BlockStatus nUpTo
= BLOCK_VALID_TRANSACTIONS
) const
257 assert(!(nUpTo
& ~BLOCK_VALID_MASK
)); // Only validity flags allowed.
258 if (nStatus
& BLOCK_FAILED_MASK
)
260 return ((nStatus
& BLOCK_VALID_MASK
) >= nUpTo
);
263 //! Raise the validity level of this block index entry.
264 //! Returns true if the validity was changed.
265 bool RaiseValidity(enum BlockStatus nUpTo
)
267 assert(!(nUpTo
& ~BLOCK_VALID_MASK
)); // Only validity flags allowed.
268 if (nStatus
& BLOCK_FAILED_MASK
)
270 if ((nStatus
& BLOCK_VALID_MASK
) < nUpTo
) {
271 nStatus
= (nStatus
& ~BLOCK_VALID_MASK
) | nUpTo
;
277 //! Build the skiplist pointer for this entry.
280 //! Efficiently find an ancestor of this block.
281 CBlockIndex
* GetAncestor(int height
);
282 const CBlockIndex
* GetAncestor(int height
) const;
285 /** Used to marshal pointers into hashes for db storage. */
286 class CDiskBlockIndex
: public CBlockIndex
292 hashPrev
= uint256();
295 explicit CDiskBlockIndex(const CBlockIndex
* pindex
) : CBlockIndex(*pindex
) {
296 hashPrev
= (pprev
? pprev
->GetBlockHash() : uint256());
299 ADD_SERIALIZE_METHODS
;
301 template <typename Stream
, typename Operation
>
302 inline void SerializationOp(Stream
& s
, Operation ser_action
, int nType
, int nVersion
) {
303 if (!(nType
& SER_GETHASH
))
304 READWRITE(VARINT(nVersion
));
306 READWRITE(VARINT(nHeight
));
307 READWRITE(VARINT(nStatus
));
308 READWRITE(VARINT(nTx
));
309 if (nStatus
& (BLOCK_HAVE_DATA
| BLOCK_HAVE_UNDO
))
310 READWRITE(VARINT(nFile
));
311 if (nStatus
& BLOCK_HAVE_DATA
)
312 READWRITE(VARINT(nDataPos
));
313 if (nStatus
& BLOCK_HAVE_UNDO
)
314 READWRITE(VARINT(nUndoPos
));
317 READWRITE(this->nVersion
);
319 READWRITE(hashMerkleRoot
);
325 uint256
GetBlockHash() const
328 block
.nVersion
= nVersion
;
329 block
.hashPrevBlock
= hashPrev
;
330 block
.hashMerkleRoot
= hashMerkleRoot
;
333 block
.nNonce
= nNonce
;
334 return block
.GetHash();
338 std::string
ToString() const
340 std::string str
= "CDiskBlockIndex(";
341 str
+= CBlockIndex::ToString();
342 str
+= strprintf("\n hashBlock=%s, hashPrev=%s)",
343 GetBlockHash().ToString(),
344 hashPrev
.ToString());
349 /** An in-memory indexed chain of blocks. */
352 std::vector
<CBlockIndex
*> vChain
;
355 /** Returns the index entry for the genesis block of this chain, or NULL if none. */
356 CBlockIndex
*Genesis() const {
357 return vChain
.size() > 0 ? vChain
[0] : NULL
;
360 /** Returns the index entry for the tip of this chain, or NULL if none. */
361 CBlockIndex
*Tip() const {
362 return vChain
.size() > 0 ? vChain
[vChain
.size() - 1] : NULL
;
365 /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */
366 CBlockIndex
*operator[](int nHeight
) const {
367 if (nHeight
< 0 || nHeight
>= (int)vChain
.size())
369 return vChain
[nHeight
];
372 /** Compare two chains efficiently. */
373 friend bool operator==(const CChain
&a
, const CChain
&b
) {
374 return a
.vChain
.size() == b
.vChain
.size() &&
375 a
.vChain
[a
.vChain
.size() - 1] == b
.vChain
[b
.vChain
.size() - 1];
378 /** Efficiently check whether a block is present in this chain. */
379 bool Contains(const CBlockIndex
*pindex
) const {
380 return (*this)[pindex
->nHeight
] == pindex
;
383 /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */
384 CBlockIndex
*Next(const CBlockIndex
*pindex
) const {
385 if (Contains(pindex
))
386 return (*this)[pindex
->nHeight
+ 1];
391 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
393 return vChain
.size() - 1;
396 /** Set/initialize a chain with a given tip. */
397 void SetTip(CBlockIndex
*pindex
);
399 /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
400 CBlockLocator
GetLocator(const CBlockIndex
*pindex
= NULL
) const;
402 /** Find the last common block between this chain and a block index entry. */
403 const CBlockIndex
*FindFork(const CBlockIndex
*pindex
) const;
406 #endif // BITCOIN_CHAIN_H