tomFlowee
b4a3da2642
These are technically static libs, but not in any way shared libs. They are used solely only by this repo and really only by the hub. Most important, no header files are installed and basically none of the normal rules for reusable libraries are applied to these files.
455 lines
17 KiB
C++
455 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/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 BlockHeaderFields *pblock, 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 (pblock->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 BlockHeaderFields *pblock, 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, pblock, params,
|
|
GetASERTAnchorBlock(pindexPrev, params));
|
|
// then the 3 year period of cw144
|
|
return CalculateNextCW144WorkRequired(pindexPrev, pblock, params);
|
|
}
|
|
|
|
// the couple of months of the emergency difficulty adjustment algo
|
|
return GetNextEDAWorkRequired(pindexPrev, pblock, params);
|
|
}
|
|
|
|
uint32_t CalculateNextASERTWorkRequired(const CBlockIndex *pindexPrev,
|
|
const BlockHeaderFields *pblock,
|
|
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 &&
|
|
(pblock->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 BlockHeaderFields *pblock, 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
|
|
&& (pblock->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();
|
|
}
|