trie

library3.1.0pypypi✓ verified 86d ago

The `trie` library is a Python implementation of the Ethereum Trie (specifically, the Hexary Trie) data structure. It provides tools for interacting with the Merkelized Patricia Trie, which is fundamental to Ethereum's state, transaction, and receipt storage. As of its current version 3.1.0, it remains an active project maintained by the Ethereum Foundation, with a release cadence tied to ongoing Ethereum development and needs.

database

pip install trie

github ↗package ↗

INSTALL

IMPORT

SIG · TRIE

trie

databasepythonv3.1.0

Install

4.1s avg

Import

803ms

Disk

40MB

Pass rate

10/ 10

Env Coverage10 / 10

glibc

3.9–3.13

musl

3.9–3.13

Install & Compatibility

Where this runs

tested against v3.1.0 · pip install

no network on importno background threads

Install × environment matrix

Each cell = how many times install + import succeeded across repeated harness runs. Partial = flaky.
glibc = Debian/Ubuntu slim · musl = Alpine Linux

musl

py 3.10–3.920 runs

installs and imports cleanly · install 0.0s · import 0.833s · 40.8MB

glibc

py 3.10–3.920 runs

installs and imports cleanly · install 4.1s · import 0.772s · 42MB

40MB installed

● package 40MB

Code

Verified usage

Verified import paths — ran on the pinned version, not inferred.

HexaryTrie

✓ from trie import HexaryTrie

The primary class for interacting with the Ethereum Hexary Trie.

HexaryTrieFog

✓ from trie import HexaryTrieFog

Used for guided traversal of large tries to manage exploration state.

TraversedPartialPath

✓ from trie.exceptions import TraversedPartialPath

An exception class indicating partial traversal into an extension node, useful for resuming exploration.

This quickstart demonstrates the basic usage of `HexaryTrie` by initializing it with an in-memory dictionary acting as a database, inserting and retrieving byte string key-value pairs, and checking for key existence. In a real-world Ethereum context, the `db` parameter would typically be a more robust, persistent database backend.

from trie import HexaryTrie # A simple in-memory dict for demonstration. For production, use a persistent database. db = {} t = HexaryTrie(db=db) # The root hash of an empty trie print(f"Initial root hash: {t.root_hash.hex()}") # Insert some key-value pairs (keys and values must be bytes) t.set(b'dog', b'puppy') t.set(b'do', b'remi') t.set(b'cat', b'kitten') print(f"Root hash after inserts: {t.root_hash.hex()}") # Retrieve values print(f"Value for 'dog': {t.get(b'dog')}") print(f"Value for 'cat': {t.get(b'cat')}") # Check for key existence print(f"'dog' in trie: {b'dog' in t}") print(f"'fish' in trie: {b'fish' in t}") # Delete a key t.delete(b'dog') print(f"'dog' in trie after deletion: {b'dog' in t}") print(f"Root hash after deletion: {t.root_hash.hex()}")

Debug

Known issues

gotchaThe `HexaryTrie` constructor accepts a `db` argument which is a dictionary-like object for storing trie nodes. Using a simple `dict` (e.g., `db={}`) will result in an ephemeral, in-memory trie state, which is not suitable for persistent storage in production Ethereum applications. A proper database backend (e.g., LevelDB, RocksDB) should be integrated for production use cases.

fix

Provide a persistent and performant database object (implementing dict-like interface) to the `HexaryTrie` constructor for production environments.

affects: All versions

gotchaDirect traversal using `t.traverse(prefix)` can be inefficient for large tries as it accesses the underlying database for every node from the root to the target. This can lead to numerous database lookups and performance bottlenecks.

fix

For navigating large tries, utilize `trie.TrieFrontierCache` and `HexaryTrie.traverse_from()` methods to minimize database interactions by caching and optimizing exploration paths.

affects: All versions

gotchaThis library implements the *Ethereum* Trie structure, which uses specific encoding schemes like Hex Prefix encoding for paths and Recursive Length Prefix (RLP) encoding for values. Users unfamiliar with these Ethereum-specific data formats may encounter unexpected behavior or incorrect results when interacting with raw trie data.

fix

Familiarize yourself with Ethereum's Hex Prefix encoding and RLP encoding specifications for keys and values to ensure correct data interaction and interpretation. The library handles much of this internally, but understanding the underlying mechanics is crucial for debugging and advanced usage.

affects: All versions

Errors

Common errors & fixes

ModuleNotFoundError: No module named 'py_trie'

The library's GitHub repository was renamed from `pipermerriam/py-trie` to `ethereum/py-trie` in November 2017. While the PyPI package name is `trie`, older code or local installations might attempt to import from `py_trie`.

fix

Update your import statements from `from py_trie import ...` to `from trie import ...`.

KeyError: b'\x00\x00\x00...'

Attempting to retrieve or delete a key that is not present in the trie, or the key is not encoded correctly as a byte string matching the trie's internal representation.

fix

Ensure all keys used for `set()`, `get()`, `delete()`, and `in` operations are byte strings (`b'your_key'`). Verify that the key you are searching for genuinely exists or has been properly inserted into the trie.

t.traverse(prefix) raises trie.exceptions.TraversedPartialPath: Partially traversed to HexaryTrieNode(...)

The `traverse()` method by default only follows a path as far as it can without ambiguity. If it hits an extension node that branches further than the exact prefix provided, it will raise `TraversedPartialPath` to indicate that a full node could not be returned for the given path.

fix

Catch the `TraversedPartialPath` exception. The exception object contains `exc.simulated_node.sub_segments` which provides the relevant sub-segments to continue exploration into the children of the extension node. Alternatively, use `HexaryTrieFog` for more controlled and stateful traversal of the trie.

Upgrade

Version history

3.1.0latest on PyPI · released Jan 29, 2025

Audit

Dependencies

eth-hashrequiredCryptographic hashing utilities for Ethereum.

eth-utilsrequiredCommon utility functions for Ethereum projects.

hexbytesrequiredHexadecimal byte string utilities.

rlprequiredRecursive Length Prefix (RLP) encoding for Ethereum data structures.

sortedcontainersrequiredSorted list and dictionary implementations, used for internal data management.

Agent activity

27 hits · last 30 days

node