merkletreejs › Globals › "src/MerkleTree" › MerkleTree

Class: MerkleTree

Class reprensenting a Merkle Tree

namespace MerkleTree

Hierarchy

Base

↳ MerkleTree

Index

Constructors

constructor

Methods

_bufferIndexOf
_isHexString
_log2
_toTreeString
_zip
addLeaf
addLeaves
bufferToHex
bufferify
bufferifyFn
getDepth
getHexLayers
getHexLayersFlat
getHexLeaves
getHexMultiProof
getHexProof
getHexRoot
getLayerCount
getLayers
getLayersAsObject
getLayersFlat
getLeaf
getLeafCount
getLeafIndex
getLeaves
getMultiProof
getPositionalHexProof
getProof
getProofFlags
getProofIndices
getRoot
isUnevenTree
print
resetTree
toString
verify
verifyMultiProof
verifyMultiProofWithFlags
bufferToHex
bufferify
getMultiProof
isHexString
marshalLeaves
marshalProof
print
unmarshalLeaves
unmarshalProof
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

`Protected` _bufferIndexOf

▸ _bufferIndexOf(array: Buffer[], element: Buffer): 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
`array`	Buffer[]
`element`	Buffer

Returns: number

Index number

`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

`Protected` _log2

▸ _log2(n: number): number

Inherited from Base._log2

log2

desc Returns the log2 of number.

Parameters:

Name	Type
`n`	number

Returns: number

`Protected` _toTreeString

▸ _toTreeString(): string

toTreeString

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

example

console.log(tree.toTreeString())

Returns: string

`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[][]

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

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.

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

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): any[]

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: any[]

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

getRoot

▸ getRoot(): Buffer

getRoot

desc Returns the Merkle root hash as a Buffer.

example

const root = tree.getRoot()

Returns: Buffer

isUnevenTree

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

Parameters:

Name	Type
`treeLayers?`	any[]

Returns: boolean

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

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

`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` 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` 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` 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` 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

Protected _bufferIndexOf

Protected _isHexString

Protected _log2

Protected _toTreeString

Protected _zip

addLeaf

addLeaves

bufferToHex

bufferify

bufferifyFn

getDepth

getHexLayers

getHexLayersFlat

getHexLeaves

getHexMultiProof

getHexProof

getHexRoot

getLayerCount

getLayers

getLayersAsObject

getLayersFlat

getLeaf

getLeafCount

getLeafIndex

getLeaves

getMultiProof

getPositionalHexProof

getProof

getProofFlags

getProofIndices

getRoot

isUnevenTree

print

resetTree

toString

verify

verifyMultiProof

verifyMultiProofWithFlags

Static bufferToHex

Static bufferify

Static getMultiProof

Static isHexString

Static marshalLeaves

Static marshalProof

Static print

Static unmarshalLeaves

Static unmarshalProof

Static verify

`Protected` _bufferIndexOf

`Protected` _isHexString

`Protected` _log2

`Protected` _toTreeString

`Protected` _zip

`Static` bufferToHex

`Static` bufferify

`Static` getMultiProof

`Static` isHexString

`Static` marshalLeaves

`Static` marshalProof

`Static` print

`Static` unmarshalLeaves

`Static` unmarshalProof

`Static` verify