diff options
Diffstat (limited to 'src/primitives')
| -rw-r--r-- | src/primitives/block.cpp | 63 | ||||
| -rw-r--r-- | src/primitives/block.h | 6 |
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; }; |