-
Notifications
You must be signed in to change notification settings - Fork 1
/
resolve.go
225 lines (192 loc) · 7.59 KB
/
resolve.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
package consensusstatemanager
import (
"sort"
"github.com/Nirvana-Chain/nirvanad/domain/consensus/model"
"github.com/Nirvana-Chain/nirvanad/domain/consensus/model/externalapi"
"github.com/Nirvana-Chain/nirvanad/infrastructure/logger"
"github.com/Nirvana-Chain/nirvanad/util/staging"
"github.com/pkg/errors"
)
// tipsInDecreasingGHOSTDAGParentSelectionOrder returns the current DAG tips in decreasing parent selection order.
// This means that the first tip in the resulting list would be the GHOSTDAG selected parent, and if removed from the list,
// the second tip would be the selected parent, and so on.
func (csm *consensusStateManager) tipsInDecreasingGHOSTDAGParentSelectionOrder(stagingArea *model.StagingArea) ([]*externalapi.DomainHash, error) {
tips, err := csm.consensusStateStore.Tips(stagingArea, csm.databaseContext)
if err != nil {
return nil, err
}
var sortErr error
sort.Slice(tips, func(i, j int) bool {
selectedParent, err := csm.ghostdagManager.ChooseSelectedParent(stagingArea, tips[i], tips[j])
if err != nil {
sortErr = err
return false
}
return selectedParent.Equal(tips[i])
})
if sortErr != nil {
return nil, sortErr
}
return tips, nil
}
func (csm *consensusStateManager) findNextPendingTip(stagingArea *model.StagingArea) (*externalapi.DomainHash, externalapi.BlockStatus, error) {
orderedTips, err := csm.tipsInDecreasingGHOSTDAGParentSelectionOrder(stagingArea)
if err != nil {
return nil, externalapi.StatusInvalid, err
}
for _, tip := range orderedTips {
log.Debugf("Resolving tip %s", tip)
isViolatingFinality, shouldNotify, err := csm.isViolatingFinality(stagingArea, tip)
if err != nil {
return nil, externalapi.StatusInvalid, err
}
if isViolatingFinality {
if shouldNotify {
//TODO: Send finality conflict notification
log.Warnf("Skipping %s tip resolution because it violates finality", tip)
}
continue
}
status, err := csm.blockStatusStore.Get(csm.databaseContext, stagingArea, tip)
if err != nil {
return nil, externalapi.StatusInvalid, err
}
if status == externalapi.StatusUTXOValid || status == externalapi.StatusUTXOPendingVerification {
return tip, status, nil
}
}
return nil, externalapi.StatusInvalid, nil
}
// getGHOSTDAGLowerTips returns the set of tips which are lower in GHOSTDAG parent selection order than `pendingTip`. i.e.,
// they can be added to virtual parents but `pendingTip` will remain the virtual selected parent
func (csm *consensusStateManager) getGHOSTDAGLowerTips(stagingArea *model.StagingArea, pendingTip *externalapi.DomainHash) ([]*externalapi.DomainHash, error) {
tips, err := csm.consensusStateStore.Tips(stagingArea, csm.databaseContext)
if err != nil {
return nil, err
}
lowerTips := []*externalapi.DomainHash{pendingTip}
for _, tip := range tips {
if tip.Equal(pendingTip) {
continue
}
selectedParent, err := csm.ghostdagManager.ChooseSelectedParent(stagingArea, tip, pendingTip)
if err != nil {
return nil, err
}
if selectedParent.Equal(pendingTip) {
lowerTips = append(lowerTips, tip)
}
}
return lowerTips, nil
}
func (csm *consensusStateManager) ResolveVirtual(maxBlocksToResolve uint64) (*externalapi.VirtualChangeSet, bool, error) {
onEnd := logger.LogAndMeasureExecutionTime(log, "csm.ResolveVirtual")
defer onEnd()
// We use a read-only staging area for some read-only actions, to avoid
// confusion with the resolve/updateVirtual staging areas below
readStagingArea := model.NewStagingArea()
pendingTip, pendingTipStatus, err := csm.findNextPendingTip(readStagingArea)
if err != nil {
return nil, false, err
}
if pendingTip == nil {
log.Warnf("None of the DAG tips are valid")
return nil, true, nil
}
previousVirtualSelectedParent, err := csm.virtualSelectedParent(readStagingArea)
if err != nil {
return nil, false, err
}
if pendingTipStatus == externalapi.StatusUTXOValid && previousVirtualSelectedParent.Equal(pendingTip) {
return nil, true, nil
}
// Resolve a chunk from the pending chain
resolveStagingArea := model.NewStagingArea()
unverifiedBlocks, err := csm.getUnverifiedChainBlocks(resolveStagingArea, pendingTip)
if err != nil {
return nil, false, err
}
// Initially set the resolve processing point to the pending tip
processingPoint := pendingTip
// Too many blocks to verify, so we only process a chunk and return
if maxBlocksToResolve != 0 && uint64(len(unverifiedBlocks)) > maxBlocksToResolve {
processingPointIndex := uint64(len(unverifiedBlocks)) - maxBlocksToResolve
processingPoint = unverifiedBlocks[processingPointIndex]
isNewVirtualSelectedParent, err := csm.isNewSelectedTip(readStagingArea, processingPoint, previousVirtualSelectedParent)
if err != nil {
return nil, false, err
}
// We must find a processing point which wins previous virtual selected parent
// even if we process more than `maxBlocksToResolve` for that.
// Otherwise, internal UTXO diff logic gets all messed up
for !isNewVirtualSelectedParent {
if processingPointIndex == 0 {
return nil, false, errors.Errorf(
"Expecting the pending tip %s to overcome the previous selected parent %s", pendingTip, previousVirtualSelectedParent)
}
processingPointIndex--
processingPoint = unverifiedBlocks[processingPointIndex]
isNewVirtualSelectedParent, err = csm.isNewSelectedTip(readStagingArea, processingPoint, previousVirtualSelectedParent)
if err != nil {
return nil, false, err
}
}
log.Debugf("Has more than %d blocks to resolve. Setting the resolve processing point to %s", maxBlocksToResolve, processingPoint)
}
processingPointStatus, reversalData, err := csm.resolveBlockStatus(
resolveStagingArea, processingPoint, true)
if err != nil {
return nil, false, err
}
if processingPointStatus == externalapi.StatusUTXOValid {
err = staging.CommitAllChanges(csm.databaseContext, resolveStagingArea)
if err != nil {
return nil, false, err
}
if reversalData != nil {
err = csm.ReverseUTXODiffs(processingPoint, reversalData)
if err != nil {
return nil, false, err
}
}
}
isActualTip := processingPoint.Equal(pendingTip)
isCompletelyResolved := isActualTip && processingPointStatus == externalapi.StatusUTXOValid
updateVirtualStagingArea := model.NewStagingArea()
virtualParents := []*externalapi.DomainHash{processingPoint}
// If `isCompletelyResolved`, set virtual correctly with all tips which have less blue work than pending
if isCompletelyResolved {
lowerTips, err := csm.getGHOSTDAGLowerTips(readStagingArea, pendingTip)
if err != nil {
return nil, false, err
}
log.Debugf("Picking virtual parents from relevant tips len: %d", len(lowerTips))
virtualParents, err = csm.pickVirtualParents(readStagingArea, lowerTips)
if err != nil {
return nil, false, err
}
log.Debugf("Picked virtual parents: %s", virtualParents)
}
virtualUTXODiff, err := csm.updateVirtualWithParents(updateVirtualStagingArea, virtualParents)
if err != nil {
return nil, false, err
}
err = staging.CommitAllChanges(csm.databaseContext, updateVirtualStagingArea)
if err != nil {
return nil, false, err
}
selectedParentChainChanges, err := csm.dagTraversalManager.
CalculateChainPath(updateVirtualStagingArea, previousVirtualSelectedParent, processingPoint)
if err != nil {
return nil, false, err
}
virtualParentsOutcome, err := csm.dagTopologyManager.Parents(updateVirtualStagingArea, model.VirtualBlockHash)
if err != nil {
return nil, false, err
}
return &externalapi.VirtualChangeSet{
VirtualSelectedParentChainChanges: selectedParentChainChanges,
VirtualUTXODiff: virtualUTXODiff,
VirtualParents: virtualParentsOutcome,
}, isCompletelyResolved, nil
}