]>
Commit | Line | Data |
---|---|---|
e8b5f0d5 | 1 | // Copyright (c) 2009-2010 Satoshi Nakamoto |
f914f1a7 | 2 | // Copyright (c) 2009-2014 The Bitcoin Core developers |
7bec6dd2 | 3 | // Distributed under the MIT software license, see the accompanying |
e8b5f0d5 | 4 | // file COPYING or http://www.opensource.org/licenses/mit-license.php. |
5 | ||
84738627 PJ |
6 | #ifndef BITCOIN_CHAIN_H |
7 | #define BITCOIN_CHAIN_H | |
e8b5f0d5 | 8 | |
734f85c4 | 9 | #include "arith_uint256.h" |
d2270111 | 10 | #include "primitives/block.h" |
e8b5f0d5 | 11 | #include "pow.h" |
85c579e3 | 12 | #include "tinyformat.h" |
e8b5f0d5 | 13 | #include "uint256.h" |
14 | ||
15 | #include <vector> | |
16 | ||
17 | #include <boost/foreach.hpp> | |
18 | ||
19 | struct CDiskBlockPos | |
20 | { | |
21 | int nFile; | |
22 | unsigned int nPos; | |
23 | ||
24 | ADD_SERIALIZE_METHODS; | |
25 | ||
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)); | |
30 | } | |
31 | ||
32 | CDiskBlockPos() { | |
33 | SetNull(); | |
34 | } | |
35 | ||
36 | CDiskBlockPos(int nFileIn, unsigned int nPosIn) { | |
37 | nFile = nFileIn; | |
38 | nPos = nPosIn; | |
39 | } | |
40 | ||
41 | friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) { | |
42 | return (a.nFile == b.nFile && a.nPos == b.nPos); | |
43 | } | |
44 | ||
45 | friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) { | |
46 | return !(a == b); | |
47 | } | |
48 | ||
49 | void SetNull() { nFile = -1; nPos = 0; } | |
50 | bool IsNull() const { return (nFile == -1); } | |
51 | }; | |
52 | ||
53 | enum BlockStatus { | |
2fdc3351 | 54 | //! Unused. |
e8b5f0d5 | 55 | BLOCK_VALID_UNKNOWN = 0, |
341735eb | 56 | |
2fdc3351 | 57 | //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future |
341735eb PW |
58 | BLOCK_VALID_HEADER = 1, |
59 | ||
2fdc3351 MF |
60 | //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents |
61 | //! are also at least TREE. | |
341735eb PW |
62 | BLOCK_VALID_TREE = 2, |
63 | ||
2fdc3351 MF |
64 | /** |
65 | * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids, | |
66 | * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all | |
67 | * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set. | |
68 | */ | |
341735eb PW |
69 | BLOCK_VALID_TRANSACTIONS = 3, |
70 | ||
2fdc3351 MF |
71 | //! Outputs do not overspend inputs, no double spends, coinbase output ok, immature coinbase spends, BIP30. |
72 | //! Implies all parents are also at least CHAIN. | |
341735eb PW |
73 | BLOCK_VALID_CHAIN = 4, |
74 | ||
2fdc3351 | 75 | //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS. |
341735eb PW |
76 | BLOCK_VALID_SCRIPTS = 5, |
77 | ||
2fdc3351 | 78 | //! All validity bits. |
e8b5f0d5 | 79 | BLOCK_VALID_MASK = BLOCK_VALID_HEADER | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS | |
80 | BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS, | |
81 | ||
2fdc3351 MF |
82 | BLOCK_HAVE_DATA = 8, //! full block available in blk*.dat |
83 | BLOCK_HAVE_UNDO = 16, //! undo data available in rev*.dat | |
e8b5f0d5 | 84 | BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO, |
85 | ||
2fdc3351 MF |
86 | BLOCK_FAILED_VALID = 32, //! stage after last reached validness failed |
87 | BLOCK_FAILED_CHILD = 64, //! descends from failed block | |
e8b5f0d5 | 88 | BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD, |
89 | }; | |
90 | ||
91 | /** The block chain is a tree shaped structure starting with the | |
92 | * genesis block at the root, with each block potentially having multiple | |
93 | * candidates to be the next block. A blockindex may have multiple pprev pointing | |
94 | * to it, but at most one of them can be part of the currently active branch. | |
95 | */ | |
96 | class CBlockIndex | |
97 | { | |
98 | public: | |
bf7835c2 | 99 | //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex |
e8b5f0d5 | 100 | const uint256* phashBlock; |
101 | ||
2fdc3351 | 102 | //! pointer to the index of the predecessor of this block |
e8b5f0d5 | 103 | CBlockIndex* pprev; |
104 | ||
2fdc3351 | 105 | //! pointer to the index of some further predecessor of this block |
e8b5f0d5 | 106 | CBlockIndex* pskip; |
107 | ||
2fdc3351 | 108 | //! height of the entry in the chain. The genesis block has height 0 |
e8b5f0d5 | 109 | int nHeight; |
110 | ||
2fdc3351 | 111 | //! Which # file this block is stored in (blk?????.dat) |
e8b5f0d5 | 112 | int nFile; |
113 | ||
2fdc3351 | 114 | //! Byte offset within blk?????.dat where this block's data is stored |
e8b5f0d5 | 115 | unsigned int nDataPos; |
116 | ||
2fdc3351 | 117 | //! Byte offset within rev?????.dat where this block's undo data is stored |
e8b5f0d5 | 118 | unsigned int nUndoPos; |
119 | ||
2fdc3351 | 120 | //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block |
734f85c4 | 121 | arith_uint256 nChainWork; |
e8b5f0d5 | 122 | |
2fdc3351 MF |
123 | //! Number of transactions in this block. |
124 | //! Note: in a potential headers-first mode, this number cannot be relied upon | |
e8b5f0d5 | 125 | unsigned int nTx; |
126 | ||
2fdc3351 MF |
127 | //! (memory only) Number of transactions in the chain up to and including this block. |
128 | //! This value will be non-zero only if and only if transactions for this block and all its parents are available. | |
129 | //! Change to 64-bit type when necessary; won't happen before 2030 | |
130 | unsigned int nChainTx; | |
e8b5f0d5 | 131 | |
2fdc3351 | 132 | //! Verification status of this block. See enum BlockStatus |
e8b5f0d5 | 133 | unsigned int nStatus; |
134 | ||
2fdc3351 | 135 | //! block header |
e8b5f0d5 | 136 | int nVersion; |
137 | uint256 hashMerkleRoot; | |
138 | unsigned int nTime; | |
139 | unsigned int nBits; | |
140 | unsigned int nNonce; | |
141 | ||
2fdc3351 | 142 | //! (memory only) Sequential id assigned to distinguish order in which blocks are received. |
e8b5f0d5 | 143 | uint32_t nSequenceId; |
144 | ||
145 | void SetNull() | |
146 | { | |
147 | phashBlock = NULL; | |
148 | pprev = NULL; | |
149 | pskip = NULL; | |
150 | nHeight = 0; | |
151 | nFile = 0; | |
152 | nDataPos = 0; | |
153 | nUndoPos = 0; | |
734f85c4 | 154 | nChainWork = arith_uint256(); |
e8b5f0d5 | 155 | nTx = 0; |
156 | nChainTx = 0; | |
157 | nStatus = 0; | |
158 | nSequenceId = 0; | |
159 | ||
160 | nVersion = 0; | |
4f152496 | 161 | hashMerkleRoot = uint256(); |
e8b5f0d5 | 162 | nTime = 0; |
163 | nBits = 0; | |
164 | nNonce = 0; | |
165 | } | |
166 | ||
167 | CBlockIndex() | |
168 | { | |
169 | SetNull(); | |
170 | } | |
171 | ||
341735eb | 172 | CBlockIndex(const CBlockHeader& block) |
e8b5f0d5 | 173 | { |
174 | SetNull(); | |
175 | ||
176 | nVersion = block.nVersion; | |
177 | hashMerkleRoot = block.hashMerkleRoot; | |
178 | nTime = block.nTime; | |
179 | nBits = block.nBits; | |
180 | nNonce = block.nNonce; | |
181 | } | |
182 | ||
183 | CDiskBlockPos GetBlockPos() const { | |
184 | CDiskBlockPos ret; | |
185 | if (nStatus & BLOCK_HAVE_DATA) { | |
186 | ret.nFile = nFile; | |
187 | ret.nPos = nDataPos; | |
188 | } | |
189 | return ret; | |
190 | } | |
191 | ||
192 | CDiskBlockPos GetUndoPos() const { | |
193 | CDiskBlockPos ret; | |
194 | if (nStatus & BLOCK_HAVE_UNDO) { | |
195 | ret.nFile = nFile; | |
196 | ret.nPos = nUndoPos; | |
197 | } | |
198 | return ret; | |
199 | } | |
200 | ||
201 | CBlockHeader GetBlockHeader() const | |
202 | { | |
203 | CBlockHeader block; | |
204 | block.nVersion = nVersion; | |
205 | if (pprev) | |
206 | block.hashPrevBlock = pprev->GetBlockHash(); | |
207 | block.hashMerkleRoot = hashMerkleRoot; | |
208 | block.nTime = nTime; | |
209 | block.nBits = nBits; | |
210 | block.nNonce = nNonce; | |
211 | return block; | |
212 | } | |
213 | ||
214 | uint256 GetBlockHash() const | |
215 | { | |
216 | return *phashBlock; | |
217 | } | |
218 | ||
219 | int64_t GetBlockTime() const | |
220 | { | |
221 | return (int64_t)nTime; | |
222 | } | |
223 | ||
e8b5f0d5 | 224 | enum { nMedianTimeSpan=11 }; |
225 | ||
226 | int64_t GetMedianTimePast() const | |
227 | { | |
228 | int64_t pmedian[nMedianTimeSpan]; | |
229 | int64_t* pbegin = &pmedian[nMedianTimeSpan]; | |
230 | int64_t* pend = &pmedian[nMedianTimeSpan]; | |
231 | ||
232 | const CBlockIndex* pindex = this; | |
233 | for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) | |
234 | *(--pbegin) = pindex->GetBlockTime(); | |
235 | ||
236 | std::sort(pbegin, pend); | |
237 | return pbegin[(pend - pbegin)/2]; | |
238 | } | |
239 | ||
e8b5f0d5 | 240 | std::string ToString() const |
241 | { | |
242 | return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", | |
243 | pprev, nHeight, | |
244 | hashMerkleRoot.ToString(), | |
245 | GetBlockHash().ToString()); | |
246 | } | |
247 | ||
2fdc3351 | 248 | //! Check whether this block index entry is valid up to the passed validity level. |
e8b5f0d5 | 249 | bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const |
250 | { | |
251 | assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. | |
252 | if (nStatus & BLOCK_FAILED_MASK) | |
253 | return false; | |
254 | return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); | |
255 | } | |
256 | ||
2fdc3351 MF |
257 | //! Raise the validity level of this block index entry. |
258 | //! Returns true if the validity was changed. | |
e8b5f0d5 | 259 | bool RaiseValidity(enum BlockStatus nUpTo) |
260 | { | |
261 | assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. | |
262 | if (nStatus & BLOCK_FAILED_MASK) | |
263 | return false; | |
264 | if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { | |
265 | nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; | |
266 | return true; | |
267 | } | |
268 | return false; | |
269 | } | |
270 | ||
2fdc3351 | 271 | //! Build the skiplist pointer for this entry. |
e8b5f0d5 | 272 | void BuildSkip(); |
273 | ||
2fdc3351 | 274 | //! Efficiently find an ancestor of this block. |
e8b5f0d5 | 275 | CBlockIndex* GetAncestor(int height); |
276 | const CBlockIndex* GetAncestor(int height) const; | |
277 | }; | |
278 | ||
279 | /** Used to marshal pointers into hashes for db storage. */ | |
280 | class CDiskBlockIndex : public CBlockIndex | |
281 | { | |
282 | public: | |
283 | uint256 hashPrev; | |
284 | ||
285 | CDiskBlockIndex() { | |
4f152496 | 286 | hashPrev = uint256(); |
e8b5f0d5 | 287 | } |
288 | ||
63d1ae55 | 289 | explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) { |
4f152496 | 290 | hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); |
e8b5f0d5 | 291 | } |
292 | ||
293 | ADD_SERIALIZE_METHODS; | |
294 | ||
295 | template <typename Stream, typename Operation> | |
296 | inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { | |
297 | if (!(nType & SER_GETHASH)) | |
298 | READWRITE(VARINT(nVersion)); | |
299 | ||
300 | READWRITE(VARINT(nHeight)); | |
301 | READWRITE(VARINT(nStatus)); | |
302 | READWRITE(VARINT(nTx)); | |
303 | if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) | |
304 | READWRITE(VARINT(nFile)); | |
305 | if (nStatus & BLOCK_HAVE_DATA) | |
306 | READWRITE(VARINT(nDataPos)); | |
307 | if (nStatus & BLOCK_HAVE_UNDO) | |
308 | READWRITE(VARINT(nUndoPos)); | |
309 | ||
310 | // block header | |
311 | READWRITE(this->nVersion); | |
312 | READWRITE(hashPrev); | |
313 | READWRITE(hashMerkleRoot); | |
314 | READWRITE(nTime); | |
315 | READWRITE(nBits); | |
316 | READWRITE(nNonce); | |
317 | } | |
318 | ||
319 | uint256 GetBlockHash() const | |
320 | { | |
321 | CBlockHeader block; | |
322 | block.nVersion = nVersion; | |
323 | block.hashPrevBlock = hashPrev; | |
324 | block.hashMerkleRoot = hashMerkleRoot; | |
325 | block.nTime = nTime; | |
326 | block.nBits = nBits; | |
327 | block.nNonce = nNonce; | |
328 | return block.GetHash(); | |
329 | } | |
330 | ||
331 | ||
332 | std::string ToString() const | |
333 | { | |
334 | std::string str = "CDiskBlockIndex("; | |
335 | str += CBlockIndex::ToString(); | |
336 | str += strprintf("\n hashBlock=%s, hashPrev=%s)", | |
337 | GetBlockHash().ToString(), | |
338 | hashPrev.ToString()); | |
339 | return str; | |
340 | } | |
341 | }; | |
342 | ||
343 | /** An in-memory indexed chain of blocks. */ | |
344 | class CChain { | |
345 | private: | |
346 | std::vector<CBlockIndex*> vChain; | |
347 | ||
348 | public: | |
349 | /** Returns the index entry for the genesis block of this chain, or NULL if none. */ | |
350 | CBlockIndex *Genesis() const { | |
351 | return vChain.size() > 0 ? vChain[0] : NULL; | |
352 | } | |
353 | ||
354 | /** Returns the index entry for the tip of this chain, or NULL if none. */ | |
355 | CBlockIndex *Tip() const { | |
356 | return vChain.size() > 0 ? vChain[vChain.size() - 1] : NULL; | |
357 | } | |
358 | ||
359 | /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */ | |
360 | CBlockIndex *operator[](int nHeight) const { | |
361 | if (nHeight < 0 || nHeight >= (int)vChain.size()) | |
362 | return NULL; | |
363 | return vChain[nHeight]; | |
364 | } | |
365 | ||
366 | /** Compare two chains efficiently. */ | |
367 | friend bool operator==(const CChain &a, const CChain &b) { | |
368 | return a.vChain.size() == b.vChain.size() && | |
369 | a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1]; | |
370 | } | |
371 | ||
372 | /** Efficiently check whether a block is present in this chain. */ | |
373 | bool Contains(const CBlockIndex *pindex) const { | |
374 | return (*this)[pindex->nHeight] == pindex; | |
375 | } | |
376 | ||
377 | /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */ | |
378 | CBlockIndex *Next(const CBlockIndex *pindex) const { | |
379 | if (Contains(pindex)) | |
380 | return (*this)[pindex->nHeight + 1]; | |
381 | else | |
382 | return NULL; | |
383 | } | |
384 | ||
385 | /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */ | |
386 | int Height() const { | |
387 | return vChain.size() - 1; | |
388 | } | |
389 | ||
b7ae2c17 | 390 | /** Set/initialize a chain with a given tip. */ |
391 | void SetTip(CBlockIndex *pindex); | |
e8b5f0d5 | 392 | |
393 | /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */ | |
394 | CBlockLocator GetLocator(const CBlockIndex *pindex = NULL) const; | |
395 | ||
396 | /** Find the last common block between this chain and a block index entry. */ | |
397 | const CBlockIndex *FindFork(const CBlockIndex *pindex) const; | |
398 | }; | |
399 | ||
84738627 | 400 | #endif // BITCOIN_CHAIN_H |