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