/
sidechains.go
393 lines (353 loc) · 12.2 KB
/
sidechains.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
// Copyright (c) 2018 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package wallet
import (
"context"
"math/big"
"sort"
"decred.org/dcrwallet/v2/errors"
"decred.org/dcrwallet/v2/wallet/walletdb"
blockchain "github.com/decred/dcrd/blockchain/standalone/v2"
"github.com/decred/dcrd/chaincfg/chainhash"
"github.com/decred/dcrd/chaincfg/v3"
"github.com/decred/dcrd/gcs/v3"
"github.com/decred/dcrd/wire"
)
// SidechainForest provides in-memory management of sidechain and orphan blocks.
// It implements a forest of disjoint rooted trees, each tree containing
// sidechains stemming from a different fork point in the main chain, or
// orphans.
//
// SidechainForest is not safe for concurrent access.
type SidechainForest struct {
trees []*sidechainRootedTree
}
// BlockNode represents a block node for a SidechainForest. BlockNodes are not
// safe for concurrent access, and all exported fields must be treated as
// immutable.
type BlockNode struct {
Header *wire.BlockHeader
Hash *chainhash.Hash
FilterV2 *gcs.FilterV2
parent *BlockNode
workSum *big.Int
invalid bool
}
// sidechainRootedTree represents a rooted tree of blocks not currently in the
// wallet's main chain. If the parent of the root is not in the wallet's main
// chain, the root and all child blocks are orphans.
type sidechainRootedTree struct {
root *BlockNode
children map[chainhash.Hash]*BlockNode
tips map[chainhash.Hash]*BlockNode
bestChain []*BlockNode // memoized
}
// newSideChainRootedTree creates a new rooted tree for a SidechainForest. The
// root must either be the first block in a fork off the main chain, or an
// orphan block.
func newSideChainRootedTree(root *BlockNode) *sidechainRootedTree {
root.workSum = blockchain.CalcWork(root.Header.Bits)
return &sidechainRootedTree{
root: root,
children: make(map[chainhash.Hash]*BlockNode),
tips: make(map[chainhash.Hash]*BlockNode),
}
}
// NewBlockNode creates a block node for usage with a SidechainForest.
func NewBlockNode(header *wire.BlockHeader, hash *chainhash.Hash, filter *gcs.FilterV2) *BlockNode {
return &BlockNode{
Header: header,
Hash: hash,
FilterV2: filter,
}
}
// BadCheckpoint marks a block node invalid due to not matching a required block
// checkpoint. Invalid blocks are still recorded in the sidechain forest but
// are not returned as a possible best chain. Nodes must be marked invalid
// prior to adding them to the forest to propagate the invalid status to child
// blocks.
func (n *BlockNode) BadCheckpoint() {
n.invalid = true
}
// duplicateNode checks if n, or another node which represents the same block,
// is already contained in the tree.
func (t *sidechainRootedTree) duplicateNode(n *BlockNode) bool {
old, ok := t.root, *t.root.Hash == *n.Hash
if !ok {
old, ok = t.children[*n.Hash]
}
// Copy the cfilter to the older node if it doesn't exist there yet.
// This happens when we received sidechains that are about to become a
// mainchain.
if ok && n.FilterV2 != nil && old.FilterV2 == nil {
old.FilterV2 = n.FilterV2
}
return ok
}
// maybeAttachNode checks whether the node is a child of any node in the rooted
// tree. If so, the child is added to the tree and true is returned. This
// function does not check for duplicate nodes and must only be called on nodes
// known to not already exist in the tree.
func (t *sidechainRootedTree) maybeAttachNode(n *BlockNode) bool {
if *t.root.Hash == n.Header.PrevBlock && n.Header.Height == t.root.Header.Height+1 {
n.parent = t.root
n.invalid = n.invalid || n.parent.invalid
t.children[*n.Hash] = n
t.tips[*n.Hash] = n
n.workSum = new(big.Int).Add(n.parent.workSum, blockchain.CalcWork(n.Header.Bits))
t.bestChain = nil
return true
}
if parent, ok := t.children[n.Header.PrevBlock]; ok && n.Header.Height == parent.Header.Height+1 {
n.parent = parent
n.invalid = n.invalid || n.parent.invalid
t.children[*n.Hash] = n
t.tips[*n.Hash] = n
delete(t.tips, *parent.Hash)
n.workSum = new(big.Int).Add(n.parent.workSum, blockchain.CalcWork(n.Header.Bits))
t.bestChain = nil
return true
}
return false
}
// best returns one of the best sidechains in the tree, starting with the root
// and sorted in increasing order of block heights, along with the summed work
// of blocks in the sidechain including the root. If there are multiple best
// chain candidates, the chosen chain is indeterminate.
//
// This method will always return at least one valid block node, or panic if
// called on an invalid tree.
func (t *sidechainRootedTree) best() ([]*BlockNode, *big.Int) {
if t.root.invalid {
panic("no best chain for invalid sidechain tree")
}
// Return memoized best chain if unchanged.
if len(t.bestChain) != 0 {
return t.bestChain, t.bestChain[len(t.bestChain)-1].workSum
}
// Find a tip block, if any, with the largest total work sum (relative to
// this tree).
var best *BlockNode
for _, n := range t.tips {
if n.invalid {
continue
}
if best == nil || best.workSum.Cmp(n.workSum) == -1 {
best = n
}
}
// If only the root exists in this tree, the entire sidechain is only one
// block long.
if best == nil {
t.bestChain = []*BlockNode{t.root}
return t.bestChain, t.root.workSum
}
// Create the sidechain by iterating the chain in reverse starting with the
// tip.
chain := make([]*BlockNode, best.Header.Height-t.root.Header.Height+1)
n := best
for i, j := 0, len(chain)-1; i < len(chain); i, j = i+1, j-1 {
chain[j] = n
n = n.parent
}
// Memoize the best chain for future calls. This value remains cached until
// a new node is added to the tree.
t.bestChain = chain
return chain, best.workSum
}
// AddBlockNode adds a sidechain block node to the forest. The node may either
// begin a new sidechain, extend an existing sidechain, or start or extend a
// tree of orphan blocks. Adding the parent node of a previously-saved orphan
// block will restructure the forest by re-rooting the previous orphan tree onto
// the tree containing the added node. Returns true iff the node if the node
// was not a duplicate.
func (f *SidechainForest) AddBlockNode(n *BlockNode) bool {
// Add the node to an existing tree if it is a direct child of any recorded
// blocks, or create a new tree containing only the node as the root.
var nodeTree *sidechainRootedTree
for _, t := range f.trees {
// Avoid adding the node if it represents the same block already in the
// tree. This keeps previous-parent consistency in the case that this
// node has a different memory address than the existing node, and
// prevents adding a duplicate block as a new root in the forest.
if t.duplicateNode(n) {
return false
}
if t.maybeAttachNode(n) {
nodeTree = t
break
}
}
if nodeTree == nil {
nodeTree = newSideChainRootedTree(n)
f.trees = append(f.trees, nodeTree)
}
// Search for any trees whose root references the added node as a parent.
// These trees, which were previously orphans, are now children of nodeTree.
// The forest is kept disjoint by attaching all nodes of the previous orphan
// tree to nodeTree and removing the old tree.
for i := 0; i < len(f.trees); {
orphanTree := f.trees[i]
if orphanTree.root.Header.PrevBlock != *n.Hash {
i++
continue
}
// The previous orphan tree must be combined with the extended side
// chain tree and removed from the forest. All nodes from the old
// orphan tree are dumped to a single slice, sorted by block height, and
// then reattached to the extended tree. A failure to add any of these
// side chain nodes indicates an internal consistency error and the
// algorithm will panic.
var nodes []*BlockNode
nodes = append(nodes, orphanTree.root)
for _, node := range orphanTree.children {
nodes = append(nodes, node)
}
sort.Slice(nodes, func(i, j int) bool {
return nodes[i].Header.Height < nodes[j].Header.Height
})
for _, n := range nodes {
if nodeTree.duplicateNode(n) || !nodeTree.maybeAttachNode(n) {
panic("sidechain forest internal consistency error")
}
}
f.trees[i] = f.trees[len(f.trees)-1]
f.trees[len(f.trees)-1] = nil
f.trees = f.trees[:len(f.trees)-1]
}
return true
}
// Prune removes any sidechain trees which contain a root that is significantly
// behind the current main chain tip block.
func (f *SidechainForest) Prune(mainChainHeight int32, params *chaincfg.Params) {
pruneDepth := int32(params.CoinbaseMaturity)
for i := 0; i < len(f.trees); {
if int32(f.trees[i].root.Header.Height)+pruneDepth < mainChainHeight {
f.trees[i] = f.trees[len(f.trees)-1]
f.trees[len(f.trees)-1] = nil
f.trees = f.trees[:len(f.trees)-1]
} else {
i++
}
}
}
// PruneTree removes the tree beginning with root from the forest.
func (f *SidechainForest) PruneTree(root *chainhash.Hash) {
for i, tree := range f.trees {
if *root == *tree.root.Hash {
f.trees[i] = f.trees[len(f.trees)-1]
f.trees[len(f.trees)-1] = nil
f.trees = f.trees[:len(f.trees)-1]
return
}
}
}
// HasSideChainBlock returns true if the given block hash is contained in the
// sidechain forest at any level.
func (f *SidechainForest) HasSideChainBlock(blockHash *chainhash.Hash) bool {
for _, tree := range f.trees {
if *blockHash == *tree.root.Hash {
return true
}
if _, ok := tree.children[*blockHash]; ok {
return true
}
}
return false
}
// FullSideChain returns the sidechain which starts at one of the existing
// roots and ends with the set of passed new blocks.
func (f *SidechainForest) FullSideChain(newBlocks []*BlockNode) ([]*BlockNode, error) {
const op errors.Op = "wallet.EvaluateBestChain"
if len(newBlocks) == 0 {
return newBlocks, nil
}
wantParent := newBlocks[0].Header.PrevBlock
for _, tree := range f.trees {
if wantParent == *tree.root.Hash {
// Connects to this root directly.
return append([]*BlockNode{tree.root}, newBlocks...), nil
}
parent, ok := tree.children[wantParent]
if !ok {
// Parent is not in this tree.
continue
}
// Shouldn't happen due to the invariants maintained by
// SidechainForest, but be cautious to avoid a large loop below
// due to wrapping uint32.
if parent.Header.Height <= tree.root.Header.Height {
err := errors.E(op, "broken assumption of height > parent.Height")
return nil, err
}
// Iterate backwards, from parent down to the root to
// accumulate the prefix chain.
prefixLen := parent.Header.Height - tree.root.Header.Height + 1
res := make([]*BlockNode, prefixLen, prefixLen+uint32(len(newBlocks)))
for i := int(prefixLen) - 1; i >= 0; i-- {
if parent == nil {
err := errors.E(op, "broken assumption about "+
"connectedness of sidechain nodes")
return nil, err
}
res[i] = parent
parent = parent.parent
}
// Add the newBlocks suffix chain.
res = append(res, newBlocks...)
return res, nil
}
// New sidechain.
return newBlocks, nil
}
// EvaluateBestChain returns block nodes to create the best main chain. These
// may extend the main chain or require a reorg. An empty slice indicates there
// is no better chain.
func (w *Wallet) EvaluateBestChain(ctx context.Context, f *SidechainForest) ([]*BlockNode, error) {
const op errors.Op = "wallet.EvaluateBestChain"
var newBestChain []*BlockNode
err := walletdb.View(ctx, w.db, func(dbtx walletdb.ReadTx) error {
tipHash, _ := w.txStore.MainChainTip(dbtx)
tipHeader, err := w.txStore.GetBlockHeader(dbtx, &tipHash)
if err != nil {
return err
}
workDiff := new(big.Int)
// Find chain with most work
for _, t := range f.trees {
// Ignore invalid and orphan trees
if t.root.invalid {
continue
}
fork := &t.root.Header.PrevBlock
inMainChain, _ := w.txStore.BlockInMainChain(dbtx, fork)
if !inMainChain {
continue
}
chain, chainWork := t.best()
work := new(big.Int)
// Subtract removed work
for hash, header := &tipHash, tipHeader; *hash != *fork; {
work.Sub(work, blockchain.CalcWork(header.Bits))
prev := &header.PrevBlock
header, err = w.txStore.GetBlockHeader(dbtx, prev)
if err != nil {
return err
}
hash = prev
}
// Add sidechain work
work.Add(work, chainWork)
if work.Cmp(workDiff) == 1 { // work > workDiff
newBestChain = chain
workDiff = work
}
}
return nil
})
if err != nil {
return nil, errors.E(op, err)
}
return newBestChain, nil
}