| 16 | } |
| 17 | |
| 18 | uint256 CBlock::BuildMerkleTree(bool* fMutated) const |
| 19 | { |
| 20 | /* WARNING! If you're reading this because you're learning about crypto |
| 21 | and/or designing a new system that will use merkle trees, keep in mind |
| 22 | that the following merkle tree algorithm has a serious flaw related to |
| 23 | duplicate txids, resulting in a vulnerability (CVE-2012-2459). |
| 24 | |
| 25 | The reason is that if the number of hashes in the list at a given time |
| 26 | is odd, the last one is duplicated before computing the next level (which |
| 27 | is unusual in Merkle trees). This results in certain sequences of |
| 28 | transactions leading to the same merkle root. For example, these two |
| 29 | trees: |
| 30 | |
| 31 | A A |
| 32 | / \ / \ |
| 33 | B C B C |
| 34 | / \ | / \ / \ |
| 35 | D E F D E F F |
| 36 | / \ / \ / \ / \ / \ / \ / \ |
| 37 | 1 2 3 4 5 6 1 2 3 4 5 6 5 6 |
| 38 | |
| 39 | for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and |
| 40 | 6 are repeated) result in the same root hash A (because the hash of both |
| 41 | of (F) and (F,F) is C). |
| 42 | |
| 43 | The vulnerability results from being able to send a block with such a |
| 44 | transaction list, with the same merkle root, and the same block hash as |
| 45 | the original without duplication, resulting in failed validation. If the |
| 46 | receiving node proceeds to mark that block as permanently invalid |
| 47 | however, it will fail to accept further unmodified (and thus potentially |
| 48 | valid) versions of the same block. We defend against this by detecting |
| 49 | the case where we would hash two identical hashes at the end of the list |
| 50 | together, and treating that identically to the block having an invalid |
| 51 | merkle root. Assuming no double-SHA256 collisions, this will detect all |
| 52 | known ways of changing the transactions without affecting the merkle |
| 53 | root. |
| 54 | */ |
| 55 | vMerkleTree.clear(); |
| 56 | vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes. |
| 57 | for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it) |
| 58 | vMerkleTree.push_back(it->GetHash()); |
| 59 | int j = 0; |
| 60 | bool mutated = false; |
| 61 | for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2) |
| 62 | { |
| 63 | for (int i = 0; i < nSize; i += 2) |
| 64 | { |
| 65 | int i2 = std::min(i+1, nSize-1); |
| 66 | if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) { |
| 67 | // Two identical hashes at the end of the list at a particular level. |
| 68 | mutated = true; |
| 69 | } |
| 70 | vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]), END(vMerkleTree[j+i]), |
| 71 | BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2]))); |
| 72 | } |
| 73 | j += nSize; |
| 74 | } |
| 75 | if (fMutated) { |