CVE-2012-2459 , possible code and performance improvement, is my logic correct?

Question

ok so, in my effort to create a fullnode from scratch both for learning purpose and need (not a topic for discussion, thanks), I was looking at the code that check Merkle Root to not be vulnerable to CVE-2012-2459.

That vulnerability basically allows you to create a block that has a valid merkle root but contains duplicate transactions, causing a node that receive such block before the correct one, to be stuck on a fork (because that block will be flagged as incorrect and having the same hash of a correct block will prevent the node to ask again for that block, causing a node to be stuck.

Anyway, this is an old CVE that was fixed back in 2012 and code changed during time. Now in bitcoin core the code is not that pretty and the method to compute merkle root are polluted from a boolean parameter that when read back reflects if the block has been mutated (malleated) or not.

The code is this

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

now thinking about the problem, I think I found a better approach that is O(log n) and way better both in readability and speed... if it works and the logic isn't flawled... so I'd like to know your thought about this. my paint skill can show you some of the logic:

A, B, C... etc... are transactions

the vertical line is what I call "safe point", basically all transactions before that safe point are guaranteed to be not duplicable (this is one of the assumption I do and one thing to check if it's correct)

then, based on how merkle root is computed and how the CVE uses that to do nasty things, you can see some example of malleated blocks

I created then a gist, containing a LINQPad code that can be run as it is and produce outputs to see if the logc is correct and can spot malleated blocks.

https://gist.github.com/MithrilMan/27985e4f5bcc3853e792aa39631b9647

this is an output example of that gist

The core logic relies into checking the last transaction against the previous, moving exponentially to the left at each iteration (see the picture with the vertical blue arrows showing which element it checks, or see the linqpad result where it's explicitly detailed)

I handle both the cases where the tx count is even or odd. To me it seems to work but would like to have some more eyes on that to see if the logic sounds correct or not. Note how for 9000 tx I have just to compare 14 transactions instead of thousands like current bitcoin code is doing. Apart from that in my case it has another pros that allow me to split the markle computation and markle cve check in two different places, without having to use a solution like that mutated boolean parameter

UPDATE for those of you not having LINQPad I adapted the POC script to be run on dotnetfiddle here for those who doesn't have linqpad I adapted the script to be run on dotnetfiddle here

https://dotnetfiddle.net/wT87D2

Answer 1

Trigger warning: I'm not about to be nice. Because this code is responsible for my elevated blood pressure.

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

'First thing I notice is the function signature.

uint256 That's 32 Bytes (octets) that's the size of your whole data cache on x86-64. And it's obtained by (dereferencing) using the first element of the vector of cache misses (or uint256, you pick the name you prefer). The one time a pointer would have sufficed… (It's ok…)

bool* Indicates the return type is wrong. In fact, I know what's wrong with all of this… It's not a member function to the TYPE that is a vector<char[32]>…

It's the tree, isn't it? Or rather "the latest branch of the[…]"

if (mutated) That doesn't check if anything mutated. That if statement should be taken out and shot. That checks if the bool* mutated is nullptr which it will rarely be. (And it SHALL NOT become nullptr inside this function. Otherwise, you have a data race and you can stop reading here because the rest is UB.)

if (hashes.size() & 1) If the size is odd, sure. How many times are we going to call that function to check if the size that so far hasn't changed? (Still the first iteration of this…  hashes.push_back(hashes.back()); 🙄 Think about this… 

We just did:

while (hashes.size() > 1) { // First check of size. 
  if (mutated) { // It's not `nullptr`. 
     // You SHOULDN'T pass a bool as a raw pointer.
     // FOR GOD SAKE.
     
    for (size_t // size_t is unsigned.
         pos = 0; // using auto you wouldn't have the problem of: 
// EVERY SINGLE loop iteration you will be checking for overflow. 
// I can tell you right away overflow is impossible in this case.
// But since the code that is coming up is so wrong… 
         pos + 1 < hashes.size(); // THIS HAS TO BE A JOKE. 
         pos += 2) 
    {
             if (hashes[pos] == hashes[pos + 1]) mutation = true; // WHY?
// And now we're looping over the whole vector. 
// Continually setting mutation to true.
// EVERY ITERATION will cause a cache miss 
//  [if the optimizer wasn't able to optimize this… 
//   (And it wasn't. The code is just wrong)].
// Every time we re-enter the while loop,
// because cache misses are slow,
// AND since you CANNOT reorder a LOAD with a STORE.
// It will waste time. `mutation = true` this is unbelievably costly on arm.


// This is a polynomial-time implementation of an algorithm which
// SHOULD be IN THE WORST CASE linear in time.

     } // for (slow; slow; fine) cache miss; cache miss; store; recurse…
  } // if (some pointer to a bool is not `nullptr`. 
    // Which is constant over the whole [dis]function)
  if (hashes.size() & 1) { // currently false for vector of size 2.
// You'll not that we never bothered to check if the size was 2. NB: Θ(1)
    hashes.push_back(hashes.back()); // more cache misses. 
// And potentially a new allocation of an object of obscene length. 
// At this point it's just intentional. 
// Nobody is that good at randomly deoptimizing code.
// Fun fact: hashes can be hashed.
// I'm pretty sure you could hash your uint256 with 2 hash functions, 
// then simply xor with the other hashes of hashes (😎),
// then if, and only if ONE of the sets of 2 hashes(of a hash) mismatches
// you would bother checking the whole. 'should be Θ(n^2) worst case.
// A cache miss from L1 to L2 is a lil' bad. 
// L2 to L3 is already very bad. 
// L3 to ram? 
// Better write it in Java it will have a higher throughput with a well-tuned GC. 
   }

I don't care what the rest does. It's just too slow as it is. return hashes[0]; may not even be NRVOed…

I looked at your code. It's nice, you're doing a clz, we only just got that in C++ in C++20 with bitcast, so we could integrate something similar. And by "we" I mean… Does nobody think it could be interesting to, now that concept has proven to generate public interest, start again with a "blankish" slate… 

Hint: the bitcoin network is essentially the biggest decentralized neural network, that I know of. I'm not sure you people realize that. The complexity doesn't have to be artificial. It was just like that to prove the concept. We've done that.

Nitpick: uint safePoint = ((uint)Math.Pow(2, higherBitPosition)); Isn't that just a binary left shift on 1 by higherBitPosition? 🤔 (it is. For higherBitPosition any Natural up to (excluding) the largest register width) Though floating-point pow is also 1 instruction, in this case it's slower (for integer powers of 2), otherwise, it's a perfect job for a gpu.