Merkle DAG research

[max-mapper]

We're working on a paper that describes the Merkle DAG we use in dat. Specifically we are interested in approaches with these properties:

• we want to diff DAGs between two peers, given 0 prior knowledge of each others DAGs
• our DAGs are append only
• we would like to support diffing a single "branch" (as opposed to the entire graph)
• minimizing the number of network round trips is very important
• not having to re-traverse the graph when inserting new news is also very important (e.g. the approach must be incremental)

Our graph node exchange protocol between 2 peers works like this:

A peer can send a question message to another peer with some graph node hashes and the other peer should reply back with an answer containing which of the requested hashes it has in its local graph.

The question/answer protocol is stateful for asker, not answerer.

when receiving question

• receive array of hashes
• look up which of these you have
• for every hash you have, put the relative index (of hash array) into answer array
• send array of indices back

when asking question

• send array of hashes you have (must fit in memory)
• send more in parallel if you want, each question has an id
• when you receive a response, use the array of indices in the response to construct a list of the hashes the other side has. you should keep the arrays and ids of the questions you send to be able to compute this step
• do_something_with_answer(hashes)

This lets the 'asker' choose the algorithm they want to use to generate a list of hashes to ask for.

We want to explore different algorithms and secondary indexing schemes we can employ here.

Here's a bunch of papers on Merkle trees/graphs for research:

• Original Merkle Tree paper http://www.merkle.com/papers/Thesis1979.pdf
• Search DAGs http://www.researchgate.net/publication/220224105_A_General_Model_for_Authenticated_Data_Structures (click to download)
• http://www.szydlo.com/logspacetime03.pdf
• https://www.cdc.informatik.tu-darmstadt.de/reports/reports/Boris_Ederov.bachelor.Merkle-Tree-Traversal-Techniques.pdf
• http://markus-jakobsson.com/papers/jakobsson-ctrsa03.pdf
• https://eprint.iacr.org/2012/352.pdf
• http://www.jaist.ac.jp/~mizuhito/papers/conference/CADE05.pdf

[max-mapper]

@mikolalysenko started writing up an outline for an idea involving merkle tries https://gist.github.com/mikolalysenko/fa1403784896870b245f

[max-mapper]

merkle tree/trie from the ethereum paper https://github.com/wanderer/merkle-patricia-tree

I think 'checkpoints' are what we wanna check out in http://gavwood.com/Paper.pdf "checkpoints, or a set of nodes in the database that allow a particular block’s state trie to be traversed"