Vertcoin Basics: Computing Merkle Root Values

Looking at Crypto coins block explorers, I was wondering in the case of altcoins if the Merkle Root field is still computed the same way as in Bitcoin.

There’s already a lot of information on the general theory behind a Merkle Tree, so please refer to external sources for a better introduction. Here is instead a small worked example of how this applies to Bitcoin and as we will see, also Vertcoin.

QByteArray sha256d(QByteArray in)
{
QCryptographicHash hash (QCryptographicHash::Sha256);

hash.addData(in);

QByteArray res1 = hash.result();
hash.reset();
hash.addData(res1);

return hash.result();
}

This simple function computes the SHA256d hash of a byte array, as used everywhere in Bitcoin.

For the simple case where Tx count = 1, the Merkle root is simply the hash of the first transaction.

For a block with more transactions, let’s illustrate.

vertblock800019

a = 32e60eb21632597c1c1545c63fae57df8d4455648b7d97150b7dcee706749588
b = 1deed158ada568b9b193473095c8eb2cef2cffe60ccce15c3c82f599a09767a8

However there’s a bug with taking these values directly. It turns out Satoshi decided to flip the hash values for whatever arbitrary reason. We’ll need to unflip them to the correct endianness for our trees to grow correctly.

QByteArray reverse_hash (QByteArray in)
{
QByteArray res;
if (in.length() != 32) return QByteArray::fromHex(“”);

for (int i = 0; i < 32; ++i)
{
res.append(in[31 – i]);
}

return res;
}

Applying this, we now get:

a’ = 88957406e7ce7d0b15977d8b6455448ddf57ae3fc645151c7c593216b20ee632
b’ = a86797a099f5823c5ce1cc0ce6ff2cef2cebc895304793b1b968a5ad58d1ee1d

Then from theory we know that in our case, Root = Hash ( A | B).

Compute this, flip the bytes again, and you get the correct Merkle root as displayed in the explorer.

QByteArray c = a + b;
QByteArray m = sha256d( c );
m = reverse_hash(m);

For blocks with more transactions, repeat this process by merging more pairs.

Conclusion

The same process is used for both Bitcoin and Vertcoin, as well as probably a lot of other alts. Displayed hash values are byte-flipped around.

Since WordPress is not very good at displaying inline C++, here is the complete code example.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s