Bitcoin ABC  0.22.13
P2P Digital Currency
aserti32d.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 #include <pow/aserti32d.h>
5 
6 #include <chain.h>
7 #include <consensus/activation.h>
8 #include <consensus/params.h>
9 #include <validation.h> // ::ChainActive()
10 
11 #include <atomic>
12 
13 static std::atomic<const CBlockIndex *> cachedAnchor{nullptr};
14 
15 void ResetASERTAnchorBlockCache() noexcept {
16  cachedAnchor = nullptr;
17 }
18 
20  return cachedAnchor.load();
21 }
22 
39 static const CBlockIndex *GetASERTAnchorBlock(const CBlockIndex *const pindex,
40  const Consensus::Params &params) {
41  assert(pindex);
42 
43  // - We check if we have a cached result, and if we do and it is really the
44  // ancestor of pindex, then we return it.
45  //
46  // - If we do not or if the cached result is not the ancestor of pindex,
47  // then we proceed with the more expensive walk back to find the ASERT
48  // anchor block.
49  //
50  // CBlockIndex::GetAncestor() is reasonably efficient; it uses
51  // CBlockIndex::pskip Note that if pindex == cachedAnchor, GetAncestor()
52  // here will return cachedAnchor, which is what we want.
53  const CBlockIndex *lastCached = cachedAnchor.load();
54  if (lastCached && pindex->GetAncestor(lastCached->nHeight) == lastCached) {
55  return lastCached;
56  }
57 
58  // Slow path: walk back until we find the first ancestor for which
59  // IsAxionEnabled() == true.
60  const CBlockIndex *anchor = pindex;
61 
62  while (anchor->pprev) {
63  // first, skip backwards testing IsAxionEnabled
64  // The below code leverages CBlockIndex::pskip to walk back efficiently.
65  if (anchor->pskip && IsAxionEnabled(params, anchor->pskip)) {
66  // skip backward
67  anchor = anchor->pskip;
68  // continue skipping
69  continue;
70  }
71  // cannot skip here, walk back by 1
72  if (!IsAxionEnabled(params, anchor->pprev)) {
73  // found it -- highest block where Axion is not enabled is
74  // anchor->pprev, and anchor points to the first block for which
75  // IsAxionEnabled() == true
76  break;
77  }
78  anchor = anchor->pprev;
79  }
80 
81  // Overwrite the cache with the anchor we found. More likely than not, the
82  // next time we are asked to validate a header it will be part of same /
83  // similar chain, not some other unrelated chain with a totally different
84  // anchor.
85  cachedAnchor = anchor;
86 
87  return anchor;
88 }
89 
90 uint32_t GetNextASERTWorkRequired(const CBlockIndex *pindexPrev,
91  const CBlockHeader *pblock,
92  const Consensus::Params &params) noexcept {
93  return GetNextASERTWorkRequired(pindexPrev, pblock, params,
94  GetASERTAnchorBlock(pindexPrev, params));
95 }
96 
107 uint32_t
109  const CBlockHeader *pblock,
110  const Consensus::Params &params,
111  const CBlockIndex *pindexAnchorBlock) noexcept {
112  // This cannot handle the genesis block and early blocks in general.
113  assert(pindexPrev != nullptr);
114 
115  // Anchor block is the block on which all ASERT scheduling calculations are
116  // based. It too must exist, and it must have a valid parent.
117  assert(pindexAnchorBlock != nullptr);
118 
119  // We make no further assumptions other than the height of the prev block
120  // must be >= that of the anchor block.
121  assert(pindexPrev->nHeight >= pindexAnchorBlock->nHeight);
122 
123  const arith_uint256 powLimit = UintToArith256(params.powLimit);
124 
125  // Special difficulty rule for testnet
126  // If the new block's timestamp is more than 2* 10 minutes then allow
127  // mining of a min-difficulty block.
128  if (params.fPowAllowMinDifficultyBlocks &&
129  (pblock->GetBlockTime() >
130  pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing)) {
131  return UintToArith256(params.powLimit).GetCompact();
132  }
133 
134  // For nTimeDiff calculation, the timestamp of the parent to the anchor
135  // block is used, as per the absolute formulation of ASERT. This is somewhat
136  // counterintuitive since it is referred to as the anchor timestamp, but as
137  // per the formula the timestamp of block M-1 must be used if the anchor is
138  // M.
139  assert(pindexPrev->pprev != nullptr);
140  // Note: time difference is to parent of anchor block (or to anchor block
141  // itself iff anchor is genesis).
142  // (according to absolute formulation of ASERT)
143  const auto anchorTime = pindexAnchorBlock->pprev
144  ? pindexAnchorBlock->pprev->GetBlockTime()
145  : pindexAnchorBlock->GetBlockTime();
146  const int64_t nTimeDiff = pindexPrev->GetBlockTime() - anchorTime;
147  // Height difference is from current block to anchor block
148  const int64_t nHeightDiff =
149  pindexPrev->nHeight - pindexAnchorBlock->nHeight;
150  const arith_uint256 refBlockTarget =
151  arith_uint256().SetCompact(pindexAnchorBlock->nBits);
152  // Do the actual target adaptation calculation in separate
153  // CalculateASERT() function
154  arith_uint256 nextTarget =
155  CalculateASERT(refBlockTarget, params.nPowTargetSpacing, nTimeDiff,
156  nHeightDiff, powLimit, params.nDAAHalfLife);
157 
158  // CalculateASERT() already clamps to powLimit.
159  return nextTarget.GetCompact();
160 }
161 
162 // ASERT calculation function.
163 // Clamps to powLimit.
165  const int64_t nPowTargetSpacing,
166  const int64_t nTimeDiff, const int64_t nHeightDiff,
167  const arith_uint256 &powLimit,
168  const int64_t nHalfLife) noexcept {
169  // Input target must never be zero nor exceed powLimit.
170  assert(refTarget > 0 && refTarget <= powLimit);
171 
172  // We need some leading zero bits in powLimit in order to have room to
173  // handle overflows easily. 32 leading zero bits is more than enough.
174  assert((powLimit >> 224) == 0);
175 
176  // Height diff should NOT be negative.
177  assert(nHeightDiff >= 0);
178 
179  // It will be helpful when reading what follows, to remember that
180  // nextTarget is adapted from anchor block target value.
181 
182  // Ultimately, we want to approximate the following ASERT formula, using
183  // only integer (fixed-point) math:
184  // new_target = old_target * 2^((blocks_time - IDEAL_BLOCK_TIME *
185  // (height_diff + 1)) / nHalfLife)
186 
187  // First, we'll calculate the exponent:
188  assert(llabs(nTimeDiff - nPowTargetSpacing * nHeightDiff) <
189  (1ll << (63 - 16)));
190  const int64_t exponent =
191  ((nTimeDiff - nPowTargetSpacing * (nHeightDiff + 1)) * 65536) /
192  nHalfLife;
193 
194  // Next, we use the 2^x = 2 * 2^(x-1) identity to shift our exponent into
195  // the [0, 1) interval. The truncated exponent tells us how many shifts we
196  // need to do Note1: This needs to be a right shift. Right shift rounds
197  // downward (floored division),
198  // whereas integer division in C++ rounds towards zero (truncated
199  // division).
200  // Note2: This algorithm uses arithmetic shifts of negative numbers. This
201  // is unpecified but very common behavior for C++ compilers before
202  // C++20, and standard with C++20. We must check this behavior e.g.
203  // using static_assert.
204  static_assert(int64_t(-1) >> 1 == int64_t(-1),
205  "ASERT algorithm needs arithmetic shift support");
206 
207  // Now we compute an approximated target * 2^(exponent/65536.0)
208 
209  // First decompose exponent into 'integer' and 'fractional' parts:
210  int64_t shifts = exponent >> 16;
211  const auto frac = uint16_t(exponent);
212  assert(exponent == (shifts * 65536) + frac);
213 
214  // multiply target by 65536 * 2^(fractional part)
215  // 2^x ~= (1 + 0.695502049*x + 0.2262698*x**2 + 0.0782318*x**3) for 0 <= x <
216  // 1 Error versus actual 2^x is less than 0.013%.
217  const uint32_t factor =
218  65536 + ((+195766423245049ull * frac + 971821376ull * frac * frac +
219  5127ull * frac * frac * frac + (1ull << 47)) >>
220  48);
221  // this is always < 2^241 since refTarget < 2^224
222  arith_uint256 nextTarget = refTarget * factor;
223 
224  // multiply by 2^(integer part) / 65536
225  shifts -= 16;
226  if (shifts <= 0) {
227  nextTarget >>= -shifts;
228  } else {
229  // Detect overflow that would discard high bits
230  const auto nextTargetShifted = nextTarget << shifts;
231  if ((nextTargetShifted >> shifts) != nextTarget) {
232  // If we had wider integers, the final value of nextTarget would
233  // be >= 2^256 so it would have just ended up as powLimit anyway.
234  nextTarget = powLimit;
235  } else {
236  // Shifting produced no overflow, can assign value
237  nextTarget = nextTargetShifted;
238  }
239  }
240 
241  if (nextTarget == 0) {
242  // 0 is not a valid target, but 1 is.
243  nextTarget = arith_uint256(1);
244  } else if (nextTarget > powLimit) {
245  nextTarget = powLimit;
246  }
247 
248  // we return from only 1 place for copy elision
249  return nextTarget;
250 }
CBlockIndex * pskip
pointer to the index of some further predecessor of this block
Definition: blockindex.h:33
bool IsAxionEnabled(const Consensus::Params &params, const CBlockIndex *pindexPrev)
Check if November 15th, 2020 protocol upgrade has activated.
Definition: activation.cpp:78
uint32_t GetNextASERTWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *pblock, const Consensus::Params &params) noexcept
Definition: aserti32d.cpp:90
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: blockindex.h:30
arith_uint256 CalculateASERT(const arith_uint256 &refTarget, const int64_t nPowTargetSpacing, const int64_t nTimeDiff, const int64_t nHeightDiff, const arith_uint256 &powLimit, const int64_t nHalfLife) noexcept
Definition: aserti32d.cpp:164
uint32_t GetCompact(bool fNegative=false) const
static const CBlockIndex * GetASERTAnchorBlock(const CBlockIndex *const pindex, const Consensus::Params &params)
Returns a pointer to the anchor block used for ASERT.
Definition: aserti32d.cpp:39
arith_uint256 UintToArith256(const uint256 &a)
static std::atomic< const CBlockIndex * > cachedAnchor
Definition: aserti32d.cpp:13
const CBlockIndex * GetASERTAnchorBlockCache() noexcept
Definition: aserti32d.cpp:19
Parameters that influence chain consensus.
Definition: params.h:59
256-bit unsigned big integer.
The block chain is a tree shaped structure starting with the genesis block at the root...
Definition: blockindex.h:23
void ResetASERTAnchorBlockCache() noexcept
ASERT caches a special block index for efficiency.
Definition: aserti32d.cpp:15
arith_uint256 & SetCompact(uint32_t nCompact, bool *pfNegative=nullptr, bool *pfOverflow=nullptr)
The "compact" format is a representation of a whole number N using an unsigned 32bit number similar t...
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: blockindex.h:36
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: blockindex.cpp:71
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22