Skip to main content

MerkleList

Dynamic-length list which is represented as a single hash

Supported operations are () and () and some variants thereof.

A Merkle list is generic over its element types, so before using it you must create a subclass for your element type:

class MyList extends MerkleList.create(MyType) {}

// now use it
let list = MyList.empty();

list.push(new MyType(...));

let element = list.pop();

Internal detail: push() adds elements to the start of the internal array and pop() removes them from the start. This is so that the hash which represents the list is consistent with MerkleListIterator, and so a MerkleList can be used as input to MerkleListIterator.startIterating(list) (which will then iterate starting from the last pushed element).

Extended by

Type parameters

T

Implements

Constructors

new MerkleList()

new MerkleList<T>(__namedParameters: MerkleListBase<T>): MerkleList<T>

Parameters

__namedParameters: MerkleListBase\<T>

Returns

MerkleList\<T>

Source

lib/provable/merkle-list.ts:83

Properties

data

data: Unconstrained<WithHash<T>[]>;

Implementation of

MerkleListBase.data

Source

lib/provable/merkle-list.ts:81


hash

hash: Field;

Implementation of

MerkleListBase.hash

Source

lib/provable/merkle-list.ts:80


_emptyHash

static _emptyHash: undefined | Field;

Source

lib/provable/merkle-list.ts:297


_innerProvable

static _innerProvable: undefined | ProvableHashable<any>;

Source

lib/provable/merkle-list.ts:300


_nextHash

static _nextHash: undefined | (hash: Field, t: any) => Field;

Source

lib/provable/merkle-list.ts:296


_provable

static _provable: undefined | ProvableHashable<MerkleList<any>>;

Source

lib/provable/merkle-list.ts:299

Accessors

Constructor

get Constructor(): typeof MerkleList

Returns

typeof MerkleList

Source

lib/provable/merkle-list.ts:302


innerProvable

get innerProvable(): ProvableHashable<T>

Returns

ProvableHashable\<T>

Source

lib/provable/merkle-list.ts:319


emptyHash

get static emptyHash(): Field

Returns

Field

Source

lib/provable/merkle-list.ts:314

Methods

clone()

clone(): MerkleList<T>

Returns

MerkleList\<T>

Source

lib/provable/merkle-list.ts:189


forEach()

forEach(length: number, callback: (element: T, isDummy: Bool, i: number) => void): void

Iterate through the list in a fixed number of steps any apply a given callback on each element.

Proves that the iteration traverses the entire list. Once past the last element, dummy elements will be passed to the callback.

Note: There are no guarantees about the contents of dummy elements, so the callback is expected to handle the isDummy flag separately.

Parameters

length: number

callback

Returns

void

Source

lib/provable/merkle-list.ts:203


isEmpty()

isEmpty(): Bool

Returns

Bool

Source

lib/provable/merkle-list.ts:88


nextHash()

nextHash(hash: Field, value: T): Field

Parameters

hash: Field

value: T

Returns

Field

Source

lib/provable/merkle-list.ts:306


pop()

pop(): T

Remove the last element from the list and return it.

If the list is empty, returns a dummy element.

Returns

T

Source

lib/provable/merkle-list.ts:154


popExn()

popExn(): T

Remove the last element from the list and return it.

This proves that the list is non-empty, and fails otherwise.

Returns

T

Source

lib/provable/merkle-list.ts:139


popIf()

popIf(condition: Bool): T

Return the last element, but only remove it if condition is true.

If the list is empty, returns a dummy element.

Parameters

condition: Bool

Returns

T

Source

lib/provable/merkle-list.ts:173


push()

push(element: T): void

Push a new element to the list.

Parameters

element: T

Returns

void

Source

lib/provable/merkle-list.ts:95


pushIf()

pushIf(condition: Bool, element: T): void

Push a new element to the list, if the condition is true.

Parameters

condition: Bool

element: T

Returns

void

Source

lib/provable/merkle-list.ts:107


startIterating()

startIterating(): MerkleListIterator<T>

Returns

MerkleListIterator\<T>

Source

lib/provable/merkle-list.ts:217


startIteratingFromLast()

startIteratingFromLast(): MerkleListIterator<T>

Returns

MerkleListIterator\<T>

Source

lib/provable/merkle-list.ts:222


create()

static create<T>(
type: ProvableHashable<T>,
nextHash: (hash: Field, value: T) => Field,
emptyHash_: Field): typeof MerkleList & {
"empty": () => MerkleList<T>;
"from": (array: T[]) => MerkleList<T>;
"fromReverse": (array: T[]) => MerkleList<T>;
"provable": ProvableHashable<MerkleList<T>>;
}

Create a Merkle list type

Optionally, you can tell create() how to do the hash that pushes a new list element, by passing a nextHash function.

Type parameters

T

Parameters

type: ProvableHashable\<T>

nextHash= undefined

emptyHash_: Field= emptyHash

Returns

typeof MerkleList & { "empty": () => MerkleList\<T>; "from": (array: T[]) => MerkleList\<T>; "fromReverse": (array: T[]) => MerkleList\<T>; "provable": ProvableHashable\<MerkleList\<T>>; }

Example

class MyList extends MerkleList.create(Field, (hash, x) =>
Poseidon.hashWithPrefix('custom', [hash, x])
) {}

Source

lib/provable/merkle-list.ts:239