merkle-tree cryptography
Project description
pymerkle
Merkle-tree cryptography
Documentation found at pymerkle.readthedocs.org.
This library provides a Merkle-tree implementation in Python. It supports multiple combinations of hash functions and encding schemas with defense against second-preimage attack enabled.
Install
pip3 install pymerkle
Usage
from pymerkle import MerkleTree, verify_inclusion, verify_consistency
tree = MerkleTree()
# Populate tree with some entries
for data in [b'foo', b'bar', b'baz', b'qux', b'quux']:
tree.append_entry(data)
# Prove and verify inclusion of `bar`
proof = tree.prove_inclusion(b'bar')
verify_inclusion(b'bar', tree.root, proof)
# Save current state
sublength = tree.length
subroot = tree.root
# Append further entries
for data in [b'corge', b'grault', b'garlpy']:
tree.append_entry(data)
# Prove and verify previous state
proof = tree.prove_consistency(sublength, subroot)
verify_consistency(subroot, tree.root, proof)
Security
This is currently a prototype requiring security review. 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 data with
0x00
. - Upon computing the hash of an interior node, prepend the hashes of its
children with
0x01
.
Refer here 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
The topology turns out to be that of a binary Sakura tree.
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 combinations of hash algorithms and encoding schemas, run
./test.sh --extended
Documentation
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.
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.