Class SMT

SparseMerkleTree 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;
  • siblings: the children of a parent node are siblings;
  • 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.

Constructors

constructor

Properties

bigNumbers entryMark hash nodes root zeroNode

Methods

add addNewNodes calculateRoot checkParameterType createProof delete deleteOldNodes get isLeaf retrieveEntry update verifyProof

Constructors

constructor

  • new SMT(hash, bigNumbers?): SMT

  • Initializes the SparseMerkleTree 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, value): 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, path, siblings, i?): 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.

    • siblings: Siblings

      The siblings of the path.

    • i: number = ...

      The index to start from.

    Returns Node

    The root node.

Private calculateRoot

  • calculateRoot(node, path, siblings): 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.

    • siblings: Siblings

      The siblings of the path.

    Returns Node

    The root node.

Private checkParameterType

  • checkParameterType(parameter): void

  • Checks the parameter type.

    Parameters

    • parameter: Node

      The parameter to check.

    Returns void

createProof

  • createProof(key): MerkleProof

  • 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 MerkleProof

    The membership or the non-membership proof.

delete

  • delete(key): 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, path, siblings): 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.

    • siblings: Siblings

      The siblings of the path.

    Returns void

get

  • get(key): 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): 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): 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 siblings of the path.

    Parameters

    • key: Node

      The key of the entry to search for.

    Returns EntryResponse

    The entry response.

update

  • update(key, value): 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(merkleProof): boolean

  • Verifies a membership or a non-membership proof.

    Parameters

    Returns boolean

    True if the proof is valid, false otherwise.

Settings

Member Visibility

Theme

On This Page

constructorbigNumbersentryMarkhashnodesrootzeroNodeaddaddNewNodescalculateRootcheckParameterTypecreateProofdeletedeleteOldNodesgetisLeafretrieveEntryupdateverifyProof