A JS Merkle Tree implementation, as used by keybase.
npm install merkle-tree
And then
var Base = require('merkle-tree').Base;
make test
All tests should pass.
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 = require('merkle-tree');
// M = the number of children per interior node.
// N = the maximum number of leaves before a resplit.
var config = new merkle_mod.Config({ N : 4, M : 16 });
var myTree = new merkle_mod.MemTree(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.upsert({'key' : key, 'value' : value}, function(err, new_root_hash) {
// Finding by default checks the hashes on all interior nodes down the tree.
// If you want to speed up your 'finds', then you can pass `skip_verify : true`
// to your find.
myTree.find({'key' : key, 'skip_verify' : false}, function(err, val2) {
assert.equal(value, val2);
});
});
// 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 = new merkle_mod.SortedMap({
"list": [
["aabbcc", "dog" ],
["ddccee", "cat" ],
["00aa33", "bird" ]
]
});
myTree.build({"sorted_map" : data }, function (err) {
console.log("done!");
});
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.
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.