tomFlowee
0a2e552168
This introduces a new BlockHeader helper class which Block and MutableBlock can both produce, which helps a lot of methods to be ported to no longer be dependent on us using a MutableBlock object, which is too costly to use when we have no intention to alter the block.
456 lines
17 KiB
C++
456 lines
17 KiB
C++
/*
|
|
* This file is part of the Flowee project
|
|
* Copyright (c) 2009-2010 Satoshi Nakamoto
|
|
* Copyright (c) 2009-2015 The Bitcoin Core developers
|
|
* Copyright (c) 2017-2020 The Bitcoin developers
|
|
* Copyright (c) 2017,2020 Tom Zander <tom@flowee.org>
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#include "pow.h"
|
|
#include <Application.h>
|
|
|
|
#include "arith_uint256.h"
|
|
#include "chain.h"
|
|
#include "primitives/BlockHeader.h"
|
|
#include "primitives/MutableBlock.h"
|
|
#include "uint256.h"
|
|
#include "util.h"
|
|
|
|
#include <atomic>
|
|
|
|
static std::atomic<const CBlockIndex*> cachedAnchor{nullptr};
|
|
|
|
void ResetASERTAnchorBlockCache()
|
|
{
|
|
cachedAnchor.store(nullptr);
|
|
}
|
|
|
|
namespace {
|
|
/**
|
|
* Compute the next required proof of work using the legacy Satoshi Difficulty adjustment + Emergency Difficulty Adjustment (EDA).
|
|
*/
|
|
uint32_t GetNextEDAWorkRequired(const CBlockIndex *pindexPrev, const BlockHeader &header, const Consensus::Params ¶ms)
|
|
{
|
|
// Only change once per difficulty adjustment interval
|
|
uint32_t nHeight = pindexPrev->nHeight + 1;
|
|
if (nHeight % params.DifficultyAdjustmentInterval() == 0) {
|
|
// Go back by what we want to be 14 days worth of blocks
|
|
assert(nHeight >= params.DifficultyAdjustmentInterval());
|
|
uint32_t nHeightFirst = nHeight - params.DifficultyAdjustmentInterval();
|
|
const CBlockIndex *pindexFirst = pindexPrev->GetAncestor(nHeightFirst);
|
|
assert(pindexFirst);
|
|
|
|
return Calculate2016NextWorkRequired(pindexPrev, pindexFirst->GetBlockTime(), params);
|
|
}
|
|
|
|
const uint32_t nProofOfWorkLimit = UintToArith256(params.powLimit).GetCompact();
|
|
|
|
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 (header.blockTime() > pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing) {
|
|
return nProofOfWorkLimit;
|
|
}
|
|
|
|
// Return the last non-special-min-difficulty-rules-block
|
|
const CBlockIndex *pindex = pindexPrev;
|
|
while (pindex->pprev && pindex->nHeight % params.DifficultyAdjustmentInterval() != 0 && pindex->nBits == nProofOfWorkLimit) {
|
|
pindex = pindex->pprev;
|
|
}
|
|
|
|
return pindex->nBits;
|
|
}
|
|
|
|
// We can't go below the minimum, so bail early.
|
|
uint32_t nBits = pindexPrev->nBits;
|
|
if (nBits == nProofOfWorkLimit)
|
|
return nProofOfWorkLimit;
|
|
|
|
// If producing the last 6 blocks took less than 12h, we keep the same
|
|
// difficulty.
|
|
const CBlockIndex *pindex6 = pindexPrev->GetAncestor(nHeight - 7);
|
|
assert(pindex6);
|
|
int64_t mtp6blocks = pindexPrev->GetMedianTimePast() - pindex6->GetMedianTimePast();
|
|
if (mtp6blocks < 12 * 3600)
|
|
return nBits;
|
|
|
|
// If producing the last 6 blocks took more than 12h, increase the
|
|
// difficulty target by 1/4 (which reduces the difficulty by 20%).
|
|
// This ensures that the chain does not get stuck in case we lose
|
|
// hashrate abruptly.
|
|
arith_uint256 nPow;
|
|
nPow.SetCompact(nBits);
|
|
nPow += (nPow >> 2);
|
|
|
|
// Make sure we do not go below allowed values.
|
|
const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
|
|
if (nPow > bnPowLimit)
|
|
nPow = bnPowLimit;
|
|
|
|
return nPow.GetCompact();
|
|
}
|
|
|
|
/**
|
|
* Compute a target based on the work done between 2 blocks and the time
|
|
* required to produce that work.
|
|
*/
|
|
arith_uint256 ComputeTarget(const CBlockIndex *pindexFirst, const CBlockIndex *pindexLast, const Consensus::Params ¶ms)
|
|
{
|
|
assert(pindexLast->nHeight > pindexFirst->nHeight);
|
|
|
|
/**
|
|
* From the total work done and the time it took to produce that much work,
|
|
* we can deduce how much work we expect to be produced in the targeted time
|
|
* between blocks.
|
|
*/
|
|
arith_uint256 work = pindexLast->nChainWork - pindexFirst->nChainWork;
|
|
work *= params.nPowTargetSpacing;
|
|
|
|
// In order to avoid difficulty cliffs, we bound the amplitude of the
|
|
// adjustment we are going to do to a factor in [0.5, 2].
|
|
int64_t nActualTimespan =
|
|
int64_t(pindexLast->nTime) - int64_t(pindexFirst->nTime);
|
|
if (nActualTimespan > 288 * params.nPowTargetSpacing) {
|
|
nActualTimespan = 288 * params.nPowTargetSpacing;
|
|
} else if (nActualTimespan < 72 * params.nPowTargetSpacing) {
|
|
nActualTimespan = 72 * params.nPowTargetSpacing;
|
|
}
|
|
|
|
work /= nActualTimespan;
|
|
|
|
/**
|
|
* We need to compute T = (2^256 / W) - 1 but 2^256 doesn't fit in 256 bits.
|
|
* By expressing 1 as W / W, we get (2^256 - W) / W, and we can compute
|
|
* 2^256 - W as the complement of W.
|
|
*/
|
|
return (-work) / work;
|
|
}
|
|
|
|
const CBlockIndex *GetASERTAnchorBlock(const CBlockIndex *const pindex, const Consensus::Params ¶ms)
|
|
{
|
|
assert(pindex);
|
|
const CBlockIndex *cached = cachedAnchor.load();
|
|
if (cached)
|
|
return cached;
|
|
assert(params.hf202011Height > 0);
|
|
const CBlockIndex *anchor = pindex->GetAncestor(params.hf202011Height - 1);
|
|
cachedAnchor.compare_exchange_strong(cached, anchor);
|
|
return anchor;
|
|
}
|
|
|
|
}
|
|
|
|
|
|
/**
|
|
* To reduce the impact of timestamp manipulation, we select the block we are
|
|
* basing our computation on via a median of 3.
|
|
*/
|
|
const CBlockIndex *GetSuitableBlock(const CBlockIndex *pindex)
|
|
{
|
|
assert(pindex->nHeight >= 3);
|
|
|
|
/**
|
|
* In order to avoid a block with a very skewed timestamp having too much
|
|
* influence, we select the median of the 3 top most blocks as a starting
|
|
* point.
|
|
*/
|
|
const CBlockIndex *blocks[3];
|
|
blocks[2] = pindex;
|
|
blocks[1] = pindex->pprev;
|
|
blocks[0] = blocks[1]->pprev;
|
|
|
|
// Sorting network.
|
|
if (blocks[0]->nTime > blocks[2]->nTime) {
|
|
std::swap(blocks[0], blocks[2]);
|
|
}
|
|
|
|
if (blocks[0]->nTime > blocks[1]->nTime) {
|
|
std::swap(blocks[0], blocks[1]);
|
|
}
|
|
|
|
if (blocks[1]->nTime > blocks[2]->nTime) {
|
|
std::swap(blocks[1], blocks[2]);
|
|
}
|
|
|
|
// We should have our candidate in the middle now.
|
|
return blocks[1];
|
|
}
|
|
|
|
uint32_t CalculateNextWorkRequired(const CBlockIndex *pindexPrev, const BlockHeader &header, const Consensus::Params ¶ms)
|
|
{
|
|
assert (pindexPrev); // Genesis block not allowed.
|
|
|
|
// Special rule for regtest: we never retarget.
|
|
if (params.fPowNoRetargeting)
|
|
return pindexPrev->nBits;
|
|
|
|
if (pindexPrev->nHeight >= params.hf201711Height) {
|
|
if (pindexPrev->nHeight + 1 >= params.hf202011Height)
|
|
return CalculateNextASERTWorkRequired(pindexPrev, header, params,
|
|
GetASERTAnchorBlock(pindexPrev, params));
|
|
// then the 3 year period of cw144
|
|
return CalculateNextCW144WorkRequired(pindexPrev, header, params);
|
|
}
|
|
|
|
// the couple of months of the emergency difficulty adjustment algo
|
|
return GetNextEDAWorkRequired(pindexPrev, header, params);
|
|
}
|
|
|
|
uint32_t CalculateNextASERTWorkRequired(const CBlockIndex *pindexPrev,
|
|
const BlockHeader &header,
|
|
const Consensus::Params ¶ms,
|
|
const CBlockIndex *pindexAnchorBlock)
|
|
{
|
|
// This cannot handle the genesis block and early blocks in general.
|
|
assert(pindexPrev != nullptr);
|
|
|
|
// Anchor block is the block on which all ASERT scheduling calculations are based.
|
|
// It too must exist, and it must have a valid parent.
|
|
assert(pindexAnchorBlock != nullptr);
|
|
|
|
// We make no further assumptions other than the height of the prev block must be >= that of the anchor block.
|
|
assert(pindexPrev->nHeight >= pindexAnchorBlock->nHeight);
|
|
|
|
const arith_uint256 powLimit = UintToArith256(params.powLimit);
|
|
|
|
// 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 (params.fPowAllowMinDifficultyBlocks &&
|
|
(header.blockTime() >
|
|
pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing)) {
|
|
return UintToArith256(params.powLimit).GetCompact();
|
|
}
|
|
|
|
// For nTimeDiff calculation, the timestamp of the parent to the anchor block is used,
|
|
// as per the absolute formulation of ASERT.
|
|
// This is somewhat counterintuitive since it is referred to as the anchor timestamp, but
|
|
// as per the formula the timestamp of block M-1 must be used if the anchor is M.
|
|
assert(pindexPrev->pprev != nullptr);
|
|
// Note: time difference is to parent of anchor block (or to anchor block itself if anchor is genesis).
|
|
// (according to absolute formulation of ASERT)
|
|
const auto anchorTime = pindexAnchorBlock->pprev
|
|
? pindexAnchorBlock->pprev->GetBlockTime()
|
|
: pindexAnchorBlock->GetBlockTime();
|
|
const int64_t nTimeDiff = pindexPrev->GetBlockTime() - anchorTime;
|
|
// Height difference is from current block to anchor block
|
|
const int64_t nHeightDiff = pindexPrev->nHeight - pindexAnchorBlock->nHeight;
|
|
const arith_uint256 refBlockTarget = arith_uint256().SetCompact(pindexAnchorBlock->nBits);
|
|
// Do the actual target adaptation calculation in separate
|
|
// CalculateASERT() function
|
|
arith_uint256 nextTarget = CalculateASERT(refBlockTarget, params.nPowTargetSpacing,
|
|
nTimeDiff, nHeightDiff, powLimit, params.nASERTHalfLife);
|
|
|
|
// CalculateASERT() already clamps to powLimit.
|
|
return nextTarget.GetCompact();
|
|
}
|
|
|
|
/// ASERT calculation function.
|
|
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
|
|
{
|
|
// Our anchor block, or reference block, has to have a sane PoW target.
|
|
assert(refTarget > 0 && refTarget <= powLimit);
|
|
|
|
// We need some leading zero bits in powLimit in order to have room to handle
|
|
// overflows easily. 32 leading zero bits is more than enough.
|
|
assert((powLimit >> 224) == 0);
|
|
|
|
// We can only calculate blocks that are appended after the anchor block.
|
|
assert(nHeightDiff >= 0);
|
|
// Sane chain-config (not regtest)
|
|
assert(nHalfLife > 0);
|
|
|
|
// It will be helpful when reading what follows, to remember that
|
|
// nextTarget is adapted from anchor block target value.
|
|
|
|
// Ultimately, we want to approximate the following ASERT formula, using only integer (fixed-point) math:
|
|
// new_target = old_target * 2^((blocks_time - IDEAL_BLOCK_TIME * (height_diff + 1)) / nHalfLife)
|
|
|
|
// First, we'll calculate the exponent:
|
|
assert( llabs(nTimeDiff - nPowTargetSpacing * nHeightDiff) < (1ll << (63 - 16)) );
|
|
const int64_t exponent = ((nTimeDiff - nPowTargetSpacing * (nHeightDiff + 1)) * 65536) / nHalfLife;
|
|
|
|
// Next, we use the 2^x = 2 * 2^(x-1) identity to shift our exponent into the [0, 1) interval.
|
|
// The truncated exponent tells us how many shifts we need to do
|
|
// Note1: This needs to be a right shift. Right shift rounds downward (floored division),
|
|
// whereas integer division in C++ rounds towards zero (truncated division).
|
|
// Note2: This algorithm uses arithmetic shifts of negative numbers. This
|
|
// is unpecified but very common behavior for C++ compilers before
|
|
// C++20, and standard with C++20. We must check this behavior e.g.
|
|
// using static_assert.
|
|
static_assert(int64_t(-1) >> 1 == int64_t(-1),
|
|
"ASERT algorithm needs arithmetic shift support");
|
|
|
|
// Now we compute an approximated target * 2^(exponent/65536.0)
|
|
|
|
// First decompose exponent into 'integer' and 'fractional' parts:
|
|
int64_t shifts = exponent >> 16;
|
|
const auto frac = uint16_t(exponent);
|
|
assert(exponent == (shifts * 65536) + frac);
|
|
|
|
// multiply target by 65536 * 2^(fractional part)
|
|
// 2^x ~= (1 + 0.695502049*x + 0.2262698*x**2 + 0.0782318*x**3) for 0 <= x < 1
|
|
// Error versus actual 2^x is less than 0.013%.
|
|
const uint32_t factor = 65536 + ((
|
|
+ 195766423245049ull * frac
|
|
+ 971821376ull * frac * frac
|
|
+ 5127ull * frac * frac * frac
|
|
+ (1ull << 47)
|
|
) >> 48);
|
|
// this is always < 2^241 since refTarget < 2^224
|
|
arith_uint256 nextTarget = refTarget * factor;
|
|
|
|
// multiply by 2^(integer part) / 65536
|
|
shifts -= 16;
|
|
if (shifts <= 0) {
|
|
nextTarget >>= -shifts;
|
|
} else {
|
|
// Predetect overflow that would silently discard high bits.
|
|
if (int64_t(nextTarget.bits()) + shifts > 255) {
|
|
// If we had wider integers, the final value of nextTarget would be
|
|
// >= 2^256 so it would have just ended up as powLimit anyway.
|
|
return powLimit;
|
|
}
|
|
nextTarget <<= shifts;
|
|
}
|
|
|
|
if (nextTarget == 0) {
|
|
// 0 is not a valid target, but 1 is.
|
|
return arith_uint256(1);
|
|
}
|
|
if (nextTarget > powLimit) {
|
|
return powLimit;
|
|
}
|
|
|
|
return nextTarget;
|
|
}
|
|
|
|
|
|
|
|
uint32_t CalculateNextCW144WorkRequired(const CBlockIndex *pindexPrev, const BlockHeader &header, const Consensus::Params ¶ms)
|
|
{
|
|
// This cannot handle the genesis block and early blocks in general.
|
|
assert(pindexPrev);
|
|
|
|
// 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 (params.fPowAllowMinDifficultyBlocks
|
|
&& (header.blockTime() > pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing))
|
|
return UintToArith256(params.powLimit).GetCompact();
|
|
|
|
// Compute the difficulty based on the full adjustment interval.
|
|
const int nHeight = pindexPrev->nHeight;
|
|
assert(nHeight >= params.DifficultyAdjustmentInterval());
|
|
|
|
// Get the last suitable block of the difficulty interval.
|
|
const CBlockIndex *pindexLast = GetSuitableBlock(pindexPrev);
|
|
assert(pindexLast);
|
|
|
|
// Get the first suitable block of the difficulty interval.
|
|
const int nHeightFirst = nHeight - 144;
|
|
const CBlockIndex *pindexFirst = GetSuitableBlock(pindexPrev->GetAncestor(nHeightFirst));
|
|
assert(pindexFirst);
|
|
|
|
// Compute the target based on time and work done during the interval.
|
|
const arith_uint256 nextTarget = ComputeTarget(pindexFirst, pindexLast, params);
|
|
|
|
const arith_uint256 powLimit = UintToArith256(params.powLimit);
|
|
if (nextTarget > powLimit)
|
|
return powLimit.GetCompact();
|
|
|
|
return nextTarget.GetCompact();
|
|
}
|
|
|
|
// Satoshi's algo
|
|
uint32_t Calculate2016NextWorkRequired(const CBlockIndex *pindexPrev, int64_t nFirstBlockTime, const Consensus::Params ¶ms)
|
|
{
|
|
if (params.fPowNoRetargeting)
|
|
return pindexPrev->nBits;
|
|
|
|
// Limit adjustment step
|
|
int64_t nActualTimespan = pindexPrev->GetBlockTime() - nFirstBlockTime;
|
|
logDebug(Log::Bitcoin) << "nActualTimespan =" << nActualTimespan << "before bounds";
|
|
if (nActualTimespan < params.nPowTargetTimespan/4)
|
|
nActualTimespan = params.nPowTargetTimespan/4;
|
|
if (nActualTimespan > params.nPowTargetTimespan*4)
|
|
nActualTimespan = params.nPowTargetTimespan*4;
|
|
|
|
// Retarget
|
|
const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
|
|
arith_uint256 bnNew;
|
|
bnNew.SetCompact(pindexPrev->nBits);
|
|
bnNew *= nActualTimespan;
|
|
bnNew /= params.nPowTargetTimespan;
|
|
|
|
if (bnNew > bnPowLimit)
|
|
bnNew = bnPowLimit;
|
|
|
|
return bnNew.GetCompact();
|
|
}
|
|
|
|
bool CheckProofOfWork(const uint256 &hash, uint32_t nBits, const Consensus::Params ¶ms) {
|
|
bool fNegative;
|
|
bool fOverflow;
|
|
arith_uint256 bnTarget;
|
|
|
|
bnTarget.SetCompact(nBits, &fNegative, &fOverflow);
|
|
|
|
// Check range
|
|
if (fNegative || bnTarget == 0 || fOverflow || bnTarget > UintToArith256(params.powLimit))
|
|
return false;
|
|
|
|
// Check proof of work matches claimed amount
|
|
if (UintToArith256(hash) > bnTarget)
|
|
return false;
|
|
|
|
return true;
|
|
}
|
|
|
|
arith_uint256 GetBlockProof(const CBlockIndex& block)
|
|
{
|
|
arith_uint256 bnTarget;
|
|
bool fNegative;
|
|
bool fOverflow;
|
|
bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
|
|
if (fNegative || fOverflow || bnTarget == 0)
|
|
return 0;
|
|
// We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
|
|
// as it's too large for a arith_uint256. However, as 2**256 is at least as large
|
|
// as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
|
|
// or ~bnTarget / (nTarget+1) + 1.
|
|
return (~bnTarget / (bnTarget + 1)) + 1;
|
|
}
|
|
|
|
int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
|
|
{
|
|
arith_uint256 r;
|
|
int sign = 1;
|
|
if (to.nChainWork > from.nChainWork) {
|
|
r = to.nChainWork - from.nChainWork;
|
|
} else {
|
|
r = from.nChainWork - to.nChainWork;
|
|
sign = -1;
|
|
}
|
|
r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
|
|
if (r.bits() > 63) {
|
|
return sign * std::numeric_limits<int64_t>::max();
|
|
}
|
|
return sign * r.GetLow64();
|
|
}
|