Bitcoin Forum
September 20, 2018, 05:45:49 PM *
News: ♦♦ Bitcoin Core users must update to 0.16.3 [Torrent]. More info.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Merkle Tree example  (Read 5544 times)
ThePiachu
Sr. Member
****
Offline Offline

Activity: 443
Merit: 251



View Profile WWW
September 19, 2011, 01:03:40 PM
 #1

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?

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
1537465549
Hero Member
*
Offline Offline

Posts: 1537465549

View Profile Personal Message (Offline)

Ignore
1537465549
Reply with quote  #2

1537465549
Report to moderator
1537465549
Hero Member
*
Offline Offline

Posts: 1537465549

View Profile Personal Message (Offline)

Ignore
1537465549
Reply with quote  #2

1537465549
Report to moderator
Make a difference with your Ether.
Donate Ether for the greater good.
SPRING.WETRUST.IO
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1537465549
Hero Member
*
Offline Offline

Posts: 1537465549

View Profile Personal Message (Offline)

Ignore
1537465549
Reply with quote  #2

1537465549
Report to moderator
1537465549
Hero Member
*
Offline Offline

Posts: 1537465549

View Profile Personal Message (Offline)

Ignore
1537465549
Reply with quote  #2

1537465549
Report to moderator
1537465549
Hero Member
*
Offline Offline

Posts: 1537465549

View Profile Personal Message (Offline)

Ignore
1537465549
Reply with quote  #2

1537465549
Report to moderator
ThePiachu
Sr. Member
****
Offline Offline

Activity: 443
Merit: 251



View Profile WWW
September 19, 2011, 06:28:44 PM
 #2

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

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
ArtForz
Sr. Member
****
Offline Offline

Activity: 406
Merit: 250


View Profile
September 19, 2011, 09:06:35 PM
 #3

"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"

bitcoin: 1Fb77Xq5ePFER8GtKRn2KDbDTVpJKfKmpz
i0coin: jNdvyvd6v6gV3kVJLD7HsB5ZwHyHwAkfdw
ThePiachu
Sr. Member
****
Offline Offline

Activity: 443
Merit: 251



View Profile WWW
September 19, 2011, 11:31:19 PM
 #4

Thank you very much, everything is working fine now.

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!