-
Notifications
You must be signed in to change notification settings - Fork 229
/
tree.go
546 lines (431 loc) · 15.5 KB
/
tree.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
package reachabilitymanager
import (
"math"
"strings"
"time"
"github.com/kaspanet/kaspad/domain/consensus/utils/reachabilitydata"
"github.com/kaspanet/kaspad/domain/consensus/model"
"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
"github.com/pkg/errors"
)
func newReachabilityTreeData() model.ReachabilityData {
// Please see the comment above model.ReachabilityTreeNode to understand why
// we use these initial values.
interval := newReachabilityInterval(1, math.MaxUint64-1)
data := reachabilitydata.EmptyReachabilityData()
data.SetInterval(interval)
return data
}
/*
Interval helper functions
*/
func (rt *reachabilityManager) intervalRangeForChildAllocation(stagingArea *model.StagingArea,
node *externalapi.DomainHash) (*model.ReachabilityInterval, error) {
interval, err := rt.interval(stagingArea, node)
if err != nil {
return nil, err
}
// We subtract 1 from the end of the range to prevent the node from allocating
// the entire interval to its child, so its interval would *strictly* contain the interval of its child.
return newReachabilityInterval(interval.Start, interval.End-1), nil
}
func (rt *reachabilityManager) remainingIntervalBefore(stagingArea *model.StagingArea, node *externalapi.DomainHash) (*model.ReachabilityInterval, error) {
childrenRange, err := rt.intervalRangeForChildAllocation(stagingArea, node)
if err != nil {
return nil, err
}
children, err := rt.children(stagingArea, node)
if err != nil {
return nil, err
}
if len(children) == 0 {
return childrenRange, nil
}
firstChildInterval, err := rt.interval(stagingArea, children[0])
if err != nil {
return nil, err
}
return newReachabilityInterval(childrenRange.Start, firstChildInterval.Start-1), nil
}
func (rt *reachabilityManager) remainingIntervalAfter(stagingArea *model.StagingArea, node *externalapi.DomainHash) (*model.ReachabilityInterval, error) {
childrenRange, err := rt.intervalRangeForChildAllocation(stagingArea, node)
if err != nil {
return nil, err
}
children, err := rt.children(stagingArea, node)
if err != nil {
return nil, err
}
if len(children) == 0 {
return childrenRange, nil
}
lastChildInterval, err := rt.interval(stagingArea, children[len(children)-1])
if err != nil {
return nil, err
}
return newReachabilityInterval(lastChildInterval.End+1, childrenRange.End), nil
}
func (rt *reachabilityManager) remainingSlackBefore(stagingArea *model.StagingArea, node *externalapi.DomainHash) (uint64, error) {
interval, err := rt.remainingIntervalBefore(stagingArea, node)
if err != nil {
return 0, err
}
return intervalSize(interval), nil
}
func (rt *reachabilityManager) remainingSlackAfter(stagingArea *model.StagingArea, node *externalapi.DomainHash) (uint64, error) {
interval, err := rt.remainingIntervalAfter(stagingArea, node)
if err != nil {
return 0, err
}
return intervalSize(interval), nil
}
func (rt *reachabilityManager) hasSlackIntervalBefore(stagingArea *model.StagingArea, node *externalapi.DomainHash) (bool, error) {
interval, err := rt.remainingIntervalBefore(stagingArea, node)
if err != nil {
return false, err
}
return intervalSize(interval) > 0, nil
}
func (rt *reachabilityManager) hasSlackIntervalAfter(stagingArea *model.StagingArea, node *externalapi.DomainHash) (bool, error) {
interval, err := rt.remainingIntervalAfter(stagingArea, node)
if err != nil {
return false, err
}
return intervalSize(interval) > 0, nil
}
/*
ReachabilityManager API functions
*/
// IsReachabilityTreeAncestorOf checks if this node is a reachability tree ancestor
// of the other node. Note that we use the graph theory convention
// here which defines that node is also an ancestor of itself.
func (rt *reachabilityManager) IsReachabilityTreeAncestorOf(stagingArea *model.StagingArea, node, other *externalapi.DomainHash) (bool, error) {
nodeInterval, err := rt.interval(stagingArea, node)
if err != nil {
return false, err
}
otherInterval, err := rt.interval(stagingArea, other)
if err != nil {
return false, err
}
return intervalContains(nodeInterval, otherInterval), nil
}
// FindNextAncestor finds the reachability tree child
// of 'ancestor' which is also an ancestor of 'descendant'.
func (rt *reachabilityManager) FindNextAncestor(stagingArea *model.StagingArea,
descendant, ancestor *externalapi.DomainHash) (*externalapi.DomainHash, error) {
childrenOfAncestor, err := rt.children(stagingArea, ancestor)
if err != nil {
return nil, err
}
nextAncestor, ok := rt.findAncestorOfNode(stagingArea, childrenOfAncestor, descendant)
if !ok {
return nil, errors.Errorf("ancestor is not an ancestor of descendant")
}
return nextAncestor, nil
}
// String returns a string representation of a reachability tree node
// and its children.
func (rt *reachabilityManager) String(stagingArea *model.StagingArea, node *externalapi.DomainHash) (string, error) {
queue := []*externalapi.DomainHash{node}
nodeInterval, err := rt.interval(stagingArea, node)
if err != nil {
return "", err
}
lines := []string{nodeInterval.String()}
for len(queue) > 0 {
var current *externalapi.DomainHash
current, queue = queue[0], queue[1:]
children, err := rt.children(stagingArea, current)
if err != nil {
return "", err
}
if len(children) == 0 {
continue
}
line := ""
for _, child := range children {
childInterval, err := rt.interval(stagingArea, child)
if err != nil {
return "", err
}
line += childInterval.String()
queue = append(queue, child)
}
lines = append([]string{line}, lines...)
}
return strings.Join(lines, "\n"), nil
}
/*
Tree helper functions
*/
func (rt *reachabilityManager) isStrictAncestorOf(stagingArea *model.StagingArea, node, other *externalapi.DomainHash) (
bool, error) {
if node.Equal(other) {
return false, nil
}
return rt.IsReachabilityTreeAncestorOf(stagingArea, node, other)
}
// findCommonAncestor finds the most recent reachability
// tree ancestor common to both node and the given reindex root. Note
// that we assume that almost always the chain between the reindex root
// and the common ancestor is longer than the chain between node and the
// common ancestor.
func (rt *reachabilityManager) findCommonAncestor(stagingArea *model.StagingArea,
node, root *externalapi.DomainHash) (*externalapi.DomainHash, error) {
current := node
for {
isAncestorOf, err := rt.IsReachabilityTreeAncestorOf(stagingArea, current, root)
if err != nil {
return nil, err
}
if isAncestorOf {
return current, nil
}
current, err = rt.parent(stagingArea, current)
if err != nil {
return nil, err
}
}
}
// splitChildren splits `node` children into two slices: the nodes that are before
// `pivot` and the nodes that are after.
func (rt *reachabilityManager) splitChildren(stagingArea *model.StagingArea, node, pivot *externalapi.DomainHash) (
nodesBeforePivot, nodesAfterPivot []*externalapi.DomainHash, err error) {
children, err := rt.children(stagingArea, node)
if err != nil {
return nil, nil, err
}
for i, child := range children {
if child.Equal(pivot) {
return children[:i], children[i+1:], nil
}
}
return nil, nil, errors.Errorf("pivot not a pivot of node")
}
/*
Internal reachabilityManager API
*/
// addChild adds child to this tree node. If this node has no
// remaining interval to allocate, a reindexing is triggered. When a reindexing
// is triggered, the reindex root point is used within the
// reindex algorithm's logic
func (rt *reachabilityManager) addChild(stagingArea *model.StagingArea, node, child, reindexRoot *externalapi.DomainHash) error {
remaining, err := rt.remainingIntervalAfter(stagingArea, node)
if err != nil {
return err
}
// Set the parent-child relationship
err = rt.stageAddChild(stagingArea, node, child)
if err != nil {
return err
}
err = rt.stageParent(stagingArea, child, node)
if err != nil {
return err
}
// No allocation space left at parent -- reindex
if intervalSize(remaining) == 0 {
// Initially set the child's interval to the empty remaining interval.
// This is done since in some cases, the underlying algorithm will
// allocate space around this point and call intervalIncreaseEnd or
// intervalDecreaseStart making for intervalSize > 0
err = rt.stageInterval(stagingArea, child, remaining)
if err != nil {
return err
}
rc := newReindexContext(rt)
reindexStartTime := time.Now()
err := rc.reindexIntervals(stagingArea, child, reindexRoot)
if err != nil {
return err
}
reindexTimeElapsed := time.Since(reindexStartTime)
log.Debugf("Reachability reindex triggered for "+
"block %s. Took %dms.",
node, reindexTimeElapsed.Milliseconds())
return nil
}
// Allocate from the remaining space
allocated, _, err := intervalSplitInHalf(remaining)
if err != nil {
return err
}
return rt.stageInterval(stagingArea, child, allocated)
}
func (rt *reachabilityManager) updateReindexRoot(stagingArea *model.StagingArea,
selectedTip *externalapi.DomainHash) error {
currentReindexRoot, err := rt.reindexRoot(stagingArea)
if err != nil {
return err
}
// First, find the new root
reindexRootAncestor, newReindexRoot, err := rt.findNextReindexRoot(stagingArea, currentReindexRoot, selectedTip)
if err != nil {
return err
}
// No update to root, return
if currentReindexRoot.Equal(newReindexRoot) {
return nil
}
rc := newReindexContext(rt)
if !newReindexRoot.Equal(reindexRootAncestor) {
log.Debugf("Concentrating the intervals towards the new reindex root")
// Iterate from reindexRootAncestor towards newReindexRoot
for {
chosenChild, err := rt.FindNextAncestor(stagingArea, selectedTip, reindexRootAncestor)
if err != nil {
return err
}
isFinalReindexRoot := chosenChild.Equal(newReindexRoot)
// Concentrate interval from current ancestor to its chosen child
err = rc.concentrateInterval(stagingArea, reindexRootAncestor, chosenChild, isFinalReindexRoot)
if err != nil {
return err
}
if isFinalReindexRoot {
break
}
reindexRootAncestor = chosenChild
}
} else {
log.Debugf("newReindexRoot is the same as reindexRootAncestor. Skipping concentration...")
}
// Update reindex root data store
rt.stageReindexRoot(stagingArea, newReindexRoot)
log.Debugf("Updated the reindex root to %s", newReindexRoot)
return nil
}
// findNextReindexRoot finds the new reindex root based on the current one and the new selected tip.
// The function also returns the common ancestor between the current and new reindex roots (possibly current root itself).
// This ancestor should be used as a starting point for concentrating the interval towards the new root.
func (rt *reachabilityManager) findNextReindexRoot(stagingArea *model.StagingArea, currentReindexRoot,
selectedTip *externalapi.DomainHash) (reindexRootAncestor, newReindexRoot *externalapi.DomainHash, err error) {
reindexRootAncestor = currentReindexRoot
newReindexRoot = currentReindexRoot
selectedTipGHOSTDAGData, err := rt.ghostdagDataStore.Get(rt.databaseContext, stagingArea, selectedTip, false)
if err != nil {
return nil, nil, err
}
isCurrentAncestorOfTip, err := rt.IsReachabilityTreeAncestorOf(stagingArea, currentReindexRoot, selectedTip)
if err != nil {
return nil, nil, err
}
// Test if current root is ancestor of selected tip - if not, this is a reorg case
if !isCurrentAncestorOfTip {
currentRootGHOSTDAGData, err := rt.ghostdagDataStore.Get(rt.databaseContext, stagingArea, currentReindexRoot, false)
if err != nil {
return nil, nil, err
}
// We have reindex root out of selected tip chain, however we switch chains only after a sufficient
// threshold of reindexSlack score in order to address possible alternating reorg attacks.
// The reindexSlack constant is used as an heuristic for a large enough constant on the one hand, but
// one which will not harm performance on the other hand - given the available slack at the chain split point.
//
// Note: In some cases the blue score selected tip can be lower than the current reindex root blue score.
// If that's the case we keep the reindex root unchanged.
if selectedTipGHOSTDAGData.BlueScore() < currentRootGHOSTDAGData.BlueScore() ||
selectedTipGHOSTDAGData.BlueScore()-currentRootGHOSTDAGData.BlueScore() < rt.reindexSlack {
// Return current - this indicates no change
return currentReindexRoot, currentReindexRoot, nil
}
// The common ancestor is where we should start concentrating the interval from
commonAncestor, err := rt.findCommonAncestor(stagingArea, selectedTip, currentReindexRoot)
if err != nil {
return nil, nil, err
}
reindexRootAncestor = commonAncestor
newReindexRoot = commonAncestor
}
// Iterate from ancestor towards selected tip until passing the reindexWindow threshold,
// for finding the new reindex root
for {
chosenChild, err := rt.FindNextAncestor(stagingArea, selectedTip, newReindexRoot)
if err != nil {
return nil, nil, err
}
chosenChildGHOSTDAGData, err := rt.ghostdagDataStore.Get(rt.databaseContext, stagingArea, chosenChild, false)
if err != nil {
return nil, nil, err
}
if selectedTipGHOSTDAGData.BlueScore() < chosenChildGHOSTDAGData.BlueScore() {
return nil, nil, errors.Errorf("chosen child %s has blue score greater "+
"than %s although it's in its selected parent chain", chosenChild, selectedTip)
}
if selectedTipGHOSTDAGData.BlueScore()-chosenChildGHOSTDAGData.BlueScore() < rt.reindexWindow {
break
}
newReindexRoot = chosenChild
}
return reindexRootAncestor, newReindexRoot, nil
}
/*
Test helper functions
*/
// Helper function (for testing purposes) to validate that all tree intervals
// under a specified subtree root are allocated correctly and as expected
func (rt *reachabilityManager) validateIntervals(stagingArea *model.StagingArea, root *externalapi.DomainHash) error {
queue := []*externalapi.DomainHash{root}
for len(queue) > 0 {
var current *externalapi.DomainHash
current, queue = queue[0], queue[1:]
children, err := rt.children(stagingArea, current)
if err != nil {
return err
}
if len(children) > 0 {
queue = append(queue, children...)
}
currentInterval, err := rt.interval(stagingArea, current)
if err != nil {
return err
}
if currentInterval.Start > currentInterval.End {
err := errors.Errorf("Interval allocation is empty")
return err
}
for i, child := range children {
childInterval, err := rt.interval(stagingArea, child)
if err != nil {
return err
}
if i > 0 {
siblingInterval, err := rt.interval(stagingArea, children[i-1])
if err != nil {
return err
}
if siblingInterval.End+1 != childInterval.Start {
err := errors.Errorf("Child intervals are expected be right after each other")
return err
}
}
if childInterval.Start < currentInterval.Start {
err := errors.Errorf("Child interval to the left of parent")
return err
}
if childInterval.End >= currentInterval.End {
err := errors.Errorf("Child interval to the right of parent")
return err
}
}
}
return nil
}
// Helper function (for testing purposes) to get all nodes under a specified subtree root
func (rt *reachabilityManager) getAllNodes(stagingArea *model.StagingArea, root *externalapi.DomainHash) ([]*externalapi.DomainHash, error) {
queue := []*externalapi.DomainHash{root}
nodes := []*externalapi.DomainHash{root}
for len(queue) > 0 {
var current *externalapi.DomainHash
current, queue = queue[0], queue[1:]
children, err := rt.children(stagingArea, current)
if err != nil {
return nil, err
}
if len(children) > 0 {
queue = append(queue, children...)
nodes = append(nodes, children...)
}
}
return nodes, nil
}