This implements a binary merkle radix tree. The point of using a binary radix tree is that it generates smaller proof size then trees with larger radixes. This tree is well suited for storing large dictonaries of fairly random keys. And is optimized for storing keys of the same length. If the keys are not random better performance can be achived by hashing them first. It builds on top of ipld-graph-builder and the resulting state and proofs are generated using it.

npm install dfinity-radix-tree

const RadixTree = require('js-dfinity-radix-tree') const level = require('level') const db = level('./tempdb') async function main () { const prover = new RadixTree({ db: db }) await prover.set('test', Buffer.from('value')) await prover.set('doge', Buffer.from('coin')) await prover.set('cat', Buffer.from('dog')) await prover.set('monkey', Buffer.from('wrench')) // create a merkle root and save the tree const merkleroot = await prover.flush() // start a new Instance with the root const verifier = new RadixTree({ db: db, root: merkleroot }) const val = await verifier.get('monkey') console.log(val.toString()) } main()

'./docs/'

'./docs/spec.md'

The result of the benchmarks show that the binary radix tree produces proofs on average %67 small then the Ethereum Trie with 100000 keys stored.

'./benchmarks/benchmarks.md'

npm run tests

MPL-2.0