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:
![[12:37]](https://i.stack.imgur.com/b6BuM.png)
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
