diff options
| -rw-r--r-- | src/core.cpp | 53 | ||||
| -rw-r--r-- | src/core.h | 6 | ||||
| -rw-r--r-- | src/main.cpp | 15 |
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); |