Package com.norswap.nanoeth.trees.patricia

Class PatriciaTree

java.lang.Object
com.norswap.nanoeth.trees.patricia.PatriciaTree
@Wrapper
public class PatriciaTree
extends Object
Implementation of the Modified Merkle Patricia Tree, as per appendix D of the yellowpaper.

A patricia tree is associated with a key-value store used to access nodes.

See trees.patricia package README for more information on patricia trees.

  • Field Summary

    Fields
    Modifier and Type Field Description
    static MerkleRoot EMPTY_TREE_ROOT
    Merkle root of an empty tree, which the Keccak hash of an empty byte sequence.
    PatriciaNode root
    The root of the tree.
    NodeStore store
    The store associated to this tree).

  • Constructor Summary

    Constructors
    Constructor Description
    PatriciaTree​(NodeStore store)
    Creates an empty patricia tree (root = null).
    PatriciaTree​(NodeStore store, PatriciaNode root)
    Creates a patricia tree with the given root node.

  • Method Summary

    Modifier and Type Method Description
    PatriciaTree add​(byte[] key, byte[] value)
    Returns the transformed tree, after associating the given value with the given key.
    boolean equals​(Object o)  
    void forBranch​(byte[] key, Consumer<BranchStep> f)
    Calls f with every node on the branch for keySuffix (represented by a step, where this branch is the node path from this node towards the node that holds the value associated to the key suffix, or to the deepest node that would have to be modified in order to associated a value with the key suffix.
    int hashCode()  
    byte[] lookup​(byte[] key)
    Lookup the value associated with the given key, or null if no such value exists.
    MerkleRoot merkleRoot()
    Returns the Merkle root of the tree, i.e.
    MerkleProof prove​(byte[] key)
    Returns a Merkle proof for the given key, either proving its association to its value, or the absence of value.
    PatriciaTree remove​(byte[] key)
    Returns the transformed tree, after removing the entry for the given key (if any).
    Map<byte[],​byte[]> toMap()
    Collects all (key, value) entries in the tree in a map, and returns it.
    String toString()  

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

    • EMPTY_TREE_ROOT

      public static final MerkleRoot EMPTY_TREE_ROOT
      Merkle root of an empty tree, which the Keccak hash of an empty byte sequence.

      Namely, this byte sequence is "0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"

    • root

      @Nullable public final PatriciaNode root
      The root of the tree.

    • store

      public final NodeStore store
      The store associated to this tree).

  • Constructor Details

    • PatriciaTree

      public PatriciaTree​(NodeStore store)
      Creates an empty patricia tree (root = null).

    • PatriciaTree

      public PatriciaTree​(NodeStore store, @Nullable PatriciaNode root)
      Creates a patricia tree with the given root node.

  • Method Details

    • lookup

      @Nullable public byte[] lookup​(byte[] key)
      Lookup the value associated with the given key, or null if no such value exists.

    • add

      public PatriciaTree add​(byte[] key, byte[] value)
      Returns the transformed tree, after associating the given value with the given key. If the key is empty, returns itself.

      The store might be modified as a result, refer to the documentation for the used store.

    • remove

      public PatriciaTree remove​(byte[] key)
      Returns the transformed tree, after removing the entry for the given key (if any).

      The store might be modified as a result, refer to the documentation for the used store.

    • toMap

      public Map<byte[],​byte[]> toMap()
      Collects all (key, value) entries in the tree in a map, and returns it.

    • merkleRoot

      public MerkleRoot merkleRoot()
      Returns the Merkle root of the tree, i.e. the TRIE function in the yellowpaper (equation 195).

    • forBranch

      public final void forBranch​(byte[] key, Consumer<BranchStep> f)
      Calls f with every node on the branch for keySuffix (represented by a step, where this branch is the node path from this node towards the node that holds the value associated to the key suffix, or to the deepest node that would have to be modified in order to associated a value with the key suffix.

      This will always at least call f with the root, if there is one (i.e. the tree is not empty).

    • prove

      public MerkleProof prove​(byte[] key)
      Returns a Merkle proof for the given key, either proving its association to its value, or the absence of value.

    • equals

      public boolean equals​(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object