1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2014 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include "primitives/block.h"
#include "hash.h"
#include "tinyformat.h"
#include "utilstrencodings.h"
#include "crypto/common.h"
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;
s << strprintf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%u)\n",
GetHash().ToString(),
nVersion,
hashPrevBlock.ToString(),
hashMerkleRoot.ToString(),
nTime, nBits, nNonce,
vtx.size());
for (unsigned int i = 0; i < vtx.size(); i++)
{
s << " " << vtx[i].ToString() << "\n";
}
return s.str();
}
|
