aboutsummaryrefslogtreecommitdiff
path: root/src/primitives
diff options
context:
space:
mode:
Diffstat (limited to 'src/primitives')
-rw-r--r--src/primitives/block.cpp63
-rw-r--r--src/primitives/block.h6
2 files changed, 0 insertions, 69 deletions
diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp
index 7a58074d24..7280c18f77 100644
--- a/src/primitives/block.cpp
+++ b/src/primitives/block.cpp
@@ -15,69 +15,6 @@ uint256 CBlockHeader::GetHash() const
return SerializeHash(*this);
}
-uint256 CBlock::ComputeMerkleRoot(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).
-
- 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.
- */
- std::vector<uint256> vMerkleTree;
- vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
- for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
- vMerkleTree.push_back(it->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() ? uint256() : vMerkleTree.back());
-}
-
std::string CBlock::ToString() const
{
std::stringstream s;
diff --git a/src/primitives/block.h b/src/primitives/block.h
index 54731ff557..5c017d436f 100644
--- a/src/primitives/block.h
+++ b/src/primitives/block.h
@@ -118,12 +118,6 @@ public:
return block;
}
- // Build the 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 ComputeMerkleRoot(bool* mutated = NULL) const;
-
std::string ToString() const;
};