hippiepug.chain implements a blockchain that only
requires logarithmic-size proofs of inclusion. Each block of such blockchain
has not one but many hash-pointers to previous blocks.
Key-value Merkle tree.
hippiepug.tree implements a verifiable
dictionary as a key-value Merkle tree that guarantees unique resolution.
For each lookup key, one can produce a proof of inclusion of the key in the
tree. Moreover, unique resolution ensures that a proof of inclusion also
proves that no other value with the same lookup key exists somewhere else
in the tree.
hippiepug.store implements a content-addressable
key-value store in which keys are cryptographic hashes of values. Using such
hippiepug data structures is convenient, because a creator of
a chain or a tree only needs to provide a querier with a hash of a chain head
or a tree root. That is, there is no need to explicitly produce and transmit
inclusion proofs. Queriers will be able to verify inclusion on the fly,
provided the storage is available. See section “Producing and verifying proofs” for more.
Using object stores¶
hippiepug includes an instantation of an in-memory content-addressable
storage that uses SHA256 for hashes:
hippiepug.store.Sha256DictStore. By default, the hashes are
truncated to 8 bytes.
from hippiepug.store import Sha256DictStore store = Sha256DictStore() obj = b'dummy' obj_hash = store.hash_object(obj) # 'b5a2c96250612366' store.add(obj) == obj_hash # True
The store verifies hashes internally on each lookup.
obj_hash in store # True store.get(obj_hash) == obj # True
If you want to use external storage, you can provide a dict-like facade to it
and pass as a
class CustomBackend(object): def get(self, k): return 'stub' def __setitem__(self, k, v): pass store = Sha256DictStore(backend=CustomBackend())
To change the hash function, subclass
hippiepug.store.BaseDictStore, and implement the
You can also define a completely different store by implementing abstract base
Building the data structures¶
To append a new block to a chain, first obtain an existing chain, or initialize
a new empty
from hippiepug.chain import Chain chain = Chain(store) chain.head # None
Then, add chain blocks ony by one.
from hippiepug.chain import BlockBuilder block_builder = BlockBuilder(chain) block_builder.payload = b'This is the first block!' block_builder.commit() chain.head # '154bdee593d8c9b2'
You can continue adding blocks using the same builder instance.
block_builder.payload # None block_builder.payload = b'This is the second block!' block_builder.commit() chain.head # '48e399de59796ab1'
The builder automatically fills all the skipchain special block attributes, like hashes of previous blocks.
hippiepug trees can not be extended. To build a new tree,
initialize the tree builder on a store, and set the key-value pairs to be
from hippiepug.tree import TreeBuilder tree_builder = TreeBuilder(store) tree_builder['foo'] = b'bar' tree_builder['baz'] = b'wow'
Once all key-value pairs are added, commit them to store and obtain a view of the committed tree:
tree = tree_builder.commit() tree.root # '150cc8da6d6cfa17'
Querying the data structures¶
To get a queryable view of a chain, you need to specify the storage where its blocks reside, and the head of the chain (hash of the latest block). You can then retrieve blocks by their indices, or iterate.
chain = Chain(store, head='48e399de59796ab1') first_block = chain first_block.payload # b'This is the first block!' for block in chain: print(block.index) # will print 1, and then 0
You can also get the latest view of a current chain while building a block in
Similarly, to get a view of a tree, you need to specify the storage, and the root of the tree (hash of the root node). You can then retrieve stored values by corresponding lookup keys.
from hippepug.tree import Tree tree = Tree(store, root='150cc8da6d6cfa17') tree['foo'] # b'bar' 'baz' in tree # True
Producing and verifying proofs¶
When the creator of a data structure and the querier use the same storage
(e.g., external database), no additional work regarding inclusion proofs needs
to be done, since queries produce inclusion proofs on the fly. This scenario,
however, is not always possible. In such case,
hippiepug allows to
produce and verify proofs explicitly.
You can get the proof of block inclusion from a chain view:
block, proof = chain.get_block_by_index(0, return_proof=True)
A proof is a subset of blocks between head block and the requested block.
To verify the proof, the querier needs to locally reproduce a store,
populating it with the blocks in the proof, and then query the chain
in the reproduced store normally. A convenience utility
hippiepug.chain.verify_chain_inclusion_proof() does all of
this internally, and only returns the verification result:
from hippiepug.chain import verify_chain_inclusion_proof verification_store = Sha256DictStore() verify_chain_inclusion_proof(verification_store, chain.head, block, proof) # True.
You can get the proof of value and lookup key inclusion from a tree view:
value, proof = tree.get_value_by_lookup_key('foo', return_proof=True)
For trees, a proof is the list of nodes on the path from root to the leaf containing the lookup key.
The mechanism of verifying an explicit proof is the same as with chains:
locally reproduce a store populating it with all the nodes in the proof,
and then query normally the tree in the reproduced store. Similarly, a
hippiepug.tree.verify_tree_inclusion_proof() does this
internally and returns the verification result:
from hippiepug.tree import verify_tree_inclusion_proof verification_store = Sha256DictStore() verify_tree_inclusion_proof(verification_store, tree.root, lookup_key='foo', value=b'bar', proof=proof) # True.
hippiepug includes default binary serialization using
from hippiepug.pack import decode, encode block = chain decode(encode(block)) == block # True
If you want to define custom serializers, be sure to check the documentation
hippiepug.pack. You need to be careful with custom encoders to not
jeopardize security of the data structure.
Once you have defined a custom encoder and decoder, you can set them to global defaults like this:
from hippiepug.pack import EncodingParams my_params = EncodingParams() my_params.encoder = lambda obj: b'encoded!' my_params.decoder = lambda encoded: b'decoded!' EncodingParams.set_global_default(my_params)
Alternatively, you can also limit their usage to a specific context:
with my_params.as_default(): encode(b'stub') # b'encoded!'