Changeset View
Changeset View
Standalone View
Standalone View
src/pow.cpp
// Copyright (c) 2009-2010 Satoshi Nakamoto | // Copyright (c) 2009-2010 Satoshi Nakamoto | ||||
// Copyright (c) 2009-2016 The Bitcoin Core developers | // Copyright (c) 2009-2016 The Bitcoin Core developers | ||||
// Copyright (c) 2017 The Bitcoin developers | |||||
// Distributed under the MIT software license, see the accompanying | // Distributed under the MIT software license, see the accompanying | ||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | // file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
#include "pow.h" | #include "pow.h" | ||||
#include "arith_uint256.h" | #include "arith_uint256.h" | ||||
#include "chain.h" | #include "chain.h" | ||||
#include "primitives/block.h" | #include "primitives/block.h" | ||||
▲ Show 20 Lines • Show All 133 Lines • ▼ Show 20 Lines | bool CheckProofOfWork(uint256 hash, uint32_t nBits, | ||||
// Check proof of work matches claimed amount | // Check proof of work matches claimed amount | ||||
if (UintToArith256(hash) > bnTarget) { | if (UintToArith256(hash) > bnTarget) { | ||||
return false; | return false; | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
/** | |||||
* Compute the a target based on the work done between 2 blocks, the time it | |||||
* took and the time it should take. | |||||
*/ | |||||
static arith_uint256 ComputeTarget(const CBlockIndex *pindexFirst, | |||||
const CBlockIndex *pindexLast, | |||||
const Consensus::Params ¶ms) { | |||||
/** | |||||
* 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. | |||||
* | |||||
* We then adjust the target depending on the time it took to do that much | |||||
* work and how much we expect a unit of work to take. | |||||
*/ | |||||
arith_uint256 work = pindexLast->nChainWork - pindexFirst->nChainWork; | |||||
int64_t actualDuration = pindexLast->nTime - pindexFirst->nTime; | |||||
return actualDuration * ((-work) / (work * params.nPowTargetSpacing)); | |||||
} | |||||
Mengerian: It should be noted that this is a slight approximation.
The exact calculation would be… | |||||
/** | |||||
* To reduce the impact of timestamp manipulation, we select the block we are | |||||
* basing our computation on via a median of 3. | |||||
*/ | |||||
static const CBlockIndex *GetSuitableBlock(const CBlockIndex *pindex) { | |||||
assert(pindex->nHeight >= 3); | |||||
/** | |||||
* In order to avoid a block is a very skewed timestamp to have 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]; | |||||
} | |||||
/** | |||||
* Compute the next required proof of work using a weighted average of the | |||||
* estimated hashrate per block. | |||||
* | |||||
* Using a weighted average ensure that the timestamp parameter cancels out in | |||||
* most of the calculation - except for the timestamp of the first and last | |||||
* block. Because timestamps are the least trustworthy information we have as | |||||
* input, this ensure the algorithm is more resistant to malicious inputs. | |||||
* | |||||
* This is done over a short timescale to be able to react quickly to fast | |||||
* hashrate changes, but also on a larger timescale. When the short timescale do | |||||
* not vary to much from the large one, then the large one is used to provide | |||||
* stability. | |||||
*/ | |||||
uint32_t GetNextCashWorkRequired(const CBlockIndex *pindexPrev, | |||||
const CBlockHeader *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->GetBlockTime() > | |||||
pindexPrev->GetBlockTime() + 2 * params.nPowTargetSpacing)) { | |||||
return UintToArith256(params.powLimit).GetCompact(); | |||||
} | |||||
// Compute the difficulty based on the full adjustement interval. | |||||
const uint32_t nHeight = pindexPrev->nHeight; | |||||
assert(nHeight >= params.DifficultyAdjustmentInterval()); | |||||
// Get the suitable last suitable block of the difficulty interval. | |||||
const CBlockIndex *pindexLast = GetSuitableBlock(pindexPrev); | |||||
assert(pindexLast); | |||||
// Get the first suitable block of the difficulty interval. | |||||
uint32_t nHeightFirst = nHeight - params.DifficultyAdjustmentInterval(); | |||||
const CBlockIndex *pindexFirst = | |||||
GetSuitableBlock(pindexPrev->GetAncestor(nHeightFirst)); | |||||
assert(pindexFirst); | |||||
// Compute the time and work done during that interval. | |||||
const arith_uint256 intervalTarget = | |||||
ComputeTarget(pindexFirst, pindexLast, params); | |||||
// In addition to the intervalTarget, we compute a target based on a much | |||||
// smaller timescale. If this target is significantly different from the one | |||||
// based on the whole interval, we use it to correct faster. | |||||
const CBlockIndex *pindexFast = nullptr; | |||||
// Try adding more and more blocks to our fast windows until it contains at | |||||
// least 5 blocks and has sufficient duration. | |||||
for (uint32_t blockCount = 3; true; blockCount++) { | |||||
// Find a suitable candidate for a block to start the window. | |||||
uint32_t nLastHeight = pindexLast->nHeight; | |||||
pindexFast = | |||||
GetSuitableBlock(pindexLast->GetAncestor(nLastHeight - blockCount)); | |||||
// We want at least 5 blocks in the window. | |||||
if ((nLastHeight - pindexFast->nHeight) < 5) { | |||||
continue; | |||||
} | |||||
// We want consistent timestamps. | |||||
if (pindexLast->nTime <= pindexFast->nTime) { | |||||
continue; | |||||
} | |||||
// We want the windows to be larger than the expected time required to | |||||
// produce 13 blocks. | |||||
if ((pindexLast->nTime - pindexFast->nTime) >= | |||||
13 * params.nPowTargetSpacing) { | |||||
// We have a winner. | |||||
break; | |||||
} | |||||
} | |||||
const arith_uint256 fastTarget = | |||||
ComputeTarget(pindexFast, pindexLast, params); | |||||
// If the fast target differs significantly from the one over the full | |||||
// interval, use it. This ensure that the most stable value, is somewhat | |||||
// sticky and diminishes oscillations. | |||||
arith_uint256 nextTarget = intervalTarget; | |||||
if ((fastTarget < (intervalTarget - (intervalTarget >> 2))) || | |||||
(fastTarget > (intervalTarget + (intervalTarget >> 2)))) { | |||||
nextTarget = fastTarget; | |||||
} | |||||
// We bound the change that can happen from the previous block. This avoid | |||||
// violent difficulty swing and to overreact to simple variance. | |||||
arith_uint256 prevTarget; | |||||
prevTarget.SetCompact(pindexPrev->nBits); | |||||
const arith_uint256 minTarget = prevTarget - (prevTarget >> 3); | |||||
if (nextTarget < minTarget) { | |||||
return minTarget.GetCompact(); | |||||
} | |||||
// If our next target is easier than the difficulty limit, set it to the | |||||
// difficulty limit. | |||||
const arith_uint256 targetLimit = UintToArith256(params.powLimit); | |||||
if (nextTarget > targetLimit) { | |||||
nextTarget = targetLimit; | |||||
} | |||||
const arith_uint256 maxTarget = prevTarget + (prevTarget >> 3); | |||||
if (nextTarget > maxTarget) { | |||||
return maxTarget.GetCompact(); | |||||
} | |||||
return nextTarget.GetCompact(); | |||||
} |
It should be noted that this is a slight approximation.
The exact calculation would be:
Because the "W" in the formula above represents the work per block, so we substitute
into
(where "-W" is the 256-bit 2's complement simplification of (2^256 - W)
In practice, this makes a very small difference, since it's off-by-one of a large 256 bit number.