A generic data integrity layer. https://dfinity.org

Latest on Hackage:0.6.3

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.

BSD-3-Clause licensed and maintained by Enzo Haussecker, Remy Goldschmidt, Armando Ramirez

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

DFINITY Hackage Dependencies License: BSD 3-Clause


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. An instance for LevelDB is 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 cacheSize root handle
  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


dfinity-radix-tree is licensed under the BSD 3-Clause License.


0.6.2 Enzo Haussecker enzo@dfinity.org Thu Mar 14 2019

  • Revise package metadata.

0.6.2 Enzo Haussecker enzo@dfinity.org Thu Mar 14 2019

  • Add Travis build script.

0.6.1 Enzo Haussecker enzo@dfinity.org Wed Mar 13 2019

  • Remove unnecessary file metadata.

0.6.0 Enzo Haussecker enzo@dfinity.org Wed Mar 13 2019

  • Update license agreement.
  • Remove bloom filter dependency.
  • Implement radix subtree construction.
  • Improve debug output.

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