New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merkle DAG research #28

Open
maxogden opened this Issue Oct 7, 2015 · 2 comments

Comments

Projects
None yet
1 participant
@maxogden
Member

maxogden commented Oct 7, 2015

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:

@maxogden

This comment has been minimized.

Show comment
Hide comment
@maxogden

maxogden Oct 7, 2015

Member

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

Member

maxogden commented Oct 7, 2015

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

@maxogden

This comment has been minimized.

Show comment
Hide comment
@maxogden

maxogden Oct 8, 2015

Member

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"

Member

maxogden commented Oct 8, 2015

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"

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment