From eece63fa72566068cb2a1bf85c95a72a5ba59bc9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 17 Nov 2015 17:35:44 +0100 Subject: Switch blocks to a constant-space Merkle root/branch algorithm. This switches the Merkle tree logic for blocks to one that runs in constant (small) space. The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations: * Verifies that the old code and new code agree for the Merkle root. * Verifies that the old code and new code agree for the Merkle branch. * Verifies that the computed Merkle branch is valid. * Verifies that mutations don't change the Merkle root. * Verifies that mutations are correctly detected. --- src/primitives/block.cpp | 63 ------------------------------------------------ 1 file changed, 63 deletions(-) (limited to 'src/primitives/block.cpp') 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 vMerkleTree; - vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. - for (std::vector::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; -- cgit v1.2.3