_src_merkletree_.merkletree.md

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