diff --git a/src/chain.h b/src/chain.h index 5171fccc3..9c62a405f 100644 --- a/src/chain.h +++ b/src/chain.h @@ -1,507 +1,510 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CHAIN_H #define BITCOIN_CHAIN_H #include "arith_uint256.h" #include "pow.h" #include "primitives/block.h" #include "tinyformat.h" #include "uint256.h" #include class CBlockFileInfo { public: //!< number of blocks stored in file unsigned int nBlocks; //!< number of used bytes of block file unsigned int nSize; //!< number of used bytes in the undo file unsigned int nUndoSize; //!< lowest height of block in file unsigned int nHeightFirst; //!< highest height of block in file unsigned int nHeightLast; //!< earliest time of block in file uint64_t nTimeFirst; //!< latest time of block in file uint64_t nTimeLast; ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(VARINT(nBlocks)); READWRITE(VARINT(nSize)); READWRITE(VARINT(nUndoSize)); READWRITE(VARINT(nHeightFirst)); READWRITE(VARINT(nHeightLast)); READWRITE(VARINT(nTimeFirst)); READWRITE(VARINT(nTimeLast)); } void SetNull() { nBlocks = 0; nSize = 0; nUndoSize = 0; nHeightFirst = 0; nHeightLast = 0; nTimeFirst = 0; nTimeLast = 0; } CBlockFileInfo() { SetNull(); } std::string ToString() const; /** update statistics (does not update nSize) */ void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) { if (nBlocks == 0 || nHeightFirst > nHeightIn) { nHeightFirst = nHeightIn; } if (nBlocks == 0 || nTimeFirst > nTimeIn) { nTimeFirst = nTimeIn; } nBlocks++; if (nHeightIn > nHeightLast) { nHeightLast = nHeightIn; } if (nTimeIn > nTimeLast) { nTimeLast = nTimeIn; } } }; struct CDiskBlockPos { int nFile; unsigned int nPos; ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(VARINT(nFile)); READWRITE(VARINT(nPos)); } CDiskBlockPos() { SetNull(); } CDiskBlockPos(int nFileIn, unsigned int nPosIn) { nFile = nFileIn; nPos = nPosIn; } friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) { return (a.nFile == b.nFile && a.nPos == b.nPos); } friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) { return !(a == b); } void SetNull() { nFile = -1; nPos = 0; } bool IsNull() const { return (nFile == -1); } std::string ToString() const { return strprintf("CBlockDiskPos(nFile=%i, nPos=%i)", nFile, nPos); } }; enum BlockStatus : uint32_t { //! Unused. BLOCK_VALID_UNKNOWN = 0, //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, //! timestamp not in future BLOCK_VALID_HEADER = 1, //! All parent headers found, difficulty matches, timestamp >= median //! previous, checkpoint. Implies all parents are also at least TREE. BLOCK_VALID_TREE = 2, /** * Only first tx is coinbase, 2 <= coinbase input script length <= 100, * transactions valid, no duplicate txids, sigops, size, merkle root. * Implies all parents are at least TREE but not necessarily TRANSACTIONS. * When all parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will * be set. */ BLOCK_VALID_TRANSACTIONS = 3, //! Outputs do not overspend inputs, no double spends, coinbase output ok, //! no immature coinbase spends, BIP30. //! Implies all parents are also at least CHAIN. BLOCK_VALID_CHAIN = 4, //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS. BLOCK_VALID_SCRIPTS = 5, //! All validity bits. BLOCK_VALID_MASK = BLOCK_VALID_HEADER | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS | BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS, //!< full block available in blk*.dat BLOCK_HAVE_DATA = 8, //!< undo data available in rev*.dat BLOCK_HAVE_UNDO = 16, BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO, //!< stage after last reached validness failed BLOCK_FAILED_VALID = 32, //!< descends from failed block BLOCK_FAILED_CHILD = 64, BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD, }; /** * The block chain is a tree shaped structure starting with the genesis block at * the root, with each block potentially having multiple candidates to be the * next block. A blockindex may have multiple pprev pointing to it, but at most * one of them can be part of the currently active branch. */ class CBlockIndex { public: //! pointer to the hash of the block, if any. Memory is owned by this //! CBlockIndex const uint256 *phashBlock; //! pointer to the index of the predecessor of this block CBlockIndex *pprev; //! pointer to the index of some further predecessor of this block CBlockIndex *pskip; //! height of the entry in the chain. The genesis block has height 0 int nHeight; //! Which # file this block is stored in (blk?????.dat) int nFile; //! Byte offset within blk?????.dat where this block's data is stored unsigned int nDataPos; //! Byte offset within rev?????.dat where this block's undo data is stored unsigned int nUndoPos; //! (memory only) Total amount of work (expected number of hashes) in the //! chain up to and including this block arith_uint256 nChainWork; //! Number of transactions in this block. //! Note: in a potential headers-first mode, this number cannot be relied //! upon unsigned int nTx; //! (memory only) Number of transactions in the chain up to and including //! this block. //! This value will be non-zero only if and only if transactions for this //! block and all its parents are available. Change to 64-bit type when //! necessary; won't happen before 2030 unsigned int nChainTx; //! Verification status of this block. See enum BlockStatus uint32_t nStatus; //! block header int32_t nVersion; uint256 hashMerkleRoot; uint32_t nTime; uint32_t nBits; uint32_t nNonce; //! (memory only) Sequential id assigned to distinguish order in which //! blocks are received. int32_t nSequenceId; //! (memory only) Maximum nTime in the chain upto and including this block. unsigned int nTimeMax; void SetNull() { phashBlock = nullptr; pprev = nullptr; pskip = nullptr; nHeight = 0; nFile = 0; nDataPos = 0; nUndoPos = 0; nChainWork = arith_uint256(); nTx = 0; nChainTx = 0; nStatus = 0; nSequenceId = 0; nTimeMax = 0; nVersion = 0; hashMerkleRoot = uint256(); nTime = 0; nBits = 0; nNonce = 0; } CBlockIndex() { SetNull(); } CBlockIndex(const CBlockHeader &block) { SetNull(); nVersion = block.nVersion; hashMerkleRoot = block.hashMerkleRoot; nTime = block.nTime; nBits = block.nBits; nNonce = block.nNonce; } CDiskBlockPos GetBlockPos() const { CDiskBlockPos ret; if (nStatus & BLOCK_HAVE_DATA) { ret.nFile = nFile; ret.nPos = nDataPos; } return ret; } CDiskBlockPos GetUndoPos() const { CDiskBlockPos ret; if (nStatus & BLOCK_HAVE_UNDO) { ret.nFile = nFile; ret.nPos = nUndoPos; } return ret; } CBlockHeader GetBlockHeader() const { CBlockHeader block; block.nVersion = nVersion; if (pprev) { block.hashPrevBlock = pprev->GetBlockHash(); } block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block; } uint256 GetBlockHash() const { return *phashBlock; } int64_t GetBlockTime() const { return (int64_t)nTime; } int64_t GetBlockTimeMax() const { return (int64_t)nTimeMax; } enum { nMedianTimeSpan = 11 }; int64_t GetMedianTimePast() const { int64_t pmedian[nMedianTimeSpan]; int64_t *pbegin = &pmedian[nMedianTimeSpan]; int64_t *pend = &pmedian[nMedianTimeSpan]; const CBlockIndex *pindex = this; for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) { *(--pbegin) = pindex->GetBlockTime(); } std::sort(pbegin, pend); return pbegin[(pend - pbegin) / 2]; } std::string ToString() const { return strprintf( "CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString()); } //! Check whether this block index entry is valid up to the passed validity //! level. bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const { // Only validity flags allowed. assert(!(nUpTo & ~BLOCK_VALID_MASK)); if (nStatus & BLOCK_FAILED_MASK) { return false; } return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); } //! Raise the validity level of this block index entry. //! Returns true if the validity was changed. bool RaiseValidity(enum BlockStatus nUpTo) { // Only validity flags allowed. assert(!(nUpTo & ~BLOCK_VALID_MASK)); if (nStatus & BLOCK_FAILED_MASK) { return false; } if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; return true; } return false; } //! Build the skiplist pointer for this entry. void BuildSkip(); //! Efficiently find an ancestor of this block. CBlockIndex *GetAncestor(int height); const CBlockIndex *GetAncestor(int height) const; }; arith_uint256 GetBlockProof(const CBlockIndex &block); -/** Return the time it would take to redo the work difference between from and + +/** + * Return the time it would take to redo the work difference between from and * to, assuming the current hashrate corresponds to the difficulty at tip, in - * seconds. */ + * seconds. + */ int64_t GetBlockProofEquivalentTime(const CBlockIndex &to, const CBlockIndex &from, const CBlockIndex &tip, const Consensus::Params &); /** Used to marshal pointers into hashes for db storage. */ class CDiskBlockIndex : public CBlockIndex { public: uint256 hashPrev; CDiskBlockIndex() { hashPrev = uint256(); } explicit CDiskBlockIndex(const CBlockIndex *pindex) : CBlockIndex(*pindex) { hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); } ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { int nVersion = s.GetVersion(); if (!(s.GetType() & SER_GETHASH)) { READWRITE(VARINT(nVersion)); } READWRITE(VARINT(nHeight)); READWRITE(VARINT(nStatus)); READWRITE(VARINT(nTx)); if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) { READWRITE(VARINT(nFile)); } if (nStatus & BLOCK_HAVE_DATA) { READWRITE(VARINT(nDataPos)); } if (nStatus & BLOCK_HAVE_UNDO) { READWRITE(VARINT(nUndoPos)); } // block header READWRITE(this->nVersion); READWRITE(hashPrev); READWRITE(hashMerkleRoot); READWRITE(nTime); READWRITE(nBits); READWRITE(nNonce); } uint256 GetBlockHash() const { CBlockHeader block; block.nVersion = nVersion; block.hashPrevBlock = hashPrev; block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block.GetHash(); } std::string ToString() const { std::string str = "CDiskBlockIndex("; str += CBlockIndex::ToString(); str += strprintf("\n hashBlock=%s, hashPrev=%s)", GetBlockHash().ToString(), hashPrev.ToString()); return str; } }; /** An in-memory indexed chain of blocks. */ class CChain { private: std::vector vChain; public: /** * Returns the index entry for the genesis block of this chain, or nullptr * if none. */ CBlockIndex *Genesis() const { return vChain.size() > 0 ? vChain[0] : nullptr; } /** * Returns the index entry for the tip of this chain, or nullptr if none. */ CBlockIndex *Tip() const { return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; } /** * Returns the index entry at a particular height in this chain, or nullptr * if no such height exists. */ CBlockIndex *operator[](int nHeight) const { if (nHeight < 0 || nHeight >= (int)vChain.size()) { return nullptr; } return vChain[nHeight]; } /** Compare two chains efficiently. */ friend bool operator==(const CChain &a, const CChain &b) { return a.vChain.size() == b.vChain.size() && a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1]; } /** Efficiently check whether a block is present in this chain. */ bool Contains(const CBlockIndex *pindex) const { return (*this)[pindex->nHeight] == pindex; } /** * Find the successor of a block in this chain, or nullptr if the given * index is not found or is the tip. */ CBlockIndex *Next(const CBlockIndex *pindex) const { if (!Contains(pindex)) { return nullptr; } return (*this)[pindex->nHeight + 1]; } /** * Return the maximal height in the chain. Is equal to chain.Tip() ? * chain.Tip()->nHeight : -1. */ int Height() const { return vChain.size() - 1; } /** Set/initialize a chain with a given tip. */ void SetTip(CBlockIndex *pindex); /** * Return a CBlockLocator that refers to a block in this chain (by default * the tip). */ CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const; /** * Find the last common block between this chain and a block index entry. */ const CBlockIndex *FindFork(const CBlockIndex *pindex) const; /** * Find the earliest block with timestamp equal or greater than the given. */ CBlockIndex *FindEarliestAtLeast(int64_t nTime) const; }; #endif // BITCOIN_CHAIN_H diff --git a/src/consensus/params.h b/src/consensus/params.h index 0b5ac95f1..5c276fd52 100644 --- a/src/consensus/params.h +++ b/src/consensus/params.h @@ -1,82 +1,83 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CONSENSUS_PARAMS_H #define BITCOIN_CONSENSUS_PARAMS_H #include "uint256.h" + #include #include namespace Consensus { enum DeploymentPos { DEPLOYMENT_TESTDUMMY, // Deployment of BIP68, BIP112, and BIP113. DEPLOYMENT_CSV, // NOTE: Also add new deployments to VersionBitsDeploymentInfo in // versionbits.cpp MAX_VERSION_BITS_DEPLOYMENTS }; /** * Struct for each individual consensus rule change using BIP9. */ struct BIP9Deployment { /** Bit position to select the particular bit in nVersion. */ int bit; /** Start MedianTime for version bits miner confirmation. Can be a date in * the past */ int64_t nStartTime; /** Timeout/expiry MedianTime for the deployment attempt. */ int64_t nTimeout; }; /** * Parameters that influence chain consensus. */ struct Params { uint256 hashGenesisBlock; int nSubsidyHalvingInterval; /** Block height and hash at which BIP34 becomes active */ int BIP34Height; uint256 BIP34Hash; /** Block height at which BIP65 becomes active */ int BIP65Height; /** Block height at which BIP66 becomes active */ int BIP66Height; /** Block height at which UAHF kicks in */ int uahfHeight; /** Block height at which OP_RETURN replay protection stops */ int antiReplayOpReturnSunsetHeight; /** Committed OP_RETURN value for replay protection */ std::vector antiReplayOpReturnCommitment; /** * Minimum blocks including miner confirmation of the total of 2016 blocks * in a retargeting period, (nPowTargetTimespan / nPowTargetSpacing) which * is also used for BIP9 deployments. * Examples: 1916 for 95%, 1512 for testchains. */ uint32_t nRuleChangeActivationThreshold; uint32_t nMinerConfirmationWindow; BIP9Deployment vDeployments[MAX_VERSION_BITS_DEPLOYMENTS]; /** Proof of work parameters */ uint256 powLimit; bool fPowAllowMinDifficultyBlocks; bool fPowNoRetargeting; int64_t nPowTargetSpacing; int64_t nPowTargetTimespan; int64_t DifficultyAdjustmentInterval() const { return nPowTargetTimespan / nPowTargetSpacing; } uint256 nMinimumChainWork; uint256 defaultAssumeValid; /** Activation time at which the cash HF kicks in. */ int64_t cashHardForkActivationTime; }; } // namespace Consensus #endif // BITCOIN_CONSENSUS_PARAMS_H diff --git a/src/pow.cpp b/src/pow.cpp index 6d67c32f9..e0e707d19 100644 --- a/src/pow.cpp +++ b/src/pow.cpp @@ -1,151 +1,273 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers +// Copyright (c) 2017 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.h" #include "arith_uint256.h" #include "chain.h" #include "primitives/block.h" #include "uint256.h" /** * Compute the next required proof of work using the legacy Bitcoin difficulty * adjustement + Emergency Difficulty Adjustement (EDA). */ static uint32_t GetNextEDAWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *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 CalculateNextWorkRequired(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->GetBlockTime() > 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 bellow the minimum, so early bail. uint32_t nBits = pindexPrev->nBits; if (nBits == nProofOfWorkLimit) { return nProofOfWorkLimit; } // If producing the last 6 block 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 block took more than 12h, increase the difficulty // target by 1/4 (which reduces the difficulty by 20%). This ensure the // chain do not get stuck in case we lose hashrate abruptly. arith_uint256 nPow; nPow.SetCompact(nBits); nPow += (nPow >> 2); // Make sure we do not go bellow allowed values. const arith_uint256 bnPowLimit = UintToArith256(params.powLimit); if (nPow > bnPowLimit) nPow = bnPowLimit; return nPow.GetCompact(); } uint32_t GetNextWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *pblock, const Consensus::Params ¶ms) { // Genesis block if (pindexPrev == nullptr) { return UintToArith256(params.powLimit).GetCompact(); } // Special rule for regtest: we never retarget. if (params.fPowNoRetargeting) { return pindexPrev->nBits; } return GetNextEDAWorkRequired(pindexPrev, pblock, params); } uint32_t CalculateNextWorkRequired(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; 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(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; } + +/** + * 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, + 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 + // adjustement we are going to do. + assert(pindexLast->nTime > pindexFirst->nTime); + int64_t nActualTimespan = pindexLast->nTime - 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; +} + +/** + * 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 ensures the algorithm is more resistant to malicious inputs. + */ +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 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 - 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(); +} diff --git a/src/pow.h b/src/pow.h index 0781355ec..35e7cbdfa 100644 --- a/src/pow.h +++ b/src/pow.h @@ -1,30 +1,37 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_POW_H #define BITCOIN_POW_H #include "consensus/params.h" #include class CBlockHeader; class CBlockIndex; class uint256; uint32_t GetNextWorkRequired(const CBlockIndex *pindexPrev, const CBlockHeader *pblock, const Consensus::Params &); uint32_t CalculateNextWorkRequired(const CBlockIndex *pindexPrev, int64_t nFirstBlockTime, const Consensus::Params &); /** * Check whether a block hash satisfies the proof-of-work requirement specified * by nBits */ bool CheckProofOfWork(uint256 hash, uint32_t nBits, const Consensus::Params &); +/** + * Bitcoin cash's difficulty adjustment mechanism. + */ +uint32_t GetNextCashWorkRequired(const CBlockIndex *pindexPrev, + const CBlockHeader *pblock, + const Consensus::Params ¶ms); + #endif // BITCOIN_POW_H diff --git a/src/test/pow_tests.cpp b/src/test/pow_tests.cpp index 356d64430..5dce4af31 100644 --- a/src/test/pow_tests.cpp +++ b/src/test/pow_tests.cpp @@ -1,190 +1,370 @@ // Copyright (c) 2015 The Bitcoin Core developers // Distributed under the MIT/X11 software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "pow.h" #include "chain.h" #include "chainparams.h" #include "random.h" #include "test/test_bitcoin.h" #include "util.h" #include BOOST_FIXTURE_TEST_SUITE(pow_tests, BasicTestingSetup) /* Test calculation of next difficulty target with no constraints applying */ BOOST_AUTO_TEST_CASE(get_next_work) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); int64_t nLastRetargetTime = 1261130161; // Block #30240 CBlockIndex pindexLast; pindexLast.nHeight = 32255; pindexLast.nTime = 1262152739; // Block #32255 pindexLast.nBits = 0x1d00ffff; BOOST_CHECK_EQUAL( CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, params), 0x1d00d86a); } /* Test the constraint on the upper bound for next work */ BOOST_AUTO_TEST_CASE(get_next_work_pow_limit) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); int64_t nLastRetargetTime = 1231006505; // Block #0 CBlockIndex pindexLast; pindexLast.nHeight = 2015; pindexLast.nTime = 1233061996; // Block #2015 pindexLast.nBits = 0x1d00ffff; BOOST_CHECK_EQUAL( CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, params), 0x1d00ffff); } /* Test the constraint on the lower bound for actual time taken */ BOOST_AUTO_TEST_CASE(get_next_work_lower_limit_actual) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); int64_t nLastRetargetTime = 1279008237; // Block #66528 CBlockIndex pindexLast; pindexLast.nHeight = 68543; pindexLast.nTime = 1279297671; // Block #68543 pindexLast.nBits = 0x1c05a3f4; BOOST_CHECK_EQUAL( CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, params), 0x1c0168fd); } /* Test the constraint on the upper bound for actual time taken */ BOOST_AUTO_TEST_CASE(get_next_work_upper_limit_actual) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); int64_t nLastRetargetTime = 1263163443; // NOTE: Not an actual block time CBlockIndex pindexLast; pindexLast.nHeight = 46367; pindexLast.nTime = 1269211443; // Block #46367 pindexLast.nBits = 0x1c387f6f; BOOST_CHECK_EQUAL( CalculateNextWorkRequired(&pindexLast, nLastRetargetTime, params), 0x1d00e1fd); } BOOST_AUTO_TEST_CASE(GetBlockProofEquivalentTime_test) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); std::vector blocks(10000); for (int i = 0; i < 10000; i++) { blocks[i].pprev = i ? &blocks[i - 1] : nullptr; blocks[i].nHeight = i; blocks[i].nTime = 1269211443 + i * params.nPowTargetSpacing; blocks[i].nBits = 0x207fffff; /* target 0x7fffff000... */ blocks[i].nChainWork = - i ? blocks[i - 1].nChainWork + GetBlockProof(blocks[i - 1]) + i ? blocks[i - 1].nChainWork + GetBlockProof(blocks[i]) : arith_uint256(0); } for (int j = 0; j < 1000; j++) { CBlockIndex *p1 = &blocks[GetRand(10000)]; CBlockIndex *p2 = &blocks[GetRand(10000)]; CBlockIndex *p3 = &blocks[GetRand(10000)]; int64_t tdiff = GetBlockProofEquivalentTime(*p1, *p2, *p3, params); BOOST_CHECK_EQUAL(tdiff, p1->GetBlockTime() - p2->GetBlockTime()); } } static CBlockIndex GetBlockIndex(CBlockIndex *pindexPrev, int64_t nTimeInterval, uint32_t nBits) { CBlockIndex block; block.pprev = pindexPrev; block.nHeight = pindexPrev->nHeight + 1; block.nTime = pindexPrev->nTime + nTimeInterval; block.nBits = nBits; + block.nChainWork = pindexPrev->nChainWork + GetBlockProof(block); return block; } BOOST_AUTO_TEST_CASE(retargeting_test) { SelectParams(CBaseChainParams::MAIN); const Consensus::Params ¶ms = Params().GetConsensus(); std::vector blocks(115); const arith_uint256 powLimit = UintToArith256(params.powLimit); arith_uint256 currentPow = powLimit >> 1; uint32_t initialBits = currentPow.GetCompact(); - // Genesis block? + // Genesis block. blocks[0] = CBlockIndex(); blocks[0].nHeight = 0; blocks[0].nTime = 1269211443; blocks[0].nBits = initialBits; + blocks[0].nChainWork = GetBlockProof(blocks[0]); + // Pile up some blocks. for (size_t i = 1; i < 100; i++) { blocks[i] = GetBlockIndex(&blocks[i - 1], params.nPowTargetSpacing, initialBits); } CBlockHeader blkHeaderDummy; // We start getting 2h blocks time. For the first 5 blocks, it doesn't // matter as the MTP is not affected. For the next 5 block, MTP difference // increases but stays below 12h. for (size_t i = 100; i < 110; i++) { blocks[i] = GetBlockIndex(&blocks[i - 1], 2 * 3600, initialBits); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[i], &blkHeaderDummy, params), initialBits); } // Now we expect the difficulty to decrease. blocks[110] = GetBlockIndex(&blocks[109], 2 * 3600, initialBits); currentPow.SetCompact(currentPow.GetCompact()); currentPow += (currentPow >> 2); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[110], &blkHeaderDummy, params), currentPow.GetCompact()); // As we continue with 2h blocks, difficulty continue to decrease. blocks[111] = GetBlockIndex(&blocks[110], 2 * 3600, currentPow.GetCompact()); currentPow.SetCompact(currentPow.GetCompact()); currentPow += (currentPow >> 2); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[111], &blkHeaderDummy, params), currentPow.GetCompact()); // We decrease again. blocks[112] = GetBlockIndex(&blocks[111], 2 * 3600, currentPow.GetCompact()); currentPow.SetCompact(currentPow.GetCompact()); currentPow += (currentPow >> 2); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[112], &blkHeaderDummy, params), currentPow.GetCompact()); // We check that we do not go below the minimal difficulty. blocks[113] = GetBlockIndex(&blocks[112], 2 * 3600, currentPow.GetCompact()); currentPow.SetCompact(currentPow.GetCompact()); currentPow += (currentPow >> 2); BOOST_CHECK(powLimit.GetCompact() != currentPow.GetCompact()); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[113], &blkHeaderDummy, params), powLimit.GetCompact()); // Once we reached the minimal difficulty, we stick with it. blocks[114] = GetBlockIndex(&blocks[113], 2 * 3600, powLimit.GetCompact()); BOOST_CHECK(powLimit.GetCompact() != currentPow.GetCompact()); BOOST_CHECK_EQUAL( GetNextWorkRequired(&blocks[114], &blkHeaderDummy, params), 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; + + blocks[0].nChainWork = GetBlockProof(blocks[0]); + + // 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 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); + } + + // Make sure we skip over blocks that are out of wack. To do so, we produce + // a block that is far in the future, and then produce a block with the + // expected timestamp. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + blocks[i] = GetBlockIndex(&blocks[i - 1], 2 * 600 - 6000, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + + // The system should continue unaffected by the block with a bogous + // timestamps. + for (size_t j = 0; j < 20; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 600, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params), + nBits); + } + + // We start emitting blocks slightly faster. The first block has no impact. + blocks[i] = GetBlockIndex(&blocks[i - 1], 550, nBits); + BOOST_CHECK_EQUAL( + GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params), nBits); + + // Now we should see difficulty increase slowly. + for (size_t j = 0; j < 10; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 550, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + arith_uint256 currentTarget; + currentTarget.SetCompact(nBits); + arith_uint256 nextTarget; + nextTarget.SetCompact(nextBits); + + // Make sure that difficulty increases very slowly. + BOOST_CHECK(nextTarget < currentTarget); + BOOST_CHECK((currentTarget - nextTarget) < (currentTarget >> 10)); + + nBits = nextBits; + } + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0fe7b1); + + // 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); + const uint32_t 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, 0x1c0db19f); + + // We start to emit blocks significantly slower. The first block has no + // impact. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + nBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + + // Check the actual value. + BOOST_CHECK_EQUAL(nBits, 0x1c0d9222); + + // If we dramatically slow down block production, difficulty decreases. + for (size_t j = 0; j < 93; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t 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. + BOOST_CHECK_EQUAL(nBits, 0x1c2f13b9); + + // Due to the window of time being bounded, next block's difficulty actually + // gets harder. + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + nBits = GetNextCashWorkRequired(&blocks[i++], &blkHeaderDummy, params); + BOOST_CHECK_EQUAL(nBits, 0x1c2ee9bf); + + // And goes down again. It takes a while due to the window being bounded and + // the skewed block causes 2 blocks to get out of the window. + for (size_t j = 0; j < 192; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t 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. + BOOST_CHECK_EQUAL(nBits, 0x1d00ffff); + + // Once the difficulty reached the minimum allowed level, it doesn't get any + // easier. + for (size_t j = 0; j < 5; i++, j++) { + blocks[i] = GetBlockIndex(&blocks[i - 1], 6000, nBits); + const uint32_t nextBits = + GetNextCashWorkRequired(&blocks[i], &blkHeaderDummy, params); + + // Check the difficulty stays constant. + BOOST_CHECK_EQUAL(nextBits, powLimitBits); + nBits = nextBits; + } +} + BOOST_AUTO_TEST_SUITE_END()