BitShares Forum
Main => Technical Support => Topic started by: crazybit on May 01, 2014, 03:29:32 am
-
root
/ \
A B
/ \ / \
t1 t2 t3 t4
A=hash(t1,t2)
B=hash(t3,t4)
Root=hash(A,B)
presented above is the typical merkle tree algorithm, but seems the merkle tree algorithm in bitshares toolkit is simplified as below(if i my understanding is not wrong),what is the purpose?is it still work properly after simplified ?and any benefit from the simplification?
A=hash(t2)
B=hash(t4)
Root=hash(B)
-
layer_two.push_back( small_hash( (char*)&layer_one, 2*sizeof(uint160) ) );
I checked the implement, which seems not the same with your simplification? How did you get that?
-
Are you referring to this?
https://github.com/BitShares/bitshares_toolkit/blob/ab177ba65f4355af9805b4e7451ed9f7dba8a0b7/libraries/blockchain/block.cpp#L49
I think that's just a clever way of doing the standard merkle tree. Notice "2*sizeof(uint160)". Your interpreted simplification effectively doesn't include t1 or t3.
-
Are you referring to this?
https://github.com/BitShares/bitshares_toolkit/blob/ab177ba65f4355af9805b4e7451ed9f7dba8a0b7/libraries/blockchain/block.cpp#L49
I think that's just a clever way of doing the standard merkle tree. Notice "2*sizeof(uint160)". Your interpreted simplification effectively doesn't include t1 or t3.
2*sizeof(uint160)
oh, i overlooked the highlighted code segment,agree that it is a clever way to implement the standard merkle tree. it makes the code elegant and easier to understand. +5% +5% +5%
-
Are you referring to this?
https://github.com/BitShares/bitshares_toolkit/blob/ab177ba65f4355af9805b4e7451ed9f7dba8a0b7/libraries/blockchain/block.cpp#L49
I think that's just a clever way of doing the standard merkle tree. Notice "2*sizeof(uint160)". Your interpreted simplification effectively doesn't include t1 or t3.
2*sizeof(uint160)
oh, i overlooked the highlighted code segment,agree that it is a clever way to implement the standard merkle tree. it makes the code elegant and easier to understand. +5% +5% +5%
Thanks for reviewing the code and looking for bugs as this level even if it was a false alarm :)
-
Are you referring to this?
https://github.com/BitShares/bitshares_toolkit/blob/ab177ba65f4355af9805b4e7451ed9f7dba8a0b7/libraries/blockchain/block.cpp#L49
I think that's just a clever way of doing the standard merkle tree. Notice "2*sizeof(uint160)". Your interpreted simplification effectively doesn't include t1 or t3.
Is there some other way to do it that is less clever or more standard?
-
Less clever would be to be sloppy with your memory and do some extra copies. Standard vs non-standard as in the OP
Sent from my SCH-I535 using Tapatalk