1 // Copyright (c) 2015-2017 The btcsuite developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
13 "github.com/btcsuite/btcd/chaincfg"
14 "github.com/btcsuite/btcd/chaincfg/chainhash"
15 "github.com/btcsuite/btcd/database"
16 "github.com/btcsuite/btcd/wire"
19 // blockNode represents a block within the block chain and is primarily used to
20 // aid in selecting the best chain to be the main chain. The main chain is
21 // stored into the block database.
22 type blockNode struct {
23 // NOTE: Additions, deletions, or modifications to the order of the
24 // definitions in this struct should not be changed without considering
25 // how it affects alignment on 64-bit platforms. The current order is
26 // specifically crafted to result in minimal padding. There will be
27 // hundreds of thousands of these in memory, so a few extra bytes of
30 // parent is the parent block for this node.
33 // hash is the double sha 256 of the block.
36 // workSum is the total amount of work in the chain up to and including
40 // height is the position in the block chain.
43 // Some fields from block headers to aid in best chain selection and
44 // reconstructing headers from memory. These must be treated as
45 // immutable and are intentionally ordered to avoid padding on 64-bit
51 merkleRoot chainhash.Hash
54 // initBlockNode initializes a block node from the given header and height. The
55 // node is completely disconnected from the chain and the workSum value is just
56 // the work for the passed block. The work sum must be updated accordingly when
57 // the node is inserted into a chain.
59 // This function is NOT safe for concurrent access. It must only be called when
60 // initially creating a node.
61 func initBlockNode(node *blockNode, blockHeader *wire.BlockHeader, height int32) {
63 hash: blockHeader.BlockHash(),
64 workSum: CalcWork(blockHeader.Bits),
66 version: blockHeader.Version,
67 bits: blockHeader.Bits,
68 nonce: blockHeader.Nonce,
69 timestamp: blockHeader.Timestamp.Unix(),
70 merkleRoot: blockHeader.MerkleRoot,
74 // newBlockNode returns a new block node for the given block header. It is
75 // completely disconnected from the chain and the workSum value is just the work
76 // for the passed block. The work sum must be updated accordingly when the node
77 // is inserted into a chain.
78 func newBlockNode(blockHeader *wire.BlockHeader, height int32) *blockNode {
80 initBlockNode(&node, blockHeader, height)
84 // Header constructs a block header from the node and returns it.
86 // This function is safe for concurrent access.
87 func (node *blockNode) Header() wire.BlockHeader {
88 // No lock is needed because all accessed fields are immutable.
90 if node.parent != nil {
91 prevHash = &node.parent.hash
93 return wire.BlockHeader{
94 Version: node.version,
96 MerkleRoot: node.merkleRoot,
97 Timestamp: time.Unix(node.timestamp, 0),
103 // Ancestor returns the ancestor block node at the provided height by following
104 // the chain backwards from this node. The returned block will be nil when a
105 // height is requested that is after the height of the passed node or is less
108 // This function is safe for concurrent access.
109 func (node *blockNode) Ancestor(height int32) *blockNode {
110 if height < 0 || height > node.height {
115 for ; n != nil && n.height != height; n = n.parent {
116 // Intentionally left blank
122 // RelativeAncestor returns the ancestor block node a relative 'distance' blocks
123 // before this node. This is equivalent to calling Ancestor with the node's
124 // height minus provided distance.
126 // This function is safe for concurrent access.
127 func (node *blockNode) RelativeAncestor(distance int32) *blockNode {
128 return node.Ancestor(node.height - distance)
131 // CalcPastMedianTime calculates the median time of the previous few blocks
132 // prior to, and including, the block node.
134 // This function is safe for concurrent access.
135 func (node *blockNode) CalcPastMedianTime() time.Time {
136 // Create a slice of the previous few block timestamps used to calculate
137 // the median per the number defined by the constant medianTimeBlocks.
138 timestamps := make([]int64, medianTimeBlocks)
141 for i := 0; i < medianTimeBlocks && iterNode != nil; i++ {
142 timestamps[i] = iterNode.timestamp
145 iterNode = iterNode.parent
148 // Prune the slice to the actual number of available timestamps which
149 // will be fewer than desired near the beginning of the block chain
151 timestamps = timestamps[:numNodes]
152 sort.Sort(timeSorter(timestamps))
154 // NOTE: The consensus rules incorrectly calculate the median for even
155 // numbers of blocks. A true median averages the middle two elements
156 // for a set with an even number of elements in it. Since the constant
157 // for the previous number of blocks to be used is odd, this is only an
158 // issue for a few blocks near the beginning of the chain. I suspect
159 // this is an optimization even though the result is slightly wrong for
160 // a few of the first blocks since after the first few blocks, there
161 // will always be an odd number of blocks in the set per the constant.
163 // This code follows suit to ensure the same rules are used, however, be
164 // aware that should the medianTimeBlocks constant ever be changed to an
165 // even number, this code will be wrong.
166 medianTimestamp := timestamps[numNodes/2]
167 return time.Unix(medianTimestamp, 0)
170 // blockIndex provides facilities for keeping track of an in-memory index of the
171 // block chain. Although the name block chain suggests a single chain of
172 // blocks, it is actually a tree-shaped structure where any node can have
173 // multiple children. However, there can only be one active branch which does
174 // indeed form a chain from the tip all the way back to the genesis block.
175 type blockIndex struct {
176 // The following fields are set when the instance is created and can't
177 // be changed afterwards, so there is no need to protect them with a
180 chainParams *chaincfg.Params
183 index map[chainhash.Hash]*blockNode
186 // newBlockIndex returns a new empty instance of a block index. The index will
187 // be dynamically populated as block nodes are loaded from the database and
189 func newBlockIndex(db database.DB, chainParams *chaincfg.Params) *blockIndex {
192 chainParams: chainParams,
193 index: make(map[chainhash.Hash]*blockNode),
197 // HaveBlock returns whether or not the block index contains the provided hash.
199 // This function is safe for concurrent access.
200 func (bi *blockIndex) HaveBlock(hash *chainhash.Hash) bool {
202 _, hasBlock := bi.index[*hash]
207 // LookupNode returns the block node identified by the provided hash. It will
208 // return nil if there is no entry for the hash.
210 // This function is safe for concurrent access.
211 func (bi *blockIndex) LookupNode(hash *chainhash.Hash) *blockNode {
213 node := bi.index[*hash]
218 // AddNode adds the provided node to the block index. Duplicate entries are not
219 // checked so it is up to caller to avoid adding them.
221 // This function is safe for concurrent access.
222 func (bi *blockIndex) AddNode(node *blockNode) {
224 bi.index[node.hash] = node
228 // RemoveNode removes the provided node from the block index. There is no check
229 // whether another node in the index depends on this one, so it is up to caller
230 // to avoid that situation.
232 // This function is safe for concurrent access.
233 func (bi *blockIndex) RemoveNode(node *blockNode) {
235 delete(bi.index, node.hash)