Topic: Merkle Tree example (Read 5694 times)
Thank you very much, everything is working fine now.
"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"
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"
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
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
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?
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?
Jump to: