diff --git a/src/pow.h b/src/pow.h --- a/src/pow.h +++ b/src/pow.h @@ -10,6 +10,9 @@ #include +// Fixed precision for weighted-time difficulty ratio +static const uint32_t DIFF_WEIGHT_PRECISION = 1000000; // 6 decimal places + class CBlockHeader; class CBlockIndex; class uint256; @@ -27,4 +30,11 @@ */ bool CheckProofOfWork(uint256 hash, uint32_t nBits, const Consensus::Params &); +/** + * Bitcoin cash's difficulty adjustement mechanism. + */ +uint32_t GetNextCashWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const Consensus::Params ¶ms); + #endif // BITCOIN_POW_H diff --git a/src/pow.cpp b/src/pow.cpp --- a/src/pow.cpp +++ b/src/pow.cpp @@ -10,6 +10,8 @@ #include "primitives/block.h" #include "uint256.h" +#include + /** * Compute the next required proof of work using the legacy Bitcoin difficulty * adjustement + Emergency Difficulty Adjustement (EDA). @@ -149,3 +151,113 @@ return true; } + +static std::deque +BlocksInRange(const CBlockIndex *pindexFirst, const CBlockIndex *pindexLast) { + std::deque blocks; + for (const CBlockIndex *i = pindexLast; i != pindexFirst; i = i->pprev) { + blocks.push_front(i); + } + return blocks; +} + +/** + * Compute the a target based on the work done between 2 blocks and the time + * required to produce that work. + */ +static arith_uint256 ComputeTarget(const CBlockIndex *pindexFirst, + const CBlockIndex *pindexLast) { + assert(pindexLast->nHeight > pindexFirst->nHeight); + std::deque blocks = + BlocksInRange(pindexFirst, pindexLast); + + // last_target = bits_to_target(states[last].bits) + arith_uint256 last_target; + last_target.SetCompact(pindexLast->nBits); + arith_uint256 last_target_fixed = last_target / DIFF_WEIGHT_PRECISION; + + // timespan = 0 + // prior_timestamp = states[first].timestamp + uint32_t timespan = 0; + uint32_t prior_timestamp = pindexFirst->nTime; + + // for i in range(first + 1, last + 1): + for (auto i = begin(blocks); i != end(blocks); ++i) { + // target_i = bits_to_target(states[i].bits) + arith_uint256 target_i; + target_i.SetCompact((*i)->nBits); + + // Prevent negative time_i values + // + // timestamp = max(states[i].timestamp, prior_timestamp) + // time_i = timestamp - prior_timestamp + // prior_timestamp = timestamp + uint32_t timestamp = std::max((*i)->nTime, prior_timestamp); + uint32_t time_i = timestamp - prior_timestamp; + prior_timestamp = timestamp; + + // Difficulty weight + // adj_time_i = time_i * target_i // last_target # Difficulty weight + uint32_t adj_time_i = + ((time_i * (target_i / DIFF_WEIGHT_PRECISION)) / last_target_fixed) + .GetLow64(); + + // Recency weight + // timespan += adj_time_i * i # Recency weight + timespan += adj_time_i * (std::distance(begin(blocks), i) + 1); + } + + int block_count = blocks.size(); + // Normalize recency weight + // timespan = timespan * 2 // (block_count + 1) + timespan = timespan * 2 / (block_count + 1); + + // Standard retarget + // target = last_target * timespan # Standard retarget + // target //= 600 * block_count + arith_uint256 target = last_target * timespan; + target /= 600 * block_count; + return target; +} + +/** + * Compute the next required proof of work using a weighted average of the + * estimated hashrate per block. + * + * Additionally, weight most recent blocks more heavily using an arithmetic + * sequence that drops to zero just before the earliest block in the window. + */ +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 adjustment interval. + const uint32_t nHeight = pindexPrev->nHeight; + assert(nHeight >= params.DifficultyAdjustmentInterval()); + + // Find the last block before the difficulty interval. + uint32_t nHeightFirst = nHeight - 144; + const CBlockIndex *pindexFirst = pindexPrev->GetAncestor(nHeightFirst); + assert(pindexFirst); + + // Compute the target based on time and work done during the interval. + const arith_uint256 nextTarget = ComputeTarget(pindexFirst, pindexPrev); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + if (nextTarget > powLimit) { + return powLimit.GetCompact(); + } + + return nextTarget.GetCompact(); +} diff --git a/src/test/pow_tests.cpp b/src/test/pow_tests.cpp --- a/src/test/pow_tests.cpp +++ b/src/test/pow_tests.cpp @@ -187,4 +187,188 @@ powLimit.GetCompact()); } +BOOST_AUTO_TEST_CASE(cash_difficulty_test) { + SelectParams(CBaseChainParams::MAIN); + const Consensus::Params ¶ms = Params().GetConsensus(); + + std::vector blocks(3000); + + const arith_uint256 powLimit = UintToArith256(params.powLimit); + uint32_t powLimitBits = powLimit.GetCompact(); + arith_uint256 currentPow = powLimit >> 4; + uint32_t initialBits = currentPow.GetCompact(); + + // Genesis block. + blocks[0] = CBlockIndex(); + blocks[0].nHeight = 0; + blocks[0].nTime = 1269211443; + blocks[0].nBits = initialBits; + + // Block counter. + size_t i; + + // Pile up some blocks every 10 mins to establish some history. + for (i = 1; i < 2050; i++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, initialBits); + } + + CBlockHeader blkHeaderDummy; + uint32_t nextBits; + uint32_t nBits = + GetNextCashWorkRequired(&blocks[2049], &blkHeaderDummy, params); + + // Difficulty stays the same as long as we produce a block every 10 mins. + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params), + nBits); + } + + // Produce a block that is far in the future + // This will produce a one-time difficulty drop of about 13% + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + BOOST_CHECK_EQUAL(nextBits, 0x1c11fc70); + nBits = nextBits; + + // Now produce a block with the expected timestamp. + // This block counts as +0s, a ~1.5% difficulty raise + blocks[i] = GetBlockIndex(&blocks[i - 1], 2 * 600 - 6000, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + BOOST_CHECK_EQUAL(nextBits, 0x1c11bac8); + nBits = nextBits; + + // The effect of the bogus timestamp is dissipated over the next 8 blocks + for (size_t j = 0; j < 8; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Check the difficulty decreases. + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 6)); + + nBits = nextBits; + } + + // We start emitting blocks slightly faster. + // Difficulty should increase slowly. + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 550, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Make sure that difficulty increases slowly. + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 8)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0fb7f5); + + // If we dramatically shorten block production, difficulty increases faster. + for (size_t j = 0; j < 20; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 10, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Make sure that difficulty increases faster. + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 4)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0baff0); + + // If we dramatically slow down block production, difficulty decreases. + for (size_t j = 0; j < 31; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 5000, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Check the difficulty decreases. + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget > currentTarget); + BOOST_CHECK((nextTarget - currentTarget) < (currentTarget >> 3)); + + nBits = nextBits; + } + + // Check the actual value. We should have just reached the limit. + BOOST_CHECK_EQUAL(nBits, 0x1d00ffff); + + // Once the difficulty reached the minimum allowed level, it doesn't get any + // easier. + blocks[i] = GetBlockIndex(&blocks[i - 1], 900, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + BOOST_CHECK_EQUAL(nextBits, powLimitBits); + nBits = nextBits; + + // Undo the effect of the last block + blocks[i] = GetBlockIndex(&blocks[i - 1], 0, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + + // Raise the difficulty back up above the minimum limit + // Make a large number of fast blocks + for (size_t j = 0; j < 31; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 0, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Check the difficulty increases. + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 6)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1d00c400); + + // Mine neutral blocks + // Difficulty continues to change slightly as weights shift + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + nextBits = GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + BOOST_CHECK(nextTarget <= powLimit); + BOOST_CHECK(nextTarget > currentTarget); + BOOST_CHECK((nextTarget - currentTarget) < (currentTarget >> 7)); + + nBits = nextBits; + } +} + BOOST_AUTO_TEST_SUITE_END()