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 <util/check.h>
  7  #include <versionbits.h>
  8  
  9  ThresholdState AbstractThresholdConditionChecker::GetStateFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const
 10  {
 11      int nPeriod = Period(params);
 12      int nThreshold = Threshold(params);
 13      int min_activation_height = MinActivationHeight(params);
 14      int64_t nTimeStart = BeginTime(params);
 15      int64_t nTimeTimeout = EndTime(params);
 16  
 17      // Check if this deployment is always active.
 18      if (nTimeStart == Consensus::BIP9Deployment::ALWAYS_ACTIVE) {
 19          return ThresholdState::ACTIVE;
 20      }
 21  
 22      // Check if this deployment is never active.
 23      if (nTimeStart == Consensus::BIP9Deployment::NEVER_ACTIVE) {
 24          return ThresholdState::FAILED;
 25      }
 26  
 27      // 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.
 28      if (pindexPrev != nullptr) {
 29          pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod));
 30      }
 31  
 32      // Walk backwards in steps of nPeriod to find a pindexPrev whose information is known
 33      std::vector<const CBlockIndex*> vToCompute;
 34      while (cache.count(pindexPrev) == 0) {
 35          if (pindexPrev == nullptr) {
 36              // The genesis block is by definition defined.
 37              cache[pindexPrev] = ThresholdState::DEFINED;
 38              break;
 39          }
 40          if (pindexPrev->GetMedianTimePast() < nTimeStart) {
 41              // Optimization: don't recompute down further, as we know every earlier block will be before the start time
 42              cache[pindexPrev] = ThresholdState::DEFINED;
 43              break;
 44          }
 45          vToCompute.push_back(pindexPrev);
 46          pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
 47      }
 48  
 49      // At this point, cache[pindexPrev] is known
 50      assert(cache.count(pindexPrev));
 51      ThresholdState state = cache[pindexPrev];
 52  
 53      // Now walk forward and compute the state of descendants of pindexPrev
 54      while (!vToCompute.empty()) {
 55          ThresholdState stateNext = state;
 56          pindexPrev = vToCompute.back();
 57          vToCompute.pop_back();
 58  
 59          switch (state) {
 60              case ThresholdState::DEFINED: {
 61                  if (pindexPrev->GetMedianTimePast() >= nTimeStart) {
 62                      stateNext = ThresholdState::STARTED;
 63                  }
 64                  break;
 65              }
 66              case ThresholdState::STARTED: {
 67                  // We need to count
 68                  const CBlockIndex* pindexCount = pindexPrev;
 69                  int count = 0;
 70                  for (int i = 0; i < nPeriod; i++) {
 71                      if (Condition(pindexCount, params)) {
 72                          count++;
 73                      }
 74                      pindexCount = pindexCount->pprev;
 75                  }
 76                  if (count >= nThreshold) {
 77                      stateNext = ThresholdState::LOCKED_IN;
 78                  } else if (pindexPrev->GetMedianTimePast() >= nTimeTimeout) {
 79                      stateNext = ThresholdState::FAILED;
 80                  }
 81                  break;
 82              }
 83              case ThresholdState::LOCKED_IN: {
 84                  // Progresses into ACTIVE provided activation height will have been reached.
 85                  if (pindexPrev->nHeight + 1 >= min_activation_height) {
 86                      stateNext = ThresholdState::ACTIVE;
 87                  }
 88                  break;
 89              }
 90              case ThresholdState::FAILED:
 91              case ThresholdState::ACTIVE: {
 92                  // Nothing happens, these are terminal states.
 93                  break;
 94              }
 95          }
 96          cache[pindexPrev] = state = stateNext;
 97      }
 98  
 99      return state;
100  }
101  
102  BIP9Stats AbstractThresholdConditionChecker::GetStateStatisticsFor(const CBlockIndex* pindex, const Consensus::Params& params, std::vector<bool>* signalling_blocks) const
103  {
104      BIP9Stats stats = {};
105  
106      stats.period = Period(params);
107      stats.threshold = Threshold(params);
108  
109      if (pindex == nullptr) return stats;
110  
111      // Find how many blocks are in the current period
112      int blocks_in_period = 1 + (pindex->nHeight % stats.period);
113  
114      // Reset signalling_blocks
115      if (signalling_blocks) {
116          signalling_blocks->assign(blocks_in_period, false);
117      }
118  
119      // Count from current block to beginning of period
120      int elapsed = 0;
121      int count = 0;
122      const CBlockIndex* currentIndex = pindex;
123      do {
124          ++elapsed;
125          --blocks_in_period;
126          if (Condition(currentIndex, params)) {
127              ++count;
128              if (signalling_blocks) signalling_blocks->at(blocks_in_period) = true;
129          }
130          currentIndex = currentIndex->pprev;
131      } while(blocks_in_period > 0);
132  
133      stats.elapsed = elapsed;
134      stats.count = count;
135      stats.possible = (stats.period - stats.threshold ) >= (stats.elapsed - count);
136  
137      return stats;
138  }
139  
140  int AbstractThresholdConditionChecker::GetStateSinceHeightFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const
141  {
142      int64_t start_time = BeginTime(params);
143      if (start_time == Consensus::BIP9Deployment::ALWAYS_ACTIVE || start_time == Consensus::BIP9Deployment::NEVER_ACTIVE) {
144          return 0;
145      }
146  
147      const ThresholdState initialState = GetStateFor(pindexPrev, params, cache);
148  
149      // BIP 9 about state DEFINED: "The genesis block is by definition in this state for each deployment."
150      if (initialState == ThresholdState::DEFINED) {
151          return 0;
152      }
153  
154      const int nPeriod = Period(params);
155  
156      // 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.
157      // To ease understanding of the following height calculation, it helps to remember that
158      // right now pindexPrev points to the block prior to the block that we are computing for, thus:
159      // if we are computing for the last block of a period, then pindexPrev points to the second to last block of the period, and
160      // if we are computing for the first block of a period, then pindexPrev points to the last block of the previous period.
161      // The parent of the genesis block is represented by nullptr.
162      pindexPrev = Assert(pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod)));
163  
164      const CBlockIndex* previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
165  
166      while (previousPeriodParent != nullptr && GetStateFor(previousPeriodParent, params, cache) == initialState) {
167          pindexPrev = previousPeriodParent;
168          previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
169      }
170  
171      // Adjust the result because right now we point to the parent block.
172      return pindexPrev->nHeight + 1;
173  }
174  
175  namespace
176  {
177  /**
178   * Class to implement versionbits logic.
179   */
180  class VersionBitsConditionChecker : public AbstractThresholdConditionChecker {
181  private:
182      const Consensus::DeploymentPos id;
183  
184  protected:
185      int64_t BeginTime(const Consensus::Params& params) const override { return params.vDeployments[id].nStartTime; }
186      int64_t EndTime(const Consensus::Params& params) const override { return params.vDeployments[id].nTimeout; }
187      int MinActivationHeight(const Consensus::Params& params) const override { return params.vDeployments[id].min_activation_height; }
188      int Period(const Consensus::Params& params) const override { return params.nMinerConfirmationWindow; }
189      int Threshold(const Consensus::Params& params) const override { return params.nRuleChangeActivationThreshold; }
190  
191      bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const override
192      {
193          return (((pindex->nVersion & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (pindex->nVersion & Mask(params)) != 0);
194      }
195  
196  public:
197      explicit VersionBitsConditionChecker(Consensus::DeploymentPos id_) : id(id_) {}
198      uint32_t Mask(const Consensus::Params& params) const { return (uint32_t{1}) << params.vDeployments[id].bit; }
199  };
200  
201  } // namespace
202  
203  ThresholdState VersionBitsCache::State(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos)
204  {
205      LOCK(m_mutex);
206      return VersionBitsConditionChecker(pos).GetStateFor(pindexPrev, params, m_caches[pos]);
207  }
208  
209  BIP9Stats VersionBitsCache::Statistics(const CBlockIndex* pindex, const Consensus::Params& params, Consensus::DeploymentPos pos, std::vector<bool>* signalling_blocks)
210  {
211      return VersionBitsConditionChecker(pos).GetStateStatisticsFor(pindex, params, signalling_blocks);
212  }
213  
214  int VersionBitsCache::StateSinceHeight(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos)
215  {
216      LOCK(m_mutex);
217      return VersionBitsConditionChecker(pos).GetStateSinceHeightFor(pindexPrev, params, m_caches[pos]);
218  }
219  
220  uint32_t VersionBitsCache::Mask(const Consensus::Params& params, Consensus::DeploymentPos pos)
221  {
222      return VersionBitsConditionChecker(pos).Mask(params);
223  }
224  
225  int32_t VersionBitsCache::ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params)
226  {
227      LOCK(m_mutex);
228      int32_t nVersion = VERSIONBITS_TOP_BITS;
229  
230      for (int i = 0; i < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
231          Consensus::DeploymentPos pos = static_cast<Consensus::DeploymentPos>(i);
232          ThresholdState state = VersionBitsConditionChecker(pos).GetStateFor(pindexPrev, params, m_caches[pos]);
233          if (state == ThresholdState::LOCKED_IN || state == ThresholdState::STARTED) {
234              nVersion |= Mask(params, pos);
235          }
236      }
237  
238      return nVersion;
239  }
240  
241  void VersionBitsCache::Clear()
242  {
243      LOCK(m_mutex);
244      for (unsigned int d = 0; d < Consensus::MAX_VERSION_BITS_DEPLOYMENTS; d++) {
245          m_caches[d].clear();
246      }
247  }