/
referenceprovider.go
240 lines (193 loc) · 9.02 KB
/
referenceprovider.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
package tangle
import (
"time"
"github.com/cockroachdb/errors"
"github.com/iotaledger/hive.go/generics/walker"
"github.com/iotaledger/goshimmer/packages/clock"
"github.com/iotaledger/goshimmer/packages/conflictdag"
"github.com/iotaledger/goshimmer/packages/ledger/utxo"
"github.com/iotaledger/goshimmer/packages/tangle/payload"
)
// region ReferenceProvider ////////////////////////////////////////////////////////////////////////////////////////////
// ReferenceProvider is a component that takes care of creating the correct references when selecting tips.
type ReferenceProvider struct {
tangle *Tangle
}
// NewReferenceProvider creates a new ReferenceProvider instance.
func NewReferenceProvider(tangle *Tangle) (newInstance *ReferenceProvider) {
return &ReferenceProvider{
tangle: tangle,
}
}
// References is an implementation of ReferencesFunc.
func (r *ReferenceProvider) References(payload payload.Payload, strongParents BlockIDs, issuingTime time.Time) (references ParentBlockIDs, err error) {
references = NewParentBlockIDs()
// If the payload is a transaction we will weakly reference unconfirmed transactions it is consuming.
if tx, isTx := payload.(utxo.Transaction); isTx {
referencedTxs := r.tangle.Ledger.Utils.ReferencedTransactions(tx)
for it := referencedTxs.Iterator(); it.HasNext(); {
referencedTx := it.Next()
if !r.tangle.ConfirmationOracle.IsTransactionConfirmed(referencedTx) {
latestAttachment := r.tangle.BlockFactory.LatestAttachment(referencedTx)
if latestAttachment == nil {
continue
}
timeDifference := clock.SyncedTime().Sub(latestAttachment.IssuingTime())
// If the latest attachment of the transaction we are consuming is too old we are not
// able to add it is a weak parent.
if timeDifference <= maxParentsTimeDifference {
if len(references[WeakParentType]) == MaxParentsCount {
return references, nil
}
references.Add(WeakParentType, latestAttachment.ID())
}
}
}
}
excludedConflictIDs := utxo.NewTransactionIDs()
for strongParent := range strongParents {
excludedConflictIDsCopy := excludedConflictIDs.Clone()
referencesToAdd, validStrongParent := r.addedReferencesForBlock(strongParent, issuingTime, excludedConflictIDsCopy)
if !validStrongParent {
if err = r.checkPayloadLiked(strongParent); err != nil {
continue
}
referencesToAdd = NewParentBlockIDs().Add(WeakParentType, strongParent)
} else {
referencesToAdd.AddStrong(strongParent)
}
if combinedReferences, success := r.tryExtendReferences(references, referencesToAdd); success {
references = combinedReferences
excludedConflictIDs = excludedConflictIDsCopy
}
}
if len(references[StrongParentType]) == 0 {
return nil, errors.Errorf("none of the provided strong parents can be referenced. Strong parents provided: %+v.", strongParents)
}
return references, nil
}
func (r *ReferenceProvider) ReferencesToMissingConflicts(issuingTime time.Time, amount int) (blockIDs BlockIDs) {
blockIDs = NewBlockIDs()
if amount == 0 {
return blockIDs
}
for it := r.tangle.TipManager.tipsConflictTracker.MissingConflicts(amount).Iterator(); it.HasNext(); {
blockID, blockIDErr := r.firstValidAttachment(it.Next(), issuingTime)
if blockIDErr != nil {
continue
}
blockIDs.Add(blockID)
}
return blockIDs
}
// addedReferenceForBlock returns the reference that is necessary to correct our opinion on the given block.
func (r *ReferenceProvider) addedReferencesForBlock(blkID BlockID, issuingTime time.Time, excludedConflictIDs utxo.TransactionIDs) (addedReferences ParentBlockIDs, success bool) {
blkConflictIDs, err := r.tangle.Booker.BlockConflictIDs(blkID)
if err != nil {
r.tangle.OrphanageManager.OrphanBlock(blkID, errors.Errorf("conflictID of %s can't be retrieved: %w", blkID, err))
return nil, false
}
addedReferences = NewParentBlockIDs()
if blkConflictIDs.IsEmpty() {
return addedReferences, true
}
if addedReferences, err = r.addedReferencesForConflicts(blkConflictIDs, issuingTime, excludedConflictIDs); err != nil {
r.tangle.OrphanageManager.OrphanBlock(blkID, errors.Errorf("cannot pick up %s as strong parent: %w", blkID, err))
return nil, false
}
// fmt.Println("excludedConflictIDs", excludedConflictIDs)
// fmt.Println("addedReferencesForBlock", blkID, addedReferences)
// A block might introduce too many references and cannot be picked up as a strong parent.
if _, success := r.tryExtendReferences(NewParentBlockIDs(), addedReferences); !success {
r.tangle.OrphanageManager.OrphanBlock(blkID, errors.Errorf("cannot pick up %s as strong parent: %w", blkID, err))
return nil, false
}
return addedReferences, true
}
// addedReferencesForConflicts returns the references that are necessary to correct our opinion on the given conflicts.
func (r *ReferenceProvider) addedReferencesForConflicts(conflictIDs utxo.TransactionIDs, issuingTime time.Time, excludedConflictIDs utxo.TransactionIDs) (referencesToAdd ParentBlockIDs, err error) {
referencesToAdd = NewParentBlockIDs()
for it := conflictIDs.Iterator(); it.HasNext(); {
conflictID := it.Next()
// If we already expressed a dislike of the conflict (through another liked instead) we don't need to revisit this conflictID.
if excludedConflictIDs.Has(conflictID) {
continue
}
if adjust, referencedBlk, referenceErr := r.adjustOpinion(conflictID, issuingTime, excludedConflictIDs); referenceErr != nil {
return nil, errors.Errorf("failed to create reference for %s: %w", conflictID, referenceErr)
} else if adjust {
referencesToAdd.Add(ShallowLikeParentType, referencedBlk)
}
}
return referencesToAdd, nil
}
// adjustOpinion returns the reference that is necessary to correct our opinion on the given conflict.
func (r *ReferenceProvider) adjustOpinion(conflictID utxo.TransactionID, issuingTime time.Time, excludedConflictIDs utxo.TransactionIDs) (adjust bool, blkID BlockID, err error) {
for w := walker.New[utxo.TransactionID](false).Push(conflictID); w.HasNext(); {
currentConflictID := w.Next()
if likedConflictID, dislikedConflictIDs := r.tangle.OTVConsensusManager.LikedConflictMember(currentConflictID); !likedConflictID.IsEmpty() {
// only triggers in first iteration
if likedConflictID == conflictID {
return false, EmptyBlockID, nil
}
if blkID, err = r.firstValidAttachment(likedConflictID, issuingTime); err != nil {
continue
}
excludedConflictIDs.AddAll(r.tangle.Ledger.Utils.ConflictIDsInFutureCone(dislikedConflictIDs))
return true, blkID, nil
}
// only walk deeper if we don't like "something else"
r.tangle.Ledger.ConflictDAG.Storage.CachedConflict(currentConflictID).Consume(func(conflict *conflictdag.Conflict[utxo.TransactionID, utxo.OutputID]) {
w.PushFront(conflict.Parents().Slice()...)
})
}
return false, EmptyBlockID, errors.Newf("failed to create dislike for %s", conflictID)
}
// firstValidAttachment returns the first valid attachment of the given transaction.
func (r *ReferenceProvider) firstValidAttachment(txID utxo.TransactionID, issuingTime time.Time) (blkID BlockID, err error) {
attachmentTime, blkID, err := r.tangle.Utils.FirstAttachment(txID)
if err != nil {
return EmptyBlockID, errors.Errorf("failed to find first attachment of Transaction with %s: %w", txID, err)
}
// TODO: we don't want to vote on anything that is in a committed epoch.
if !r.validTime(attachmentTime, issuingTime) {
return EmptyBlockID, errors.Errorf("attachment of %s with %s is too far in the past", txID, blkID)
}
return blkID, nil
}
func (r *ReferenceProvider) validTime(parentTime, issuingTime time.Time) bool {
// TODO: we don't want to vote on anything that is in a committed epoch.
return issuingTime.Sub(parentTime) < maxParentsTimeDifference
}
func (r *ReferenceProvider) validTimeForStrongParent(blkID BlockID, issuingTime time.Time) (valid bool) {
r.tangle.Storage.Block(blkID).Consume(func(blk *Block) {
valid = r.validTime(blk.IssuingTime(), issuingTime)
})
return valid
}
// checkPayloadLiked checks if the payload of a Block is liked.
func (r *ReferenceProvider) checkPayloadLiked(blkID BlockID) (err error) {
conflictIDs, err := r.tangle.Booker.PayloadConflictIDs(blkID)
if err != nil {
return errors.Errorf("failed to determine payload conflictIDs of %s: %w", blkID, err)
}
if !r.tangle.Utils.AllConflictsLiked(conflictIDs) {
return errors.Errorf("payload of %s is not liked: %s", blkID, conflictIDs)
}
return nil
}
// tryExtendReferences tries to extend the references with the given referencesToAdd.
func (r *ReferenceProvider) tryExtendReferences(references ParentBlockIDs, referencesToAdd ParentBlockIDs) (extendedReferences ParentBlockIDs, success bool) {
if referencesToAdd.IsEmpty() {
return references, true
}
extendedReferences = references.Clone()
for referenceType, referencedBlockIDs := range referencesToAdd {
extendedReferences.AddAll(referenceType, referencedBlockIDs)
if len(extendedReferences[referenceType]) > MaxParentsCount {
return nil, false
}
}
return extendedReferences, true
}
// endregion ///////////////////////////////////////////////////////////////////////////////////////////////////////////