默克尔树的重复交易攻击

Posted on |

什么是bmt

bmt的全称是Binary Merkle Tree, 是一种二叉的默克尔树，他具有如下的特点：

  • 是一棵二叉树
  • 叶子节点的数据是自定义的，在比特币中既是交易的hash
  • 非叶子节点的值是由他的左儿子和右儿子进行组合后hash后得到的

bmt的作用主要是用于验证数据，对于一个bmt包含的交易，只需要验证根节点的hash，如果根节点的hash数据正确，那么整个bmt所对应的交易都是正确的，可以方便存储和做一些轻节点的验证

为什么会被重复交易攻击

这里就要牵涉到比特币中bmt实现的机制了，代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
    bool mutation = false;
    while (hashes.size() > 1) {
        if (mutated) {
            for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
                // 此处就在校验我们的重复交易攻击了
                if (hashes[pos] == hashes[pos + 1]) mutation = true;
            }
        }
        if (hashes.size() & 1) {
            // 如果hash列表是奇数，则会重复插入尾部的值
            hashes.push_back(hashes.back());
        }
        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
        hashes.resize(hashes.size() / 2);
    }
    if (mutated) *mutated = mutation;
    if (hashes.size() == 0) return uint256();
    return hashes[0];
}

可以看到由于尾部的重复插入，会导致比特币对于如下两种默克尔树是完全无法验证的，因为是一样的。

1
2
3
4
5
6
7
8
在比特币中相同的默克尔树
                   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

可以看到，右侧的树在叶子节点上重复出现了5，6两个交易，但是这两种交易得到的默克尔树的根节点确是一样的。

如何解决

因为每个叶子节点都是交易的hash，那如果要实现这样的重复交易攻击，必然交易的txid必须是一样的。因此比特币是在验证默克尔树的时候就做了处理，剔除了每个块中txid一样的交易，从源头上保证了这样的默克尔树不会产生。

1
2
if (mutated)
            return state.DoS(100, false, REJECT_INVALID, "bad-txns-duplicate", true, "duplicate transaction");