Package com.norswap.nanoeth.trees.patricia

Class PatriciaNode

java.lang.Object

com.norswap.nanoeth.trees.patricia.PatriciaNode

Direct Known Subclasses:

PatriciaBranchNode, PatriciaExtensionNode, PatriciaLeafNode

public abstract class PatriciaNode
extends Object

Abstract base class for Modified Merkle Patricia Tree nodes, to be compatible with PatriciaTree.

nanoeth includes a in-memory patricia tree implementation (in the memory sub-package), but such an implementation is not realistic in practice as the mainnet account trie is itself larger than 20GB. The inclusion of this interface enables more efficient implementation to be plugged into nanoeth, by subclassing PatriciaTree.

Field Summary

Fields

Modifier and Type	Field	Description
protected byte[]	cap	Memoization for cap().

Constructor Summary

Constructors

Constructor	Description
PatriciaNode()

Method Summary

Modifier and Type	Method	Description
abstract PatriciaNode	add(NodeStore store, Nibbles keySuffix, byte[] value)	Returns the transformed node, after associating the given key with the given key suffix.
byte[]	cap()	This method implements the node cap function n (equation 194 in the yellowpaper).
abstract void	collectEntries(NodeStore store, Nibbles prefix, Map<byte[],byte[]> map)	Adds all the entries store under this node to map, given that the prefix to reach this node is given by prefix.
abstract RLP	compose()	This method implements the structural composition function c (equation 197 and previous in the yellowpaper).
abstract byte[]	lookup(NodeStore store, Nibbles keySuffix)	Lookup the entry with the given key suffix, the suffix of a sequence of nibbles, where the missing prefix was used to reach the present node.
MerkleRoot	merkleRoot()	Returns the Merkle root of the Merkle tree rooted at this node.
static PatriciaNode	parse(RLP rlp)	Parses a node from a RLP object in the format returned by compose().
abstract PatriciaNode	remove(NodeStore store, Nibbles keySuffix)	Returns the transformed node, after removing the entry for the given key suffix (if any), or returns null if the removal of the key means that the node itself must disappear.
abstract BranchStep	step(NodeStore store, Nibbles keySuffix)	Returns a qudruplet of: this node.
abstract byte[]	value()	Returns the value associated with the node, or null if no value is associated.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

cap

@Nullable
protected byte[] cap

Memoization for cap().

Constructor Details

PatriciaNode

public PatriciaNode()

Method Details

parse

public static PatriciaNode parse(RLP rlp)
                          throws RLPParsingException

Parses a node from a RLP object in the format returned by compose().

The returned will be a store-backed node (StorePatriciaBranchNode or StorePatriciaExtensionNode) or a PatriciaLeafNode.

It's the caller responsibility to add the node to a store, if necessary. Similarly, this also doesn't validate that the cap value of children (if any) are valid with respect to any specific store.

Throws:

RLPParsingException

value

@Nullable
public abstract byte[] value()

Returns the value associated with the node, or null if no value is associated.

step

public abstract BranchStep step(NodeStore store,
Nibbles keySuffix)

Returns a qudruplet of:

1. this node.
2. the child in which to look for the value for the given key suffix (or equivalently, the child to modify to insert a value to be associated with the given key suffix). Can be null if no such child exists.
3. the number of nibbles shared between this node and the key suffix. For leaf and extension node, this will be the length of the shared prefix the key suffix and the node's key fragment. For branch nodes, this will be 0 if the returned node is this and 1 otherwise.
4. the number of nibbles left in the key suffix after deducting the shared nibbles.

lookup

public abstract byte[] lookup(NodeStore store,
Nibbles keySuffix)

Lookup the entry with the given key suffix, the suffix of a sequence of nibbles, where the missing prefix was used to reach the present node.

This must handle empty nibble sequences.

add

public abstract PatriciaNode add(NodeStore store,
Nibbles keySuffix,
byte[] value)

Returns the transformed node, after associating the given key with the given key suffix.

This must handle empty nibble sequences.

The method must add its return value to the store, and remove the current node from the store. Any other node added/removed from the tree in the process must similarly be added/removed from the store.

remove

public abstract PatriciaNode remove(NodeStore store,
Nibbles keySuffix)

Returns the transformed node, after removing the entry for the given key suffix (if any), or returns null if the removal of the key means that the node itself must disappear.

This must handle empty nibble sequences.

The method must add its return value to the store, and remove the current node from the store. Any other node added/removed from the tree in the process must similarly be added/removed from the store.

cap

public final byte[] cap()

This method implements the node cap function n (equation 194 in the yellowpaper).

This method memoizes its result. This is an important optimization which avoids traversing the whole tree whenever recomputing the Merkle root after a change to the tree.

compose

public abstract RLP compose()

This method implements the structural composition function c (equation 197 and previous in the yellowpaper). See the README of this package for more information.

merkleRoot

public final MerkleRoot merkleRoot()

Returns the Merkle root of the Merkle tree rooted at this node. This implements the TRIE function in the yellowpaper (equation 195).

collectEntries

public abstract void collectEntries(NodeStore store,
Nibbles prefix,
Map<byte[],byte[]> map)

Adds all the entries store under this node to map, given that the prefix to reach this node is given by prefix.