Merkle-tree cryptography

Documentation found at pymerkle.readthedocs.org.

This library provides a Merkle-tree implementation in Python. It supports most combinations of hash functions and encoding types with defense against second-preimage attack enabled.

pip3 install pymerkle

from pymerkle import MerkleTree

tree = MerkleTree()

# Populate tree with some records
for data in [b'foo', b'bar', b'baz', b'qux', b'quux']:
    tree.encrypt(data)

# Prove and verify encryption of `bar`
challenge = b'485904129bdda5d1b5fbc6bc4a82959ecfb9042db44dc08fe87e360b0a3f2501'
proof = tree.generate_audit_proof(challenge)
proof.verify()

# Save current tree state
state = tree.get_root_hash()

# Append further leaves
for data in [b'corge', b'grault', b'garlpy']:
    tree.encrypt(data)

# Prove and verify saved state
proof = tree.generate_consistency_proof(challenge=state)
proof.verify()

This is currently a prototype requiring security review, so use at your own risk for the moment. However, some steps have been made to this direction:

This consists in the following standard technique:

• Upon computing the hash of a leaf, prepend its data with 0x00.
• Upon computing the hash of an interior node, prepend the hashes of its children with 0x01.

Refer to test_security.py to see how to perform second-preimage attack against the present implementation.

Contrary to the bitcoin specification for Merkle-trees, lonely leaves are not duplicated while the tree is growing. Instead, when appending new leaves, a bifurcation node is created at the rightmost branch. As a consequence, the present implementation should be invulnerable to the DOS attack reported as CVE-2012-2459 (see also here for explanation).

When appending a new leaf node, instead of promoting lonely leaves to the next level or duplicating them, an internal bifurcation node is being created. This is important for efficient recalculation of the root hash (since only the hash values at the tree's rightmost branch need be recalculated) and efficient generation of consistency paths (based on additive decompositions in decreasing powers of 2). The topology turns out to be identical with that of a binary Sakura tree, depicted in Section 5.4 of this paper.

pip3 install -r requirements-dev.txt

./test.sh [pytest options]

to run tests against the limited set of encoding schemas UTF-8, UTF-16 and UTF-32. To run tests against all possible hash types, encoding schemas and security modes, run

./test.sh --extended

./benchmark.sh [pytest options]

pymerkle.readthedocs.org.

Documentation is built with sphinx:

pip3 install -r requirements-doc.txt

Once installed, build docs with

./build-docs.sh [--help]

and browse at

docs/target/build/html/index.html

to view them.