The hippiehug Merkle Tree Library

Installation

The hippiehug Merkle Tree is a pure python library, available through the usual pypi repositories. You can install it using pip:

pip install hippiehug

The Redis backend requires a working installation of the Redis database and associated python libraries.

Introduction and Examples

The hippiehug module provides a Merkle Tree data structure representing a set of byte strings. It also provides a Hash Chain based on a skip list allowing sublinear lookups and proofs of inclusion.

Tree

Using secure hash functions the tree is stored into a data store, that may be persistent and remote. The store is not trusted for integrity, however though cryptographic checks membership operations for items in the set are guaranteed to return the correct answer (or no answer).

In the following example we create a new Tree, and insert item Hello into it. Subsequent queries for items Hello and World return the expected results.

Merkle Trees also allow us to extract a small amount of evidence that would convince anyone with knowledge of the root of the tree whether an element is is the represented set, or not. The volume of this evidence is logarithmic in the size of the set, and therefore efficient.

In the following example we extract information out of a tree, and then check it by reconstructing a partial tree with the evidence.

Chain

The hippiehug hash chain provides a way of sealing multiple sequential entries into a chain, and also allows for efficient proofs of includion of size O(log^2 N). The chain is checked by extracting a bundle of evidence, building a partial chain, and checking the inclusion of an item, as in the example that follows:

Store

A number of stores can be used to back the state of the tree. Those can be local or remote. By default a local python dictionary is used, which offers no persistence. However, the library also offers a Redis backed store through RedisStore. Any class that defined __getitem__ and __setitem__ may be used as a store. Neither its integrity, not its consistency can affect the integrity of the set operations on the Tree.

Security Properties

The key security property offered by the hippiehug Tree relates to high-integrity, despite a possibly adversarial store. Given the root value of the tree is kept with high-integrity, the integrity of the addition (add) and set membership (is_in) operations, are guaranteed to be correct if they return a result.

However, availability properties are not guaranteed: a store that does not respond, loses or modifies data can make operations fail. Replicating the store across different parties can mitigate this.

The Merkle Tree & Chain Classes

class hippiehug.Tree(store={}, root_hash=None)
__init__(store={}, root_hash=None)

Initiates a Merkle tree from a store and a root hash.

Example:
>>> from hippiehug import Tree
>>> t = Tree()
>>> t.add(b"Hello")
>>> b"Hello" in t
True
>>> b"World" not in t
True
add(item, key=None)

Add and element to the Merkle tree.

evidence(key=None)

Gathers evidence about the inclusion / exclusion of the item.

The evidence includes all Branches and Leafs necessary to prove the item is, or is not, in the Merkle Tree. They are ordered from the root to the Leaf that either contrains the sought item, or not.

Example:
>>> t = Tree()
>>> t.add(b"Hello")
>>> t.add(b"World")
>>> root, E = t.evidence(b"World")
>>> evidence_store = dict((e.identity(), e) for e in E)
>>> t2 = Tree(evidence_store, root)
>>> b"World" in t2
True
is_in(item, key=None)

Checks whether an element is in the Merkle Tree.

multi_add(items, keys=None)

Add many elements to the Merkle tree. This is more efficient than adding individual elements.

Example:
>>> t = Tree()
>>> t.multi_add([b"Hello", b"World"])
>>> assert b"Hello" in t and b"World" in t
multi_is_in(items, keys=None, evidence=False)

Checks whether the items are in the Tree. Optionally, returns the current head of the Tree and a list of Branches and Leafs as evidence.

Example lookup:
>>> t = Tree()
>>> t.multi_add([b"Hello", b"World"])
>>> t.multi_is_in([b"Hello", b"World", b"!"])
[True, True, False]
Example gathering of evidence:
>>> _, head, bag = t.multi_is_in([b"Hello", b"World", b"!"], evidence=True)
>>> new_store = dict((e.identity(), e) for e in bag)
>>> new_t = Tree(new_store, head)
>>> new_t.multi_is_in([b"Hello", b"World", b"!"])
[True, True, False]
Example using key-values:
>>> t = Tree()
>>> t.add(key=b"K1", item=b"V1")
>>> t.add(key=b"K2", item=b"V2")
>>> t.is_in(key=b"K2", item=b"V2")
True
>>> t.is_in(key=b"K1", item=b"V1")
True
>>> t.multi_is_in(keys=[b"K2", b"K1", b"K2", b"!"], items=[b"V2", b"V1", b"!", b"V2"])
[True, True, False, False]
root()

Returns the root of the Tree. Keep this value safe, and the integrity of the set is guaranteed.

class hippiehug.Chain(store={}, root_hash=None)
__init__(store={}, root_hash=None)

Initializes a chained backed by a store.

get(block_index, item_index, evidence=None)

Returns the record at a specific block an item ID, and potentially a bundle of evidence.

multi_add(items)

Adds a batch of elements and seals a new block.

root()

Returns the head of the chain.

class hippiehug.DocChain(store={}, root_hash=None)

A chain that stores hashes of documents. Construct like a Chain.

check(root, block_index, item_index, item)

Check that an item is within the structure at a specific point.

get(block_index, item_index, evidence=None)

Get a sealed item, and optionally a bundle of evidence.

multi_add(items)

Add multiple items to seal a new block.

Helper Structures

class hippiehug.Leaf(item, key)
identity()

Returns the hash ID of the Leaf.

item = None

The item stored in the Leaf.

key = None

The key under which the item is stored in the leaf.

class hippiehug.Branch(pivot, left_branch_id, right_branch_id)
identity()

Returns the hash ID of the Branch.

left_branch = None

The hash ID of the left leaf.

pivot = None

The pivot element which determines the left and right leafs.

right_branch = None

The hash ID of the right leaf.

class hippiehug.Block(items, sequence=0, fingers=[])
get_item(store, block_seq, item_seq, evidence=None)

Returns an iten from the chain, at a specific block and item ID. Optionally returns a bundle of evidence.

head()

Returns the head of the block.

next_block(store, items)

Builds a subsequent block, selaing a list of transactions.

Backend Storage Drivers

class hippiehug.RedisStore(host='localhost', port=6379, db=0)
__init__(host='localhost', port=6379, db=0)

Initialize a Redis backed store for the Merkle Tree.

Development and How to Contribute?

The development of hippiehug takes place on github. Please send patches and bug fixes through pull requests. You can clone the repository, and test the package, through the following commands:

git clone https://github.com/gdanezis/rousseau-chain.git
cd hippiehug-package
paver test

Other targets for paver include docs to build documentation, and build to build the package ready for pip installation or distribution.

Indices and tables