Skip to main content

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

Project description

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.

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for hippiepug, version 0.5.0
Filename, size File type Python version Upload date Hashes
Filename, size hippiepug-0.5.0.tar.gz (509.9 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page