Class MerkleTrie

An ITrie implementation implemented Merkle Patricia Trie.

Inheritance

System.Object

MerkleTrie

Implements

ITrie

Namespace: Libplanet.Store.Trie

Assembly: Libplanet.Store.dll

Syntax

public class MerkleTrie : object, ITrie

Constructors

MerkleTrie(IKeyValueStore, HashDigest<SHA256>, HashNodeCache)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, HashDigest<SHA256> rootHash, HashNodeCache cache = null)

Parameters

Type	Name	Description
IKeyValueStore	keyValueStore	The IKeyValueStore storage to store nodes.
HashDigest<SHA256>	rootHash	The root Hash of MerkleTrie.
HashNodeCache	cache	The HashNodeCache to use as cache.

MerkleTrie(IKeyValueStore, INode, HashNodeCache)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, INode root = null, HashNodeCache cache = null)

Parameters

Type	Name	Description
IKeyValueStore	keyValueStore	The IKeyValueStore storage to store nodes.
INode	root	The root node of MerkleTrie. If it is null, it will be treated like empty trie.
HashNodeCache	cache	The HashNodeCache to use as cache.

Fields

EmptyRootHash

An ITrie implementation implemented Merkle Patricia Trie.

Declaration

public static readonly HashDigest<SHA256> EmptyRootHash

Field Value

Type	Description
HashDigest<SHA256>

Properties

Hash

The state root hash of the trie.

Declaration

public HashDigest<SHA256> Hash { get; }

Property Value

Type	Description
HashDigest<SHA256>

Remarks

If Root is null, this still gives a unique HashDigest<T> value corresponding to null that is never recorded.

See Also

Root

Recorded

Whether Root is recorded in the store.

Declaration

public bool Recorded { get; }

Property Value

Type	Description
System.Boolean

Remarks

A Root that is null is always considered as recorded.

Root

The root of the ITrie. This is null if and only if the ITrie is empty. That is, this is never a "hashed node" of a null root.

Declaration

public INode Root { get; }

Property Value

Type	Description
INode

See Also

Hash

Methods

Diff(ITrie)

Lists every non-null that is different from the one stored in other given any KeyBytes path.

Declaration

public IEnumerable<(KeyBytes Path, IValue? TargetValue, IValue SourceValue)> Diff(ITrie other)

Parameters

Type	Name	Description
ITrie	other	The other MerkleTrie to compare to.

Returns

Type	Description
IEnumerable<System.ValueTuple<KeyBytes, System.Nullable<IValue>, IValue>>	A list of tuples where each tuple consists of the path where the difference occurred, the "old" value from other and the current "new" value.

Remarks

This operation has the following properties:

• This operation is non-symmetric. That is, in general, trieA.Diff(trieB) and trieB.Diff(trieA) are not the same.
• Values existing in other but not in the source instance, considered as null in the source, are not included in the result.

Exceptions

Type	Condition
InvalidTrieNodeException	Thrown when the method fails to traverse the ITrie.

GenerateProof(KeyBytes, IValue)

Generates a proof of existence for value at key.

Declaration

public IReadOnlyList<INode> GenerateProof(KeyBytes key, IValue value)

Parameters

Type	Name	Description
KeyBytes	key	The path in KeyBytes to search.
IValue	value	The to search.

Returns

Type	Description
IReadOnlyList<INode>	An of INodes that can prove key and value pair exists or not given an ITrie's Hash.

Remarks

In order to generate a valid proof, both a valid key and a valid value must be known beforehand.

Get(IReadOnlyList<KeyBytes>)

Gets the values stored with keys in Set(in KeyBytes, IValue).

Declaration

public IReadOnlyList<IValue?> Get(IReadOnlyList<KeyBytes> keys)

Parameters

Type	Name	Description
IReadOnlyList<KeyBytes>	keys	The keys used in Set(in KeyBytes, IValue) to store a value.

Returns

Type	Description
IReadOnlyList<System.Nullable<IValue>>	The values associated to the specified keys. The associated values are ordered in the same way to the corresponding keys. Absent values are represented as null.

Get(KeyBytes)

Gets the values stored with key in Set(in KeyBytes, IValue).

Declaration

public IValue? Get(KeyBytes key)

Parameters

Type	Name	Description
KeyBytes	key	The key used in Set(in KeyBytes, IValue) to store a value.

Returns

Type	Description
System.Nullable<IValue>	The value associated to the specified key. Absent value is represented as null.

GetNode(Nibbles)

Gets the first node encountered at nibbles when traversing down from Root.

Declaration

public INode GetNode(Nibbles nibbles)

Parameters

Type	Name	Description
Nibbles	nibbles	The path to check.

Returns

Type	Description
INode	A node at nibbles, if any. Otherwise null.

Remarks

There may be more than one INode at nibbles. For instance, a FullNode, a ValueNode as the value of the aforementioned FullNode, and up to two additional HashNodes is possible.

As such, for two equivalent ITries, Libplanet.Store.Tries that would have the same committed Hashes, this may return different types of INode depending on the actual underlying "structure". However, returned INodes for such ITries are equivalent as sub-ITries.

Exceptions

Type	Condition
InvalidTrieNodeException	Thrown when an unknown type of INode is encountered while traversing to the given path.

IterateNodes()

Iterates and every stored INode along with its respective path in Nibbles.

Declaration

public IEnumerable<(Nibbles Path, INode Node)> IterateNodes()

Returns

Type	Description
IEnumerable<System.ValueTuple<Nibbles, INode>>	An of all INodes in no particular order.

Remarks

This is a very heavy operation.

IterateSubTrieNodes(KeyBytes)

Iterates all sub-nodes from a sub-ITrie with INode at rootPath as its root.

Declaration

public IEnumerable<(Nibbles Path, INode Node)> IterateSubTrieNodes(KeyBytes rootPath)

Parameters

Type	Name	Description
KeyBytes	rootPath	The KeyBytes path of an INode to use as the root of traversal.

Returns

Type	Description
IEnumerable<System.ValueTuple<Nibbles, INode>>	All INodes together with its full Nibbles paths.

Remarks

This requires an INode to exist at rootPath. As such, this does not necessarily return all INode with paths starting with rootPath. In particular, if there doesn't exist an INode at rootPath, this returns nothing.

IterateSubTrieValues(KeyBytes)

Iterates all values that can be reached from a sub-ITrie with INode at rootPath as its root.

Declaration

public IEnumerable<(KeyBytes Path, IValue Value)> IterateSubTrieValues(KeyBytes rootPath)

Parameters

Type	Name	Description
KeyBytes	rootPath	The KeyBytes path of an INode to use as the root of traversal.

Returns

Type	Description
IEnumerable<System.ValueTuple<KeyBytes, IValue>>	All s together with its full KeyBytes paths.

Remarks

This requires an INode to exist at rootPath. As such, this does not necessarily return all INode with paths starting with rootPath. In particular, if there doesn't exist an INode at rootPath, this returns nothing.

IterateValues()

Iterates and every stored along with its respective path in KeyBytes.

Declaration

public IEnumerable<(KeyBytes Path, IValue Value)> IterateValues()

Returns

Type	Description
IEnumerable<System.ValueTuple<KeyBytes, IValue>>	An of all s in no particular order.

Remarks

This is a very heavy operation.

Remove(in KeyBytes)

Removes the value at the path corresponding to given key in memory. If there is no at key, this does nothing.

Declaration

public ITrie Remove(in KeyBytes key)

Parameters

Type	Name	Description
KeyBytes	key	The unique key to associate with the value.

Returns

Type	Description
ITrie	Returns new updated ITrie.

Remarks

This should not actually remove anything from storage. The removal of the value at the marked path given by key is actually recorded to storage when Commit(ITrie) is called. Regardless, there is actually no removal of any value from storage even when Commit(ITrie) is called.

See Also

Commit(ITrie)

Set(in KeyBytes, IValue)

Stores the value at the path corresponding to given key in memory.

Declaration

public ITrie Set(in KeyBytes key, IValue value)

Parameters

Type	Name	Description
KeyBytes	key	The unique key to associate with the value.
IValue	value	The value to store.

Returns

Type	Description
ITrie	Returns new updated ITrie.

Remarks

This should not actually write anything to storage. Stored value is actually written to storage when Commit(ITrie) is called.

See Also

Commit(ITrie)

ValidateProof(HashDigest<SHA256>, IReadOnlyList<INode>, KeyBytes, IValue)

Checks whether given proof is a valid proof for given key and value against given stateRootHash.

Declaration

public static bool ValidateProof(HashDigest<SHA256> stateRootHash, IReadOnlyList<INode> proof, KeyBytes key, IValue value)

Parameters

Type	Name	Description
HashDigest<SHA256>	stateRootHash	A known Hash of a ITrie to check proof against.
IReadOnlyList<INode>	proof	An of INodes that acts as a proof of existence for value at key.
KeyBytes	key	The path in KeyBytes to validate.
IValue	value	The to search.

Returns

Type	Description
System.Boolean	true if proof is valid, false otherwise.

Implements

ITrie