dat-ecosystem-archive / datproject-discussions

a repo for discussions and other non-code organizing stuff [ DEPRECATED - More info on active projects and modules at https://dat-ecosystem.org/ ]
65 stars 6 forks source link

Merkle DAG research #28

Open max-mapper opened 9 years ago

max-mapper commented 9 years ago

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

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

when asking question

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:

max-mapper commented 9 years ago

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

max-mapper commented 9 years ago

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"