diff options
Diffstat (limited to 'src/consensus')
| -rw-r--r-- | src/consensus/consensus.h | 7 | ||||
| -rw-r--r-- | src/consensus/merkle.cpp | 103 | ||||
| -rw-r--r-- | src/consensus/merkle.h | 10 | ||||
| -rw-r--r-- | src/consensus/params.h | 5 |
4 files changed, 125 insertions, 0 deletions
diff --git a/src/consensus/consensus.h b/src/consensus/consensus.h index 384f70bc10..cffe9cdafd 100644 --- a/src/consensus/consensus.h +++ b/src/consensus/consensus.h @@ -27,4 +27,11 @@ static const size_t MIN_SERIALIZABLE_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * /** Interpret sequence numbers as relative lock-time constraints. */ static constexpr unsigned int LOCKTIME_VERIFY_SEQUENCE = (1 << 0); +/** + * Maximum number of seconds that the timestamp of the first + * block of a difficulty adjustment period is allowed to + * be earlier than the last block of the previous period (BIP94). + */ +static constexpr int64_t MAX_TIMEWARP = 600; + #endif // BITCOIN_CONSENSUS_CONSENSUS_H diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp index af01902c92..dc32f0ab80 100644 --- a/src/consensus/merkle.cpp +++ b/src/consensus/merkle.cpp @@ -83,3 +83,106 @@ uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated) return ComputeMerkleRoot(std::move(leaves), mutated); } +/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ +static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) { + if (pbranch) pbranch->clear(); + if (leaves.size() == 0) { + if (pmutated) *pmutated = false; + if (proot) *proot = uint256(); + return; + } + bool mutated = false; + // count is the number of leaves processed so far. + uint32_t count = 0; + // inner is an array of eagerly computed subtree hashes, indexed by tree + // level (0 being the leaves). + // For example, when count is 25 (11001 in binary), inner[4] is the hash of + // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to + // the last leaf. The other inner entries are undefined. + uint256 inner[32]; + // Which position in inner is a hash that depends on the matching leaf. + int matchlevel = -1; + // First process all leaves into 'inner' values. + while (count < leaves.size()) { + uint256 h = leaves[count]; + bool matchh = count == branchpos; + count++; + int level; + // For each of the lower bits in count that are 0, do 1 step. Each + // corresponds to an inner value that existed before processing the + // current leaf, and each needs a hash to combine it. + for (level = 0; !(count & ((uint32_t{1}) << level)); level++) { + if (pbranch) { + if (matchh) { + pbranch->push_back(inner[level]); + } else if (matchlevel == level) { + pbranch->push_back(h); + matchh = true; + } + } + mutated |= (inner[level] == h); + h = Hash(inner[level], h); + } + // Store the resulting hash at inner position level. + inner[level] = h; + if (matchh) { + matchlevel = level; + } + } + // Do a final 'sweep' over the rightmost branch of the tree to process + // odd levels, and reduce everything to a single top value. + // Level is the level (counted from the bottom) up to which we've sweeped. + int level = 0; + // As long as bit number level in count is zero, skip it. It means there + // is nothing left at this level. + while (!(count & ((uint32_t{1}) << level))) { + level++; + } + uint256 h = inner[level]; + bool matchh = matchlevel == level; + while (count != ((uint32_t{1}) << level)) { + // If we reach this point, h is an inner value that is not the top. + // We combine it with itself (Bitcoin's special rule for odd levels in + // the tree) to produce a higher level one. + if (pbranch && matchh) { + pbranch->push_back(h); + } + h = Hash(h, h); + // Increment count to the value it would have if two entries at this + // level had existed. + count += ((uint32_t{1}) << level); + level++; + // And propagate the result upwards accordingly. + while (!(count & ((uint32_t{1}) << level))) { + if (pbranch) { + if (matchh) { + pbranch->push_back(inner[level]); + } else if (matchlevel == level) { + pbranch->push_back(h); + matchh = true; + } + } + h = Hash(inner[level], h); + level++; + } + } + // Return result. + if (pmutated) *pmutated = mutated; + if (proot) *proot = h; +} + +static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) { + std::vector<uint256> ret; + MerkleComputation(leaves, nullptr, nullptr, position, &ret); + return ret; +} + +std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position) +{ + std::vector<uint256> leaves; + leaves.resize(block.vtx.size()); + for (size_t s = 0; s < block.vtx.size(); s++) { + leaves[s] = block.vtx[s]->GetHash(); + } + return ComputeMerkleBranch(leaves, position); +} diff --git a/src/consensus/merkle.h b/src/consensus/merkle.h index 4ae5a5b897..363f68039c 100644 --- a/src/consensus/merkle.h +++ b/src/consensus/merkle.h @@ -24,4 +24,14 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = nullptr); */ uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated = nullptr); +/** + * Compute merkle path to the specified transaction + * + * @param[in] block the block + * @param[in] position transaction for which to calculate the merkle path, defaults to coinbase + * + * @return merkle path ordered from the deepest + */ +std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position = 0); + #endif // BITCOIN_CONSENSUS_MERKLE_H diff --git a/src/consensus/params.h b/src/consensus/params.h index 25f53eb620..dd29b9408e 100644 --- a/src/consensus/params.h +++ b/src/consensus/params.h @@ -108,6 +108,11 @@ struct Params { /** Proof of work parameters */ uint256 powLimit; bool fPowAllowMinDifficultyBlocks; + /** + * Enforce BIP94 timewarp attack mitigation. On testnet4 this also enforces + * the block storm mitigation. + */ + bool enforce_BIP94; bool fPowNoRetargeting; int64_t nPowTargetSpacing; int64_t nPowTargetTimespan; |