Options
All
  • Public
  • Public/Protected
  • All
Menu

Class SMT

SMT class provides all the functions to create a sparse Merkle tree and to take advantage of its features: SMT.add, SMT.get, SMT.update, SMT.delete, SMT.createProof, SMT.verifyProof. To better understand the code below it may be useful to describe the terminology used:

  • nodes: every node in the tree is the hash of the two child nodes (H(x, y));
  • root node: the root node is the top hash and since it represents the whole data structure it can be used to certify its integrity;
  • leaf nodes: every leaf node is the hash of a key/value pair and an additional value to mark the node as leaf node (H(x, y, 1));
  • entry: a tree entry is a key/value pair used to create the leaf nodes;
  • zero nodes: a zero node is an hash of zeros and in this implementation H(0,0) = 0;
  • side node: if you take one of the two child nodes, the other one is its side node;
  • path: every entry key is a number < 2^256 that can be converted in a binary number, and this binary number is the path used to place the entry in the tree (1 or 0 define the child node to choose);
  • matching node: when an entry is not found and the path leads to another existing entry, this entry is a matching entry and it has some of the first bits in common with the entry not found;
  • depth: the depth of a node is the length of the path to its root.

Hierarchy

  • SMT

Index

Constructors

Properties

Methods

Constructors

constructor

  • new SMT(hash: HashFunction, bigNumbers?: boolean): SMT

  • Initializes the SMT attributes.

    Parameters

    • hash: HashFunction

      Hash function used to hash the child nodes.

    • bigNumbers: boolean = false

      BigInt type enabling.

    Returns SMT

Properties

Private bigNumbers

bigNumbers: boolean

Private entryMark

entryMark: Node

Private hash

hash: HashFunction

Private nodes

nodes: Map<Node, ChildNodes>

root

root: Node

Private zeroNode

zeroNode: Node

Methods

add

  • add(key: Node, value: Node): void

  • Adds a new entry in the tree. It retrieves a matching entry or a zero node with a top-down approach and then it updates all the hashes of the nodes in the path of the new entry with a bottom-up approach.

    Parameters

    • key: Node

      The key of the new entry.

    • value: Node

      The value of the new entry.

    Returns void

Private addNewNodes

  • addNewNodes(node: Node, path: number[], sidenodes: SideNodes, i?: number): Node

  • Adds new nodes in the tree with a bottom-up approach until it reaches the root node.

    Parameters

    • node: Node

      The node to start from.

    • path: number[]

      The path of the key.

    • sidenodes: SideNodes

      The side nodes of the path.

    • i: number = ...

      The index to start from.

    Returns Node

    The root node.

Private calculateRoot

  • calculateRoot(node: Node, path: number[], sidenodes: SideNodes): Node

  • Calculates nodes with a bottom-up approach until it reaches the root node.

    Parameters

    • node: Node

      The node to start from.

    • path: number[]

      The path of the key.

    • sidenodes: SideNodes

      The side nodes of the path.

    Returns Node

    The root node.

Private checkParameterType

  • checkParameterType(parameter: Node): void

  • Checks the parameter type.

    Parameters

    • parameter: Node

      The parameter to check.

    Returns void

createProof

  • createProof(key: Node): Proof

  • Creates a proof to prove the membership or the non-membership of a tree entry.

    Parameters

    • key: Node

      A key of an existing or a non-existing entry.

    Returns Proof

    The membership or the non-membership proof.

delete

  • delete(key: Node): void

  • Deletes an entry in the tree. Also in this case all the hashes of the nodes in the path of the entry are updated with a bottom-up approach.

    Parameters

    • key: Node

      The key of the entry.

    Returns void

Private deleteOldNodes

  • deleteOldNodes(node: Node, path: number[], sidenodes: SideNodes, i?: number): void

  • Deletes nodes in the tree with a bottom-up approach until it reaches the root node.

    Parameters

    • node: Node

      The node to start from.

    • path: number[]

      The path of the key.

    • sidenodes: SideNodes

      The side nodes of the path.

    • i: number = ...

      The index to start from.

    Returns void

get

  • get(key: Node): undefined | Node

  • Gets a key and if the key exists in the tree the function returns the value, otherwise it returns 'undefined'.

    Parameters

    • key: Node

      A key of a tree entry.

    Returns undefined | Node

    A value of a tree entry or 'undefined'.

Private isLeaf

  • isLeaf(node: Node): boolean

  • Checks if a node is a leaf node.

    Parameters

    • node: Node

      A node of the tree.

    Returns boolean

    True if the node is a leaf, false otherwise.

Private retrieveEntry

  • retrieveEntry(key: Node): EntryResponse

  • Searches for an entry in the tree. If the key passed as parameter exists in the tree, the function returns the entry, otherwise it returns the entry with only the key, and when there is another existing entry in the same path it returns also this entry as 'matching entry'. In any case the function returns the side nodes of the path.

    Parameters

    • key: Node

      The key of the entry to search for.

    Returns EntryResponse

    The entry response.

update

  • update(key: Node, value: Node): void

  • Updates a value of an entry in the tree. Also in this case all the hashes of the nodes in the path of the entry are updated with a bottom-up approach.

    Parameters

    • key: Node

      The key of the entry.

    • value: Node

      The value of the entry.

    Returns void

verifyProof

  • verifyProof(proof: Proof): boolean

  • Verifies a membership or a non-membership proof.

    Parameters

    • proof: Proof

      The proof to verify.

    Returns boolean

    True if the proof is valid, false otherwise.

Generated using TypeDoc