Bitcoin ABC  0.22.12
P2P Digital Currency
grasberg.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 
5 #include <pow/grasberg.h>
6 
7 #include <arith_uint256.h>
8 #include <chain.h>
9 #include <chainparams.h>
10 #include <consensus/params.h>
11 
12 using namespace grasberg;
13 
14 // 2^32 * ln(2) = 2977044471.82
15 static constexpr int64_t LN2_32 = 2977044472;
16 
17 static constexpr int64_t POW2_32 = int64_t(1) << 32;
18 
20  const CBlockIndex *pindexRef,
21  const CChainParams &params) {
22  const int64_t targetBlockTime = computeTargetBlockTime(pindexTip, params);
23  const int64_t expectedBlockTime = params.GetConsensus().nPowTargetSpacing;
24 
25  const int64_t refBlockTime = pindexRef->GetBlockTime();
26  const int64_t refBlockInterval =
27  (pindexRef->pprev == nullptr)
28  ? expectedBlockTime
29  : (refBlockTime - pindexRef->pprev->GetBlockTime());
30  const int64_t refInterval =
31  refBlockInterval + pindexTip->GetBlockTime() - refBlockTime;
32  const int64_t refIntervalSize = pindexTip->nHeight - pindexRef->nHeight;
33  const int64_t timeOffset =
34  refInterval - (targetBlockTime + refIntervalSize * expectedBlockTime);
35 
36  // Compute the adjustment factor.
37  const int64_t tau32 = 288 * expectedBlockTime * LN2_32;
38  const int64_t x32 = (timeOffset * POW2_32) / (tau32 >> 32);
39  const int32_t xi = x32 >> 32;
40  const uint32_t xd = x32 & uint32_t(-1);
41 
47  arith_uint256 lastBlockTarget;
48  lastBlockTarget.SetCompact(pindexRef->nBits);
49 
50  // Clip adjustment to avoid overflow.
51  if (xi >= 32) {
52  return lastBlockTarget << 32;
53  } else if (xi <= -32) {
54  return lastBlockTarget >> 32;
55  }
56 
57  const uint32_t e31 = (deterministicExp2(xd) >> 1) | (1u << 31);
58  return (lastBlockTarget * e31) >> (31 - xi);
59 }
60 
71 uint32_t GetNextGrasbergWorkRequired(const CBlockIndex *pindexPrev,
72  const CBlockHeader *pblock,
73  const CChainParams &chainParams) {
74  const Consensus::Params &params = chainParams.GetConsensus();
75  const CBlockIndex *pindexTip = pindexPrev;
76 
77  if (params.fPowAllowMinDifficultyBlocks) {
78  // Special difficulty rule for testnet:
79  // If the new block's timestamp is more than 2* 10 minutes then allow
80  // mining of a min-difficulty block.
81  if (pblock->GetBlockTime() >
82  pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing) {
83  return UintToArith256(params.powLimit).GetCompact();
84  }
85 
86  // Use the last non-special-min-difficulty-rules-block as a base to
87  // compute difficulty.
88  while (pindexPrev->pprev && (pindexPrev->GetBlockTime() >
89  pindexPrev->pprev->GetBlockTime() +
90  2 * params.nPowTargetSpacing)) {
91  pindexPrev = pindexPrev->pprev;
92  }
93  }
94 
95  const arith_uint256 nextTarget =
96  ComputeNextTarget(pindexTip, pindexPrev, chainParams);
97 
98  const arith_uint256 powLimit = UintToArith256(params.powLimit);
99  if (nextTarget > powLimit) {
100  return powLimit.GetCompact();
101  }
102 
103  return nextTarget.GetCompact();
104 }
105 
106 namespace grasberg {
107 
108 int64_t computeTargetBlockTime(const CBlockIndex *pindexPrev,
109  const CChainParams &chainParams) {
110  const Consensus::Params &params = chainParams.GetConsensus();
111 
112  const int64_t lastBlockTime = pindexPrev->GetBlockTime();
113  const int64_t powTargetSpacing = params.nPowTargetSpacing;
114  const int64_t expectedTime = pindexPrev->nHeight * powTargetSpacing +
115  chainParams.GenesisBlock().nTime;
116  const int64_t drift = expectedTime - lastBlockTime;
117 
118  const int64_t tau = params.nPowTargetTimespan;
119  const int64_t x32 = (drift * POW2_32) / tau;
120 
121  // 2^32 * ln2(675/600) = 729822323.967
122  static constexpr int64_t X_CLIP = 729822324;
123 
124  // We clip to ensure block time stay around 10 minutes in practice.
125  const uint32_t x = std::max(std::min(x32, X_CLIP), -X_CLIP);
126  const int64_t offsetTime32 = powTargetSpacing * deterministicExp2(x);
127 
137  return (powTargetSpacing + (offsetTime32 >> 32)) >> (x32 < 0);
138 }
139 
140 uint32_t deterministicExp2(const uint32_t n) {
145  const uint32_t bucket = n >> 30;
146 
155  const uint32_t x = n & 0x3fffffff;
156 
157  constexpr uint32_t scales[4] = {
158  // 2^31 * 2^(0/4) = 2147483648
159  2147483648,
160  // 2^31 * 2^(1/4) = 2553802833.55
161  2553802834,
162  // 2^31 * 2^(2/4) = 3037000499.98
163  3037000500,
164  // 2^31 * 2^(3/4) = 3611622602.84
165  3611622603,
166  };
167  const uint32_t scale = scales[bucket];
168 
169  // Compute quartic polynomial (((dx + c) * x + b) * x + a) * x, fitted to
170  // 2**x-1 for 0 <= x < 0.25
171  uint64_t P = 0;
172  P = ((P + 45037112) * x) >> 32;
173  P = ((P + 237575834) * x) >> 32;
174  P = ((P + 1031834945) * x) >> 32;
175  P = ((P + 2977042554) * x) >> 32;
176 
177  // Apply binning factor 2^(bucket/4)
178  return (((P + POW2_32) * scale) >> 31) - POW2_32;
179 }
180 
181 } // namespace grasberg
static constexpr int64_t POW2_32
Definition: grasberg.cpp:17
int64_t GetBlockTime() const
Definition: blockindex.h:160
int64_t nPowTargetTimespan
Definition: params.h:105
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: blockindex.h:30
int64_t computeTargetBlockTime(const CBlockIndex *pindexPrev, const CChainParams &chainParams)
Compute the block time we are aiming for.
Definition: grasberg.cpp:108
bool fPowAllowMinDifficultyBlocks
Definition: params.h:101
uint32_t deterministicExp2(const uint32_t n)
Computes exp2(n) = 2^32 * (2^(n/2^32) - 1)
Definition: grasberg.cpp:140
const CBlock & GenesisBlock() const
Definition: chainparams.h:64
CChainParams defines various tweakable parameters of a given instance of the Bitcoin system...
Definition: chainparams.h:47
uint32_t GetCompact(bool fNegative=false) const
uint32_t nTime
Definition: block.h:28
arith_uint256 UintToArith256(const uint256 &a)
uint256 powLimit
Proof of work parameters.
Definition: params.h:100
int64_t nPowTargetSpacing
Definition: params.h:104
Parameters that influence chain consensus.
Definition: params.h:59
int64_t GetBlockTime() const
Definition: block.h:59
static const uint8_t tau[]
Definition: chacha20.cpp:30
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
uint32_t GetNextGrasbergWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *pblock, const CChainParams &chainParams)
Compute the next required proof of work using a relative target based ASERT algorithm.
Definition: grasberg.cpp:71
static constexpr int64_t LN2_32
Definition: grasberg.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...
static arith_uint256 ComputeNextTarget(const CBlockIndex *pindexTip, const CBlockIndex *pindexRef, const CChainParams &params)
Definition: grasberg.cpp:19
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: blockindex.h:36
const Consensus::Params & GetConsensus() const
Definition: chainparams.h:59
uint32_t nBits
Definition: blockindex.h:82
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22