A generic data integrity layer. https://github.com/dfinity-lab/dev

Latest on Hackage:0.5.2

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

GPL-3.0-only licensed and maintained by Enzo Haussecker, Remy Goldschmidt, Armando Ramirez

dfinity-radix-tree: A generic data integrity layer.

DFINITY Build Status Hackage Dependencies License: GPLv3


This library allows you to construct a Merkle tree on top of any underlying key-value database. It works by organizing your key-value pairs into a binary radix tree, which is well suited for storing large dictionaries of fairly random keys, and is optimized for storing keys of the same length.


Define your database as an instance of the RadixDatabase type class. Instances for LevelDB and LMDB are already provided.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

import Control.Monad.IO.Class (MonadIO)
import Database.LevelDB (DB, defaultReadOptions, defaultWriteOptions, get, put)

import DFINITY.RadixTree

instance MonadIO m => RadixDatabase m DB where
   load database = get database defaultReadOptions
   store database = put database defaultWriteOptions

Create a RadixTree that is parameterized by your database. If you want to make things more explicit, then you can define a simple type alias and wrapper function.

import Control.Monad.Trans.Resource (MonadResource)
import Database.LevelDB (DB, Options(..), defaultOptions, open)

import DFINITY.RadixTree

type RadixTree' = RadixTree DB

   :: MonadResource m
   => FilePath -- Database.
   -> Maybe RadixRoot -- State root.
   -> m RadixTree'
createRadixTree' file root = do
   handle <- open file options
   createRadixTree bloomSize cacheSize root handle
   bloomSize = 262144
   cacheSize = 2048
   options   = defaultOptions { createIfMissing = True }

Using the definitions above, you can create a radix tree, perform some basic operations on it, and see that its contents is uniquely defined by its RadixRoot.

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad.IO.Class (liftIO)
import Control.Monad.Trans.Resource (runResourceT)
import Data.ByteString.Base16 (encode)
import Data.ByteString.Char8 (unpack)
import Data.ByteString.Short (fromShort)

import DFINITY.RadixTree

main :: IO ()
main = runResourceT $ do

   -- Create a radix tree, insert a key-value pair, and Merkleize.
   tree  <- createRadixTree' "/path/to/database" Nothing
   tree' <- insertRadixTree "Hello" "World" tree
   root  <- fst <$> merkleizeRadixTree tree'

   -- Print the state root.
   liftIO $ putStrLn $ "State Root: 0x" ++ pretty root
   where pretty = unpack . encode . fromShort

Running the program above should produce the following result.

State Root: 0xb638755216858bc84de8b80f480f15ca5c733e95


Feel free to join in. All are welcome. Open an issue!


dfinity-radix-tree is licensed under the GNU General Public License version 3.


0.5.2 Enzo Haussecker enzo@dfinity.org Fri Oct 19 2018

  • Fix bug related to search strategy.

0.5.1 Enzo Haussecker enzo@dfinity.org Fri Oct 19 2018

  • Expose lens-based interface to radix tree data structures.

0.5.0 Enzo Haussecker enzo@dfinity.org Fri Oct 19 2018

  • Implement Merkle proofs.
  • Reduce memory footprint of parallel download combinators.

0.4.0 Enzo Haussecker enzo@dfinity.org Tue Sep 25 2018

  • Change hash function from SHA-256 to BLAKE-256.
  • Clean-up documentation.

0.3.1 Enzo Haussecker enzo@dfinity.org Mon Aug 06 2018

  • Relax monadic constraint on radix database instance.

0.3.0 Enzo Haussecker enzo@dfinity.org Thu Aug 02 2018

  • Add thread safety to parallel download combinators.
  • Separate impure code from base module.
  • Remove deprecated functions.

0.2.1 Enzo Haussecker enzo@dfinity.org Wed Jul 25 2018

  • Fix bug related to temporary reference creation.

0.2.0 Enzo Haussecker enzo@dfinity.org Sat Jul 21 2018

  • Remove configuration parameter from type class.

0.1.1 Enzo Haussecker enzo@dfinity.org Thu Jul 12 2018

  • Create aliases for verbose functions.
  • Implement debug utilities.
  • Clean-up documentation.

0.1.0 Enzo Haussecker enzo@dfinity.org Tue Jul 03 2018

  • Abstract database to type class.
  • Implement radix tree construction via conduit.
  • Clean-up documentation.
comments powered byDisqus