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> | |||||
#include <pow/util.h> | |||||
using namespace grasberg; | |||||
bvk: In the interest of catching any potential issues/bugs upfront, I am pasting Johnathan Toomim's… | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsThanks. The accumulation problem is fixed thanks to the drift correction mechanism so it is not a concern here. The clipping is limited to multiplying or dividing the difficulty by 4B, which you don't expect tot ever hit in practice - you'd literally have to go 2 month without blocks. The clipping is required to avoid overflow. Without it, it is possible to jack up the difficulty so high it actually gets lower. deadalnix: Thanks.
The accumulation problem is fixed thanks to the drift correction mechanism so it is… | |||||
// 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 ComputeNextWork(const CBlockIndex *pindexPrev, | |||||
const CChainParams ¶ms) { | |||||
const int64_t targetBlockTime = computeTargetBlockTime(pindexPrev, params); | |||||
const int64_t expectedBlockTime = params.GetConsensus().nPowTargetSpacing; | |||||
const int64_t lastBlockTime = | |||||
(pindexPrev->pprev == nullptr) | |||||
? expectedBlockTime | |||||
: (pindexPrev->GetBlockTime() - pindexPrev->pprev->GetBlockTime()); | |||||
const int64_t timeOffset = targetBlockTime - lastBlockTime; | |||||
// Compute the adjustement 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); | |||||
const arith_uint256 lastBlockWork = | |||||
(pindexPrev->pprev == nullptr) | |||||
? pindexPrev->nChainWork | |||||
: (pindexPrev->nChainWork - pindexPrev->pprev->nChainWork); | |||||
// Clip adjustement to avoid overflow. | |||||
if (xi >= 32) { | |||||
return lastBlockWork << 32; | |||||
} else if (xi <= -32) { | |||||
return lastBlockWork >> 32; | |||||
} | |||||
const arith_uint256 offsetWork32 = lastBlockWork * deterministicExp2(xd); | |||||
const arith_uint256 nextWork = | |||||
xi < 0 ? (lastBlockWork + (offsetWork32 >> 32)) >> (-xi) | |||||
: (lastBlockWork << xi) + (offsetWork32 >> (32 - xi)); | |||||
return nextWork; | |||||
} | |||||
/** | |||||
* Compute the next required proof of work using a reative work based ASERT | |||||
MengerianUnsubmitted Not Done Inline Actionsreative -> relative Mengerian: reative -> relative | |||||
* 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 | |||||
MengerianUnsubmitted Not Done Inline Actionsaproximation -> approximation Mengerian: aproximation -> approximation | |||||
* 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(); | |||||
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 nextWork = ComputeNextWork(pindexPrev, chainParams); | |||||
const arith_uint256 nextTarget = ComputeTargetFromWork(nextWork); | |||||
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(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]; | |||||
/** | |||||
* Now we aproximate the result using a taylor serie. | |||||
bvkUnsubmitted Not Done Inline Actionss/serie/series/ bvk: s/serie/series/
| |||||
* | |||||
* /!\ C++ right shift signedness handling is implementation defined. It is | |||||
* defined as an arithmetic on all the plateform we support, but this | |||||
bvkUnsubmitted Not Done Inline Actionss/plateform/platform/ bvk: s/plateform/platform/
| |||||
* may not be the case on other plateforms. It is paramount to run the | |||||
* test suite to ensure this is the case if you want to use this on | |||||
* another plateform. | |||||
* | |||||
* NB: C++20 defines signed right shift as being arithmetic shifts, so in | |||||
* practice, we should see all plateforms converge toward that behavior if | |||||
bvkUnsubmitted Not Done Inline Actionss/plateforms/platforms/ bvk: s/plateforms/platforms/ | |||||
* they haven't already. | |||||
*/ | |||||
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 |
In the interest of catching any potential issues/bugs upfront, I am pasting Johnathan Toomim's comment on reddit in here. It sounded like there could be a few issues (I am not sure):
u/jtoomim says:
His version uses a relative definition (which is susceptible to the accumulation of approximation error, and which requires clients to examine at least one more block header when computing the difficulty), and attempts to negate historical drift. His version also uses chainwork, which seems unnecessary, and maybe a bit superstitious. It also includes clipping, which is risky, as it can allow for infinite block attacks if done poorly.