pymerkle 3.0.0

Cryptographic library for Merkle-proofs

pymerkle

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.

Install

pip3 install pymerkle

Usage

from pymerkle import MerkleTree

tree = MerkleTree()

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

# 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 record in [b'corge', b'grault', b'garlpy']:
    tree.encrypt(record)

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

Security

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:

Defense against second-preimage attack

This consists in the following standard technique:

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

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

Defense against CVE-2012-2459 DOS

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).

Tree structure

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.

Development

pip3 install -r requirements-dev.txt

Tests

./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

Benchmarks

./benchmark.sh [pytest options]

Documentation

pymerkle.readthedocs.org.

Build locally

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.