Changeset 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 | ||||||||||||
Fabien: This comment is no longer accurate | ||||||||||||
* 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); | ||||||||||||
/** | ||||||||||||
* The split between the intereger and decimal part of x32 does not happen | ||||||||||||
FabienUnsubmitted Not Done Inline Actionsintereger => integer Fabien: `intereger` => `integer` | ||||||||||||
* like one might intuitively think using "regular math". This is because | ||||||||||||
* "computer math" differs in ways that might be subtle, but nevertheless | ||||||||||||
* are very important. The intereger part is *ALWAYS* rounded down. For | ||||||||||||
FabienUnsubmitted Not Done Inline ActionsDito Fabien: Dito | ||||||||||||
* instance, 0.3 is split as 0 + 0.3, which is intuitive. But -0.3 is split | ||||||||||||
* as -1 + 0.7 , which means we need to multiply by 2^-1 when x32 is | ||||||||||||
* negative. This is implemented as a right shift. | ||||||||||||
*/ | ||||||||||||
return (powTargetSpacing + (offsetTime32 >> 32)) >> (x32 < 0); | ||||||||||||
} | ||||||||||||
uint32_t deterministicExp2(const uint32_t n) { | ||||||||||||
jhoenickeUnsubmitted Not Done Inline ActionsCopy over the comment from the header file? Maybe also expand a bit. This function returns an approximation of 2^n - 1 in 32-bit fixed point notation. Thus the argument is is interpreted as the number (n/2^32) in the interval [0, 1[. The result is also in the interval [0, 1[ and scaled by 2^32. In other words, this function returns an approximation of (2^(n / 2^32) - 1) * 2^32. jhoenicke: Copy over the comment from the header file? Maybe also expand a bit.
This function returns… | ||||||||||||
/** | ||||||||||||
* 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]; | ||||||||||||
/** | ||||||||||||
* /!\ 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."); | ||||||||||||
// Scale x so that exp(xscaled) = 2^x, i.e. xscaled= x*ln(2). | ||||||||||||
const int64_t xscaled = (x * LN2_32) >> 32; | ||||||||||||
// Approximate exp(xscaled)-1 by the Taylor series x + x^2/2 (the right | ||||||||||||
// shift by 33 divides x^2 by 2). | ||||||||||||
const int64_t u = xscaled + ((xscaled * xscaled) >> 33); | ||||||||||||
// Multiply result by 1+k0. Note that we need to return (1+k0)*exp(xscaled) | ||||||||||||
jhoenickeUnsubmitted Not Done Inline Actions
nitpicking my own code :) Beware that this diff doesn't delete all old lines. Is there a way to do a proper multi-line diff in phabricator? jhoenicke: nitpicking my own code :)
It returns exactly the same value but is a tiny bit simpler.
Beware… | ||||||||||||
deadalnixAuthorUnsubmitted Done Inline ActionsWhile your proposal was very good, @markblundeberg ended up sending me something that is both simpler and more precise, that I'm working on integrating now. The progress made here is fantastic, thanks to you and Mark. deadalnix: While your proposal was very good, @markblundeberg ended up sending me something that is both… | ||||||||||||
// - 1 = (1+k0)*(exp(xscaled)-1) + k0 | ||||||||||||
return k0 + ((u * (k0 + POW2_32)) >> 32); | ||||||||||||
} | ||||||||||||
} // namespace grasberg |
This comment is no longer accurate