Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: merkle tree algorithm in toolkit  (Read 461 times)

0 Members and 1 Guest are viewing this topic.

Offline crazybit

  • Sr. Member
  • ****
  • Posts: 416
    • View Profile
merkle tree algorithm in toolkit
« 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)


Offline HackFisher

  • Hero Member
  • *****
  • Posts: 883
    • View Profile
Re: merkle tree algorithm in toolkit
« Reply #1 on: May 01, 2014, 04:33:23 AM »
Quote
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?
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline toast

Re: merkle tree algorithm in toolkit
« Reply #2 on: May 01, 2014, 04:34:26 AM »
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.
Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

Offline crazybit

  • Sr. Member
  • ****
  • Posts: 416
    • View Profile
Re: merkle tree algorithm in toolkit
« Reply #3 on: May 01, 2014, 05:48:46 AM »
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.

Quote
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%

Offline bytemaster

Re: merkle tree algorithm in toolkit
« Reply #4 on: May 01, 2014, 02:41:19 PM »
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.

Quote
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 :)
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline bytemaster

Re: merkle tree algorithm in toolkit
« Reply #5 on: May 01, 2014, 02:42:39 PM »
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?
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline toast

Re: merkle tree algorithm in toolkit
« Reply #6 on: May 01, 2014, 03:01:58 PM »
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

Do not use this post as information for making any important decisions. The only agreements I ever make are informal and non-binding. Take the same precautions as when dealing with a compromised account, scammer, sockpuppet, etc.

 

Google+