ethereum-merkle-patricia-db-0.0.1: A modified Merkle Patricia DB

Safe HaskellNone



This is an implementation of the modified Merkle Patricia database described in the Ethereum Yellowpaper ( This modified version works like a canonical Merkle Patricia database, but includes certain optimizations. In particular, a new type of "shortcut node" has been added to represent multiple traditional nodes that fall in a linear string (ie- a stretch of parent child nodes where no branch choices exist).

A Merkle Patricia Database effeciently retains its full history, and a snapshot of all key-value pairs at a given time can be looked up using a "stateRoot" (a pointer to the root of the tree representing that data). Many of the functions in this module work by updating this object, so for anything more complicated than a single update, use of the state monad is recommended.

The underlying data is actually stored in LevelDB. This module provides the logic to organize the key-value pairs in the appropriate Patricia Merkle Tree.



type Key = NibbleString Source

The type of the database key

type Val = RLPObject Source

The type of the values in the database

putKeyVal Source



The object containing the current stateRoot.

-> Key

Key of the data to be inserted.

-> Val

Value of the new data

-> ResourceT IO MPDB

The object containing the stateRoot to the data after the insert. putKeyVal db key val | trace ("^^^^^^^^^^putKeyVal: key = " ++ show (pretty key) ++ ", val = " ++ show (pretty val)) False = undefined

Adds a new key/value pair.

getKeyVals Source



Object containing the current stateRoot.

-> Key

The partial key (the query will return any key that is prefixed by this value)

-> ResourceT IO [(Key, Val)]

The requested data.

Retrieves all key/value pairs whose key starts with the given parameter.

deleteKey Source



The object containing the current stateRoot.

-> Key

The key to be deleted.

-> ResourceT IO MPDB

The object containing the stateRoot to the data after the delete.

Deletes a key (and its corresponding data) from the database.

Note that the key/value pair will still be present in the history, and can be accessed by using an older MPDB object.

data MPDB Source

This is the database reference type, contianing both the handle to the underlying database, as well as the stateRoot to the current tree holding the data.

The MPDB acts a bit like a traditional database handle, although because it contains the stateRoot, many functions act by updating its value. Because of this, it is recommended that this item be stored and modified within the state monad.




ldb :: DB
stateRoot :: SHAPtr

openMPDB Source


:: String

The filepath with the location of the underlying database.

-> ResourceT IO MPDB 

This function is used to create an MPDB object corresponding to the blank database. After creation, the stateRoot can be changed to a previously saved version.

newtype SHAPtr Source

Internal nodes are indexed in the underlying database by their 256-bit SHA3 hash. This types represents said hash.

The stateRoot is of this type, (ie- the pointer to the full set of key/value pairs at a particular time in history), and will be of interest if you need to refer to older or parallel version of the data.


SHAPtr ByteString 

emptyTriePtr :: SHAPtr Source

The stateRoot of the empty database.