1 package blockchain
2 3 import (
4 "math"
5 "sort"
6 "sync"
7 "time"
8 )
9 10 // TODO: tighten maxAllowedOffsetSecs for hf1 - also, consider changing to a mode, as this makes it harder to manipulate
11 // even with huge hash power
12 const (
13 // maxAllowedOffsetSeconds is the maximum number of seconds in either direction that local clock will be adjusted.
14 // When the median time of the network is outside of this range, no offset will be applied.
15 maxAllowedOffsetSecs = MaxTimeOffsetSeconds
16 // similarTimeSecs is the number of seconds in either direction from the local clock that is used to determine that
17 // it is likley wrong and hence to show a warning.
18 similarTimeSecs = 5 * 60 // 5 minutes
19 )
20 21 var (
22 // maxMedianTimeEntries is the maximum number of entries allowed in the median time data. This is a variable as
23 // opposed to a constant so the test code can modify it.
24 maxMedianTimeEntries = 200
25 )
26 27 // MedianTimeSource provides a mechanism to add several time samples which are used to determine a median time which is
28 // then used as an offset to the local clock.
29 type MedianTimeSource interface {
30 // AdjustedTime returns the current time adjusted by the median time offset as calculated from the time samples
31 // added by AddTimeSample.
32 AdjustedTime() time.Time
33 // AddTimeSample adds a time sample that is used when determining the median time of the added samples.
34 AddTimeSample(id string, timeVal time.Time)
35 // Offset returns the number of seconds to adjust the local clock based upon the median of the time samples added by
36 // AddTimeData.
37 Offset() time.Duration
38 }
39 40 // int64Sorter implements sort.Interface to allow a slice of 64-bit integers to be sorted.
41 type int64Sorter []int64
42 43 // Len returns the number of 64-bit integers in the slice. It is part of the sort.Interface implementation.
44 func (s int64Sorter) Len() int {
45 return len(s)
46 }
47 48 // Swap swaps the 64-bit integers at the passed indices. It is part of the sort.Interface implementation.
49 func (s int64Sorter) Swap(i, j int) {
50 s[i], s[j] = s[j], s[i]
51 }
52 53 // Less returns whether the 64-bit integer with index i should txsort before the 64-bit integer with index j. It is part
54 // of the sort.Interface implementation.
55 func (s int64Sorter) Less(i, j int) bool {
56 return s[i] < s[j]
57 }
58 59 // medianTime provides an implementation of the MedianTimeSource interface. It is limited to maxMedianTimeEntries
60 // includes the same buggy behavior as the time offset mechanism in Bitcoin Core. This is necessary because it is used
61 // in the consensus code.
62 type medianTime struct {
63 mtx sync.Mutex
64 knownIDs map[string]struct{}
65 offsets []int64
66 offsetSecs int64
67 invalidTimeChecked bool
68 }
69 70 // Ensure the medianTime type implements the MedianTimeSource interface.
71 var _ MedianTimeSource = (*medianTime)(nil)
72 73 // AdjustedTime returns the current time adjusted by the median time offset as calculated from the time samples added by
74 // AddTimeSample. This function is safe for concurrent access and is part of the MedianTimeSource interface
75 // implementation.
76 func (m *medianTime) AdjustedTime() time.Time {
77 m.mtx.Lock()
78 defer m.mtx.Unlock()
79 // Limit the adjusted time to 1 second precision.
80 now := time.Unix(time.Now().Unix(), 0)
81 return now.Add(time.Duration(m.offsetSecs) * time.Second)
82 }
83 84 // AddTimeSample adds a time sample that is used when determining the median time of the added samples. This function is
85 // safe for concurrent access and is part of the MedianTimeSource interface implementation.
86 func (m *medianTime) AddTimeSample(sourceID string, timeVal time.Time) {
87 m.mtx.Lock()
88 defer m.mtx.Unlock()
89 // Don't add time data from the same source.
90 if _, exists := m.knownIDs[sourceID]; exists {
91 return
92 }
93 m.knownIDs[sourceID] = struct{}{}
94 // Truncate the provided offset to seconds and append it to the slice of offsets while respecting the maximum number
95 // of allowed entries by replacing the oldest entry with the new entry once the maximum number of entries is
96 // reached.
97 now := time.Unix(time.Now().Unix(), 0)
98 offsetSecs := int64(timeVal.Sub(now).Seconds())
99 numOffsets := len(m.offsets)
100 if numOffsets == maxMedianTimeEntries && maxMedianTimeEntries > 0 {
101 m.offsets = m.offsets[1:]
102 numOffsets--
103 }
104 m.offsets = append(m.offsets, offsetSecs)
105 numOffsets++
106 // Sort the offsets so the median can be obtained as needed later.
107 sortedOffsets := make([]int64, numOffsets)
108 copy(sortedOffsets, m.offsets)
109 sort.Sort(int64Sorter(sortedOffsets))
110 offsetDuration := time.Duration(offsetSecs) * time.Second
111 T.F("Added time sample of %v (total: %v)", offsetDuration,
112 numOffsets,
113 )
114 T.Ln("samples:", sortedOffsets)
115 // NOTE: The following code intentionally has a bug to mirror the buggy behavior in Bitcoin Core since the median
116 // time is used in the consensus rules. In particular, the offset is only updated when the number of entries is odd,
117 // but the max number of entries is 200, an even number. Thus, the offset will never be updated again once the max
118 // number of entries is reached. The median offset is only updated when there are enough offsets and the number of
119 // offsets is odd so the middle value is the true median. Thus, there is nothing to do when those conditions are not
120 // met.
121 if numOffsets < 5 || numOffsets&0x01 != 1 {
122 return
123 }
124 // At this point the number of offsets in the list is odd, so the middle value of the sorted offsets is the median.
125 median := sortedOffsets[numOffsets/2]
126 // Set the new offset when the median offset is within the allowed offset range.
127 if math.Abs(float64(median)) < maxAllowedOffsetSecs {
128 m.offsetSecs = median
129 } else {
130 // The median offset of all added time data is larger than the maximum allowed offset, so don't use an offset.
131 // This effectively limits how far the local clock can be skewed.
132 m.offsetSecs = 0
133 if !m.invalidTimeChecked {
134 m.invalidTimeChecked = true
135 // Find if any time samples have a time that is close to the local
136 // time.
137 var remoteHasCloseTime bool
138 for _, offset := range sortedOffsets {
139 if math.Abs(float64(offset)) < similarTimeSecs {
140 remoteHasCloseTime = true
141 break
142 }
143 }
144 // Warn if none of the time samples are close.
145 if !remoteHasCloseTime {
146 W.Ln("Please check your date and time are correct! pod " +
147 "will not work properly with an invalid time",
148 )
149 }
150 }
151 }
152 medianDuration := time.Duration(m.offsetSecs) * time.Second
153 D.Ln("new time offset:", medianDuration)
154 }
155 156 // Offset returns the number of seconds to adjust the local clock based upon the median of the time samples added by
157 // AddTimeData. This function is safe for concurrent access and is part of the MedianTimeSource interface
158 // implementation.
159 func (m *medianTime) Offset() time.Duration {
160 m.mtx.Lock()
161 defer m.mtx.Unlock()
162 return time.Duration(m.offsetSecs) * time.Second
163 }
164 165 // NewMedianTime returns a new instance of concurrency-safe implementation of the MedianTimeSource interface. The
166 // returned implementation contains the rules necessary for proper time handling in the chain consensus rules and
167 // expects the time samples to be added from the timestamp field of the version message received from remote peers that
168 // successfully connect and negotiate.
169 func NewMedianTime() MedianTimeSource {
170 return &medianTime{
171 knownIDs: make(map[string]struct{}),
172 offsets: make([]int64, 0, maxMedianTimeEntries),
173 }
174 }
175