Merkle Tree example

[ThePiachu]

I`m trying to program some Bitcoin functions and I`m currently stuck on Merkle Trees. I have the whole structure implemented, but I'm not sure if my results are correct. The only example of inputs and outputs of a Merkle Tree I can find for Bitcoin are here:
https://en.bitcoin.it/wiki/Dump_format#CBlock
given the inputs:
2d7f4d
3407a8
5edf5a
65c356
89aa32
e3e69c

my tree produces the following outputs:
49077d9f111495a68ee83b0a957cdbf23d3429358a219581faed8380f857c176
7b3aed86534e6195d67a106fee36cbbfe3e0d440d802d77d63b6a39a8777fdec
87fb3a4169f54593cd177376a6c2628996059cfb07f3ea6e2ca2d4fdd16073e7

58714118c458c33a9383518edee1d70e1e43a0984c8c5f2a610e8b513de544dc
0cdee207129aaeee382580d6a0326e865450acff847e46f424dc18553bfb548c

and the root is:
31a87e51bf34a495713016846bcc668ced0b448c7030fffe92d9a637609154b1

whereas I should get
8ebc6a
d5e414
89b77c

d1074c
70a4e6

e81287

which aren't even of the same size. What I`m getting looks like the proper output of a double hash (https://en.bitcoin.it/wiki/Protocol_specification#Hashes), and I`ve tested my hashing against the examples and got the same results. Am I missing some important step here?

[1715558437]

1715558437

[1715558437]

1715558437

[ThePiachu]

Okay, noticed that the hashes were truncated in the example. I still am having some problems with the hashing though:
I`ve used some hashes from http://blockexplorer.com/rawblock/000000000000a85d42610b292d2baebe54ff0c854847fe3d2ca37ac7d6e46b99

Example inputs:

Ina: 3a459eab5f0cf8394a21e04d2ed3b2beeaa59795912e20b9c680e9db74dfb18c
Inb: be38f46f0eccba72416aed715851fd07b881ffb7928b7622847314588e06a6b7

First round of SHA hashing:

H1 v1: 3e4d8b84960b6b018ae65f10f60a58a56f49bdbd3cca0a3f927b0e9eddb49648
H2 v1: 34bf5e40c9680e329810108e419264a1379013f3b7a50c8595e4c7f1d15a766e

Second round of SHA hashing:

H1 v2: 87640ed02464776c31547f05c58ea95b87998aa4469fd991245988e715d6a75b
H2 v2: 290a0693e21299051e40419244c3d581620495beddec11471fd157c4f8e5f2d7

Concatenated string (H1+H2):
87640ed02464776c31547f05c58ea95b87998aa4469fd991245988e715d6a75b290a0693e212990 51e40419244c3d581620495beddec11471fd157c4f8e5f2d7

Hash of concatenated string:
Ans v1: d60b649e5e03787afbdca22cc9ab877188791de1468c81d7f94240a132372e15

Final hash of concatenated string:
Ans v2: 0508902b5b87cb30c68dc49ca53a96818fba374ba32f36964864ad9b934c3a8d

Result I got:
0508902b5b87cb30c68dc49ca53a96818fba374ba32f36964864ad9b934c3a8d
Expected result:
13a3595f2610c8e4d727130daade66c772fdec4bd2463d773fd0f85c20ced32d

Checked my calculations "manually" using http://www.fileformat.info/tool/hash.htm?hex=d60b649e5e03787afbdca22cc9ab877188791de1468c81d7f94240a132372e15
and got the same results. Am I doing someting wrong following this example: https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees

[ArtForz]

"You're doing it wrong"
note that the byte order for displaying these hashes is basically exactly backwards vs. normal notation
I'm using hex strings without quotes to show bytes-as-they-would-be-in-memory and in quotes to show uint256s in hex like in blockexplorer or returned by bitcoin rpc

tx hashes for that block:
"3a459eab5f0cf8394a21e04d2ed3b2beeaa59795912e20b9c680e9db74dfb18c"
"be38f46f0eccba72416aed715851fd07b881ffb7928b7622847314588e06a6b7"
"d173f2a12b6ff63a77d9fe7bbb590bdb02b826d07739f90ebb016dc9297332be"
"59d1e83e5268bbb491234ff23cbbf2a7c0aa87df553484afee9e82385fc7052f"
"f1ce77a69d06efb79e3b08a0ff441fa3b1deaf71b358df55244d56dd797ac60c"
"84053cba91fe659fd3afa1bf2fd0e3746b99215b50cd74e44bda507d8edf52e0"
again, that's when you read them as uint256s, little-endian all the way, so "bytes in memory" those really are:
8cb1df74dbe980c6b9202e919597a5eabeb2d32e4de0214a39f80c5fab9e453a
b7a6068e5814738422768b92b7ff81b807fd515871ed6a4172bacc0e6ff438be
...
so, to start the merkle building, we do sha256(sha256(h1 . h2)) for the first two
result:
2dd3ce205cf8d03f773d46d24becfd72c766deaa0d1327d7e4c810265f59a313
again read it backwards because we display stuff in little-endian, and...
"13a3595f2610c8e4d727130daade66c772fdec4bd2463d773fd0f85c20ced32d"
looks familiar?
do the same for "d173..." and "59d1..." and...
"f6ae335dc2d2aecb6a255ebd03caaf6820e6c0534531051066810080e0d822c8"
last pair...
"a751efbeabe73bdf9d08df5760104feff915d9d807d4c62178cdeb98d8c25f43"

now we only have 3, so last one gets concat'd with itself
"13a3595f2610c8e4d727130daade66c772fdec4bd2463d773fd0f85c20ced32d"
"f6ae335dc2d2aecb6a255ebd03caaf6820e6c0534531051066810080e0d822c8"
gives
"59545fd8dfdd821ca7accecab0655d77437f5bba5aaa5ea8c042a26bc9ae514b"

"a751efbeabe73bdf9d08df5760104feff915d9d807d4c62178cdeb98d8c25f43"
"a751efbeabe73bdf9d08df5760104feff915d9d807d4c62178cdeb98d8c25f43"
gives
"15eca0aa3e2cc2b9b4fbe0629f1dda87f329500fcdcd6ef546d163211266b3b3"

and final level of the tree
"59545fd8dfdd821ca7accecab0655d77437f5bba5aaa5ea8c042a26bc9ae514b"
"15eca0aa3e2cc2b9b4fbe0629f1dda87f329500fcdcd6ef546d163211266b3b3"
gives
"9cdf7722eb64015731ba9794e32bdefd9cf69b42456d31f5e59aedb68c57ed52"

[ThePiachu]

Thank you very much, everything is working fine now.