1  // Copyright (c) 2016-2022 The Bitcoin Core developers
  2  // Distributed under the MIT software license, see the accompanying
  3  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4  
  5  #include <consensus/params.h>
  6  #include <deploymentinfo.h>
  7  #include <kernel/chainparams.h>
  8  #include <util/check.h>
  9  #include <versionbits.h>
 10  #include <versionbits_impl.h>
 11  
 12  using enum ThresholdState;
 13  
 14  std::string StateName(ThresholdState state)
 15  {
 16      switch (state) {
 17      case DEFINED: return "defined";
 18      case STARTED: return "started";
 19      case LOCKED_IN: return "locked_in";
 20      case ACTIVE: return "active";
 21      case FAILED: return "failed";
 22      }
 23      return "invalid";
 24  }
 25  
 26  ThresholdState AbstractThresholdConditionChecker::GetStateFor(const CBlockIndex* pindexPrev, ThresholdConditionCache& cache) const
 27  {
 28      int nPeriod = Period();
 29      int nThreshold = Threshold();
 30      int min_activation_height = MinActivationHeight();
 31      int64_t nTimeStart = BeginTime();
 32      int64_t nTimeTimeout = EndTime();
 33  
 34      // Check if this deployment is always active.
 35      if (nTimeStart == Consensus::BIP9Deployment::ALWAYS_ACTIVE) {
 36          return ThresholdState::ACTIVE;
 37      }
 38  
 39      // Check if this deployment is never active.
 40      if (nTimeStart == Consensus::BIP9Deployment::NEVER_ACTIVE) {
 41          return ThresholdState::FAILED;
 42      }
 43  
 44      // A block's state is always the same as that of the first of its period, so it is computed based on a pindexPrev whose height equals a multiple of nPeriod - 1.
 45      if (pindexPrev != nullptr) {
 46          pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod));
 47      }
 48  
 49      // Walk backwards in steps of nPeriod to find a pindexPrev whose information is known
 50      std::vector<const CBlockIndex*> vToCompute;
 51      while (cache.count(pindexPrev) == 0) {
 52          if (pindexPrev == nullptr) {
 53              // The genesis block is by definition defined.
 54              cache[pindexPrev] = ThresholdState::DEFINED;
 55              break;
 56          }
 57          if (pindexPrev->GetMedianTimePast() < nTimeStart) {
 58              // Optimization: don't recompute down further, as we know every earlier block will be before the start time
 59              cache[pindexPrev] = ThresholdState::DEFINED;
 60              break;
 61          }
 62          vToCompute.push_back(pindexPrev);
 63          pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
 64      }
 65  
 66      // At this point, cache[pindexPrev] is known
 67      assert(cache.count(pindexPrev));
 68      ThresholdState state = cache[pindexPrev];
 69  
 70      // Now walk forward and compute the state of descendants of pindexPrev
 71      while (!vToCompute.empty()) {
 72          ThresholdState stateNext = state;
 73          pindexPrev = vToCompute.back();
 74          vToCompute.pop_back();
 75  
 76          switch (state) {
 77              case ThresholdState::DEFINED: {
 78                  if (pindexPrev->GetMedianTimePast() >= nTimeStart) {
 79                      stateNext = ThresholdState::STARTED;
 80                  }
 81                  break;
 82              }
 83              case ThresholdState::STARTED: {
 84                  // We need to count
 85                  const CBlockIndex* pindexCount = pindexPrev;
 86                  int count = 0;
 87                  for (int i = 0; i < nPeriod; i++) {
 88                      if (Condition(pindexCount)) {
 89                          count++;
 90                      }
 91                      pindexCount = pindexCount->pprev;
 92                  }
 93                  if (count >= nThreshold) {
 94                      stateNext = ThresholdState::LOCKED_IN;
 95                  } else if (pindexPrev->GetMedianTimePast() >= nTimeTimeout) {
 96                      stateNext = ThresholdState::FAILED;
 97                  }
 98                  break;
 99              }
100              case ThresholdState::LOCKED_IN: {
101                  // Progresses into ACTIVE provided activation height will have been reached.
102                  if (pindexPrev->nHeight + 1 >= min_activation_height) {
103                      stateNext = ThresholdState::ACTIVE;
104                  }
105                  break;
106              }
107              case ThresholdState::FAILED:
108              case ThresholdState::ACTIVE: {
109                  // Nothing happens, these are terminal states.
110                  break;
111              }
112          }
113          cache[pindexPrev] = state = stateNext;
114      }
115  
116      return state;
117  }
118  
119  BIP9Stats AbstractThresholdConditionChecker::GetStateStatisticsFor(const CBlockIndex* pindex, std::vector<bool>* signalling_blocks) const
120  {
121      BIP9Stats stats = {};
122  
123      stats.period = Period();
124      stats.threshold = Threshold();
125  
126      if (pindex == nullptr) return stats;
127  
128      // Find how many blocks are in the current period
129      int blocks_in_period = 1 + (pindex->nHeight % stats.period);
130  
131      // Reset signalling_blocks
132      if (signalling_blocks) {
133          signalling_blocks->assign(blocks_in_period, false);
134      }
135  
136      // Count from current block to beginning of period
137      int elapsed = 0;
138      int count = 0;
139      const CBlockIndex* currentIndex = pindex;
140      do {
141          ++elapsed;
142          --blocks_in_period;
143          if (Condition(currentIndex)) {
144              ++count;
145              if (signalling_blocks) signalling_blocks->at(blocks_in_period) = true;
146          }
147          currentIndex = currentIndex->pprev;
148      } while(blocks_in_period > 0);
149  
150      stats.elapsed = elapsed;
151      stats.count = count;
152      stats.possible = (stats.period - stats.threshold ) >= (stats.elapsed - count);
153  
154      return stats;
155  }
156  
157  int AbstractThresholdConditionChecker::GetStateSinceHeightFor(const CBlockIndex* pindexPrev, ThresholdConditionCache& cache) const
158  {
159      int64_t start_time = BeginTime();
160      if (start_time == Consensus::BIP9Deployment::ALWAYS_ACTIVE || start_time == Consensus::BIP9Deployment::NEVER_ACTIVE) {
161          return 0;
162      }
163  
164      const ThresholdState initialState = GetStateFor(pindexPrev, cache);
165  
166      // BIP 9 about state DEFINED: "The genesis block is by definition in this state for each deployment."
167      if (initialState == ThresholdState::DEFINED) {
168          return 0;
169      }
170  
171      const int nPeriod = Period();
172  
173      // A block's state is always the same as that of the first of its period, so it is computed based on a pindexPrev whose height equals a multiple of nPeriod - 1.
174      // To ease understanding of the following height calculation, it helps to remember that
175      // right now pindexPrev points to the block prior to the block that we are computing for, thus:
176      // if we are computing for the last block of a period, then pindexPrev points to the second to last block of the period, and
177      // if we are computing for the first block of a period, then pindexPrev points to the last block of the previous period.
178      // The parent of the genesis block is represented by nullptr.
179      pindexPrev = Assert(pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod)));
180  
181      const CBlockIndex* previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
182  
183      while (previousPeriodParent != nullptr && GetStateFor(previousPeriodParent, cache) == initialState) {
184          pindexPrev = previousPeriodParent;
185          previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
186      }
187  
188      // Adjust the result because right now we point to the parent block.
189      return pindexPrev->nHeight + 1;
190  }
191  
192  BIP9Info VersionBitsCache::Info(const CBlockIndex& block_index, const Consensus::Params& params, Consensus::DeploymentPos id)
193  {
194      BIP9Info result;
195  
196      VersionBitsConditionChecker checker(params, id);
197  
198      ThresholdState current_state, next_state;
199  
200      {
201          LOCK(m_mutex);
202          current_state = checker.GetStateFor(block_index.pprev, m_caches[id]);
203          next_state = checker.GetStateFor(&block_index, m_caches[id]);
204          result.since = checker.GetStateSinceHeightFor(block_index.pprev, m_caches[id]);
205      }
206  
207      result.current_state = StateName(current_state);
208      result.next_state = StateName(next_state);
209  
210      const bool has_signal = (STARTED == current_state || LOCKED_IN == current_state);
211      if (has_signal) {
212          result.stats.emplace(checker.GetStateStatisticsFor(&block_index, &result.signalling_blocks));
213          if (LOCKED_IN == current_state) {
214              result.stats->threshold = 0;
215              result.stats->possible = false;
216          }
217      }
218  
219      if (current_state == ACTIVE) {
220          result.active_since = result.since;
221      } else if (next_state == ACTIVE) {
222          result.active_since = block_index.nHeight + 1;
223      }
224  
225      return result;
226  }
227  
228  BIP9GBTStatus VersionBitsCache::GBTStatus(const CBlockIndex& block_index, const Consensus::Params& params)
229  {
230      BIP9GBTStatus result;
231  
232      LOCK(m_mutex);
233      for (int i = 0; i < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
234          auto pos = static_cast<Consensus::DeploymentPos>(i);
235          VersionBitsConditionChecker checker(params, pos);
236          ThresholdState state = checker.GetStateFor(&block_index, m_caches[pos]);
237          const VBDeploymentInfo& vbdepinfo = VersionBitsDeploymentInfo[pos];
238          BIP9GBTStatus::Info gbtinfo{.bit=params.vDeployments[pos].bit, .mask=checker.Mask(), .gbt_optional_rule=vbdepinfo.gbt_optional_rule};
239  
240          switch (state) {
241          case DEFINED:
242          case FAILED:
243              // Not exposed to GBT
244              break;
245          case STARTED:
246              result.signalling.try_emplace(vbdepinfo.name, gbtinfo);
247              break;
248          case LOCKED_IN:
249              result.locked_in.try_emplace(vbdepinfo.name, gbtinfo);
250              break;
251          case ACTIVE:
252              result.active.try_emplace(vbdepinfo.name, gbtinfo);
253              break;
254          }
255      }
256      return result;
257  }
258  
259  bool VersionBitsCache::IsActiveAfter(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos)
260  {
261      LOCK(m_mutex);
262      return ThresholdState::ACTIVE == VersionBitsConditionChecker(params, pos).GetStateFor(pindexPrev, m_caches[pos]);
263  }
264  
265  static int32_t ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params, std::array<ThresholdConditionCache, Consensus::MAX_VERSION_BITS_DEPLOYMENTS>& caches)
266  {
267      int32_t nVersion = VERSIONBITS_TOP_BITS;
268  
269      for (int i = 0; i < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
270          Consensus::DeploymentPos pos = static_cast<Consensus::DeploymentPos>(i);
271          VersionBitsConditionChecker checker(params, pos);
272          ThresholdState state = checker.GetStateFor(pindexPrev, caches[pos]);
273          if (state == ThresholdState::LOCKED_IN || state == ThresholdState::STARTED) {
274              nVersion |= checker.Mask();
275          }
276      }
277  
278      return nVersion;
279  }
280  
281  int32_t VersionBitsCache::ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params)
282  {
283      LOCK(m_mutex);
284      return ::ComputeBlockVersion(pindexPrev, params, m_caches);
285  }
286  
287  void VersionBitsCache::Clear()
288  {
289      LOCK(m_mutex);
290      for (unsigned int d = 0; d < Consensus::MAX_VERSION_BITS_DEPLOYMENTS; d++) {
291          m_caches[d].clear();
292      }
293  }
294  
295  namespace {
296  /**
297   * Threshold condition checker that triggers when unknown versionbits are seen on the network.
298   */
299  class WarningBitsConditionChecker : public AbstractThresholdConditionChecker
300  {
301  private:
302      const Consensus::Params& m_params;
303      std::array<ThresholdConditionCache, Consensus::MAX_VERSION_BITS_DEPLOYMENTS>& m_caches;
304      int m_bit;
305      int period{2016};
306      int threshold{1815}; // 90% threshold used in BIP 341
307  
308  public:
309      explicit WarningBitsConditionChecker(const CChainParams& chainparams, std::array<ThresholdConditionCache, Consensus::MAX_VERSION_BITS_DEPLOYMENTS>& caches, int bit)
310      : m_params{chainparams.GetConsensus()}, m_caches{caches}, m_bit(bit)
311      {
312          if (chainparams.IsTestChain()) {
313              period = chainparams.GetConsensus().DifficultyAdjustmentInterval();
314              threshold = period * 3 / 4; // 75% for test nets per BIP9 suggestion
315          }
316      }
317  
318      int64_t BeginTime() const override { return 0; }
319      int64_t EndTime() const override { return std::numeric_limits<int64_t>::max(); }
320      int Period() const override { return period; }
321      int Threshold() const override { return threshold; }
322  
323      bool Condition(const CBlockIndex* pindex) const override
324      {
325          return pindex->nHeight >= m_params.MinBIP9WarningHeight &&
326                 ((pindex->nVersion & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) &&
327                 ((pindex->nVersion >> m_bit) & 1) != 0 &&
328                 ((::ComputeBlockVersion(pindex->pprev, m_params, m_caches) >> m_bit) & 1) == 0;
329      }
330  };
331  } // anonymous namespace
332  
333  std::vector<std::pair<int, bool>> VersionBitsCache::CheckUnknownActivations(const CBlockIndex* pindex, const CChainParams& chainparams)
334  {
335      LOCK(m_mutex);
336      std::vector<std::pair<int, bool>> result;
337      for (int bit = 0; bit < VERSIONBITS_NUM_BITS; ++bit) {
338          WarningBitsConditionChecker checker(chainparams, m_caches, bit);
339          ThresholdState state = checker.GetStateFor(pindex, m_warning_caches.at(bit));
340          if (state == ACTIVE || state == LOCKED_IN) {
341              result.emplace_back(bit, state == ACTIVE);
342          }
343      }
344      return result;
345  }