1 package blockchain
2 3 import (
4 "github.com/p9c/p9/pkg/chaincfg"
5 "github.com/p9c/p9/pkg/fork"
6 "math/big"
7 "sort"
8 "sync"
9 "sync/atomic"
10 "time"
11 12 "github.com/p9c/p9/pkg/chainhash"
13 "github.com/p9c/p9/pkg/database"
14 "github.com/p9c/p9/pkg/wire"
15 )
16 17 // blockStatus is a bit field representing the validation state of the block.
18 type blockStatus byte
19 20 const (
21 // statusDataStored indicates that the block's payload is stored on disk.
22 statusDataStored blockStatus = 1 << iota
23 // statusValid indicates that the block has been fully validated.
24 statusValid
25 // statusValidateFailed indicates that the block has failed validation.
26 statusValidateFailed
27 // statusInvalidAncestor indicates that one of the block's ancestors has has failed validation, thus the block is
28 // also invalid.
29 statusInvalidAncestor
30 // statusNone indicates that the block has no validation state flags set.
31 //
32 // NOTE: This must be defined last in order to avoid influencing iota.
33 statusNone blockStatus = 0
34 )
35 36 // HaveData returns whether the full block data is stored in the database. This will return false for a block node where
37 // only the header is downloaded or kept.
38 func (status blockStatus) HaveData() bool {
39 return status&statusDataStored != 0
40 }
41 42 // KnownValid returns whether the block is known to be valid. This will return false for a valid block that has not been
43 // fully validated yet.
44 func (status blockStatus) KnownValid() bool {
45 return status&statusValid != 0
46 }
47 48 // KnownInvalid returns whether the block is known to be invalid. This may be because the block itself failed validation
49 // or any of its ancestors is invalid. This will return false for invalid blocks that have not been proven invalid yet.
50 func (status blockStatus) KnownInvalid() bool {
51 return status&(statusValidateFailed|statusInvalidAncestor) != 0
52 }
53 54 // BlockNode represents a block within the block chain and is primarily used to aid in selecting the best chain to be
55 // the main chain. The main chain is stored into the block database.
56 type BlockNode struct {
57 // NOTE: Additions, deletions, or modifications to the order of the definitions in this struct should not be changed
58 // without considering how it affects alignment on 64-bit platforms. The current order is specifically crafted to
59 // result in minimal padding. There will be hundreds of thousands of these in memory, so a few extra bytes of
60 // padding adds up. parent is the parent block for this node.
61 parent *BlockNode
62 // hash is the double sha 256 of the block.
63 hash chainhash.Hash
64 // workSum is the total amount of work in the chain up to and including this node.
65 workSum *big.Int
66 // height is the position in the block chain.
67 height int32
68 // Some fields from block headers to aid in best chain selection and reconstructing headers from memory. These must
69 // be treated as immutable and are intentionally ordered to avoid padding on 64-bit platforms.
70 version int32
71 bits uint32
72 nonce uint32
73 timestamp int64
74 merkleRoot chainhash.Hash
75 // status is a bitfield representing the validation state of the block. The status field, unlike the other fields,
76 // may be written to and so should only be accessed using the concurrent -safe NodeStatus method on blockIndex once
77 // the node has been added to the global index.
78 status blockStatus
79 // Diffs is the computed difficulty targets for a block to be connected to this one
80 Diffs atomic.Value
81 }
82 83 // initBlockNode initializes a block node from the given header and parent node, calculating the height and workSum from
84 // the respective fields on the parent. This function is NOT safe for concurrent access. It must only be called when
85 // initially creating a node.
86 func initBlockNode(node *BlockNode, blockHeader *wire.BlockHeader, parent *BlockNode) {
87 *node = BlockNode{
88 hash: blockHeader.BlockHash(),
89 version: blockHeader.Version,
90 bits: blockHeader.Bits,
91 nonce: blockHeader.Nonce,
92 timestamp: blockHeader.Timestamp.Unix(),
93 merkleRoot: blockHeader.MerkleRoot,
94 }
95 if parent != nil {
96 node.parent = parent
97 node.height = parent.height + 1
98 node.workSum = CalcWork(blockHeader.Bits, node.height, node.version)
99 parent.workSum = CalcWork(parent.bits, parent.height, parent.version)
100 node.workSum = node.workSum.Add(parent.workSum, node.workSum)
101 }
102 }
103 104 // NewBlockNode returns a new block node for the given block header and parent node, calculating the height and workSum
105 // from the respective fields on the parent. This function is NOT safe for concurrent access.
106 func NewBlockNode(blockHeader *wire.BlockHeader, parent *BlockNode) *BlockNode {
107 var node BlockNode
108 initBlockNode(&node, blockHeader, parent)
109 return &node
110 }
111 112 // Header constructs a block header from the node and returns it. This function is safe for concurrent access.
113 func (node *BlockNode) Header() wire.BlockHeader {
114 // No lock is needed because all accessed fields are immutable.
115 prevHash := &zeroHash
116 if node.parent != nil {
117 prevHash = &node.parent.hash
118 }
119 return wire.BlockHeader{
120 Version: node.version,
121 PrevBlock: *prevHash,
122 MerkleRoot: node.merkleRoot,
123 Timestamp: time.Unix(node.timestamp, 0),
124 Bits: node.bits,
125 Nonce: node.nonce,
126 }
127 }
128 129 // Ancestor returns the ancestor block node at the provided height by following the chain backwards from this node. The
130 // returned block will be nil when a height is requested that is after the height of the passed node or is less than
131 // zero. This function is safe for concurrent access.
132 func (node *BlockNode) Ancestor(height int32) *BlockNode {
133 if height < 0 || height > node.height {
134 return nil
135 }
136 n := node
137 for ; n != nil && n.height != height; n = n.parent {
138 // Intentionally left blank
139 }
140 return n
141 }
142 143 // RelativeAncestor returns the ancestor block node a relative 'distance' blocks before this node. This is equivalent to
144 // calling Ancestor with the node's height minus provided distance. This function is safe for concurrent access.
145 func (node *BlockNode) RelativeAncestor(distance int32) *BlockNode {
146 return node.Ancestor(node.height - distance)
147 }
148 149 // CalcPastMedianTime calculates the median time of the previous few blocks prior to, and including, the block node.
150 // This function is safe for concurrent access.
151 func (node *BlockNode) CalcPastMedianTime() time.Time {
152 // Create a slice of the previous few block timestamps used to calculate the median per the number defined by the
153 // constant medianTimeBlocks.
154 timestamps := make([]int64, medianTimeBlocks)
155 numNodes := 0
156 iterNode := node
157 for i := 0; i < medianTimeBlocks && iterNode != nil; i++ {
158 timestamps[i] = iterNode.timestamp
159 numNodes++
160 iterNode = iterNode.parent
161 }
162 // Prune the slice to the actual number of available timestamps which will be fewer than desired near the beginning
163 // of the block chain and txsort them.
164 timestamps = timestamps[:numNodes]
165 sort.Sort(timeSorter(timestamps))
166 // NOTE: The consensus rules incorrectly calculate the median for even numbers of blocks. A true median averages the
167 // middle two elements for a set with an even number of elements in it. Since the constant for the previous number
168 // of blocks to be used is odd, this is only an issue for a few blocks near the beginning of the chain. I suspect
169 // this is an optimization even though the result is slightly wrong for a few of the first blocks since after the
170 // first few blocks, there will always be an odd number of blocks in the set per the constant. This code follows
171 // suit to ensure the same rules are used, however, be aware that should the medianTimeBlocks constant ever be
172 // changed to an even number, this code will be wrong.
173 medianTimestamp := timestamps[numNodes/2]
174 return time.Unix(medianTimestamp, 0)
175 }
176 177 // blockIndex provides facilities for keeping track of an in-memory index of the block chain. Although the name block
178 // chain suggests a single chain of blocks, it is actually a tree-shaped structure where any node can have multiple
179 // children. However, there can only be one active branch which does indeed form a chain from the tip all the way back
180 // to the genesis block.
181 type blockIndex struct {
182 // The following fields are set when the instance is created and can't be changed afterwards, so there is no need to
183 // protect them with a separate mutex.
184 db database.DB
185 chainParams *chaincfg.Params
186 sync.RWMutex
187 index map[chainhash.Hash]*BlockNode
188 dirty map[*BlockNode]struct{}
189 }
190 191 // newBlockIndex returns a new empty instance of a block index. The index will be dynamically populated as block nodes
192 // are loaded from the database and manually added.
193 func newBlockIndex(db database.DB, chainParams *chaincfg.Params) *blockIndex {
194 return &blockIndex{
195 db: db,
196 chainParams: chainParams,
197 index: make(map[chainhash.Hash]*BlockNode),
198 dirty: make(map[*BlockNode]struct{}),
199 }
200 }
201 202 // HaveBlock returns whether or not the block index contains the provided hash. This function is safe for concurrent
203 // access.
204 func (bi *blockIndex) HaveBlock(hash *chainhash.Hash) bool {
205 bi.RLock()
206 _, hasBlock := bi.index[*hash]
207 bi.RUnlock()
208 return hasBlock
209 }
210 211 // LookupNode returns the block node identified by the provided hash. It will return nil if there is no entry for the
212 // hash. This function is safe for concurrent access.
213 func (bi *blockIndex) LookupNode(hash *chainhash.Hash) *BlockNode {
214 bi.RLock()
215 node := bi.index[*hash]
216 bi.RUnlock()
217 return node
218 }
219 220 // AddNode adds the provided node to the block index and marks it as dirty. Duplicate entries are not checked so it is
221 // up to caller to avoid adding them. This function is safe for concurrent access.
222 func (bi *blockIndex) AddNode(node *BlockNode) {
223 bi.Lock()
224 bi.addNode(node)
225 bi.dirty[node] = struct{}{}
226 bi.Unlock()
227 }
228 229 // addNode adds the provided node to the block index, but does not mark it as dirty. This can be used while initializing
230 // the block index. This function is NOT safe for concurrent access.
231 func (bi *blockIndex) addNode(node *BlockNode) {
232 bi.index[node.hash] = node
233 }
234 235 // NodeStatus provides concurrent-safe access to the status field of a node. This function is safe for concurrent
236 // access.
237 func (bi *blockIndex) NodeStatus(node *BlockNode) blockStatus {
238 bi.RLock()
239 status := node.status
240 bi.RUnlock()
241 return status
242 }
243 244 // SetStatusFlags flips the provided status flags on the block node to on, regardless of whether they were on or off
245 // previously. This does not unset any flags currently on. This function is safe for concurrent access.
246 func (bi *blockIndex) SetStatusFlags(node *BlockNode, flags blockStatus) {
247 bi.Lock()
248 node.status |= flags
249 bi.dirty[node] = struct{}{}
250 bi.Unlock()
251 }
252 253 // UnsetStatusFlags flips the provided status flags on the block node to off, regardless of whether they were on or off
254 // previously. This function is safe for concurrent access.
255 func (bi *blockIndex) UnsetStatusFlags(node *BlockNode, flags blockStatus) {
256 bi.Lock()
257 node.status &^= flags
258 bi.dirty[node] = struct{}{}
259 bi.Unlock()
260 }
261 262 // flushToDB writes all dirty block nodes to the database. If all writes succeed, this clears the dirty set.
263 func (bi *blockIndex) flushToDB() (e error) {
264 bi.Lock()
265 if len(bi.dirty) == 0 {
266 bi.Unlock()
267 return nil
268 }
269 e = bi.db.Update(
270 func(dbTx database.Tx) (e error) {
271 for node := range bi.dirty {
272 e := dbStoreBlockNode(dbTx, node)
273 if e != nil {
274 E.Ln(e)
275 return e
276 }
277 }
278 return nil
279 },
280 )
281 // If write was successful, clear the dirty set.
282 if e == nil {
283 bi.dirty = make(map[*BlockNode]struct{})
284 }
285 bi.Unlock()
286 return e
287 }
288 289 // GetAlgo returns the algorithm of a block node
290 func (node *BlockNode) GetAlgo() int32 {
291 return node.version
292 }
293 294 // GetLastWithAlgo returns the newest block from node with specified algo
295 func (node *BlockNode) GetLastWithAlgo(algo int32) (prev *BlockNode) {
296 if node == nil {
297 return
298 }
299 if fork.GetCurrent(node.height+1) == 0 {
300 // F.Ln("checking pre-hardfork algo versions")
301 if algo != 514 &&
302 algo != 2 {
303 D.Ln("irregular version", algo, "block, assuming 2 (sha256d)")
304 algo = 2
305 }
306 }
307 prev = node
308 for {
309 if prev == nil {
310 return nil
311 }
312 // Tracef("node %d %d %8x", prev.height, prev.version, prev.bits)
313 prevversion := prev.version
314 if fork.GetCurrent(prev.height) == 0 {
315 // F.Ln("checking pre-hardfork algo versions")
316 if prev.version != 514 &&
317 prev.version != 2 {
318 D.Ln("irregular version block", prev.version, ", assuming 2 (sha256d)")
319 prevversion = 2
320 }
321 }
322 if prevversion == algo {
323 // Tracef(
324 // "found height %d version %d prev version %d prev bits %8x",
325 // prev.height, prev.version, prevversion, prev.bits)
326 return
327 }
328 prev = prev.RelativeAncestor(1)
329 }
330 }
331 332 // if node == nil {
333 // F.Ln("this node is nil")
334 // return nil
335 // }
336 // prev = node.RelativeAncestor(1)
337 // if prev == nil {
338 // F.Ln("the previous node was nil")
339 // return nil
340 // }
341 // prevFork := fork.GetCurrent(prev.height)
342 // if prevFork == 0 {
343 // if algo != 514 &&
344 // algo != 2 {
345 // F.Ln("bogus version halcyon", algo)
346 // algo = 2
347 // }
348 // }
349 // if prev.version == algo {
350 // Tracef("found previous %d %d %08x", prev.height, prev.version,
351 // prev.bits)
352 // return prev
353 // }
354 // prev = prev.RelativeAncestor(1)
355 // for {
356 // if prev == nil {
357 // F.Ln("passed through genesis")
358 // return nil
359 // }
360 // F.Ln(prev.height)
361 // prevVersion := prev.version
362 // if fork.GetCurrent(prev.height) == 0 {
363 // if prevVersion != 514 &&
364 // prevVersion != 2 {
365 // F.Ln("bogus version", prevVersion)
366 // prevVersion = 2
367 // }
368 // }
369 // if prevVersion == algo {
370 // Tracef("found previous %d %d %08x", prev.height, prev.version,
371 // prev.bits)
372 // return prev
373 // } else {
374 // F.Ln(prev.height)
375 // prev = prev.RelativeAncestor(1)
376 // }
377 // }
378 // }
379