node-merkle-tree
A JS Merkle Tree implementation, as used by keybase.
Install
npm install merkle-tree
And then
var Base = Base;
Testing
make test
All tests should pass.
API
This module is just a library, and for it to do anything useful, you'll have to subclass
the Base
class required above. As an example, we provide a subclass of a Merkle-Tree
that lives in memory, which can be accessed as follows:
var merkle_mod = ; // M = the number of children per interior node.// N = the maximum number of leaves before a resplit.var config = N : 4 M : 16 ;var myTree = config; // Keys are hashes expressed as hex strings.var key = "961b6dd3ede3cb8ecbaacbd68de040cd78eb2ed5889130cceb4c49268ea4d506";var value = "foo" : 10 ; // We're just inserting one, but you can insert as many as you'd like.myTree; // You can either build a tree one key/value pair at a time, as above, or// you can build the whole thing at once.var data = "list": "aabbcc" "dog" "ddccee" "cat" "00aa33" "bird" ;myTree;
To review, the Merkle Tree module provides the following classes:
Config
-- A configuration object that controls the shape of the tree.SortedMap
-- A sorted map of key/value pairs that used for inputting a whole bunch of data at a time, and is also used internally.Base
-- A base, abstract tree implementation that needs to specialized.MemTree
-- A speciailization ofBase
; all data lives in memory and disappears when the process ends.
The Base
class has the following method calls:
build({sortedMap}, cb)
--- Build a tree from scratch using the given sorted map of data, and callback when done.upsert({key,value,[txinfo]}, cb)
--- Update or insert the given value at the given key. Provide optionaltxinfo
that is passed to the storage engine.find({key}, cb)
--- Find the given key in the Merkle tree, starting from the root and going down.
How to Make an On-Disk Tree
The keybase server stores its Merkle tree on disk. It
implements the following methods of the Base
class to do so:
hash_fn(s)
-- A function to hash an interior node into a key. Return the hex-string hash of the given string. I'd just use SHA512:require('crypto').createHash('SHA512').update(s).digest('hex')
.store_node({key, obj, obj_s}, cb)
--- Store the node valueobj
under the keykey
. For convenience, you are also passedobj_s
, the stringification of the object.lookup_node({key},cb)
--- Read from disk the node whose key is key. Callback with the parsed (not stringified) objectlookup_root(cb)
--- Should callback with the hash of the most recent tree root.commit_root({key,txinfo}, cb)
--- Store the root hash to disk, optionally with thetxinfo
transaction info annotation.
For an example of how to do this, see the simple MemTree class.