vendor/github.com/btcsuite/btcd/blockchain/mediantime.go

   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
   5 package blockchain
   6
   7 import (
   8         "math"
   9         "sort"
  10         "sync"
  11         "time"
  12 )
  13
  14 const (
  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 likley wrong and
  22         // hence to show a warning.
  23         similarTimeSecs = 5 * 60 // 5 minutes
  24 )
  25
  26 var (
  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.
  36 type 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.
  52 type int64Sorter []int64
  53
  54 // Len returns the number of 64-bit integers in the slice.  It is part of the
  55 // sort.Interface implementation.
  56 func (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.
  62 func (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.
  69 func (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.
  77 type 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.
  86 var _ 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.
  93 func (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.
 107 func (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.
 201 func (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.
 213 func NewMedianTime() MedianTimeSource {
 214         return &medianTime{
 215                 knownIDs: make(map[string]struct{}),
 216                 offsets:  make([]int64, 0, maxMedianTimeEntries),
 217         }
 218 }