Changeset View
Changeset View
Standalone View
Standalone View
src/pow/grasberg.cpp
- This file was added.
// Copyright (c) 2020 The Bitcoin developers | |||||
// Distributed under the MIT software license, see the accompanying | |||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | |||||
#include <pow/grasberg.h> | |||||
#include <arith_uint256.h> | |||||
#include <chain.h> | |||||
#include <chainparams.h> | |||||
#include <consensus/params.h> | |||||
using namespace grasberg; | |||||
// 2^32 * ln(2) = 2977044471.82 | |||||
static constexpr int64_t LN2_32 = 2977044472; | |||||
static constexpr int64_t POW2_32 = int64_t(1) << 32; | |||||
static arith_uint256 ComputeNextTarget(const CBlockIndex *pindexTip, | |||||
const CBlockIndex *pindexRef, | |||||
const CChainParams ¶ms) { | |||||
const int64_t targetBlockTime = computeTargetBlockTime(pindexTip, params); | |||||
const int64_t expectedBlockTime = params.GetConsensus().nPowTargetSpacing; | |||||
const int64_t refBlockTime = pindexRef->GetBlockTime(); | |||||
const int64_t refBlockInterval = | |||||
(pindexRef->pprev == nullptr) | |||||
? expectedBlockTime | |||||
: (refBlockTime - pindexRef->pprev->GetBlockTime()); | |||||
const int64_t refInterval = | |||||
refBlockInterval + pindexTip->GetBlockTime() - refBlockTime; | |||||
const int64_t refIntervalSize = pindexTip->nHeight - pindexRef->nHeight; | |||||
const int64_t timeOffset = | |||||
refInterval - (targetBlockTime + refIntervalSize * expectedBlockTime); | |||||
// Compute the adjustment factor. | |||||
const int64_t tau32 = 288 * expectedBlockTime * LN2_32; | |||||
const int64_t x32 = (timeOffset * POW2_32) / (tau32 >> 32); | |||||
const int32_t xi = x32 >> 32; | |||||
const uint32_t xd = x32 & uint32_t(-1); | |||||
/** | |||||
* Even though the correct thing to do would be to add 1 to the target, and | |||||
* then remove 1 at the end, experimentation showed that the cases in which | |||||
* the results differ are vanishingly few and we therefore skip this step. | |||||
*/ | |||||
arith_uint256 lastBlockTarget; | |||||
lastBlockTarget.SetCompact(pindexRef->nBits); | |||||
// Clip adjustment to avoid overflow. | |||||
if (xi >= 32) { | |||||
return lastBlockTarget << 32; | |||||
} else if (xi <= -32) { | |||||
return lastBlockTarget >> 32; | |||||
} | |||||
const arith_uint256 offsetTarget32 = | |||||
lastBlockTarget * deterministicExp2(xd); | |||||
const arith_uint256 nextTarget = | |||||
xi < 0 ? (lastBlockTarget + (offsetTarget32 >> 32)) >> (-xi) | |||||
: (lastBlockTarget << xi) + (offsetTarget32 >> (32 - xi)); | |||||
return nextTarget; | |||||
} | |||||
/** | |||||
* Compute the next required proof of work using a reative work based ASERT | |||||
* algorithm. | |||||
* | |||||
* Because the relation between work and target is not an immediate inverse, | |||||
* this is actually the correct thing to do, even though the difference | |||||
* shouldn't be big enough to matter in practice most of the time. The algorithm | |||||
* uses a combination of lookup table and polynomial aproximation to compute the | |||||
* value of the exponential using exclusively integer operations. This removes | |||||
* any risk of consensus failure due to inconsistent rounding problems. | |||||
* | |||||
* This algorithm uses the relative formulation of ASERT in order to allow for | |||||
* activation at any point in time without complications. | |||||
* | |||||
* In addition, this algorithm contains a drift correction mechanism. While | |||||
* ASERT by itself drifts very little, the chain is already off schedule. | |||||
*/ | |||||
uint32_t GetNextGrasbergWorkRequired(const CBlockIndex *pindexPrev, | |||||
const CBlockHeader *pblock, | |||||
const CChainParams &chainParams) { | |||||
const Consensus::Params ¶ms = chainParams.GetConsensus(); | |||||
const CBlockIndex *pindexTip = pindexPrev; | |||||
if (params.fPowAllowMinDifficultyBlocks) { | |||||
// Special difficulty rule for testnet: | |||||
// If the new block's timestamp is more than 2* 10 minutes then allow | |||||
// mining of a min-difficulty block. | |||||
if (pblock->GetBlockTime() > | |||||
pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing) { | |||||
return UintToArith256(params.powLimit).GetCompact(); | |||||
} | |||||
// Use the last non-special-min-difficulty-rules-block as a base to | |||||
// compute difficulty. | |||||
while (pindexPrev->pprev && (pindexPrev->GetBlockTime() > | |||||
pindexPrev->pprev->GetBlockTime() + | |||||
2 * params.nPowTargetSpacing)) { | |||||
pindexPrev = pindexPrev->pprev; | |||||
} | |||||
} | |||||
const arith_uint256 nextTarget = | |||||
ComputeNextTarget(pindexTip, pindexPrev, chainParams); | |||||
const arith_uint256 powLimit = UintToArith256(params.powLimit); | |||||
if (nextTarget > powLimit) { | |||||
return powLimit.GetCompact(); | |||||
} | |||||
return nextTarget.GetCompact(); | |||||
} | |||||
namespace grasberg { | |||||
int64_t computeTargetBlockTime(const CBlockIndex *pindexPrev, | |||||
const CChainParams &chainParams) { | |||||
const Consensus::Params ¶ms = chainParams.GetConsensus(); | |||||
const int64_t lastBlockTime = pindexPrev->GetBlockTime(); | |||||
const int64_t powTargetSpacing = params.nPowTargetSpacing; | |||||
const int64_t expectedTime = pindexPrev->nHeight * powTargetSpacing + | |||||
chainParams.GenesisBlock().nTime; | |||||
const int64_t drift = expectedTime - lastBlockTime; | |||||
const int64_t tau = params.nPowTargetTimespan; | |||||
const int64_t x32 = (drift * POW2_32) / tau; | |||||
// 2^32 * ln2(675/600) = 729822323.967 | |||||
static constexpr int64_t X_CLIP = 729822324; | |||||
// We clip to ensure block time stay around 10 minutes in practice. | |||||
const uint32_t x = std::max(std::min(x32, X_CLIP), -X_CLIP); | |||||
const int64_t offsetTime32 = powTargetSpacing * deterministicExp2(x); | |||||
return (powTargetSpacing + (offsetTime32 >> 32)) >> (x32 < 0); | |||||
} | |||||
uint32_t deterministicExp2(const uint32_t n) { | |||||
/** | |||||
* Rescale the computation depending on n for better precision. | |||||
* We use the MSB to form 16 buckets. | |||||
*/ | |||||
const uint32_t bucket = n >> 28; | |||||
/** | |||||
* Rescale around the middle of the range via: | |||||
* exp2(n) = 2^32 * 2^(n/2^32) | |||||
* = 2^32 * 2^((n - d)/2^32 + d/2^32) | |||||
* = 2^32 * 2^(d/2^32) * 2^((n - d)/2^32) | |||||
* Using x = n - d: | |||||
* exp2(n) = 2^32 * 2^(d/2^32) * 2^(x/2^32) | |||||
*/ | |||||
const int64_t d = int64_t(2 * bucket + 1) << 27; | |||||
const int64_t x = n - d; | |||||
constexpr static uint32_t k0s[16] = { | |||||
// 2^32 * (2^(1/32) - 1) = 94047537.3451 | |||||
94047537, | |||||
// 2^32 * (2^(3/32) - 1) = 288365825.147 | |||||
288365825, | |||||
// 2^32 * (2^(5/32) - 1) = 491287318.545 | |||||
491287319, | |||||
// 2^32 * (2^(7/32) - 1) = 703192913.992 | |||||
703192914, | |||||
// 2^32 * (2^(9/32) - 1) = 924480371.666 | |||||
924480372, | |||||
// 2^32 * (2^(11/32) - 1) = 1155565062.10 | |||||
1155565062, | |||||
// 2^32 * (2^(13/32) - 1) = 1396880745.83 | |||||
1396880746, | |||||
// 2^32 * (2^(15/32) - 1) = 1648880387.65 | |||||
1648880388, | |||||
// 2^32 * (2^(17/32) - 1) = 1912037006.77 | |||||
1912037007, | |||||
// 2^32 * (2^(19/32) - 1) = 2186844564.80 | |||||
2186844565, | |||||
// 2^32 * (2^(21/32) - 1) = 2473818892.86 | |||||
2473818893, | |||||
// 2^32 * (2^(23/32) - 1) = 2773498659.88 | |||||
2773498660, | |||||
// 2^32 * (2^(25/32) - 1) = 3086446383.71 | |||||
3086446384, | |||||
// 2^32 * (2^(27/32) - 1) = 3413249486.97 | |||||
3413249487, | |||||
// 2^32 * (2^(29/32) - 1) = 3754521399.73 | |||||
3754521400, | |||||
// 2^32 * (2^(31/32) - 1) = 4110902710.89 | |||||
4110902711, | |||||
}; | |||||
const uint32_t k0 = k0s[bucket]; | |||||
constexpr int64_t k1s[16] = { | |||||
// 2^32 * ln(2) * 2^(1/32) = 3042233257.17 | |||||
3042233257, | |||||
// 2^32 * ln(2) * 2^(3/32) = 3176924430.49 | |||||
3176924430, | |||||
// 2^32 * ln(2) * 2^(5/32) = 3317578891.51 | |||||
3317578892, | |||||
// 2^32 * ln(2) * 2^(7/32) = 3464460657.54 | |||||
3464460658, | |||||
// 2^32 * ln(2) * 2^(9/32) = 3617845434.92 | |||||
3617845435, | |||||
// 2^32 * ln(2) * 2^(11/32) = 3778021136.56 | |||||
3778021137, | |||||
// 2^32 * ln(2) * 2^(13/32) = 3945288422.37 | |||||
3945288422, | |||||
// 2^32 * ln(2) * 2^(15/32) = 4119961263.60 | |||||
4119961264, | |||||
// 2^32 * ln(2) * 2^(17/32) = 4302367532.19 | |||||
4302367532, | |||||
// 2^32 * ln(2) * 2^(19/32) = 4492849616.23 | |||||
4492849616, | |||||
// 2^32 * ln(2) * 2^(21/32) = 4691765062.62 | |||||
4691765063, | |||||
// 2^32 * ln(2) * 2^(23/32) = 4899487248.21 | |||||
4899487248, | |||||
// 2^32 * ln(2) * 2^(25/32) = 5116406080.64 | |||||
5116406081, | |||||
// 2^32 * ln(2) * 2^(27/32) = 5342928730.26 | |||||
5342928730, | |||||
// 2^32 * ln(2) * 2^(29/32) = 5579480394.39 | |||||
5579480394, | |||||
// 2^32 * ln(2) * 2^(31/32) = 5826505095.43 | |||||
5826505095, | |||||
}; | |||||
const int64_t k1 = k1s[bucket]; | |||||
/** | |||||
* /!\ C++ right shift signedness handling is implementation defined. It is | |||||
* defined as an arithmetic on all the platform we support, but this | |||||
* may not be the case on other platforms. | |||||
* | |||||
* NB: C++20 defines signed right shift as being arithmetic shifts, so in | |||||
* practice, we should see all platforms converge toward that behavior if | |||||
* they haven't already. | |||||
*/ | |||||
static_assert( | |||||
(int64_t(-1) >> 1) == int64_t(-1), | |||||
"deterministicExp2 require a compiler using arithmetic right shift."); | |||||
/** | |||||
* Now we aproximate the result using a taylor series. | |||||
*/ | |||||
const int64_t u0 = k0; | |||||
const int64_t u1_31 = (x * k1) >> 1; | |||||
const int64_t u2_31 = (((x * LN2_32) >> 32) * ((x * k1) >> 32)) >> 2; | |||||
return u0 + ((u1_31 + u2_31) >> 31); | |||||
} | |||||
} // namespace grasberg |