Sublinear-lookup blockchains and efficient key-value Merkle trees with a flexible storage backend

## hippiepug

Sublinear-lookup blockchains and efficient key-value Merkle trees.

Check out the documentation.

This library provides implementations of two cryptographic data structures:

• Blockchains with log(n) sublinear traversal, implemented as high-integrity deterministic skip-lists (skipchains). In this kind of blockchain verifying that block b extends block a does not require to download and process all blocks between a and b, but only a logarithmic amount of them.

• Verifiable dictionary, implemented as a key-value Merkle tree that guarantees unique resolution. A proof of inclusion of a key-value pair in such a tree also proves that there does not exist another value for a given key somewhere else in the tree.

Both are meant to be used with a content-addressable storage. Each data structure supports logarithmic queries, and logarithmic proofs of inclusion:

Retrievals per lookup

Inclusion proof size

Append

Skipchain

O(log(n))

O(log(n))

O(1)

Key-value Merkle tree

O(log(n))

O(log(n))

Immutable

with n being the size of the dictionary, or the number of blocks in the case of a chain.

The theoretical details are in the paper.

### Getting started

You can install the library from PyPI:

pip install hippiepug

Then, the easiest way to run the tests is:

python setup.py test

Be sure to check out the usage guide.

### Acknowledgements

• The library is a reimplementation of G. Danezis’s hippiehug (hence the name).

• This work is funded by the NEXTLEAP project within the European Union’s Horizon 2020 Framework Programme for Research and Innovation (H2020-ICT-2015, ICT-10-2015) under grant agreement 688722.

• The hippie pug logo kindly donated by M. Naiem.

## Project details

Uploaded source