Skip to main content

MerkleTree

o1js / Modules / MerkleTree

Class: MerkleTree

A Merkle Tree is a binary tree in which every leaf is the cryptography hash of a piece of data, and every node is the hash of the concatenation of its two child nodes.

A Merkle Tree allows developers to easily and securely verify the integrity of large amounts of data.

Take a look at our documentation on how to use Merkle Trees in combination with zkApps and zero knowledge programming!

Levels are indexed from leaves (level 0) to root (level N - 1).

Table of contents

Constructors

Properties

Accessors

Methods

Constructors

constructor

new MerkleTree(height)

Creates a new, empty Merkle Tree.

Parameters

NameTypeDescription
heightnumberThe height of Merkle Tree.

Defined in

lib/merkle_tree.ts:38

Properties

height

Readonly height: number

The height of Merkle Tree.

Defined in

lib/merkle_tree.ts:38


nodes

Private nodes: Record\<number, Record\<string, Field>> = {}

Defined in

lib/merkle_tree.ts:30


zeroes

Private zeroes: Field[]

Defined in

lib/merkle_tree.ts:31

Accessors

leafCount

get leafCount(): bigint

Returns the amount of leaf nodes.

Returns

bigint

Amount of leaf nodes.

Defined in

lib/merkle_tree.ts:147

Methods

fill

fill(leaves): void

Fills all leaves of the tree.

Parameters

NameTypeDescription
leavesField[]Values to fill the leaves with.

Returns

void

Defined in

lib/merkle_tree.ts:137


getNode

getNode(level, index): Field

Returns a node which lives at a given index and level.

Parameters

NameTypeDescription
levelnumberLevel of the node.
indexbigintIndex of the node.

Returns

Field

The data of the node.

Defined in

lib/merkle_tree.ts:52


getRoot

getRoot(): Field

Returns the root of the Merkle Tree.

Returns

Field

The root of the Merkle Tree.

Defined in

lib/merkle_tree.ts:60


getWitness

getWitness(index): Witness

Returns the witness (also known as Merkle Proof or Merkle Witness) for the leaf at the given index.

Parameters

NameTypeDescription
indexbigintPosition of the leaf node.

Returns

Witness

The witness that belongs to the leaf.

Defined in

lib/merkle_tree.ts:98


setLeaf

setLeaf(index, leaf): void

Sets the value of a leaf node at a given index to a given value.

Parameters

NameTypeDescription
indexbigintPosition of the leaf node.
leafFieldNew value.

Returns

void

Defined in

lib/merkle_tree.ts:75


setNode

Private setNode(level, index, value): void

Parameters

NameType
levelnumber
indexbigint
valueField

Returns

void

Defined in

lib/merkle_tree.ts:65


validate

validate(index): boolean

Checks if the witness that belongs to the leaf at the given index is a valid witness.

Parameters

NameTypeDescription
indexbigintPosition of the leaf node.

Returns

boolean

True if the witness for the leaf node is valid.

Defined in

lib/merkle_tree.ts:120