Ethereum Trie (py-trie)

Common errors

• ModuleNotFoundError: No module named 'py_trie'

  cause 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...'

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

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

Warnings

• gotcha The `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.
• gotcha Direct 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.
• gotcha This 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.

Install

• pip install trie Install stable release

Imports

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

Quickstart

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()}")