Sublinear-traversal blockchains and efficient key-value Merkle trees
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
docs
hippiepug
tests
.gitignore
.travis.yml
CONTRIBUTING.rst
LICENSE.txt
MANIFEST.in
NOTICE.txt
README.rst
hippiepug.svg
pytest.ini
setup.cfg
setup.py
tox.ini

README.rst

Hippiepug

hippiepug

PyPI version Build status Test coverage Documentation status License

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.

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.