Bitcoin full node and query server

Apr 12, 2024

View in context in the libbitcoin Slack #general mirror.

evoskuil01:54

We didn't hold the weekly today, so here's a quick update on my end. I was in London for a few days, home for a day, and then in FL for a few days. Managed to get some work done though. As you saw above, I was working out the algorithm to accurately detect malleability, which I haven't found anywhere. Core doesn't have it right and then interleave it with Merkle tree computation. Despite this complexity it's far less efficient. Their algorithm is:

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) {
            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];
}

It's confusing but if *mutated starts true then it attempts to set mutation and then returns that back in the *mutated in/out parameter. As you can see, for each row of Merkle computation it compares all hashes in the row as pairs - even though only the last pair can cause mutation. And that only happens on odd count rows - as a result of the push_back(hashes.back()) statement. And that can only result when the log2(count) of the duplicated hashes equals the depth of the first odd row. So clearly there is a lot of extra iteration and comparison happening.