{"id":7806,"library":"trie","title":"Ethereum Trie (py-trie)","description":"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.","status":"active","version":"3.1.0","language":"en","source_language":"en","source_url":"https://github.com/ethereum/py-trie","tags":["ethereum","trie","blockchain","data-structure","merkle-patricia-trie","cryptocurrency"],"install":[{"cmd":"pip install trie","lang":"bash","label":"Install stable release"}],"dependencies":[{"reason":"Cryptographic hashing utilities for Ethereum.","package":"eth-hash","optional":false},{"reason":"Common utility functions for Ethereum projects.","package":"eth-utils","optional":false},{"reason":"Hexadecimal byte string utilities.","package":"hexbytes","optional":false},{"reason":"Recursive Length Prefix (RLP) encoding for Ethereum data structures.","package":"rlp","optional":false},{"reason":"Sorted list and dictionary implementations, used for internal data management.","package":"sortedcontainers","optional":false}],"imports":[{"note":"The primary class for interacting with the Ethereum Hexary Trie.","symbol":"HexaryTrie","correct":"from trie import HexaryTrie"},{"note":"Used for guided traversal of large tries to manage exploration state.","symbol":"HexaryTrieFog","correct":"from trie import HexaryTrieFog"},{"note":"An exception class indicating partial traversal into an extension node, useful for resuming exploration.","symbol":"TraversedPartialPath","correct":"from trie.exceptions import TraversedPartialPath"}],"quickstart":{"code":"from trie import HexaryTrie\n\n# A simple in-memory dict for demonstration. For production, use a persistent database.\ndb = {}\n\nt = HexaryTrie(db=db)\n\n# The root hash of an empty trie\nprint(f\"Initial root hash: {t.root_hash.hex()}\")\n\n# Insert some key-value pairs (keys and values must be bytes)\nt.set(b'dog', b'puppy')\nt.set(b'do', b'remi')\nt.set(b'cat', b'kitten')\n\nprint(f\"Root hash after inserts: {t.root_hash.hex()}\")\n\n# Retrieve values\nprint(f\"Value for 'dog': {t.get(b'dog')}\")\nprint(f\"Value for 'cat': {t.get(b'cat')}\")\n\n# Check for key existence\nprint(f\"'dog' in trie: {b'dog' in t}\")\nprint(f\"'fish' in trie: {b'fish' in t}\")\n\n# Delete a key\nt.delete(b'dog')\nprint(f\"'dog' in trie after deletion: {b'dog' in t}\")\nprint(f\"Root hash after deletion: {t.root_hash.hex()}\")","lang":"python","description":"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."},"warnings":[{"fix":"Provide a persistent and performant database object (implementing dict-like interface) to the `HexaryTrie` constructor for production environments.","message":"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.","severity":"gotcha","affected_versions":"All versions"},{"fix":"For navigating large tries, utilize `trie.TrieFrontierCache` and `HexaryTrie.traverse_from()` methods to minimize database interactions by caching and optimizing exploration paths.","message":"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.","severity":"gotcha","affected_versions":"All versions"},{"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.","message":"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.","severity":"gotcha","affected_versions":"All versions"}],"env_vars":null,"last_verified":"2026-04-16T00:00:00.000Z","next_check":"2026-07-15T00:00:00.000Z","problems":[{"fix":"Update your import statements from `from py_trie import ...` to `from trie import ...`.","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`.","error":"ModuleNotFoundError: No module named 'py_trie'"},{"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.","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.","error":"KeyError: b'\\x00\\x00\\x00...'"},{"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.","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.","error":"t.traverse(prefix) raises trie.exceptions.TraversedPartialPath: Partially traversed to HexaryTrieNode(...)"}]}