/
otv.go
145 lines (118 loc) · 5.29 KB
/
otv.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
package otv
import (
"bytes"
"sort"
"github.com/iotaledger/hive.go/core/generics/set"
"github.com/iotaledger/hive.go/core/generics/walker"
"github.com/iotaledger/hive.go/core/types/confirmation"
"github.com/iotaledger/goshimmer/packages/core/conflictdag"
"github.com/iotaledger/goshimmer/packages/core/consensus"
"github.com/iotaledger/goshimmer/packages/core/ledger/utxo"
)
// OnTangleVoting is a pluggable implementation of tangle.ConsensusMechanism2. On tangle voting is a generalized form of
// Nakamoto consensus for the parallel-reality-based ledger state where the heaviest conflict according to approval weight
// is liked by any given node.
type OnTangleVoting struct {
conflictDAG *conflictdag.ConflictDAG[utxo.TransactionID, utxo.OutputID]
weightFunc consensus.WeightFunc
}
// NewOnTangleVoting is the constructor for OnTangleVoting.
func NewOnTangleVoting(conflictDAG *conflictdag.ConflictDAG[utxo.TransactionID, utxo.OutputID], weightFunc consensus.WeightFunc) *OnTangleVoting {
return &OnTangleVoting{
conflictDAG: conflictDAG,
weightFunc: weightFunc,
}
}
// LikedConflictMember returns the liked ConflictID across the members of its conflict sets.
func (o *OnTangleVoting) LikedConflictMember(conflictID utxo.TransactionID) (likedConflict utxo.TransactionID, dislikedConflicts utxo.TransactionIDs) {
dislikedConflicts = utxo.NewTransactionIDs()
if o.ConflictLiked(conflictID) {
likedConflict = conflictID
} else {
dislikedConflicts.Add(conflictID)
}
o.conflictDAG.Utils.ForEachConflictingConflictID(conflictID, func(conflictingConflictID utxo.TransactionID) bool {
if likedConflict.IsEmpty() && o.ConflictLiked(conflictingConflictID) {
likedConflict = conflictingConflictID
} else {
dislikedConflicts.Add(conflictingConflictID)
}
return true
})
return
}
// ConflictLiked returns whether the conflict is the winner across all conflict sets (it is in the liked reality).
func (o *OnTangleVoting) ConflictLiked(conflictID utxo.TransactionID) (conflictLiked bool) {
conflictLiked = true
if conflictID == utxo.EmptyTransactionID {
return
}
for likeWalker := walker.New[utxo.TransactionID]().Push(conflictID); likeWalker.HasNext(); {
if conflictLiked = conflictLiked && o.conflictPreferred(likeWalker.Next(), likeWalker); !conflictLiked {
return
}
}
return
}
// conflictPreferred returns whether the conflict is the winner across its conflict sets.
func (o *OnTangleVoting) conflictPreferred(conflictID utxo.TransactionID, likeWalker *walker.Walker[utxo.TransactionID]) (preferred bool) {
preferred = true
if conflictID == utxo.EmptyTransactionID {
return
}
o.conflictDAG.Storage.CachedConflict(conflictID).Consume(func(conflict *conflictdag.Conflict[utxo.TransactionID, utxo.OutputID]) {
switch conflict.ConfirmationState() {
case confirmation.Rejected:
preferred = false
return
case confirmation.Accepted:
case confirmation.Confirmed:
return
}
if preferred = !o.dislikedConnectedConflictingConflicts(conflictID).Has(conflictID); preferred {
for it := conflict.Parents().Iterator(); it.HasNext(); {
likeWalker.Push(it.Next())
}
}
})
return
}
func (o *OnTangleVoting) dislikedConnectedConflictingConflicts(currentConflictID utxo.TransactionID) (dislikedConflicts set.Set[utxo.TransactionID]) {
dislikedConflicts = set.New[utxo.TransactionID]()
o.forEachConnectedConflictingConflictInDescendingOrder(currentConflictID, func(conflictID utxo.TransactionID, weight float64) {
if dislikedConflicts.Has(conflictID) {
return
}
rejectionWalker := walker.New[utxo.TransactionID]()
o.conflictDAG.Utils.ForEachConflictingConflictID(conflictID, func(conflictingConflictID utxo.TransactionID) bool {
rejectionWalker.Push(conflictingConflictID)
return true
})
for rejectionWalker.HasNext() {
rejectedConflictID := rejectionWalker.Next()
dislikedConflicts.Add(rejectedConflictID)
o.conflictDAG.Storage.CachedChildConflicts(rejectedConflictID).Consume(func(childConflict *conflictdag.ChildConflict[utxo.TransactionID]) {
rejectionWalker.Push(childConflict.ChildConflictID())
})
}
})
return dislikedConflicts
}
// forEachConnectedConflictingConflictInDescendingOrder iterates over all conflicts connected via conflict sets
// and sorts them by weight. It calls the callback for each of them in that order.
func (o *OnTangleVoting) forEachConnectedConflictingConflictInDescendingOrder(conflictID utxo.TransactionID, callback func(conflictID utxo.TransactionID, weight float64)) {
conflictWeights := make(map[utxo.TransactionID]float64)
conflictsOrderedByWeight := make([]utxo.TransactionID, 0)
o.conflictDAG.Utils.ForEachConnectedConflictingConflictID(conflictID, func(conflictingConflictID utxo.TransactionID) {
conflictWeights[conflictingConflictID] = o.weightFunc(conflictingConflictID)
conflictsOrderedByWeight = append(conflictsOrderedByWeight, conflictingConflictID)
})
sort.Slice(conflictsOrderedByWeight, func(i, j int) bool {
conflictI := conflictsOrderedByWeight[i]
conflictJ := conflictsOrderedByWeight[j]
return !(conflictWeights[conflictI] < conflictWeights[conflictJ] || (conflictWeights[conflictI] == conflictWeights[conflictJ] && bytes.Compare(conflictI.Bytes(), conflictJ.Bytes()) > 0))
})
for _, orderedConflictID := range conflictsOrderedByWeight {
callback(orderedConflictID, conflictWeights[orderedConflictID])
}
}