Feature/merkle extend

[satellitex]

Merkle Tree Extend

This merkle tree has cumulation hash.

order

Memory order : log_capacity( node ) capacity add : O( log_capacity( node ) ) get_root : O( log_capacity( node ) ) drop: O( log_capacity( node ) capacity )

Restriction

• drop()'s argument is must be greater than num that is previous called.
• Can only hash the coverage of the capacity. ( e.g, Roughly cover the whole )
• hash function must not have commutative property.

Change Point

• fix CirucularStack
• drop() / add() / get_root()
• add merkle test and buffer test

[l4l]

Why hash must be associative? I don't remember anything that fulfill that property. The hash just a one-way function. The identity element just needed just because hash applies on two objects, so user can decide should it be basic concatenation or smth else.

Also if you want make usual non-optimized merkle tree, plz create new class for it (e.g juts MerkleTree). NarrowMerkleTree doesn't intend to have this implementation.

Btw as long as tests should be the same for both of that classes you can just extract the current test body in template functions and just call them from both of the tests.

[satellitex]

Come to think of it, hash haven't not to be associative. ( Repair description )

I think this code fulfil requirement of NarrowMerkleTree. It purvey :

• add
  • add new element to right most.
• get_root
  • get hash that associated all hash.
• drop
  • erase elements that is right than be assigned by element-id.

[l4l]

well, yeah it maybe fulfill the requirement of usual merkle tree, but not narrow (: check out my last comment in #49 Did you understand the description before the class?

[satellitex]

I saw its code and description. I interpret that is ilasterated by ↓ https://docs.google.com/presentation/d/1-deOggYLlUHCajO0_3NqCLuV59sQy-cjEg5SnwLVIt8/edit?usp=sharing If it is wrong, please tell me.

[l4l]

Well, not really The idea is to minimize the buffer size, so it should be like this (gray here means pointer to last element). That look pretty complicated, so maybe it's not a good idea to describe it as a buffer states, i'll try to come up with a better explanation

[satellitex]

I see. I somehow understand. But, I think merkle tree was written by me and narrow merkle tree has nearly equal to performance ( Order and Space order ).

Compare order ( I gueess )

my merkle

N = number of transactions.

• Memory order : log_capacity( N ) * capacity
• add : O( log_capacity( N) )
• get_root : O( log_capacity( N ) )
• drop(m) : O( log_capacity( node ) * N )

  narrow merkle tree

• Memory order : log_capacity( N ) * capacity
• add : O( log_capacity( N ) * capacity )
• get_root : O( 1 )
• drop(m) : O( log_capacity( node ) * m ) (?) ( i think drop purvey diffrent function each other ).

In actually, opreate that alike this. The idea is easier exetend capacity, I think.

[Warchant]

@l4l @satellitex decide which merkle tree we should use and try to finalize it. Because tomorrow I will have to implement it inside MVP v0.1.

For the first version it is enough to implement unoptimized (in terms of storage) tree.

[Warchant]

Sorry for this chaos in our code. Soon we will fix this.