aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/core.cpp53
-rw-r--r--src/core.h6
-rw-r--r--src/main.cpp15
3 files changed, 57 insertions, 17 deletions
diff --git a/src/core.cpp b/src/core.cpp
index 1489d77bb3..380b1c38e0 100644
--- a/src/core.cpp
+++ b/src/core.cpp
@@ -224,29 +224,66 @@ uint256 CBlockHeader::GetHash() const
return Hash(BEGIN(nVersion), END(nNonce));
}
-uint256 CBlock::BuildMerkleTree() const
+uint256 CBlock::BuildMerkleTree(bool* fMutated) const
{
- // WARNING! If you're reading this because you're learning about crypto
- // and/or designing a new system that will use merkle trees, keep in mind
- // that the following merkle tree algorithm has a serious flaw related to
- // duplicate txids, resulting in a vulnerability. (CVE-2012-2459) Bitcoin
- // has since worked around the flaw, but for new applications you should
- // use something different; don't just copy-and-paste this code without
- // understanding the problem first.
+ /* WARNING! If you're reading this because you're learning about crypto
+ and/or designing a new system that will use merkle trees, keep in mind
+ that the following merkle tree algorithm has a serious flaw related to
+ duplicate txids, resulting in a vulnerability (CVE-2012-2459).
+
+ The reason is that if the number of hashes in the list at a given time
+ is odd, the last one is duplicated before computing the next level (which
+ is unusual in Merkle trees). This results in certain sequences of
+ transactions leading to the same merkle root. For example, these two
+ trees:
+
+ A A
+ / \ / \
+ B C B C
+ / \ | / \ / \
+ D E F D E F F
+ / \ / \ / \ / \ / \ / \ / \
+ 1 2 3 4 5 6 1 2 3 4 5 6 5 6
+
+ for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
+ 6 are repeated) result in the same root hash A (because the hash of both
+ of (F) and (F,F) is C).
+
+ The vulnerability results from being able to send a block with such a
+ transaction list, with the same merkle root, and the same block hash as
+ the original without duplication, resulting in failed validation. If the
+ receiving node proceeds to mark that block as permanently invalid
+ however, it will fail to accept further unmodified (and thus potentially
+ valid) versions of the same block. We defend against this by detecting
+ the case where we would hash two identical hashes at the end of the list
+ together, and treating that identically to the block having an invalid
+ merkle root. Assuming no double-SHA256 collisions, this will detect all
+ known ways of changing the transactions without affecting the merkle
+ root.
+ */
vMerkleTree.clear();
+ vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
BOOST_FOREACH(const CTransaction& tx, vtx)
vMerkleTree.push_back(tx.GetHash());
int j = 0;
+ bool mutated = false;
for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
for (int i = 0; i < nSize; i += 2)
{
int i2 = std::min(i+1, nSize-1);
+ if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
+ // Two identical hashes at the end of the list at a particular level.
+ mutated = true;
+ }
vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]), END(vMerkleTree[j+i]),
BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
}
j += nSize;
}
+ if (fMutated) {
+ *fMutated = mutated;
+ }
return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}
diff --git a/src/core.h b/src/core.h
index e8435c8b0d..a348293578 100644
--- a/src/core.h
+++ b/src/core.h
@@ -529,7 +529,11 @@ public:
return block;
}
- uint256 BuildMerkleTree() const;
+ // Build the in-memory merkle tree for this block and return the merkle root.
+ // If non-NULL, *mutated is set to whether mutation was detected in the merkle
+ // tree (a duplication of transactions in the block leading to an identical
+ // merkle root).
+ uint256 BuildMerkleTree(bool* mutated = NULL) const;
std::vector<uint256> GetMerkleBranch(int nIndex) const;
static uint256 CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex);
diff --git a/src/main.cpp b/src/main.cpp
index 5a5c700574..32393e5e03 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -2236,13 +2236,12 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
if (!CheckTransaction(tx, state))
return error("CheckBlock() : CheckTransaction failed");
- // Check for duplicate txids. This is caught by ConnectInputs(),
- // but catching it earlier avoids a potential DoS attack:
- set<uint256> uniqueTx;
- BOOST_FOREACH(const CTransaction &tx, block.vtx) {
- uniqueTx.insert(tx.GetHash());
- }
- if (uniqueTx.size() != block.vtx.size())
+ // Check for merkle tree malleability (CVE-2012-2459): repeating sequences
+ // of transactions in a block without affecting the merkle root of a block,
+ // while still invalidating it.
+ bool mutated;
+ uint256 hashMerkleRoot2 = block.BuildMerkleTree(&mutated);
+ if (mutated)
return state.DoS(100, error("CheckBlock() : duplicate transaction"),
REJECT_INVALID, "bad-txns-duplicate", true);
@@ -2256,7 +2255,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
REJECT_INVALID, "bad-blk-sigops", true);
// Check merkle root
- if (fCheckMerkleRoot && block.hashMerkleRoot != block.BuildMerkleTree())
+ if (fCheckMerkleRoot && block.hashMerkleRoot != hashMerkleRoot2)
return state.DoS(100, error("CheckBlock() : hashMerkleRoot mismatch"),
REJECT_INVALID, "bad-txnmrklroot", true);