This repository has been archived by the owner on Jun 17, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 72
/
median_time.go
83 lines (71 loc) · 2.38 KB
/
median_time.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
package vector
import (
"sort"
"github.com/Fantom-foundation/go-lachesis/hash"
"github.com/Fantom-foundation/go-lachesis/inter"
"github.com/Fantom-foundation/go-lachesis/inter/idx"
"github.com/Fantom-foundation/go-lachesis/inter/pos"
)
// medianTimeIndex is a handy index for the MedianTime() func
type medianTimeIndex struct {
stake pos.Stake
claimedTime inter.Timestamp
}
// MedianTime calculates weighted median of claimed time within highest observed events.
func (vi *Index) MedianTime(id hash.Event, genesisTime inter.Timestamp) inter.Timestamp {
vi.initBranchesInfo()
// get event by hash
beforeSeq, times := vi.getHighestBeforeAllBranchesTime(id)
if beforeSeq == nil || times == nil {
vi.Log.Error("Event not found", "event", id.String())
return 0
}
honestTotalStake := pos.Stake(0) // isn't equal to validators.TotalStake(), because doesn't count cheaters
highests := make([]medianTimeIndex, 0, len(vi.validatorIdxs))
// convert []HighestBefore -> []medianTimeIndex
for creatorIdxI := range vi.validators.IDs() {
creatorIdx := idx.Validator(creatorIdxI)
highest := medianTimeIndex{}
highest.stake = vi.validators.GetStakeByIdx(creatorIdx)
highest.claimedTime = times.Get(creatorIdx)
seq := beforeSeq.Get(creatorIdx)
// edge cases
if seq.IsForkDetected() {
// cheaters don't influence medianTime
highest.stake = 0
} else if seq.Seq == 0 {
// if no event was observed from this node, then use genesisTime
highest.claimedTime = genesisTime
}
highests = append(highests, highest)
honestTotalStake += highest.stake
}
// it's technically possible honestTotalStake == 0 (all validators are cheaters)
// sort by claimed time (partial order is enough here, because we need only claimedTime)
sort.Slice(highests, func(i, j int) bool {
a, b := highests[i], highests[j]
return a.claimedTime < b.claimedTime
})
// Calculate weighted median
halfStake := honestTotalStake / 2
var currStake pos.Stake
var median inter.Timestamp
for _, highest := range highests {
currStake += highest.stake
if currStake >= halfStake {
median = highest.claimedTime
break
}
}
// sanity check
if currStake < halfStake || currStake > honestTotalStake {
vi.Log.Crit("Median wasn't calculated correctly",
"median", median,
"currStake", currStake,
"totalStake", honestTotalStake,
"len(highests)", len(highests),
"id", id.String(),
)
}
return median
}