Skip to main content

MerkleList

Defined in: lib/provable/merkle-list.ts:81

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>

Defined in: lib/provable/merkle-list.ts:85

Parameters

__namedParameters

MerkleListBase<T>

Returns

MerkleList<T>

Properties

data

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

Defined in: lib/provable/merkle-list.ts:83

Implementation of

MerkleListBase.data

hash

hash: Field;

Defined in: lib/provable/merkle-list.ts:82

Implementation of

MerkleListBase.hash

_emptyHash

static _emptyHash: undefined | Field;

Defined in: lib/provable/merkle-list.ts:348


_innerProvable

static _innerProvable: 
| undefined
| ProvableHashable<any>;

Defined in: lib/provable/merkle-list.ts:351


_nextHash

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

Defined in: lib/provable/merkle-list.ts:347


_provable

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

Defined in: lib/provable/merkle-list.ts:350

Accessors

Constructor

Get Signature

get Constructor(): typeof MerkleList

Defined in: lib/provable/merkle-list.ts:353

Returns

typeof MerkleList


innerProvable

Get Signature

get innerProvable(): ProvableHashable<T>

Defined in: lib/provable/merkle-list.ts:367

Returns

ProvableHashable<T>


emptyHash

Get Signature

get static emptyHash(): Field

Defined in: lib/provable/merkle-list.ts:362

Returns

Field

Methods

clone()

clone(): MerkleList<T>

Defined in: lib/provable/merkle-list.ts:236

Returns

MerkleList<T>


forEach()

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

Defined in: lib/provable/merkle-list.ts:250

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

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

Returns

void


isEmpty()

isEmpty(): Bool

Defined in: lib/provable/merkle-list.ts:90

Returns

Bool


lengthUnconstrained()

lengthUnconstrained(): Unconstrained<number>

Defined in: lib/provable/merkle-list.ts:273

Returns

Unconstrained<number>


nextHash()

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

Defined in: lib/provable/merkle-list.ts:357

Parameters

hash

Field

value

T

Returns

Field


pop()

pop(): T

Defined in: lib/provable/merkle-list.ts:152

Remove the last element from the list and return it.

If the list is empty, returns a dummy element.

Returns

T


popExn()

popExn(): T

Defined in: lib/provable/merkle-list.ts:137

Remove the last element from the list and return it.

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

Returns

T


popIf()

popIf(condition: Bool): T

Defined in: lib/provable/merkle-list.ts:192

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


popIfUnsafe()

popIfUnsafe(shouldPop: Bool): T

Defined in: lib/provable/merkle-list.ts:216

Low-level, minimal version of pop() which lets the caller decide whether there is an element to pop.

I.e. this proves:

  • If the input condition is true, this returns the last element and removes it from the list.
  • If the input condition is false, the list is unchanged and the return value is garbage.

Note that if the caller passes true but the list is empty, this will fail. If the caller passes false but the list is non-empty, this succeeds and just doesn't pop off an element.

Parameters

shouldPop

Bool

Returns

T


popOption()

popOption(): Option<T>

Defined in: lib/provable/merkle-list.ts:172

Remove the last element from the list and return it as an option: Some(element) if the list is non-empty, None if the list is empty.

Warning: If the list is empty, the the option's .value is entirely unconstrained.

Returns

Option<T>


push()

push(element: T): void

Defined in: lib/provable/merkle-list.ts:97

Push a new element to the list.

Parameters

element

T

Returns

void


pushIf()

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

Defined in: lib/provable/merkle-list.ts:109

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

Parameters

condition

Bool

element

T

Returns

void


startIterating()

startIterating(): MerkleListIterator<T>

Defined in: lib/provable/merkle-list.ts:259

Returns

MerkleListIterator<T>


startIteratingFromLast()

startIteratingFromLast(): MerkleListIterator<T>

Defined in: lib/provable/merkle-list.ts:264

Returns

MerkleListIterator<T>


toArrayUnconstrained()

toArrayUnconstrained(): Unconstrained<T[]>

Defined in: lib/provable/merkle-list.ts:269

Returns

Unconstrained<T[]>


create()

static create<T>(
type: WithProvable<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>>;
}

Defined in: lib/provable/merkle-list.ts:289

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

WithProvable<ProvableHashable<T>>

nextHash

(hash: Field, value: T) => Field

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])
) {}