hippiepug¶
Sublinear-lookup blockchains and efficient key-value Merkle trees
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.
Contents