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

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain]

Warnings:

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.


[Skip to ReadMe]

Properties

Versions0.0.0, 0.1.0, 0.1.0, 0.1.1, 0.2.0, 0.2.1, 0.3.0, 0.3.1, 0.4.0, 0.5.0, 0.5.1, 0.5.2
Change logCHANGELOG.md
Dependenciesaeson, base (>=4.10 && <5), base16-bytestring, bloomfilter, BoundedChan, bytestring, cmdargs, conduit, containers, cryptohash-sha256, data-default-class, deepseq, dfinity-radix-tree, ghc-prim, lens-simple, leveldb-haskell, lrucaching, resourcet, semigroups, serialise, text, unordered-containers [details]
LicenseGPL-3.0-only
Copyright2018 DFINITY Stiftung
AuthorEnzo Haussecker <enzo@dfinity.org>
MaintainerDFINITY USA Research <team@dfinity.org>
CategoryBlockchain, DFINITY, Database
Home pagehttps://github.com/dfinity-lab/hs-radix-tree
Bug trackerhttps://github.com/dfinity-lab/hs-radix-tree/issues
Executablesdfinity-radix-tree-benchmarks, dfinity-radix-tree-unit-tests
UploadedTue Jul 3 18:17:27 UTC 2018 by EnzoHaussecker

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees


Readme for dfinity-radix-tree-0.1.0

[back to package description]

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

Build Status Hackage Dependencies License: GPLv3

Overview

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.

Usage

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.Trans.Resource
import Database.LevelDB
import Network.DFINITY.RadixTree

instance MonadResource m => RadixDatabase (FilePath, Options) m DB where
   create = uncurry open
   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 define some simple type aliases and wrapper functions.

import Control.Monad.Trans.Resource
import Data.ByteString
import Database.LevelDB
import Network.DFINITY.RadixTree

type MerkleTree = RadixTree DB
type MerkleRoot = RadixRoot

createMerkleTree
   :: MonadResource m
   => FilePath -- Database.
   -> Maybe MerkleRoot -- State root.
   -> m MerkleTree
createMerkleTree path root =
   createRadixTree bloomSize cacheSize root (path, options)
   where
   bloomSize = 262144
   cacheSize = 2048
   options = defaultOptions {createIfMissing = True}

insertMerkleTree
   :: MonadResource m
   => ByteString -- Key.
   -> ByteString -- Value.
   -> MerkleTree -- Tree.
   -> m MerkleTree
insertMerkleTree = insertRadixTree

deleteMerkleTree
   :: MonadResource m
   => ByteString -- Key.
   -> MerkleTree -- Tree.
   -> m MerkleTree
deleteMerkleTree = deleteRadixTree

merkleizeMerkleTree
   :: MonadResource m
   => MerkleTree -- Tree.
   -> m (MerkleRoot, MerkleTree)
merkleizeMerkleTree = merkleizeRadixTree

lookupMerkleTree
   :: MonadResource m
   => ByteString -- Key.
   -> MerkleTree -- Tree.
   -> m (Maybe (ByteString, MerkleTree))
lookupMerkleTree = lookupMerkleizedRadixTree

Using the API above, we can perform operations on the tree as a proxy for the database and see that its contents is uniquely defined by its MerkleRoot.

Contribute

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

License

GPLv3