Merkle Root for Block 100000: calculation in Excel

Question

I am stuck doing the calculations for the infamous block 100000. I am doing those in excel. I am trying to add as much detail here of the operation I am doing and intermediate results.

TX1: 8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87
TX2: fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4
TX3: 6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4
TX4: e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d

I byte swap those txids to little endian (text functions):

TX1: 876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c
TX2: c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff
TX3: c46e239ab7d28e2c019b6d66ad8fae98a56ef1f21aeecb94d1b1718186f05963
TX4: 1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9

I concatenate the little endian of the first two transactions: (text functions)

tx1 + tx2 = 876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff

I convert this 128 character hex string into a 512 binary string: (I concatenate a series of HEX2BIN(MID(concatenated,starting chars,2),8).

10000111011011011101000010100011111011110100101000101000000101101111111111010001110000010010101010110110010010011000001001011010100101011000101100001111111100111011101100111101011011110011111000010010010100001111000100111101110110111111000000010100100011001100010000000010100101111111011100110000110111010111101101011010100110010101011001111110101110001101001001111011011110000111010110001111011000000111010100000111110001010010001010010010110100000010110101000000001100011000100101011011010100101111001011111111

I do a sha256 of the above binary using fresle sha function (referenced here on SE). The result is:

c9aee68969373b4aecc87382fb2aa28276c6b9a9bfb6956615b4b29eb14d51d2

I convert this 64 hex string into a 256 binary string: (I concatenate a series of HEX2BIN(MID(concatenated,starting chars,2),8)

1100100110101110111001101000100101101001001101110011101101001010111011001100100001110011100000101111101100101010101000101000001001110110110001101011100110101001101111111011011010010101011001100001010110110100101100101001111010110001010011010101000111010010

I do a sha256 of the above binary using fresle sha function (referenced here on SE)

branch1= f2d117d431bf81ee1a18c12d8c6b2bb05fe0d63b86ca5f2d43b30781fdbd6583

I bet that you already spotted the error by now.

To complete I do all the above steps for the second two transactions (tx3 & tx4).

The result of the second sha round is:

branch2= 910dc8ac1c1373c0a22c74f4ba04fb0e0f45232e292227015400ca549ceec4ef

Now I redo all the above steps for branch1 + branch2, giving me:

eb834a22120b5195270085f999afed5c7f79351e0a8ac9f2d5b355495700cddb

I convert back to big endian:

dbcd00574955b3d5f2c98a0a1e35797f5cedaf99f985002795510b12224a83eb

This should be the merkle root, but it's not. What am I doing wrong?

Here the excel I used:

https://drive.google.com/file/d/1Qdy_PpUj4ZWLGBXCsSSBmQgTMhQITLVz

If I check my sha(hex) with anyahsh.com i get different result, while if i check sha(binary) i get the exact same result. The strange thing I double checked the hex=>bin conversion and it is correct, so I don't understand what's going wrong.

Answer 1

The SHA256 function that you are using in the excel sheet is hashing the binary as a text rather than using the bits from it. This results in the output of your excel function being different from the desired one. Below is a simple python script that will illustrate it to you.

import hashlib
string1 = '876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148cc40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff'
string2 = '10000111011011011101000010100011111011110100101000101000000101101111111111010001110000010010101010110110010010011000001001011010100101011000101100001111111100111011101100111101011011110011111000010010010100001111000100111101110110111111000000010100100011001100010000000010100101111111011100110000110111010111101101011010100110010101011001111110101110001101001001111011011110000111010110001111011000000111010100000111110001010010001010010010110100000010110101000000001100011000100101011011010100101111001011111111'

hashlib.sha256(bytes.fromhex(string1)).hexdigest()
>>> 'cd93fc352d3b9f27392b3052c61190609fdc80194ade62771ce9588808980be9'

hashlib.sha256(string2.encode('utf-8')).hexdigest()
>>> 'c9aee68969373b4aecc87382fb2aa28276c6b9a9bfb6956615b4b29eb14d51d2'

The first output is the actual one you should get from the first round of hashing. The second output is the one that you are getting from the excel function. That is because you are hashing that binary in the same way as hashing a string like 'hello world'.