merkletreejs › Globals › "src/MerkleTree" › MerkleTree

Class: MerkleTree

Class reprensenting a Merkle Tree

namespace MerkleTree

Hierarchy

Base

↳ MerkleTree

Index

Constructors

constructor

Methods

addLeaf
addLeaves
bigNumberify
binarySearch
bufferIndexOf
bufferToHex
bufferify
bufferifyFn
getDepth
getHexLayers
getHexLayersFlat
getHexLeaves
getHexMultiProof
getHexProof
getHexProofs
getHexRoot
getLayerCount
getLayers
getLayersAsObject
getLayersFlat
getLeaf
getLeafCount
getLeafIndex
getLeaves
getMultiProof
getOptions
getPositionalHexProof
getProof
getProofFlags
getProofIndices
getProofs
getProofsDFS
getRoot
isHexString
isUnevenTree
linearSearch
log2
print
resetTree
toString
toTreeString
verify
verifyMultiProof
verifyMultiProofWithFlags
zip
bigNumberify
binarySearch
bufferToHex
bufferify
getMultiProof
hexZeroPad
isHexString
linearSearch
marshalLeaves
marshalProof
marshalTree
print
unmarshalLeaves
unmarshalProof
unmarshalTree
verify

Constructors

constructor

+ new MerkleTree(leaves: any[], hashFn: any, options: Options): MerkleTree

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:

Name	Type	Default	Description
`leaves`	any[]	-	Array of hashed leaves. Each leaf must be a Buffer.
`hashFn`	any	SHA256	-
`options`	Options	{}	Additional options

Returns: MerkleTree

Methods

addLeaf

▸ addLeaf(leaf: TLeaf, shouldHash: boolean): void

addLeaf

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

example

tree.addLeaf(newLeaf)

Parameters:

Name	Type	Default
`leaf`	TLeaf	-
`shouldHash`	boolean	false

Returns: void

addLeaves

▸ addLeaves(leaves: TLeaf[], shouldHash: boolean): void

addLeaves

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

example

tree.addLeaves(newLeaves)

Parameters:

Name	Type	Default
`leaves`	TLeaf[]	-
`shouldHash`	boolean	false

Returns: void

bigNumberify

▸ bigNumberify(value: any): BigInt

Inherited from Base.bigNumberify

Parameters:

Name	Type
`value`	any

Returns: BigInt

binarySearch

▸ binarySearch(array: Buffer[], element: Buffer, compareFunction: function): number

Inherited from Base.binarySearch

binarySearch

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

example

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

Parameters:

▪ array: Buffer[]

Array of items.

▪ element: Buffer

Item to find.

▪ compareFunction: function

▸ (a: unknown, b: unknown): number

Parameters:

Name	Type
`a`	unknown
`b`	unknown

Returns: number

Index number

`Protected` bufferIndexOf

▸ bufferIndexOf(array: Buffer[], element: Buffer, isSorted: boolean): number

Inherited from Base.bufferIndexOf

bufferIndexOf

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

example

const index = tree.bufferIndexOf(haystack, needle)

Parameters:

Name	Type	Default
`array`	Buffer[]	-
`element`	Buffer	-
`isSorted`	boolean	false

Returns: number

Index number

bufferToHex

▸ bufferToHex(value: Buffer, withPrefix: boolean): string

Inherited from Base.bufferToHex

bufferToHex

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

example

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

Parameters:

Name	Type	Default
`value`	Buffer	-
`withPrefix`	boolean	true

Returns: string

bufferify

▸ bufferify(value: any): Buffer

Inherited from Base.bufferify

bufferify

desc Returns a buffer type for the given value.

example

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

Parameters:

Name	Type
`value`	any

Returns: Buffer

bufferifyFn

▸ bufferifyFn(f: any): any

Inherited from Base.bufferifyFn

bufferifyFn

desc Returns a function that will bufferify the return value.

example

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

Parameters:

Name	Type
`f`	any

Returns: any

getDepth

▸ getDepth(): number

getDepth

desc Returns the tree depth (number of layers)

example

const depth = tree.getDepth()

Returns: number

getHexLayers

▸ getHexLayers(): string[][]

getHexLayers

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

example

const layers = tree.getHexLayers()

Returns: string[][]

getHexLayersFlat

▸ getHexLayersFlat(): string[]

getHexLayersFlat

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

example

const layers = tree.getHexLayersFlat()

Returns: string[]

getHexLeaves

▸ getHexLeaves(): string[]

getHexLeaves

desc Returns array of leaves of Merkle Tree as hex strings.

example

const leaves = tree.getHexLeaves()

Returns: string[]

getHexMultiProof

▸ getHexMultiProof(tree: Buffer[] | string[], indices: number[]): string[]

getHexMultiProof

desc Returns the multiproof for given tree indices as hex strings.

example

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

Parameters:

Name	Type	Description
`tree`	Buffer[] \| string[]	-
`indices`	number[]	Tree indices.

Returns: string[]

Multiproofs as hex strings.

getHexProof

▸ getHexProof(leaf: Buffer | string, index?: number): string[]

getHexProof

desc Returns the proof for a target leaf as hex strings.

example

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

Parameters:

Name	Type	Description
`leaf`	Buffer \| string	Target leaf
`index?`	number	-

Returns: string[]

Proof array as hex strings.

getHexProofs

▸ getHexProofs(): string[]

getHexProofs

desc Returns the proofs for all leaves as hex strings.

example

const proofs = tree.getHexProofs()

Returns: string[]

Proofs array as hex strings.

getHexRoot

▸ getHexRoot(): string

getHexRoot

desc Returns the Merkle root hash as a hex string.

example

const root = tree.getHexRoot()

Returns: string

getLayerCount

▸ getLayerCount(): number

getLayerCount

desc Returns the total number of layers.

example

const count = tree.getLayerCount()

Returns: number

getLayers

▸ getLayers(): Buffer[][]

getLayers

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

example

const layers = tree.getLayers()

Returns: Buffer[][]

getLayersAsObject

▸ getLayersAsObject(): any

getLayersAsObject

desc Returns the layers as nested objects instead of an array.

example

const layersObj = tree.getLayersAsObject()

Returns: any

getLayersFlat

▸ getLayersFlat(): Buffer[]

getLayersFlat

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

example

const layers = tree.getLayersFlat()

Returns: Buffer[]

getLeaf

▸ getLeaf(index: number): Buffer

getLeaf

desc Returns the leaf at the given index.

example

const leaf = tree.getLeaf(1)

Parameters:

Name	Type
`index`	number

Returns: Buffer

getLeafCount

▸ getLeafCount(): number

getLeafCount

desc Returns the total number of leaves.

example

const count = tree.getLeafCount()

Returns: number

getLeafIndex

▸ getLeafIndex(target: TLeaf): number

getLeafIndex

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

example

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

Parameters:

Name	Type
`target`	TLeaf

Returns: number

getLeaves

▸ getLeaves(values?: any[]): Buffer[]

getLeaves

desc Returns array of leaves of Merkle Tree.

example

const leaves = tree.getLeaves()

Parameters:

Name	Type
`values?`	any[]

Returns: Buffer[]

getMultiProof

▸ getMultiProof(tree?: any[], indices?: any[]): Buffer[]

getMultiProof

desc Returns the multiproof for given tree indices.

example

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

Parameters:

Name	Type	Description
`tree?`	any[]	-
`indices?`	any[]	Tree indices.

Returns: Buffer[]

Multiproofs

getOptions

▸ getOptions(): object

Returns: object

complete: boolean = this.complete
duplicateOdd: boolean = this.duplicateOdd
fillDefaultHash: string = this.fillDefaultHash?.toString() ?? null
hashLeaves: boolean = this.hashLeaves
isBitcoinTree: boolean = this.isBitcoinTree
sort: boolean = this.sort
sortLeaves: boolean = this.sortLeaves
sortPairs: boolean = this.sortPairs

getPositionalHexProof

▸ getPositionalHexProof(leaf: Buffer | string, index?: number): (string | number)[][]

getPositionalHexProof

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

example

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

Parameters:

Name	Type	Description
`leaf`	Buffer \| string	Target leaf
`index?`	number	-

Returns: (string | number)[][]

Proof array as hex strings. position at index 0

getProof

▸ getProof(leaf: Buffer | string, index?: number): object[]

getProof

desc Returns the proof for a target leaf.

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:

Name	Type	Description
`leaf`	Buffer \| string	Target leaf
`index?`	number	-

Returns: object[]

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

getProofFlags

▸ getProofFlags(leaves: any[], proofs: Buffer[] | string[]): boolean[]

getProofFlags

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

example

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

Parameters:

Name	Type
`leaves`	any[]
`proofs`	Buffer[] \| string[]

Returns: boolean[]

Boolean flags

getProofIndices

▸ getProofIndices(treeIndices: number[], depth: number): number[]

getProofIndices

desc Returns the proof indices for given tree indices.

example

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

Parameters:

Name	Type	Description
`treeIndices`	number[]	Tree indices
`depth`	number	Tree depth; number of layers.

Returns: number[]

Proof indices

getProofs

▸ getProofs(): any[]

getProofs

desc Returns the proofs 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[]

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.

getProofsDFS

▸ getProofsDFS(currentLayer: any, index: any, proof: any, proofs: any): 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:

Name	Type	Description
`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

▸ getRoot(): Buffer

getRoot

desc Returns the Merkle root hash as a Buffer.

example

const root = tree.getRoot()

Returns: Buffer

`Protected` isHexString

▸ isHexString(value: string): boolean

Inherited from Base.isHexString

isHexString

desc Returns true if value is a hex string.

example

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

Parameters:

Name	Type
`value`	string

Returns: boolean

isUnevenTree

▸ isUnevenTree(treeLayers?: any[]): boolean

Parameters:

Name	Type
`treeLayers?`	any[]

Returns: boolean

linearSearch

▸ linearSearch(array: Buffer[], element: Buffer, eqChecker: function): number

Inherited from Base.linearSearch

linearSearch

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

example

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

Parameters:

▪ array: Buffer[]

Array of items.

▪ element: Buffer

Item to find.

▪ eqChecker: function

▸ (a: unknown, b: unknown): boolean

Parameters:

Name	Type
`a`	unknown
`b`	unknown

Returns: number

Index number

`Protected` log2

▸ log2(n: number): number

Inherited from Base.log2

log2

desc Returns the log2 of number.

Parameters:

Name	Type
`n`	number

Returns: number

print

▸ print(): void

Inherited from Base.print

print

desc Prints out a visual representation of the merkle tree.

example

tree.print()

Returns: void

resetTree

▸ resetTree(): void

resetTree

desc Resets the tree by clearing the leaves and layers.

example

tree.resetTree()

Returns: void

toString

▸ toString(): string

toString

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

example

console.log(tree.toString())

Returns: string

`Protected` toTreeString

▸ toTreeString(): string

toTreeString

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

example

console.log(tree.toTreeString())

Returns: string

verify

▸ verify(proof: any[], targetNode: Buffer | string, root: Buffer | string): boolean

verify

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

example

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

Parameters:

Name	Type	Description
`proof`	any[]	Array of proof objects that should connect target node to Merkle root.
`targetNode`	Buffer \| string	Target node Buffer
`root`	Buffer \| string	Merkle root Buffer

Returns: boolean

verifyMultiProof

▸ verifyMultiProof(root: Buffer | string, proofIndices: number[], proofLeaves: Buffer[] | string[], leavesCount: number, proof: Buffer[] | string[]): boolean

verifyMultiProof

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

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:

Name	Type	Description
`root`	Buffer \| string	Merkle tree root
`proofIndices`	number[]	Leave indices for proof
`proofLeaves`	Buffer[] \| string[]	Leaf values at indices for proof
`leavesCount`	number	Count of original leaves
`proof`	Buffer[] \| string[]	Multiproofs given indices

Returns: boolean

verifyMultiProofWithFlags

▸ verifyMultiProofWithFlags(root: Buffer | string, leaves: TLeaf[], proofs: Buffer[] | string[], proofFlag: boolean[]): boolean

Parameters:

Name	Type
`root`	Buffer \| string
`leaves`	TLeaf[]
`proofs`	Buffer[] \| string[]
`proofFlag`	boolean[]

Returns: boolean

`Protected` zip

▸ zip(a: any[], b: any[]): any[][]

Inherited from Base.zip

zip

desc Returns true if value is a hex string.

example

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

Parameters:

Name	Type	Description
`a`	any[]	first array
`b`	any[]	second array

Returns: any[][]

`Static` bigNumberify

▸ bigNumberify(value: any): BigInt

Inherited from Base.bigNumberify

Parameters:

Name	Type
`value`	any

Returns: BigInt

`Static` binarySearch

▸ binarySearch(array: Buffer[], element: Buffer, compareFunction: function): number

Inherited from Base.binarySearch

binarySearch

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

example

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

Parameters:

▪ array: Buffer[]

Array of items.

▪ element: Buffer

Item to find.

▪ compareFunction: function

▸ (a: unknown, b: unknown): number

Parameters:

Name	Type
`a`	unknown
`b`	unknown

Returns: number

Index number

`Static` bufferToHex

▸ bufferToHex(value: Buffer, withPrefix: boolean): string

Inherited from Base.bufferToHex

bufferToHex

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

example

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

Parameters:

Name	Type	Default
`value`	Buffer	-
`withPrefix`	boolean	true

Returns: string

`Static` bufferify

▸ bufferify(value: any): Buffer

Inherited from Base.bufferify

bufferify

desc Returns a buffer type for the given value.

example

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

Parameters:

Name	Type
`value`	any

Returns: Buffer

`Static` getMultiProof

▸ getMultiProof(tree: Buffer[] | string[], indices: number[]): Buffer[]

getMultiProof

desc Returns the multiproof for given tree indices.

example

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

Parameters:

Name	Type	Description
`tree`	Buffer[] \| string[]	Tree as a flat array.
`indices`	number[]	Tree indices.

Returns: Buffer[]

Multiproofs

`Static` hexZeroPad

▸ hexZeroPad(hexStr: string, length: number): string

Inherited from Base.hexZeroPad

Parameters:

Name	Type
`hexStr`	string
`length`	number

Returns: string

`Static` isHexString

▸ isHexString(v: string): boolean

Inherited from Base.isHexString

isHexString

desc Returns true if value is a hex string.

example

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

Parameters:

Name	Type
`v`	string

Returns: boolean

`Static` linearSearch

▸ linearSearch(array: Buffer[], element: Buffer, eqChecker: function): number

Inherited from Base.linearSearch

linearSearch

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

example

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

Parameters:

▪ array: Buffer[]

Array of items.

▪ element: Buffer

Item to find.

▪ eqChecker: function

▸ (a: unknown, b: unknown): boolean

Parameters:

Name	Type
`a`	unknown
`b`	unknown

Returns: number

Index number

`Static` marshalLeaves

▸ marshalLeaves(leaves: any[]): string

marshalLeaves

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

example

const jsonStr = MerkleTree.marshalLeaves(leaves)

Parameters:

Name	Type
`leaves`	any[]

Returns: string

List of leaves as JSON string

`Static` marshalProof

▸ marshalProof(proof: any[]): string

marshalProof

desc Returns proof array as JSON string.

example

const jsonStr = MerkleTree.marshalProof(proof)

Parameters:

Name	Type	Description
`proof`	any[]	Merkle tree proof array

Returns: string

Proof array as JSON string.

`Static` marshalTree

▸ marshalTree(tree: MerkleTree): string

Parameters:

Name	Type
`tree`	MerkleTree

Returns: string

`Static` print

▸ print(tree: any): void

Inherited from Base.print

print

desc Prints out a visual representation of the given merkle tree.

example

MerkleTree.print(tree)

Parameters:

Name	Type	Description
`tree`	any	Merkle tree instance.

Returns: void

`Static` unmarshalLeaves

▸ unmarshalLeaves(jsonStr: string | object): Buffer[]

unmarshalLeaves

desc Returns array of leaves of Merkle Tree as a Buffers.

example

const leaves = MerkleTree.unmarshalLeaves(jsonStr)

Parameters:

Name	Type
`jsonStr`	string \| object

Returns: Buffer[]

Unmarshalled list of leaves

`Static` unmarshalProof

▸ unmarshalProof(jsonStr: string | object): any[]

unmarshalProof

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

example

const proof = MerkleTree.unmarshalProof(jsonStr)

Parameters:

Name	Type
`jsonStr`	string \| object

Returns: any[]

Marshalled proof

`Static` unmarshalTree

▸ unmarshalTree(jsonStr: string | object, hashFn: any, options: Options): MerkleTree

Parameters:

Name	Type	Default
`jsonStr`	string \| object	-
`hashFn`	any	SHA256
`options`	Options	{}

Returns: MerkleTree

`Static` verify

▸ verify(proof: any[], targetNode: Buffer | string, root: Buffer | string, hashFn: any, options: Options): boolean

verify

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

example

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

Parameters:

Name	Type	Default	Description
`proof`	any[]	-	Array of proof objects that should connect target node to Merkle root.
`targetNode`	Buffer \| string	-	Target node Buffer
`root`	Buffer \| string	-	Merkle root Buffer
`hashFn`	any	SHA256	-
`options`	Options	{}	Additional options

Returns: boolean

Files

_src_merkletree_.merkletree.md

Latest commit

History

_src_merkletree_.merkletree.md

File metadata and controls

Class: MerkleTree

Hierarchy

Index

Constructors

Methods

Constructors

constructor

Methods

addLeaf

addLeaves

bigNumberify

binarySearch

Protected bufferIndexOf

bufferToHex

bufferify

bufferifyFn

getDepth

getHexLayers

getHexLayersFlat

getHexLeaves

getHexMultiProof

getHexProof

getHexProofs

getHexRoot

getLayerCount

getLayers

getLayersAsObject

getLayersFlat

getLeaf

getLeafCount

getLeafIndex

getLeaves

getMultiProof

getOptions

getPositionalHexProof

getProof

getProofFlags

getProofIndices

getProofs

getProofsDFS

getRoot

Protected isHexString

isUnevenTree

linearSearch

Protected log2

print

resetTree

toString

Protected toTreeString

verify

verifyMultiProof

verifyMultiProofWithFlags

Protected zip

Static bigNumberify

Static binarySearch

Static bufferToHex

Static bufferify

Static getMultiProof

Static hexZeroPad

Static isHexString

Static linearSearch

Static marshalLeaves

Static marshalProof

Static marshalTree

Static print

Static unmarshalLeaves

Static unmarshalProof

Static unmarshalTree

Static verify

`Protected` bufferIndexOf

`Protected` isHexString

`Protected` log2

`Protected` toTreeString

`Protected` zip

`Static` bigNumberify

`Static` binarySearch

`Static` bufferToHex

`Static` bufferify

`Static` getMultiProof

`Static` hexZeroPad

`Static` isHexString

`Static` linearSearch

`Static` marshalLeaves

`Static` marshalProof

`Static` marshalTree

`Static` print

`Static` unmarshalLeaves

`Static` unmarshalProof

`Static` unmarshalTree

`Static` verify