1 // Copyright (c) 2016-2022 The Limenka 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 // NOLINTBEGIN(misc-no-recursion)
10 ThresholdState AbstractThresholdConditionChecker::GetStateFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const
11 {
12 int nPeriod = Period(params);
13 int nThreshold = Threshold(params);
14 int min_activation_height = MinActivationHeight(params);
15 int max_activation_height = MaxActivationHeight(params);
16 int active_duration = ActiveDuration(params);
17 int64_t nTimeStart = BeginTime(params);
18 int64_t nTimeTimeout = EndTime(params);
19 20 // Check if this deployment is always active.
21 if (nTimeStart == Consensus::BIP9Deployment::ALWAYS_ACTIVE) {
22 return ThresholdState::ACTIVE;
23 }
24 25 // Check if this deployment is never active.
26 if (nTimeStart == Consensus::BIP9Deployment::NEVER_ACTIVE) {
27 return ThresholdState::FAILED;
28 }
29 30 // 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.
31 if (pindexPrev != nullptr) {
32 pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod));
33 }
34 35 // Walk backwards in steps of nPeriod to find a pindexPrev whose information is known
36 std::vector<const CBlockIndex*> vToCompute;
37 while (cache.count(pindexPrev) == 0) {
38 if (pindexPrev == nullptr) {
39 // The genesis block is by definition defined.
40 cache[pindexPrev] = ThresholdState::DEFINED;
41 break;
42 }
43 if (pindexPrev->GetMedianTimePast() < nTimeStart) {
44 // Optimization: don't recompute down further, as we know every earlier block will be before the start time
45 cache[pindexPrev] = ThresholdState::DEFINED;
46 break;
47 }
48 vToCompute.push_back(pindexPrev);
49 pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
50 }
51 52 // At this point, cache[pindexPrev] is known
53 assert(cache.count(pindexPrev));
54 ThresholdState state = cache[pindexPrev];
55 56 // Everything is already cached. Return immediately.
57 if (vToCompute.empty()) {
58 return state;
59 }
60 61 // For temporary deployments, we need to know when ACTIVE started to determine the
62 // ACTIVE -> EXPIRED transition. We get this by calling GetStateSinceHeightFor, which
63 // internally calls GetStateFor on earlier periods. Those calls could recurse back here
64 // and call GetStateSinceHeightFor again, but the early return above prevents this:
65 // the walk-back above guarantees all periods before pindexPrev are already cached,
66 // and GetStateSinceHeightFor only walks backwards, so its GetStateFor calls always hit
67 // the cache, have empty vToCompute, and return immediately via the early return.
68 int activation_height = 0;
69 if (state == ThresholdState::ACTIVE && active_duration < std::numeric_limits<int>::max()) {
70 activation_height = GetStateSinceHeightFor(pindexPrev, params, cache);
71 }
72 73 // Now walk forward and compute the state of descendants of pindexPrev
74 while (!vToCompute.empty()) {
75 ThresholdState stateNext = state;
76 pindexPrev = vToCompute.back();
77 vToCompute.pop_back();
78 79 switch (state) {
80 case ThresholdState::DEFINED: {
81 if (pindexPrev->GetMedianTimePast() >= nTimeStart) {
82 stateNext = ThresholdState::STARTED;
83 }
84 break;
85 }
86 case ThresholdState::STARTED: {
87 // We need to count
88 const CBlockIndex* pindexCount = pindexPrev;
89 int count = 0;
90 for (int i = 0; i < nPeriod; i++) {
91 if (Condition(pindexCount, params)) {
92 count++;
93 }
94 pindexCount = pindexCount->pprev;
95 }
96 if (count >= nThreshold) {
97 // Normal BIP9 activation via signaling
98 stateNext = ThresholdState::LOCKED_IN;
99 } else if (max_activation_height < std::numeric_limits<int>::max() && pindexPrev->nHeight + 1 >= max_activation_height - nPeriod) {
100 // Force LOCKED_IN one period before max_activation_height
101 // This ensures activation happens AT max_activation_height (not one period later)
102 // Overrides timeout to guarantee activation
103 stateNext = ThresholdState::LOCKED_IN;
104 } else if (pindexPrev->GetMedianTimePast() >= nTimeTimeout) {
105 // Timeout without activation
106 stateNext = ThresholdState::FAILED;
107 }
108 break;
109 }
110 case ThresholdState::LOCKED_IN: {
111 // Progresses into ACTIVE provided activation height will have been reached.
112 if (pindexPrev->nHeight + 1 >= min_activation_height) {
113 stateNext = ThresholdState::ACTIVE;
114 if (active_duration < std::numeric_limits<int>::max()) {
115 activation_height = pindexPrev->nHeight + 1;
116 }
117 }
118 break;
119 }
120 case ThresholdState::ACTIVE: {
121 if (active_duration < std::numeric_limits<int>::max() &&
122 pindexPrev->nHeight + 1 >= activation_height + active_duration) {
123 stateNext = ThresholdState::EXPIRED;
124 }
125 break;
126 }
127 case ThresholdState::FAILED:
128 case ThresholdState::EXPIRED: {
129 // Nothing happens, these are terminal states.
130 break;
131 }
132 }
133 cache[pindexPrev] = state = stateNext;
134 }
135 136 return state;
137 }
138 // NOLINTEND(misc-no-recursion)
139 140 BIP9Stats AbstractThresholdConditionChecker::GetStateStatisticsFor(const CBlockIndex* pindex, const Consensus::Params& params, std::vector<bool>* signalling_blocks) const
141 {
142 BIP9Stats stats = {};
143 144 stats.period = Period(params);
145 stats.threshold = Threshold(params);
146 147 if (pindex == nullptr) return stats;
148 149 // Find how many blocks are in the current period
150 int blocks_in_period = 1 + (pindex->nHeight % stats.period);
151 152 // Reset signalling_blocks
153 if (signalling_blocks) {
154 signalling_blocks->assign(blocks_in_period, false);
155 }
156 157 // Count from current block to beginning of period
158 int elapsed = 0;
159 int count = 0;
160 const CBlockIndex* currentIndex = pindex;
161 do {
162 ++elapsed;
163 --blocks_in_period;
164 if (Condition(currentIndex, params)) {
165 ++count;
166 if (signalling_blocks) signalling_blocks->at(blocks_in_period) = true;
167 }
168 currentIndex = currentIndex->pprev;
169 } while(blocks_in_period > 0);
170 171 stats.elapsed = elapsed;
172 stats.count = count;
173 stats.possible = (stats.period - stats.threshold ) >= (stats.elapsed - count);
174 175 return stats;
176 }
177 178 // WARNING: This function is called from GetStateFor and calls GetStateFor in turn.
179 // The recursion is safe because this function calls GetStateFor first (which populates
180 // the cache), then only walks BACKWARDS through periods that are now cached. GetStateFor
181 // returns immediately for cached entries (via the early return when vToCompute is empty).
182 // If the backwards walk is ever changed to query uncached periods, infinite recursion
183 // will result.
184 // NOLINTBEGIN(misc-no-recursion)
185 int AbstractThresholdConditionChecker::GetStateSinceHeightFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const
186 {
187 int64_t start_time = BeginTime(params);
188 if (start_time == Consensus::BIP9Deployment::ALWAYS_ACTIVE || start_time == Consensus::BIP9Deployment::NEVER_ACTIVE) {
189 return 0;
190 }
191 192 const ThresholdState initialState = GetStateFor(pindexPrev, params, cache);
193 194 // BIP 9 about state DEFINED: "The genesis block is by definition in this state for each deployment."
195 if (initialState == ThresholdState::DEFINED) {
196 return 0;
197 }
198 199 const int nPeriod = Period(params);
200 201 // 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.
202 // To ease understanding of the following height calculation, it helps to remember that
203 // right now pindexPrev points to the block prior to the block that we are computing for, thus:
204 // if we are computing for the last block of a period, then pindexPrev points to the second to last block of the period, and
205 // if we are computing for the first block of a period, then pindexPrev points to the last block of the previous period.
206 // The parent of the genesis block is represented by nullptr.
207 pindexPrev = Assert(pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod)));
208 209 const CBlockIndex* previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
210 211 while (previousPeriodParent != nullptr && GetStateFor(previousPeriodParent, params, cache) == initialState) {
212 pindexPrev = previousPeriodParent;
213 previousPeriodParent = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
214 }
215 216 // Adjust the result because right now we point to the parent block.
217 return pindexPrev->nHeight + 1;
218 }
219 // NOLINTEND(misc-no-recursion)
220 221 namespace
222 {
223 /**
224 * Class to implement versionbits logic.
225 */
226 class VersionBitsConditionChecker : public AbstractThresholdConditionChecker {
227 private:
228 const Consensus::DeploymentPos id;
229 230 protected:
231 int64_t BeginTime(const Consensus::Params& params) const override { return params.vDeployments[id].nStartTime; }
232 int64_t EndTime(const Consensus::Params& params) const override { return params.vDeployments[id].nTimeout; }
233 int MinActivationHeight(const Consensus::Params& params) const override { return params.vDeployments[id].min_activation_height; }
234 int MaxActivationHeight(const Consensus::Params& params) const override { return params.vDeployments[id].max_activation_height; }
235 int ActiveDuration(const Consensus::Params& params) const override { return params.vDeployments[id].active_duration; }
236 int Period(const Consensus::Params& params) const override { return params.nMinerConfirmationWindow; }
237 int Threshold(const Consensus::Params& params) const override {
238 // Use per-deployment threshold if set, otherwise fall back to global
239 int deploymentThreshold = params.vDeployments[id].threshold;
240 return deploymentThreshold > 0 ? deploymentThreshold : params.nRuleChangeActivationThreshold;
241 }
242 243 bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const override
244 {
245 return (((pindex->nVersion & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (pindex->nVersion & Mask(params)) != 0);
246 }
247 248 public:
249 explicit VersionBitsConditionChecker(Consensus::DeploymentPos id_) : id(id_) {}
250 uint32_t Mask(const Consensus::Params& params) const { return (uint32_t{1}) << params.vDeployments[id].bit; }
251 };
252 253 } // namespace
254 255 ThresholdState VersionBitsCache::State(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos)
256 {
257 LOCK(m_mutex);
258 return VersionBitsConditionChecker(pos).GetStateFor(pindexPrev, params, m_caches[pos]);
259 }
260 261 BIP9Stats VersionBitsCache::Statistics(const CBlockIndex* pindex, const Consensus::Params& params, Consensus::DeploymentPos pos, std::vector<bool>* signalling_blocks)
262 {
263 return VersionBitsConditionChecker(pos).GetStateStatisticsFor(pindex, params, signalling_blocks);
264 }
265 266 int VersionBitsCache::StateSinceHeight(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos)
267 {
268 LOCK(m_mutex);
269 return VersionBitsConditionChecker(pos).GetStateSinceHeightFor(pindexPrev, params, m_caches[pos]);
270 }
271 272 uint32_t VersionBitsCache::Mask(const Consensus::Params& params, Consensus::DeploymentPos pos)
273 {
274 return VersionBitsConditionChecker(pos).Mask(params);
275 }
276 277 int32_t VersionBitsCache::ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params)
278 {
279 LOCK(m_mutex);
280 int32_t nVersion = VERSIONBITS_TOP_BITS;
281 282 for (int i = 0; i < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
283 Consensus::DeploymentPos pos = static_cast<Consensus::DeploymentPos>(i);
284 ThresholdState state = VersionBitsConditionChecker(pos).GetStateFor(pindexPrev, params, m_caches[pos]);
285 if (state == ThresholdState::LOCKED_IN || state == ThresholdState::STARTED) {
286 nVersion |= Mask(params, pos);
287 }
288 }
289 290 return nVersion;
291 }
292 293 void VersionBitsCache::Clear()
294 {
295 LOCK(m_mutex);
296 for (unsigned int d = 0; d < Consensus::MAX_VERSION_BITS_DEPLOYMENTS; d++) {
297 m_caches[d].clear();
298 }
299 }
300