Page MenuHomePhabricator
Differential D614 Diff 1580 src/consensus/merkle.cpp

Changeset View

Standalone View

View Options

src/consensus/merkle.cpp

// Copyright (c) 2015-2016 The Bitcoin Core developers // Copyright (c) 2015-2016 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying // Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include "merkle.h" #include "merkle.h"
#include "hash.h" #include "hash.h"
#include "utilstrencodings.h" #include "utilstrencodings.h"
/* WARNING! If you're reading this because you're learning about crypto /* 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 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 that the following merkle tree algorithm has a serious flaw related to
duplicate txids, resulting in a vulnerability (CVE-2012-2459). duplicate txhashes, resulting in a vulnerability (CVE-2012-2459).
The reason is that if the number of hashes in the list at a given time 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 odd, the last one is duplicated before computing the next level (which
is unusual in Merkle trees). This results in certain sequences of is unusual in Merkle trees). This results in certain sequences of
transactions leading to the same merkle root. For example, these two transactions leading to the same merkle root. For example, these two
trees: trees:
A A A A
▲ Show 20 Lines • Show All 150 Lines • ▼ Show 20 Linesuint256 ComputeMerkleRootFromBranch(const uint256 &leaf,
} }
return hash; return hash;
} }
uint256 BlockMerkleRoot(const CBlock &block, bool *mutated) { uint256 BlockMerkleRoot(const CBlock &block, bool *mutated) {
std::vector<uint256> leaves; std::vector<uint256> leaves;
leaves.resize(block.vtx.size()); leaves.resize(block.vtx.size());
for (size_t s = 0; s < block.vtx.size(); s++) { for (size_t s = 0; s < block.vtx.size(); s++) {
leaves[s] = block.vtx[s]->GetId(); leaves[s] = block.vtx[s]->GetHash();
} }
return ComputeMerkleRoot(leaves, mutated); return ComputeMerkleRoot(leaves, mutated);
} }
std::vector<uint256> BlockMerkleBranch(const CBlock &block, uint32_t position) { std::vector<uint256> BlockMerkleBranch(const CBlock &block, uint32_t position) {
std::vector<uint256> leaves; std::vector<uint256> leaves;
leaves.resize(block.vtx.size()); leaves.resize(block.vtx.size());
for (size_t s = 0; s < block.vtx.size(); s++) { for (size_t s = 0; s < block.vtx.size(); s++) {
leaves[s] = block.vtx[s]->GetId(); leaves[s] = block.vtx[s]->GetHash();
} }
return ComputeMerkleBranch(leaves, position); return ComputeMerkleBranch(leaves, position);
} }