1 package blockchain
2 3 import (
4 "sync"
5 )
6 7 // approxNodesPerWeek is an approximation of the number of new blocks there are in a week on average.
8 const approxNodesPerWeek = 7 * 24 * 60 * 60 / 12
9 10 // log2FloorMasks defines the masks to use when quickly calculating floor(log2(x)) in a constant log2(32) = 5 steps,
11 // where x is a uint32, using shifts. They are derived from (2^(2^x) - 1) * (2^(2^x)), for x in 4..0.
12 var log2FloorMasks = []uint32{0xffff0000, 0xff00, 0xf0, 0xc, 0x2}
13 14 // fastLog2Floor calculates and returns floor(log2(x)) in a constant 5 steps.
15 func fastLog2Floor(n uint32) uint8 {
16 rv := uint8(0)
17 exponent := uint8(16)
18 for i := 0; i < 5; i++ {
19 if n&log2FloorMasks[i] != 0 {
20 rv += exponent
21 n >>= exponent
22 }
23 exponent >>= 1
24 }
25 return rv
26 }
27 28 // chainView provides a flat view of a specific branch of the block chain from its tip back to the genesis block and
29 // provides various convenience functions for comparing chains. For example, assume a block chain with a side chain as
30 // depicted below:
31 //
32 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
33 // \-> 4a -> 5a -> 6a
34 //
35 // The chain view for the branch ending in 6a consists of:
36 //
37 // genesis -> 1 -> 2 -> 3 -> 4a -> 5a -> 6a
38 type chainView struct {
39 mtx sync.Mutex
40 nodes []*BlockNode
41 }
42 43 // newChainView returns a new chain view for the given tip block node. Passing nil as the tip will result in a chain
44 // view that is not initialized. The tip can be updated at any time via the setTip function.
45 func newChainView(tip *BlockNode) *chainView {
46 // The mutex is intentionally not held since this is a constructor.
47 var c chainView
48 c.setTip(tip)
49 return &c
50 }
51 52 // genesis returns the genesis block for the chain view. This only differs from the exported version in that it is up to
53 // the caller to ensure the lock is held. This function MUST be called with the view mutex locked (for reads).
54 func (c *chainView) genesis() *BlockNode {
55 if len(c.nodes) == 0 {
56 return nil
57 }
58 return c.nodes[0]
59 }
60 61 // Genesis returns the genesis block for the chain view. This function is safe for concurrent access.
62 func (c *chainView) Genesis() *BlockNode {
63 c.mtx.Lock()
64 genesis := c.genesis()
65 c.mtx.Unlock()
66 return genesis
67 }
68 69 // tip returns the current tip block node for the chain view. It will return nil if there is no tip. This only differs
70 // from the exported version in that it is up to the caller to ensure the lock is held. This function MUST be called
71 // with the view mutex locked (for reads).
72 func (c *chainView) tip() *BlockNode {
73 if len(c.nodes) == 0 {
74 return nil
75 }
76 return c.nodes[len(c.nodes)-1]
77 }
78 79 // Tip returns the current tip block node for the chain view. It will return nil if there is no tip. This function is
80 // safe for concurrent access.
81 func (c *chainView) Tip() *BlockNode {
82 c.mtx.Lock()
83 tip := c.tip()
84 c.mtx.Unlock()
85 return tip
86 }
87 88 // setTip sets the chain view to use the provided block node as the current tip and ensures the view is consistent by
89 // populating it with the nodes obtained by walking backwards all the way to genesis block as necessary. Further calls
90 // will only perform the minimum work needed, so switching between chain tips is efficient. This only differs from the
91 // exported version in that it is up to the caller to ensure the lock is held. This function MUST be called with the
92 // view mutex locked (for writes).
93 func (c *chainView) setTip(node *BlockNode) {
94 if node == nil {
95 // Keep the backing array around for potential future use.
96 c.nodes = c.nodes[:0]
97 return
98 }
99 // Create or resize the slice that will hold the block nodes to the provided tip height. When creating the slice, it
100 // is created with some additional capacity for the underlying array as append would do in order to reduce overhead
101 // when extending the chain later. As long as the underlying array already has enough capacity, simply expand or
102 // contract the slice accordingly. The additional capacity is chosen such that the array should only have to be
103 // extended about once a week.
104 needed := node.height + 1
105 if int32(cap(c.nodes)) < needed {
106 nodes := make([]*BlockNode, needed, needed+approxNodesPerWeek)
107 copy(nodes, c.nodes)
108 c.nodes = nodes
109 } else {
110 prevLen := int32(len(c.nodes))
111 c.nodes = c.nodes[0:needed]
112 for i := prevLen; i < needed; i++ {
113 c.nodes[i] = nil
114 }
115 }
116 for c.nodes[node.height] != node {
117 c.nodes[node.height] = node
118 node = node.parent
119 if node == nil {
120 break
121 }
122 }
123 }
124 125 // SetTip sets the chain view to use the provided block node as the current tip and ensures the view is consistent by
126 // populating it with the nodes obtained by walking backwards all the way to genesis block as necessary. Further calls
127 // will only perform the minimum work needed, so switching between chain tips is efficient. This function is safe for
128 // concurrent access.
129 func (c *chainView) SetTip(node *BlockNode) {
130 c.mtx.Lock()
131 c.setTip(node)
132 c.mtx.Unlock()
133 }
134 135 // height returns the height of the tip of the chain view. It will return -1 if there is no tip (which only happens if
136 // the chain view has not been initialized). This only differs from the exported version in that it is up to the caller
137 // to ensure the lock is held. This function MUST be called with the view mutex locked (for reads).
138 func (c *chainView) height() int32 {
139 return int32(len(c.nodes) - 1)
140 }
141 142 // Height returns the height of the tip of the chain view. It will return -1 if there is no tip (which only happens if
143 // the chain view has not been initialized). This function is safe for concurrent access.
144 func (c *chainView) Height() int32 {
145 c.mtx.Lock()
146 height := c.height()
147 c.mtx.Unlock()
148 return height
149 }
150 151 // nodeByHeight returns the block node at the specified height. Nil will be returned if the height does not exist. This
152 // only differs from the exported version in that it is up to the caller to ensure the lock is held. This function MUST
153 // be called with the view mutex locked (for reads).
154 func (c *chainView) nodeByHeight(height int32) *BlockNode {
155 if height < 0 || height >= int32(len(c.nodes)) {
156 return nil
157 }
158 return c.nodes[height]
159 }
160 161 // NodeByHeight returns the block node at the specified height. Nil will be returned if the height does not exist. This
162 // function is safe for concurrent access.
163 func (c *chainView) NodeByHeight(height int32) *BlockNode {
164 c.mtx.Lock()
165 node := c.nodeByHeight(height)
166 c.mtx.Unlock()
167 return node
168 }
169 170 // Equals returns whether or not two chain views are the same. Uninitialized views (tip set to nil) are considered
171 // equal. This function is safe for concurrent access.
172 func (c *chainView) Equals(other *chainView) bool {
173 c.mtx.Lock()
174 other.mtx.Lock()
175 equals := len(c.nodes) == len(other.nodes) && c.tip() == other.tip()
176 other.mtx.Unlock()
177 c.mtx.Unlock()
178 return equals
179 }
180 181 // contains returns whether or not the chain view contains the passed block node. This only differs from the exported
182 // version in that it is up to the caller to ensure the lock is held. This function MUST be called with the view mutex
183 // locked (for reads).
184 func (c *chainView) contains(node *BlockNode) bool {
185 return c.nodeByHeight(node.height) == node
186 }
187 188 // Contains returns whether or not the chain view contains the passed block node.
189 //
190 // This function is safe for concurrent access.
191 func (c *chainView) Contains(node *BlockNode) bool {
192 c.mtx.Lock()
193 contains := c.contains(node)
194 c.mtx.Unlock()
195 return contains
196 }
197 198 // next returns the successor to the provided node for the chain view. It will return nil if there is no successor or
199 // the provided node is not part of the view. This only differs from the exported version in that it is up to the caller
200 // to ensure the lock is held. See the comment on the exported function for more details.
201 //
202 // This function MUST be called with the view mutex locked (for reads).
203 func (c *chainView) next(node *BlockNode) *BlockNode {
204 if node == nil || !c.contains(node) {
205 return nil
206 }
207 return c.nodeByHeight(node.height + 1)
208 }
209 210 // Next returns the successor to the provided node for the chain view. It will return nil if there is no successfor or
211 // the provided node is not part of the view. For example, assume a block chain with a side chain as depicted below:
212 //
213 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
214 // \-> 4a -> 5a -> 6a
215 // Further, assume the view is for the longer chain depicted above. That is to say it consists of:
216 //
217 // genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
218 //
219 // Invoking this function with block node 5 would return block node 6 while invoking it with block node 5a would return
220 // nil since that node is not part of the view. This function is safe for concurrent access.
221 func (c *chainView) Next(node *BlockNode) *BlockNode {
222 c.mtx.Lock()
223 next := c.next(node)
224 c.mtx.Unlock()
225 return next
226 }
227 228 // findFork returns the final common block between the provided node and the the chain view. It will return nil if there
229 // is no common block. This only differs from the exported version in that it is up to the caller to ensure the lock is
230 // held. See the exported FindFork comments for more details. This function MUST be called with the view mutex locked
231 // (for reads).
232 func (c *chainView) findFork(node *BlockNode) *BlockNode {
233 // No fork point for node that doesn't exist.
234 if node == nil {
235 return nil
236 }
237 // When the height of the passed node is higher than the height of the tip of the current chain view, walk backwards
238 // through the nodes of the other chain until the heights match (or there or no more nodes in which case there is no
239 // common node between the two). NOTE: This isn't strictly necessary as the following section will find the node as
240 // well, however, it is more efficient to avoid the contains check since it is already known that the common node
241 // can't possibly be past the end of the current chain view. It also allows this code to take advantage of any
242 // potential future optimizations to the Ancestor function such as using an O(log n) skip list.
243 chainHeight := c.height()
244 if node.height > chainHeight {
245 node = node.Ancestor(chainHeight)
246 }
247 // Walk the other chain backwards as long as the current one does not contain the node or there are no more nodes in
248 // which case there is no common node between the two.
249 for node != nil && !c.contains(node) {
250 node = node.parent
251 }
252 return node
253 }
254 255 // FindFork returns the final common block between the provided node and the the chain view. It will return nil if there
256 // is no common block. For example, assume a block chain with a side chain as depicted below:
257 //
258 // genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8
259 // \-> 6a -> 7a
260 // Further, assume the view is for the longer chain depicted above. That is to say it consists of:
261 //
262 // genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8.
263 //
264 // Invoking this function with block node 7a would return block node 5 while invoking it with block node 7 would return
265 // itself since it is already part of the branch formed by the view. This function is safe for concurrent access.
266 func (c *chainView) FindFork(node *BlockNode) *BlockNode {
267 c.mtx.Lock()
268 fork := c.findFork(node)
269 c.mtx.Unlock()
270 return fork
271 }
272 273 // blockLocator returns a block locator for the passed block node. The passed node can be nil in which case the block
274 // locator for the current tip associated with the view will be returned. This only differs from the exported version in
275 // that it is up to the caller to ensure the lock is held. See the exported BlockLocator function comments for more
276 // details.
277 //
278 // This function MUST be called with the view mutex locked (for reads).
279 func (c *chainView) blockLocator(node *BlockNode) BlockLocator {
280 // Use the current tip if requested.
281 if node == nil {
282 node = c.tip()
283 }
284 if node == nil {
285 return nil
286 }
287 // Calculate the max number of entries that will ultimately be in the block locator. See the description of the
288 // algorithm for how these numbers are derived.
289 var maxEntries uint8
290 if node.height <= 12 {
291 maxEntries = uint8(node.height) + 1
292 } else {
293 // Requested hash itself + previous 10 entries + genesis block. Then floor(log2(height-10)) entries for the skip
294 // portion.
295 adjustedHeight := uint32(node.height) - 10
296 maxEntries = 12 + fastLog2Floor(adjustedHeight)
297 }
298 locator := make(BlockLocator, 0, maxEntries)
299 step := int32(1)
300 for node != nil {
301 locator = append(locator, &node.hash)
302 // Nothing more to add once the genesis block has been added.
303 if node.height == 0 {
304 break
305 }
306 // Calculate height of previous node to include ensuring the final node is the genesis block.
307 height := node.height - step
308 if height < 0 {
309 height = 0
310 }
311 // When the node is in the current chain view, all of its ancestors must be too, so use a much faster O(1)
312 // lookup in that case. Otherwise, fall back to walking backwards through the nodes of the other chain to the
313 // correct ancestor.
314 if c.contains(node) {
315 node = c.nodes[height]
316 } else {
317 node = node.Ancestor(height)
318 }
319 // Once 11 entries have been included, start doubling the distance between included hashes.
320 if len(locator) > 10 {
321 step *= 2
322 }
323 }
324 return locator
325 }
326 327 // BlockLocator returns a block locator for the passed block node. The passed node can be nil in which case the block
328 // locator for the current tip associated with the view will be returned. See the BlockLocator type for details on the
329 // algorithm used to create a block locator. This function is safe for concurrent access.
330 func (c *chainView) BlockLocator(node *BlockNode) BlockLocator {
331 c.mtx.Lock()
332 locator := c.blockLocator(node)
333 c.mtx.Unlock()
334 return locator
335 }
336