Checking the Merkle Root for Block #100000

Question

The below text is copied from the Bitcoin Developer Reference at bitcoin.org:

If a block has three or more transactions, intermediate merkle tree rows are formed. The TXIDs are placed in order and paired, starting with the coinbase transaction’s TXID. Each pair is concatenated together as 64 raw bytes and SHA256(SHA256()) hashed to form a second row of hashes. If there are an odd (non-even) number of TXIDs, the last TXID is concatenated with a copy of itself and hashed. If there are more than two hashes in the second row, the process is repeated to create a third row (and, if necessary, repeated further to create additional rows). Once a row is obtained with only two hashes, those hashes are concatenated and hashed to produce the merkle root.

I'm trying to use this logic to recreate the merkle root for block #100000. There are 4 transactions in this block. I start by copying the transaction hash for the coinbase transaction and the one following back-to-back into a Sha256 calculator to get the hash. Then I hash that hash one more time: Sha256(sha256()). I repeat that procedure one more time with the second two transactions in the block. Finally, I repeat the procedure again using the resulting hashes to obtain the Merkle Root. Unfortunately, this doesn't tie to the Merkle Root shown in the block header at blockchain.info.

Can someone explain where I went wrong?

Thanks.

Answer 1

You have to byte-swap the transaction ID's before hashing them, hash each child node, and byte-swap the final hashed hex value.

Transaction 1 (Coibase Transaction) 8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87

To Byteswap it you can use:

a = "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87" "".join(reversed([a[i:i+2] for i in range(0, len(a), 2)])) @Greg Hewgill

Byteswapped = 876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c

Transaction 2 fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4 Byteswapped = c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff

You want to concatenate the byte-swapped transaction values of 1 and 2. Transaction 1 goes first.

876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff

To hash this hex string you can use the following code running Python in your command terminal:

import hashlib

transaction12_hex = "876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff"

transaction12_bin = transaction12_hex.decode('hex')

hash = hashlib.sha256(hashlib.sha256(transaction12_bin).digest()).digest()

hash.encode('hex_codec')

15b88c5107195bf09eb9da89b83d95b3d070079a3c5c5d3d17d0dcd873fbdacc

Transaction 3 6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4 Byteswapped = c46e239ab7d28e2c019b6d66ad8fae98a56ef1f21aeecb94d1b1718186f05963

Transaction 4 e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d Byteswapped = 1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9

If you do the same thing for transaction 3 and 4 the final hash is: 49aef42d78e3e9999c9e6ec9e1dddd6cb880bf3b076a03be1318ca789089308e

Our last step is to combine the final hashed value of 1 & 2 and 3 & 4 and double hash it and byte-swap it.

Our answer is f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766 the Merkle Root.

Answer 2

I think the errors is the building the hash correctly and I was a same problem, now I want shared the my experience.

For build the hash I have used this good library c++/java.

I will try to explain myself with simple code.

This is the hash of transaction the genesis block

string versionRawTransaction = "01000000";
string numbarTransactionInput = "01";
string output = "0000000000000000000000000000000000000000000000000000000000000000ffffffff";
string scriptLenght = "4d";
string scriptSing = "04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73";
string sequences = "ffffffff";
string numbarTransactionOutput = "01";
string cAmmount = "00f2052a01000000";
string publicKeyScriptLenght = "43";
string publicKeyScript = "4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac";
string lockTime = "00000000";

The complete hash is 01000000010000000000000000000000000000000000000000000000000000000000000000FFFFFFFF4D04FFFF001D0104455468652054696D65732030332F4A616E2F32303039204368616E63656C6C6F72206F6E206272696E6B206F66207365636F6E64206261696C6F757420666F722062616E6B73FFFFFFFF0100F2052A01000000434104678AFDB0FE5548271967F1A67130B7105CD6A828E03909A67962E0EA1F61DEB649F6BC3F4CEF38C4F35504E51EC112DE5C384DF7BA0B8D578A4C702B6BF11D5FAC00000000

Whent you calculate the hash. can me get this hash 4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b

up to here everything is simple

The value bitcoin is converted to big endian convention but whent the hash is calculate the single type was converted to little endian.

Whi the real form transaction can me execute this passage

1. convert the value form big-endian to little-endian
2. Convert the value into Hex
3. join all the propieties hex form in the correcto order
4. Convert to the binary form the big string
5. Apply the sha256
6. convert the result to big-endian

I used the C++ and this operation they managed to do it thanks to the bitcoin libraries but if you used python you can use this example for calculate the hash.

to build the tree the steps are simple, just make sure you calculate the hash correctly, so I suggest you test first on the hash functions and then on the tree construction, to avoid unnecessary loss of time in trivial errors

ps: If you have the transaction script in raw format (if you read the information from the blk files) they are already converted to little-endian and therefore should not be converted any further. (depends on your deserialization process)