streaming merkle tree

[dominictarr]

A while back I implemented https://github.com/dominictarr/level-merkle I had been meaning to implement a merkle tree for a while, and wish I had done so sooner. Unfortunately, my experience with scuttlebutt and level-replicate had blinded me to the strengths of merkle tree based replication.

The strength of scuttlebutt replication is that it's good for real time data, and can do peer-to-peer, but it has security problems...

@hij1nx was essential in getting me interested in the problem, as he was working on a merkle tree thing too. level-merkle was as simple as possible, and can only replicate an entire database. However, the most facinating strength of merkle tree replication is that you can replicate subsets.

So, level-merkle needs to be reimplemented, and heres how it needs to work.

take an ordered stream of hashes, and compute hashes of tumbling groups of hashes recursively.

1a1  ---\
1a2     | hashes that start with 1a --,
1a3     | hash(1a...)--\                                              
1a4  ---/              | hashes that start with 1...
1b1  ---\              |-----------------\
1b2     | hash(1b...)--/                 |
1b3     | hashes that start with 1b      | hash(*)
1b4  ---/                                | The "Top Hash"
                                         | all the hashes hashed together.
other                                    | 
hashes ----------------------------------/

Hashing is pretty fast, so it probably wont be a problem to calculate this on the fly, as long as the traversal is fast. I can hash a 350 mb file in 1.5 seconds, if that file was only 40 character hex shasums, that is 350e6/ 40 = 8.75e6 ~ 9 million. that means the tree for even rather large sets could be calculated very easily.

In the current level-merkle, the hash is stored in the database, and recalculated async, but I think that is not necessary in most cases. instead, it is much simpler to recalculate every time by default, and possibly support materialising the tree for nodes that must replicate at high frequency.

I know @substack and @Raynos is also interested in this.

[Raynos]

:+1: for replication. Specifically replicating arbitrary sub levels or ranges of sub levels

[dominictarr]

@Raynos a traversal or a query will provide a stream of hashes, which is the subset to be replicated. or, if the stream is just a db.createKeyStream() then it will replicate everything in the database (or sublevel)

note: stream must be sorted.