Expand description
Merkle-Radix Tree state.
Merkle Hashes
Transact provides an addressable Merkle-Radix tree to store data for state. Let’s break that down: The tree is a Merkle tree because it is a copy-on-write data structure which stores successive node hashes from leaf-to-root upon any changes to the tree. For a given set of state transitions, we can generate a single root hash which points to that version of the tree.
The root hash can be used to verify that the same set of state transitions applied against the same state ID in another database will produce the same results.
Radix Addresses
The tree is an addressable Radix tree because addresses uniquely identify the paths to leaf nodes in the tree where information is stored. An address is a hex-encoded byte array. In the tree implementation, each byte is a Radix path segment which identifies the next node in the path to the leaf containing the data associated with the address. This gives the tree a branch factor of 256.
State Pruning
Transact’s implementation of the merkle-radix tree for state includes the
Prune trait.
A given State root can be viewed as a successor to a previous state root on which it was built. Using this knowledge, pruning operates in one of two ways, depending on where in the chain of successors a given root is.
- If state root has successors, then all of the nodes that were removed during the creation of the root are removed. In other words, any data that would not be accessible from the given state root from prior state roots would be removed.
- If a state root has no successors (it’s the tip of a successor chain), then all of the nodes that were added by that state root are removed. In other words, any data that would not be accessible by any other state root that still exists in the tree.
The later method exists in service of removing forks in a successor chain of a tree.
Re-exports
pub use kv::MerkleLeafIterator;pub use kv::MerkleRadixTree;pub use kv::MerkleState;pub use kv::StateDatabaseError;pub use kv::CHANGE_LOG_INDEX;pub use kv::DUPLICATE_LOG_INDEX;pub use kv::INDEXES;
Modules
- SQL-backed merkle-radix state implementation.
Enums
- Error variants that may occur while reading Merkle Radix tree leaves.
Traits
- A Merkle-Radix tree leaf reader.