Sublinear-lookup blockchains and efficient key-value Merkle trees with a flexible storage backend
Project description
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.
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
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distribution
Hashes for hippiepug-0.4.2-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 64c5956e4bbdb2c42bf517cb6b1cabc6bac6d1262986d9ebd2e7551c4205b9c8 |
|
MD5 | 77d8e176977465bdfe17dbd129ba3592 |
|
BLAKE2b-256 | 8ec52a51fa95e8da0f8a9e341bb51682a5100e4e0d4f4866102c30532794ef55 |