1 package blockchain
2 3 import (
4 "fmt"
5 "math/rand"
6 "reflect"
7 "testing"
8 9 "github.com/p9c/p9/pkg/wire"
10 )
11 12 // testNoncePrng provides a deterministic prng for the nonce in generated fake nodes. The ensures that the node have
13 // unique hashes.
14 var testNoncePrng = rand.New(rand.NewSource(0))
15 16 // chainedNodes returns the specified number of nodes constructed such that each subsequent node points to the previous
17 // one to create a chain. The first node will point to the passed parent which can be nil if desired.
18 func chainedNodes(parent *BlockNode, numNodes int) []*BlockNode {
19 nodes := make([]*BlockNode, numNodes)
20 tip := parent
21 for i := 0; i < numNodes; i++ {
22 // This is invalid, but all that is needed is enough to get the synthetic tests to work.
23 header := wire.BlockHeader{Nonce: testNoncePrng.Uint32()}
24 if tip != nil {
25 header.PrevBlock = tip.hash
26 }
27 nodes[i] = NewBlockNode(&header, tip)
28 tip = nodes[i]
29 }
30 return nodes
31 }
32 33 // String returns the block node as a human-readable name.
34 func (node BlockNode) String() string {
35 return fmt.Sprintf("%s(%d)", node.hash, node.height)
36 }
37 38 // tstTip is a convenience function to grab the tip of a chain of block nodes created via chainedNodes.
39 func tstTip(nodes []*BlockNode) *BlockNode {
40 return nodes[len(nodes)-1]
41 }
42 43 // locatorHashes is a convenience function that returns the hashes for all of the passed indexes of the provided nodes.
44 // It is used to construct expected block locators in the tests.
45 func locatorHashes(nodes []*BlockNode, indexes ...int) BlockLocator {
46 hashes := make(BlockLocator, 0, len(indexes))
47 for _, idx := range indexes {
48 hashes = append(hashes, &nodes[idx].hash)
49 }
50 return hashes
51 }
52 53 // zipLocators is a convenience function that returns a single block locator given a variable number of them and is used
54 // in the tests.
55 func zipLocators(locators ...BlockLocator) BlockLocator {
56 var hashes BlockLocator
57 for _, locator := range locators {
58 hashes = append(hashes, locator...)
59 }
60 return hashes
61 }
62 63 // TestChainView ensures all of the exported functionality of chain views works as intended with the exception of some
64 // special cases which are handled in other tests.
65 func TestChainView(t *testing.T) {
66 // Construct a synthetic block index consisting of the following structure.
67 //
68 // 0 -> 1 -> 2 -> 3 -> 4
69 // \-> 2a -> 3a -> 4a -> 5a -> 6a -> 7a -> ... -> 26a
70 // \-> 3a'-> 4a' -> 5a'
71 branch0Nodes := chainedNodes(nil, 5)
72 branch1Nodes := chainedNodes(branch0Nodes[1], 25)
73 branch2Nodes := chainedNodes(branch1Nodes[0], 3)
74 tip := tstTip
75 tests := []struct {
76 name string
77 // active view
78 view *chainView
79 // expected genesis block of active view
80 genesis *BlockNode
81 // expected tip of active view
82 tip *BlockNode
83 // side chain view
84 side *chainView
85 // expected tip of side chain view
86 sideTip *BlockNode
87 // expected fork node
88 fork *BlockNode
89 // expected nodes in active view
90 contains []*BlockNode
91 // expected nodes NOT in active view
92 noContains []*BlockNode
93 // view expected equal to active view
94 equal *chainView
95 // view expected NOT equal to active
96 unequal *chainView
97 // expected locator for active view tip
98 locator BlockLocator
99 }{
100 {
101 // Create a view for branch 0 as the active chain and another view for branch 1 as the side chain.
102 name: "chain0-chain1",
103 view: newChainView(tip(branch0Nodes)),
104 genesis: branch0Nodes[0],
105 tip: tip(branch0Nodes),
106 side: newChainView(tip(branch1Nodes)),
107 sideTip: tip(branch1Nodes),
108 fork: branch0Nodes[1],
109 contains: branch0Nodes,
110 noContains: branch1Nodes,
111 equal: newChainView(tip(branch0Nodes)),
112 unequal: newChainView(tip(branch1Nodes)),
113 locator: locatorHashes(branch0Nodes, 4, 3, 2, 1, 0),
114 },
115 {
116 // Create a view for branch 1 as the active chain and another view for branch 2 as the side chain.
117 name: "chain1-chain2",
118 view: newChainView(tip(branch1Nodes)),
119 genesis: branch0Nodes[0],
120 tip: tip(branch1Nodes),
121 side: newChainView(tip(branch2Nodes)),
122 sideTip: tip(branch2Nodes),
123 fork: branch1Nodes[0],
124 contains: branch1Nodes,
125 noContains: branch2Nodes,
126 equal: newChainView(tip(branch1Nodes)),
127 unequal: newChainView(tip(branch2Nodes)),
128 locator: zipLocators(
129 locatorHashes(branch1Nodes, 24, 23, 22, 21, 20,
130 19, 18, 17, 16, 15, 14, 13, 11, 7,
131 ),
132 locatorHashes(branch0Nodes, 1, 0),
133 ),
134 },
135 {
136 // Create a view for branch 2 as the active chain and another view for branch 0 as the side chain.
137 name: "chain2-chain0",
138 view: newChainView(tip(branch2Nodes)),
139 genesis: branch0Nodes[0],
140 tip: tip(branch2Nodes),
141 side: newChainView(tip(branch0Nodes)),
142 sideTip: tip(branch0Nodes),
143 fork: branch0Nodes[1],
144 contains: branch2Nodes,
145 noContains: branch0Nodes[2:],
146 equal: newChainView(tip(branch2Nodes)),
147 unequal: newChainView(tip(branch0Nodes)),
148 locator: zipLocators(
149 locatorHashes(branch2Nodes, 2, 1, 0),
150 locatorHashes(branch1Nodes, 0),
151 locatorHashes(branch0Nodes, 1, 0),
152 ),
153 },
154 }
155 testLoop:
156 for _, test := range tests {
157 // Ensure the active and side chain heights are the expected values.
158 if test.view.Height() != test.tip.height {
159 t.Errorf("%s: unexpected active view height -- got "+
160 "%d, want %d", test.name, test.view.Height(),
161 test.tip.height,
162 )
163 continue
164 }
165 if test.side.Height() != test.sideTip.height {
166 t.Errorf("%s: unexpected side view height -- got %d, "+
167 "want %d", test.name, test.side.Height(),
168 test.sideTip.height,
169 )
170 continue
171 }
172 // Ensure the active and side chain genesis block is the expected value.
173 if test.view.Genesis() != test.genesis {
174 t.Errorf("%s: unexpected active view genesis -- got "+
175 "%v, want %v", test.name, test.view.Genesis(),
176 test.genesis,
177 )
178 continue
179 }
180 if test.side.Genesis() != test.genesis {
181 t.Errorf("%s: unexpected side view genesis -- got %v, want %v", test.name, test.view.Genesis(),
182 test.genesis,
183 )
184 continue
185 }
186 // Ensure the active and side chain tips are the expected nodes.
187 if test.view.Tip() != test.tip {
188 t.Errorf("%s: unexpected active view tip -- got %v, "+
189 "want %v", test.name, test.view.Tip(), test.tip,
190 )
191 continue
192 }
193 if test.side.Tip() != test.sideTip {
194 t.Errorf("%s: unexpected active view tip -- got %v, "+
195 "want %v", test.name, test.side.Tip(),
196 test.sideTip,
197 )
198 continue
199 }
200 // Ensure that regardless of the order the two chains are compared they both return the expected fork point.
201 forkNode := test.view.FindFork(test.side.Tip())
202 if forkNode != test.fork {
203 t.Errorf("%s: unexpected fork node (view, side) -- "+
204 "got %v, want %v", test.name, forkNode,
205 test.fork,
206 )
207 continue
208 }
209 forkNode = test.side.FindFork(test.view.Tip())
210 if forkNode != test.fork {
211 t.Errorf("%s: unexpected fork node (side, view) -- "+
212 "got %v, want %v", test.name, forkNode,
213 test.fork,
214 )
215 continue
216 }
217 // Ensure that the fork point for a node that is already part of the chain view is the node itself.
218 forkNode = test.view.FindFork(test.view.Tip())
219 if forkNode != test.view.Tip() {
220 t.Errorf("%s: unexpected fork node (view, tip) -- "+
221 "got %v, want %v", test.name, forkNode,
222 test.view.Tip(),
223 )
224 continue
225 }
226 // Ensure all expected nodes are contained in the active view.
227 for _, node := range test.contains {
228 if !test.view.Contains(node) {
229 t.Errorf("%s: expected %v in active view",
230 test.name, node,
231 )
232 continue testLoop
233 }
234 }
235 // Ensure all nodes from side chain view are NOT contained in the active view.
236 for _, node := range test.noContains {
237 if test.view.Contains(node) {
238 t.Errorf("%s: unexpected %v in active view",
239 test.name, node,
240 )
241 continue testLoop
242 }
243 }
244 // Ensure equality of different views into the same chain works as intended.
245 if !test.view.Equals(test.equal) {
246 t.Errorf("%s: unexpected unequal views", test.name)
247 continue
248 }
249 if test.view.Equals(test.unequal) {
250 t.Errorf("%s: unexpected equal views", test.name)
251 continue
252 }
253 // Ensure all nodes contained in the view return the expected next node.
254 for i, node := range test.contains {
255 // Final node expects nil for the next node.
256 var expected *BlockNode
257 if i < len(test.contains)-1 {
258 expected = test.contains[i+1]
259 }
260 if next := test.view.Next(node); next != expected {
261 t.Errorf("%s: unexpected next node -- got %v, "+
262 "want %v", test.name, next, expected,
263 )
264 continue testLoop
265 }
266 }
267 // Ensure nodes that are not contained in the view do not produce a successor node.
268 for _, node := range test.noContains {
269 if next := test.view.Next(node); next != nil {
270 t.Errorf("%s: unexpected next node -- got %v, "+
271 "want nil", test.name, next,
272 )
273 continue testLoop
274 }
275 }
276 // Ensure all nodes contained in the view can be retrieved by height.
277 for _, wantNode := range test.contains {
278 node := test.view.NodeByHeight(wantNode.height)
279 if node != wantNode {
280 t.Errorf("%s: unexpected node for height %d -- "+
281 "got %v, want %v", test.name,
282 wantNode.height, node, wantNode,
283 )
284 continue testLoop
285 }
286 }
287 // Ensure the block locator for the tip of the active view consists of the expected hashes.
288 locator := test.view.BlockLocator(test.view.tip())
289 if !reflect.DeepEqual(locator, test.locator) {
290 t.Errorf("%s: unexpected locator -- got %v, want %v",
291 test.name, locator, test.locator,
292 )
293 continue
294 }
295 }
296 }
297 298 // TestChainViewForkCorners ensures that finding the fork between two chains works in some corner cases such as when the
299 // two chains have completely unrelated histories.
300 func TestChainViewForkCorners(t *testing.T) {
301 // Construct two unrelated single branch synthetic block indexes.
302 branchNodes := chainedNodes(nil, 5)
303 unrelatedBranchNodes := chainedNodes(nil, 7)
304 // Create chain views for the two unrelated histories.
305 view1 := newChainView(tstTip(branchNodes))
306 view2 := newChainView(tstTip(unrelatedBranchNodes))
307 // Ensure attempting to find a fork point with a node that doesn't exist doesn't produce a node.
308 if fork := view1.FindFork(nil); fork != nil {
309 t.Fatalf("FindFork: unexpected fork -- got %v, want nil", fork)
310 }
311 // Ensure attempting to find a fork point in two chain views with totally unrelated histories doesn't produce a node.
312 for _, node := range branchNodes {
313 if fork := view2.FindFork(node); fork != nil {
314 t.Fatalf("FindFork: unexpected fork -- got %v, want nil",
315 fork,
316 )
317 }
318 }
319 for _, node := range unrelatedBranchNodes {
320 if fork := view1.FindFork(node); fork != nil {
321 t.Fatalf("FindFork: unexpected fork -- got %v, want nil",
322 fork,
323 )
324 }
325 }
326 }
327 328 // TestChainViewSetTip ensures changing the tip works as intended including capacity changes.
329 func TestChainViewSetTip(t *testing.T) {
330 // Construct a synthetic block index consisting of the following structure.
331 //
332 // 0 -> 1 -> 2 -> 3 -> 4
333 // \-> 2a -> 3a -> 4a -> 5a -> 6a -> 7a -> ... -> 26a
334 branch0Nodes := chainedNodes(nil, 5)
335 branch1Nodes := chainedNodes(branch0Nodes[1], 25)
336 tip := tstTip
337 tests := []struct {
338 name string
339 view *chainView // active view
340 tips []*BlockNode // tips to set
341 contains [][]*BlockNode // expected nodes in view for each tip
342 }{
343 {
344 // Create an empty view and set the tip to increasingly longer chains.
345 name: "increasing",
346 view: newChainView(nil),
347 tips: []*BlockNode{tip(branch0Nodes), tip(branch1Nodes)},
348 contains: [][]*BlockNode{branch0Nodes, branch1Nodes},
349 },
350 {
351 // Create a view with a longer chain and set the tip to increasingly shorter chains.
352 name: "decreasing",
353 view: newChainView(tip(branch1Nodes)),
354 tips: []*BlockNode{tip(branch0Nodes), nil},
355 contains: [][]*BlockNode{branch0Nodes, nil},
356 },
357 {
358 // Create a view with a shorter chain and set the tip to a longer chain followed by setting it back to the
359 // shorter chain.
360 name: "small-large-small",
361 view: newChainView(tip(branch0Nodes)),
362 tips: []*BlockNode{tip(branch1Nodes), tip(branch0Nodes)},
363 contains: [][]*BlockNode{branch1Nodes, branch0Nodes},
364 },
365 {
366 // Create a view with a longer chain and set the tip to a smaller chain followed by setting it back to the
367 // longer chain.
368 name: "large-small-large",
369 view: newChainView(tip(branch1Nodes)),
370 tips: []*BlockNode{tip(branch0Nodes), tip(branch1Nodes)},
371 contains: [][]*BlockNode{branch0Nodes, branch1Nodes},
372 },
373 }
374 testLoop:
375 for _, test := range tests {
376 for i, tip := range test.tips {
377 // Ensure the view tip is the expected node.
378 test.view.SetTip(tip)
379 if test.view.Tip() != tip {
380 t.Errorf("%s: unexpected view tip -- got %v, "+
381 "want %v", test.name, test.view.Tip(),
382 tip,
383 )
384 continue testLoop
385 }
386 // Ensure all expected nodes are contained in the view.
387 for _, node := range test.contains[i] {
388 if !test.view.Contains(node) {
389 t.Errorf("%s: expected %v in active view",
390 test.name, node,
391 )
392 continue testLoop
393 }
394 }
395 }
396 }
397 }
398 399 // TestChainViewNil ensures that creating and accessing a nil chain view behaves as expected.
400 func TestChainViewNil(t *testing.T) {
401 // Ensure two unininitialized views are considered equal.
402 view := newChainView(nil)
403 if !view.Equals(newChainView(nil)) {
404 t.Fatal("uninitialized nil views unequal")
405 }
406 // Ensure the genesis of an uninitialized view does not produce a node.
407 if genesis := view.Genesis(); genesis != nil {
408 t.Fatalf("Genesis: unexpected genesis -- got %v, want nil",
409 genesis,
410 )
411 }
412 // Ensure the tip of an uninitialized view does not produce a node.
413 if tip := view.Tip(); tip != nil {
414 t.Fatalf("Tip: unexpected tip -- got %v, want nil", tip)
415 }
416 // Ensure the height of an uninitialized view is the expected value.
417 if height := view.Height(); height != -1 {
418 t.Fatalf("Height: unexpected height -- got %d, want -1", height)
419 }
420 // Ensure attempting to get a node for a height that does not exist does not produce a node.
421 if node := view.NodeByHeight(10); node != nil {
422 t.Fatalf("NodeByHeight: unexpected node -- got %v, want nil", node)
423 }
424 // Ensure an uninitialized view does not report it contains nodes.
425 fakeNode := chainedNodes(nil, 1)[0]
426 if view.Contains(fakeNode) {
427 t.Fatalf("Contains: view claims it contains node %v", fakeNode)
428 }
429 // Ensure the next node for a node that does not exist does not produce a node.
430 if next := view.Next(nil); next != nil {
431 t.Fatalf("Next: unexpected next node -- got %v, want nil", next)
432 }
433 // Ensure the next node for a node that exists does not produce a node.
434 if next := view.Next(fakeNode); next != nil {
435 t.Fatalf("Next: unexpected next node -- got %v, want nil", next)
436 }
437 // Ensure attempting to find a fork point with a node that doesn't exist doesn't produce a node.
438 if fork := view.FindFork(nil); fork != nil {
439 t.Fatalf("FindFork: unexpected fork -- got %v, want nil", fork)
440 }
441 // Ensure attempting to get a block locator for the tip doesn't produce one since the tip is nil.
442 if locator := view.BlockLocator(nil); locator != nil {
443 t.Fatalf("BlockLocator: unexpected locator -- got %v, want nil",
444 locator,
445 )
446 }
447 // Ensure attempting to get a block locator for a node that exists still works as intended.
448 branchNodes := chainedNodes(nil, 50)
449 wantLocator := locatorHashes(branchNodes, 49, 48, 47, 46, 45, 44, 43,
450 42, 41, 40, 39, 38, 36, 32, 24, 8, 0,
451 )
452 locator := view.BlockLocator(tstTip(branchNodes))
453 if !reflect.DeepEqual(locator, wantLocator) {
454 t.Fatalf("BlockLocator: unexpected locator -- got %v, want %v",
455 locator, wantLocator,
456 )
457 }
458 }
459