Class Tree

java.lang.Object
io.crums.util.mrkl.Tree
Direct Known Subclasses:
DeltaTree, FixedLeafTree, FreeLeafTree

public abstract class Tree
extends java.lang.Object
The Merkle tree. Instances are immutable. This class abstracts away the memory layout for the tree.
See Also:
Builder, FixedLeafTree, FreeLeafTree
  • Field Summary

    Fields
    Modifier and Type Field Description
    static byte BRANCH_PAD  
    static byte LEAF_PAD  
  • Constructor Summary

    Constructors
    Modifier Constructor Description
    protected Tree​(int leaves, java.lang.String algo)
    Base constructor creates an index and locks down the algo.
    protected Tree​(Tree copy)
    Copy constructor.
  • Method Summary

    Modifier and Type Method Description
    protected java.lang.StringBuilder appendToStringDetail​(java.lang.StringBuilder string)  
    abstract byte[] data​(int level, int index)
    Returns [a copy of] the data for the node at the specified coordinates.
    java.lang.String getHashAlgo()  
    byte[] hash()
    Returns the hash of the root of the tree.
    int hashAlgoWidth()
    Returns the byte width of the hashing algorithm by observing the width of the node at coordinates (1, 0), which is the first internal node constructed in a tree.
    static byte[] hashInternals​(byte[] left, byte[] right, java.security.MessageDigest digest)  
    static byte[] hashLeaves​(byte[] left, byte[] right, java.security.MessageDigest digest)  
    static byte[] hashUncommon​(byte[] leftInternal, byte[] rightLeaf, java.security.MessageDigest digest)  
    TreeIndex<Node> idx()
    Returns the random access index into tree structure.
    boolean isLeafWidthFixed()
    Determines whether the width of the leaves is fixed.
    boolean isOmniWidth()
    Determines whether the width of the leaves is the same as the byte width of the hashing algorithm.
    abstract int leafWidth()
    Returns the leaf width in bytes if fixed; -1, otherwise (variable).
    Proof proof​(int leafIndex)
    Returns a cryptographic path to the root of the Merkle tree.
    Node root()
    Returns the root node of the tree.
    java.lang.String toString()
    For debug use.
    boolean verify​(Node node, java.security.MessageDigest digest)  

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Field Details

  • Constructor Details

    • Tree

      protected Tree​(int leaves, java.lang.String algo)
      Base constructor creates an index and locks down the algo.
      Parameters:
      leaves - the number of leaf nodes in the tree
      algo - the hash algo used for the trees internal nodes.
    • Tree

      protected Tree​(Tree copy)
      Copy constructor.
  • Method Details

    • hashLeaves

      public static byte[] hashLeaves​(byte[] left, byte[] right, java.security.MessageDigest digest)
    • hashInternals

      public static byte[] hashInternals​(byte[] left, byte[] right, java.security.MessageDigest digest)
    • hashUncommon

      public static byte[] hashUncommon​(byte[] leftInternal, byte[] rightLeaf, java.security.MessageDigest digest)
    • root

      public final Node root()
      Returns the root node of the tree.
      See Also:
      hash()
    • hash

      public final byte[] hash()
      Returns the hash of the root of the tree.
    • getHashAlgo

      public final java.lang.String getHashAlgo()
    • idx

      public final TreeIndex<Node> idx()
      Returns the random access index into tree structure.
    • verify

      public final boolean verify​(Node node, java.security.MessageDigest digest)
    • data

      public abstract byte[] data​(int level, int index)
      Returns [a copy of] the data for the node at the specified coordinates.
      See Also:
      Node.data(), #data(int, int, ByteBuffer)
    • leafWidth

      public abstract int leafWidth()
      Returns the leaf width in bytes if fixed; -1, otherwise (variable).
    • isLeafWidthFixed

      public final boolean isLeafWidthFixed()
      Determines whether the width of the leaves is fixed.
      Returns:
      true iff the leaf width is not variable
    • isOmniWidth

      public final boolean isOmniWidth()
      Determines whether the width of the leaves is the same as the byte width of the hashing algorithm.
    • hashAlgoWidth

      public final int hashAlgoWidth()
      Returns the byte width of the hashing algorithm by observing the width of the node at coordinates (1, 0), which is the first internal node constructed in a tree.
    • proof

      public final Proof proof​(int leafIndex)
      Returns a cryptographic path to the root of the Merkle tree.
    • toString

      public java.lang.String toString()
      For debug use.
      Overrides:
      toString in class java.lang.Object
    • appendToStringDetail

      protected java.lang.StringBuilder appendToStringDetail​(java.lang.StringBuilder string)