Class reprensenting a Merkle Tree

Namespace

MerkleTree

Hierarchy

Constructors

  • Desc

    Constructs a Merkle Tree. All nodes and leaves are stored as Buffers. Lonely leaf nodes are promoted to the next level up without being hashed again.

    Example

    const MerkleTree = require('merkletreejs')
    const crypto = require('crypto')

    function sha256(data) {
    // returns Buffer
    return crypto.createHash('sha256').update(data).digest()
    }

    const leaves = ['a', 'b', 'c'].map(value => keccak(value))

    const tree = new MerkleTree(leaves, sha256)

    Parameters

    • leaves: any[]

      Array of hashed leaves. Each leaf must be a Buffer.

    • Optional hashFn: any
    • Optional options: Options

      Additional options

    Returns MerkleTree

Properties

calculateRootForUnevenTree: any
complete: any
concatenator: any
createHashes: any
duplicateOdd: any
fillDefaultHash: any
getMultiProofForUnevenTree: any
getPairNode: any

getPairNode

Desc

Returns the node at the index for given layer.

Param

Tree layer

Param

Index at layer.

Returns

  • Node

Example

const node = tree.getPairNode(layer, index)
getProofIndicesForUnevenTree: any
hashFn: any
hashLeaves: any
isBitcoinTree: any
isPowOf2: any
layers: any
leaves: any
processLeaves: any
sort: any
sortLeaves: any
sortPairs: any
verifyMultiProofForUnevenTree: any

Methods

  • addLeaf

    Desc

    Adds a leaf to the tree and re-calculates layers.

    Example

    tree.addLeaf(newLeaf)
    

    Parameters

    • leaf: Buffer
    • Optional shouldHash: boolean

    Returns void

  • addLeaves

    Desc

    Adds multiple leaves to the tree and re-calculates layers.

    Example

    tree.addLeaves(newLeaves)
    

    Parameters

    • leaves: Buffer[]
    • Optional shouldHash: boolean

    Returns void

  • Parameters

    • value: any

    Returns BigInt

  • binarySearch

    Desc

    Returns the first index of which given item is found in array using binary search.

    Returns

    • Index number

    Example

    const index = tree.binarySearch(array, element, Buffer.compare)
    

    Parameters

    • array: Buffer[]

      Array of items.

    • element: Buffer

      Item to find.

    • compareFunction: ((a: unknown, b: unknown) => number)
        • (a: unknown, b: unknown): number
        • Parameters

          • a: unknown
          • b: unknown

          Returns number

    Returns number

  • bufferIndexOf

    Desc

    Returns the first index of which given buffer is found in array.

    Returns

    • Index number

    Example

    const index = tree.bufferIndexOf(haystack, needle)
    

    Parameters

    Returns number

  • bufferToHex

    Desc

    Returns a hex string with 0x prefix for given buffer.

    Returns

    Example

    const hexStr = tree.bufferToHex(Buffer.from('A'))
    

    Parameters

    • value: Buffer
    • Optional withPrefix: boolean

    Returns string

  • bufferify

    Desc

    Returns a buffer type for the given value.

    Returns

    Example

    const buf = tree.bufferify('0x1234')
    

    Parameters

    • value: any

    Returns Buffer

  • bufferifyFn

    Desc

    Returns a function that will bufferify the return value.

    Returns

    Example

    const fn = tree.bufferifyFn((value) => sha256(value))
    

    Parameters

    • f: any

    Returns any

  • getDepth

    Desc

    Returns the tree depth (number of layers)

    Returns

    Example

    const depth = tree.getDepth()
    

    Returns number

  • getHexLayers

    Desc

    Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root as hex strings.

    Returns

    Example

    const layers = tree.getHexLayers()
    

    Returns string[]

  • getHexLayersFlat

    Desc

    Returns single flat array of all layers of Merkle Tree, including leaves and root as hex string.

    Returns

    Example

    const layers = tree.getHexLayersFlat()
    

    Returns string[]

  • getHexLeaves

    Desc

    Returns array of leaves of Merkle Tree as hex strings.

    Returns

    Example

    const leaves = tree.getHexLeaves()
    

    Returns string[]

  • getHexMultiProof

    Desc

    Returns the multiproof for given tree indices as hex strings.

    Returns

    • Multiproofs as hex strings.

    Example

    const indices = [2, 5, 6]
    const proof = tree.getHexMultiProof(indices)

    Parameters

    • tree: string[] | Buffer[]
    • indices: number[]

      Tree indices.

    Returns string[]

  • getHexProof

    Desc

    Returns the proof for a target leaf as hex strings.

    Returns

    • Proof array as hex strings.

    Example

    const proof = tree.getHexProof(leaves[2])
    

    Parameters

    • leaf: string | Buffer

      Target leaf

    • Optional index: number

      Target leaf index in leaves array. Use if there are leaves containing duplicate data in order to distinguish it.

    Returns string[]

  • getHexProofs

    Desc

    Returns the proofs for all leaves as hex strings.

    Returns

    • Proofs array as hex strings.

    Example

    const proofs = tree.getHexProofs()
    

    Returns string[]

  • getHexRoot

    Desc

    Returns the Merkle root hash as a hex string.

    Returns

    Example

    const root = tree.getHexRoot()
    

    Returns string

  • getLayerCount

    Desc

    Returns the total number of layers.

    Returns

    Example

    const count = tree.getLayerCount()
    

    Returns number

  • getLayers

    Desc

    Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root.

    Returns

    Example

    const layers = tree.getLayers()
    

    Returns Buffer[]

  • getLayersAsObject

    Desc

    Returns the layers as nested objects instead of an array.

    Example

    const layersObj = tree.getLayersAsObject()
    

    Returns any

  • getLayersFlat

    Desc

    Returns single flat array of all layers of Merkle Tree, including leaves and root.

    Returns

    Example

    const layers = tree.getLayersFlat()
    

    Returns Buffer[]

  • getLeaf

    Desc

    Returns the leaf at the given index.

    Returns

    Example

    const leaf = tree.getLeaf(1)
    

    Parameters

    • index: number

    Returns Buffer

  • getLeafCount

    Desc

    Returns the total number of leaves.

    Returns

    Example

    const count = tree.getLeafCount()
    

    Returns number

  • getLeafIndex

    Desc

    Returns the index of the given leaf, or -1 if the leaf is not found.

    Returns

    Example

    const leaf = Buffer.from('abc')
    const index = tree.getLeafIndex(leaf)

    Parameters

    Returns number

  • getLeaves

    Desc

    Returns array of leaves of Merkle Tree.

    Returns

    Example

    const leaves = tree.getLeaves()
    

    Parameters

    • Optional values: any[]

    Returns Buffer[]

  • getMultiProof

    Desc

    Returns the multiproof for given tree indices.

    Returns

    • Multiproofs

    Example

    const indices = [2, 5, 6]
    const proof = tree.getMultiProof(indices)

    Parameters

    • Optional tree: any[]
    • Optional indices: any[]

      Tree indices.

    Returns Buffer[]

  • Returns {
        complete: boolean;
        duplicateOdd: boolean;
        fillDefaultHash: string;
        hashLeaves: boolean;
        isBitcoinTree: boolean;
        sort: boolean;
        sortLeaves: boolean;
        sortPairs: boolean;
    }

    • complete: boolean
    • duplicateOdd: boolean
    • fillDefaultHash: string
    • hashLeaves: boolean
    • isBitcoinTree: boolean
    • sort: boolean
    • sortLeaves: boolean
    • sortPairs: boolean
  • getPositionalHexProof

    Desc

    Returns the proof for a target leaf as hex strings and the position in binary (left == 0).

    Returns

    • Proof array as hex strings. position at index 0

    Example

    const proof = tree.getPositionalHexProof(leaves[2])
    

    Parameters

    • leaf: string | Buffer

      Target leaf

    • Optional index: number

      Target leaf index in leaves array. Use if there are leaves containing duplicate data in order to distinguish it.

    Returns (string | number)[][]

  • getProof

    Desc

    Returns the proof for a target leaf.

    Returns

    • Array of objects containing a position property of type string with values of 'left' or 'right' and a data property of type Buffer.

    Example

    const proof = tree.getProof(leaves[2])
    

    Example

    const leaves = ['a', 'b', 'a'].map(value => keccak(value))
    const tree = new MerkleTree(leaves, keccak)
    const proof = tree.getProof(leaves[2], 2)

    Parameters

    • leaf: string | Buffer

      Target leaf

    • Optional index: number

      Target leaf index in leaves array. Use if there are leaves containing duplicate data in order to distinguish it.

    Returns {
        data: Buffer;
        position: "left" | "right";
    }[]

  • getProofFlags

    Desc

    Returns list of booleans where proofs should be used instead of hashing. Proof flags are used in the Solidity multiproof verifiers.

    Returns

    • Boolean flags

    Example

    const indices = [2, 5, 6]
    const proof = tree.getMultiProof(indices)
    const proofFlags = tree.getProofFlags(leaves, proof)

    Parameters

    • leaves: any[]
    • proofs: string[] | Buffer[]

    Returns boolean[]

  • getProofIndices

    Desc

    Returns the proof indices for given tree indices.

    Returns

    • Proof indices

    Example

    const proofIndices = tree.getProofIndices([2,5,6], 4)
    console.log(proofIndices) // [ 23, 20, 19, 8, 3 ]

    Parameters

    • treeIndices: number[]

      Tree indices

    • depth: number

      Tree depth; number of layers.

    Returns number[]

  • getProofs

    Desc

    Returns the proofs for all leaves.

    Returns

    • Array of objects containing a position property of type string with values of 'left' or 'right' and a data property of type Buffer for all leaves.

    Example

    const proofs = tree.getProofs()
    

    Example

    const leaves = ['a', 'b', 'a'].map(value => keccak(value))
    const tree = new MerkleTree(leaves, keccak)
    const proofs = tree.getProofs()

    Returns any[]

  • getProofsDFS

    Desc

    Get all proofs through single traverse

    Example

    const layers = tree.getLayers()
    const index = 0;
    let proof = [];
    let proofs = [];
    const proof = tree.getProofsDFS(layers, index, proof, proofs)

    Parameters

    • currentLayer: any

      Current layer index in traverse.

    • index: any

      Current tarvese node index in traverse.

    • proof: any

      Proof chain for single leaf.

    • proofs: any

      Proofs for all leaves

    Returns any[]

  • getRoot

    Desc

    Returns the Merkle root hash as a Buffer.

    Returns

    Example

    const root = tree.getRoot()
    

    Returns Buffer

  • isHexString

    Desc

    Returns true if value is a hex string.

    Returns

    Example

    console.log(MerkleTree.isHexString('0x1234'))
    

    Parameters

    • value: string

    Returns boolean

  • Parameters

    • Optional treeLayers: any[]

    Returns boolean

  • linearSearch

    Desc

    Returns the first index of which given item is found in array using linear search.

    Returns

    • Index number

    Example

    const index = tree.linearSearch(array, element, (a, b) => a === b)
    

    Parameters

    • array: Buffer[]

      Array of items.

    • element: Buffer

      Item to find.

    • eqChecker: ((a: unknown, b: unknown) => boolean)
        • (a: unknown, b: unknown): boolean
        • Parameters

          • a: unknown
          • b: unknown

          Returns boolean

    Returns number

  • log2

    Desc

    Returns the log2 of number.

    Returns

    Parameters

    • n: number

    Returns number

  • print

    Desc

    Prints out a visual representation of the merkle tree.

    Example

    tree.print()
    

    Returns void

  • resetTree

    Desc

    Resets the tree by clearing the leaves and layers.

    Example

    tree.resetTree()
    

    Returns void

  • toString

    Desc

    Returns a visual representation of the merkle tree as a string.

    Example

    console.log(tree.toString())
    

    Returns string

  • toTreeString

    Desc

    Returns a visual representation of the merkle tree as a string.

    Returns

    Example

    console.log(tree.toTreeString())
    

    Returns string

  • verify

    Desc

    Returns true if the proof path (array of hashes) can connect the target node to the Merkle root.

    Returns

    Example

    const root = tree.getRoot()
    const proof = tree.getProof(leaves[2])
    const verified = tree.verify(proof, leaves[2], root)

    Parameters

    • proof: any[]

      Array of proof objects that should connect target node to Merkle root.

    • targetNode: string | Buffer

      Target node Buffer

    • root: string | Buffer

      Merkle root Buffer

    Returns boolean

  • verifyMultiProof

    Desc

    Returns true if the multiproofs can connect the leaves to the Merkle root.

    Returns

    Example

    const leaves = tree.getLeaves()
    const root = tree.getRoot()
    const treeFlat = tree.getLayersFlat()
    const leavesCount = leaves.length
    const proofIndices = [2, 5, 6]
    const proofLeaves = proofIndices.map(i => leaves[i])
    const proof = tree.getMultiProof(treeFlat, indices)
    const verified = tree.verifyMultiProof(root, proofIndices, proofLeaves, leavesCount, proof)

    Parameters

    • root: string | Buffer

      Merkle tree root

    • proofIndices: number[]

      Leave indices for proof

    • proofLeaves: string[] | Buffer[]

      Leaf values at indices for proof

    • leavesCount: number

      Count of original leaves

    • proof: string[] | Buffer[]

      Multiproofs given indices

    Returns boolean

  • Parameters

    Returns boolean

  • zip

    Desc

    Returns true if value is a hex string.

    Returns

    Example

    const zipped = tree.zip(['a', 'b'],['A', 'B'])
    console.log(zipped) // [ [ 'a', 'A' ], [ 'b', 'B' ] ]

    Parameters

    • a: any[]

      first array

    • b: any[]

      second array

    Returns any[][]

  • Parameters

    • value: any

    Returns BigInt

  • binarySearch

    Desc

    Returns the first index of which given item is found in array using binary search.

    Returns

    • Index number

    Example

    const index = MerkleTree.binarySearch(array, element, Buffer.compare)
    

    Parameters

    • array: Buffer[]

      Array of items.

    • element: Buffer

      Item to find.

    • compareFunction: ((a: unknown, b: unknown) => number)
        • (a: unknown, b: unknown): number
        • Parameters

          • a: unknown
          • b: unknown

          Returns number

    Returns number

  • bufferToHex

    Desc

    Returns a hex string with 0x prefix for given buffer.

    Returns

    Example

    const hexStr = MerkleTree.bufferToHex(Buffer.from('A'))
    

    Parameters

    • value: Buffer
    • Optional withPrefix: boolean

    Returns string

  • bufferify

    Desc

    Returns a buffer type for the given value.

    Returns

    Example

    const buf = MerkleTree.bufferify('0x1234')
    

    Parameters

    • value: any

    Returns Buffer

  • getMultiProof

    Desc

    Returns the multiproof for given tree indices.

    Returns

    • Multiproofs

    Example

    const flatTree = tree.getLayersFlat()
    const indices = [2, 5, 6]
    const proof = MerkleTree.getMultiProof(flatTree, indices)

    Parameters

    • tree: string[] | Buffer[]

      Tree as a flat array.

    • indices: number[]

      Tree indices.

    Returns Buffer[]

  • Parameters

    • hexStr: string
    • length: number

    Returns string

  • isHexString

    Desc

    Returns true if value is a hex string.

    Returns

    Example

    console.log(MerkleTree.isHexString('0x1234'))
    

    Parameters

    • v: string

    Returns boolean

  • linearSearch

    Desc

    Returns the first index of which given item is found in array using linear search.

    Returns

    • Index number

    Example

    const index = MerkleTree.linearSearch(array, element, (a, b) => a === b)
    

    Parameters

    • array: Buffer[]

      Array of items.

    • element: Buffer

      Item to find.

    • eqChecker: ((a: unknown, b: unknown) => boolean)
        • (a: unknown, b: unknown): boolean
        • Parameters

          • a: unknown
          • b: unknown

          Returns boolean

    Returns number

  • marshalLeaves

    Desc

    Returns array of leaves of Merkle Tree as a JSON string.

    Returns

    • List of leaves as JSON string

    Example

    const jsonStr = MerkleTree.marshalLeaves(leaves)
    

    Parameters

    • leaves: any[]

    Returns string

  • marshalProof

    Desc

    Returns proof array as JSON string.

    Returns

    • Proof array as JSON string.

    Example

    const jsonStr = MerkleTree.marshalProof(proof)
    

    Parameters

    • proof: any[]

      Merkle tree proof array

    Returns string

  • Parameters

    Returns string

  • print

    Desc

    Prints out a visual representation of the given merkle tree.

    Returns

    Example

    MerkleTree.print(tree)
    

    Parameters

    • tree: any

      Merkle tree instance.

    Returns void

  • unmarshalLeaves

    Desc

    Returns array of leaves of Merkle Tree as a Buffers.

    Returns

    • Unmarshalled list of leaves

    Example

    const leaves = MerkleTree.unmarshalLeaves(jsonStr)
    

    Parameters

    • jsonStr: string | object

    Returns Buffer[]

  • unmarshalProof

    Desc

    Returns the proof for a target leaf as a list of Buffers.

    Returns

    • Marshalled proof

    Example

    const proof = MerkleTree.unmarshalProof(jsonStr)
    

    Parameters

    • jsonStr: string | object

    Returns any[]

  • Parameters

    • jsonStr: string | object
    • Optional hashFn: any
    • Optional options: Options

    Returns MerkleTree

  • verify

    Desc

    Returns true if the proof path (array of hashes) can connect the target node to the Merkle root.

    Returns

    Example

    const verified = MerkleTree.verify(proof, leaf, root, sha256, options)
    

    Parameters

    • proof: any[]

      Array of proof objects that should connect target node to Merkle root.

    • targetNode: string | Buffer

      Target node Buffer

    • root: string | Buffer

      Merkle root Buffer

    • Optional hashFn: any
    • Optional options: Options

      Additional options

    Returns boolean

Generated using TypeDoc