Bitcoin ABC  0.26.3
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/params.h>
8 
9 uint32_t GetNextASERTWorkRequired(const CBlockIndex *pindexPrev,
10  const CBlockHeader *pblock,
11  const Consensus::Params &params) noexcept {
13  pindexPrev, pblock, params,
14  pindexPrev->GetAncestor(params.axionHeight));
15 }
16 
27 uint32_t
29  const CBlockHeader *pblock,
30  const Consensus::Params &params,
31  const CBlockIndex *pindexAnchorBlock) noexcept {
32  // This cannot handle the genesis block and early blocks in general.
33  assert(pindexPrev != nullptr);
34 
35  // Anchor block is the block on which all ASERT scheduling calculations are
36  // based. It too must exist, and it must have a valid parent.
37  assert(pindexAnchorBlock != nullptr);
38 
39  // We make no further assumptions other than the height of the prev block
40  // must be >= that of the anchor block.
41  assert(pindexPrev->nHeight >= pindexAnchorBlock->nHeight);
42 
43  const arith_uint256 powLimit = UintToArith256(params.powLimit);
44 
45  // Special difficulty rule for testnet
46  // If the new block's timestamp is more than 2* 10 minutes then allow
47  // mining of a min-difficulty block.
48  if (params.fPowAllowMinDifficultyBlocks &&
49  (pblock->GetBlockTime() >
50  pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing)) {
51  return UintToArith256(params.powLimit).GetCompact();
52  }
53 
54  // For nTimeDiff calculation, the timestamp of the parent to the anchor
55  // block is used, as per the absolute formulation of ASERT. This is somewhat
56  // counterintuitive since it is referred to as the anchor timestamp, but as
57  // per the formula the timestamp of block M-1 must be used if the anchor is
58  // M.
59  assert(pindexPrev->pprev != nullptr);
60  // Note: time difference is to parent of anchor block (or to anchor block
61  // itself iff anchor is genesis).
62  // (according to absolute formulation of ASERT)
63  const auto anchorTime = pindexAnchorBlock->pprev
64  ? pindexAnchorBlock->pprev->GetBlockTime()
65  : pindexAnchorBlock->GetBlockTime();
66  const int64_t nTimeDiff = pindexPrev->GetBlockTime() - anchorTime;
67  // Height difference is from current block to anchor block
68  const int64_t nHeightDiff =
69  pindexPrev->nHeight - pindexAnchorBlock->nHeight;
70  const arith_uint256 refBlockTarget =
71  arith_uint256().SetCompact(pindexAnchorBlock->nBits);
72  // Do the actual target adaptation calculation in separate
73  // CalculateASERT() function
74  arith_uint256 nextTarget =
75  CalculateASERT(refBlockTarget, params.nPowTargetSpacing, nTimeDiff,
76  nHeightDiff, powLimit, params.nDAAHalfLife);
77 
78  // CalculateASERT() already clamps to powLimit.
79  return nextTarget.GetCompact();
80 }
81 
82 // ASERT calculation function.
83 // Clamps to powLimit.
85  const int64_t nPowTargetSpacing,
86  const int64_t nTimeDiff, const int64_t nHeightDiff,
87  const arith_uint256 &powLimit,
88  const int64_t nHalfLife) noexcept {
89  // Input target must never be zero nor exceed powLimit.
90  assert(refTarget > 0 && refTarget <= powLimit);
91 
92  // We need some leading zero bits in powLimit in order to have room to
93  // handle overflows easily. 32 leading zero bits is more than enough.
94  assert((powLimit >> 224) == 0);
95 
96  // Height diff should NOT be negative.
97  assert(nHeightDiff >= 0);
98 
99  // It will be helpful when reading what follows, to remember that
100  // nextTarget is adapted from anchor block target value.
101 
102  // Ultimately, we want to approximate the following ASERT formula, using
103  // only integer (fixed-point) math:
104  // new_target = old_target * 2^((blocks_time - IDEAL_BLOCK_TIME *
105  // (height_diff + 1)) / nHalfLife)
106 
107  // First, we'll calculate the exponent:
108  assert(llabs(nTimeDiff - nPowTargetSpacing * nHeightDiff) <
109  (1ll << (63 - 16)));
110  const int64_t exponent =
111  ((nTimeDiff - nPowTargetSpacing * (nHeightDiff + 1)) * 65536) /
112  nHalfLife;
113 
114  // Next, we use the 2^x = 2 * 2^(x-1) identity to shift our exponent into
115  // the [0, 1) interval. The truncated exponent tells us how many shifts we
116  // need to do Note1: This needs to be a right shift. Right shift rounds
117  // downward (floored division),
118  // whereas integer division in C++ rounds towards zero (truncated
119  // division).
120  // Note2: This algorithm uses arithmetic shifts of negative numbers. This
121  // is unpecified but very common behavior for C++ compilers before
122  // C++20, and standard with C++20. We must check this behavior e.g.
123  // using static_assert.
124  static_assert(int64_t(-1) >> 1 == int64_t(-1),
125  "ASERT algorithm needs arithmetic shift support");
126 
127  // Now we compute an approximated target * 2^(exponent/65536.0)
128 
129  // First decompose exponent into 'integer' and 'fractional' parts:
130  int64_t shifts = exponent >> 16;
131  const auto frac = uint16_t(exponent);
132  assert(exponent == (shifts * 65536) + frac);
133 
134  // multiply target by 65536 * 2^(fractional part)
135  // 2^x ~= (1 + 0.695502049*x + 0.2262698*x**2 + 0.0782318*x**3) for 0 <= x <
136  // 1 Error versus actual 2^x is less than 0.013%.
137  const uint32_t factor =
138  65536 + ((+195766423245049ull * frac + 971821376ull * frac * frac +
139  5127ull * frac * frac * frac + (1ull << 47)) >>
140  48);
141  // this is always < 2^241 since refTarget < 2^224
142  arith_uint256 nextTarget = refTarget * factor;
143 
144  // multiply by 2^(integer part) / 65536
145  shifts -= 16;
146  if (shifts <= 0) {
147  nextTarget >>= -shifts;
148  } else {
149  // Detect overflow that would discard high bits
150  const auto nextTargetShifted = nextTarget << shifts;
151  if ((nextTargetShifted >> shifts) != nextTarget) {
152  // If we had wider integers, the final value of nextTarget would
153  // be >= 2^256 so it would have just ended up as powLimit anyway.
154  nextTarget = powLimit;
155  } else {
156  // Shifting produced no overflow, can assign value
157  nextTarget = nextTargetShifted;
158  }
159  }
160 
161  if (nextTarget == 0) {
162  // 0 is not a valid target, but 1 is.
163  nextTarget = arith_uint256(1);
164  } else if (nextTarget > powLimit) {
165  nextTarget = powLimit;
166  }
167 
168  // we return from only 1 place for copy elision
169  return nextTarget;
170 }
arith_uint256 UintToArith256(const uint256 &a)
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:84
uint32_t GetNextASERTWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *pblock, const Consensus::Params &params) noexcept
Definition: aserti32d.cpp:9
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: blockindex.h:23
256-bit unsigned big integer.
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...
uint32_t GetCompact(bool fNegative=false) const
Parameters that influence chain consensus.
Definition: params.h:59
assert(!tx.IsCoinBase())