search

keybase / node-merkle-tree

A JS Merkle Tree implementation
BSD 3-Clause "New" or "Revised" License
39 stars 8 forks source link

documentation? #1

Open dominictarr opened 9 years ago

dominictarr commented 9 years ago

This looks interesting!

Can you provide some simple documentation of an example use and the api?

maxtaco commented 9 years ago

I hacked something together, please ask any questions you might have.

What are you building?

Also, randomly, if you want an email address @tarr.com, @malgorithms can hook you up.

dominictarr commented 9 years ago

Ah, what is this based on?

From what I have read, the term "merkle tree" doesn't seem to be very well defined. there seems to be two basic things it describes - one where you take a series of blocks and hash them into a tree, such that you supply a proof that any block is part of entire set.

The other case is as part of an anti-entropy protocol - this is briefly described in the dynamo paper, but I can't seem to find another source that describes it being used that way (the dynamo paper cites the original merkle paper, which discusses the first usage)

Since you have the upsert method and keys it looks like you are implementing the second case. Do you have a link to a paper or other description of how it works?

I'm working on a secure replicatable database, secure-scuttlebutt. Each user has an append only log, that can link to messages in other logs (the data model is basically twitter). All the data can be replicated and verified offline.

I have been thinking about using the first sort of merkle tree so that you can verify a message within a log without having to replicate the entire log.

How is this used in keybase? I think the most important thing missing from your documentation is a description of the security property it aims to provide.

maxtaco commented 9 years ago

Sorry, I was too busy describing the tree to tell you about the forest.

Keybase's use is exactly what you describe for secure-scuttlebutt. Each user has an append-only log of signatures, and the Merkle tree is a sitewide database of all user logs. We sign and publish the root of the merkle tree, and the interior nodes. Also, we publish the hash of the root to the bitcoin blockchain every 6 hours.

More details here and here.

alinush commented 8 years ago

Hi Max, are Keybase Merkle trees sorted in any way so as to provide non-membership proofs when looking up by username? Do you guys use a prefix tree or a BST?

maxtaco commented 8 years ago

We use a prefix tree, so it should also provide proof of non-membership. The problem here is decidedly easier than CONIKS's because we're all public and out in the open with this data and aren't fearing spammers.