Skip to main content
Version: 2.4.0

MerkleListIterator

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

MerkleListIterator helps iterating through a Merkle list. This works similar to calling list.pop() or list.push() repeatedly, but maintaining the entire list instead of removing elements.

The core methods that support iteration are () and ().

let iterator = MerkleListIterator.startIterating(list);

let firstElement = iterator.next();

We maintain two commitments:

  • One to the entire array, to be able to prove that we end iteration at the correct point.
  • One to the array from the current index until the end, to efficiently step forward.

Type Parameters

T

Implements

Constructors

new MerkleListIterator()

new MerkleListIterator<T>(value: MerkleListIteratorBase<T>): MerkleListIterator<T>

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

Parameters

value

MerkleListIteratorBase<T>

Returns

MerkleListIterator<T>

Properties

currentHash

currentHash: Field;

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

The merkle list hash of [data[currentIndex], ..., data[length-1]] (when hashing from right to left).

For example:

  • If currentIndex === 0, then currentHash === this.hash is the hash of the entire array.
  • If currentIndex === length, then currentHash === emptyHash is the hash of an empty array.

Implementation of

MerkleListIteratorBase.currentHash

currentIndex

currentIndex: Unconstrained<number>;

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

The index of the element that will be returned by the next call to next().

Implementation of

MerkleListIteratorBase.currentIndex

data

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

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

Implementation of

MerkleListIteratorBase.data

hash

readonly hash: Field;

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

Implementation of

MerkleListIteratorBase.hash

_emptyHash

static _emptyHash: undefined | Field;

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


_innerProvable

static _innerProvable: 
| undefined
| ProvableHashable<any>;

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


_nextHash

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

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


_provable

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

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

Accessors

Constructor

Get Signature

get Constructor(): typeof MerkleListIterator

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

Returns

typeof MerkleListIterator


innerProvable

Get Signature

get innerProvable(): ProvableHashable<T>

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

Returns

ProvableHashable<T>


Unsafe

Get Signature

get Unsafe(): {
next: {
element: T;
isDummy: Bool;
};
previous: {
element: T;
isDummy: Bool;
};
}

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

Low-level APIs for advanced uses

Returns
{
next: {
element: T;
isDummy: Bool;
};
previous: {
element: T;
isDummy: Bool;
};
}
next()

Version of next which doesn't guarantee anything about the returned element in case the iterator is at the end.

Instead, the isDummy flag is also returned so that this case can be handled in a custom way.

Returns
{
element: T;
isDummy: Bool;
}
element
element: T;
isDummy
isDummy: Bool;
previous()

Version of previous which doesn't guarantee anything about the returned element in case the iterator is at the start.

Instead, the isDummy flag is also returned so that this case can be handled in a custom way.

Returns
{
element: T;
isDummy: Bool;
}
element
element: T;
isDummy
isDummy: Bool;

emptyHash

Get Signature

get static emptyHash(): Field

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

Returns

Field

Methods

_index()

_index(direction: "next" | "previous", i?: number): number

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

Parameters

direction

"next" | "previous"

i?

number

Returns

number


_updateIndex()

_updateIndex(direction: "next" | "previous"): void

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

Parameters

direction

"next" | "previous"

Returns

void


assertAtEnd()

assertAtEnd(message?: string): void

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

Parameters

message?

string

Returns

void


assertAtStart()

assertAtStart(): void

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

Returns

void


clone()

clone(): MerkleListIterator<T>

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

Returns

MerkleListIterator<T>


isAtEnd()

isAtEnd(): Bool

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

Returns

Bool


isAtStart()

isAtStart(): Bool

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

Returns

Bool


jumpToEnd()

jumpToEnd(): void

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

Returns

void


jumpToEndIf()

jumpToEndIf(condition: Bool): void

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

Parameters

condition

Bool

Returns

void


jumpToStart()

jumpToStart(): void

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

Returns

void


jumpToStartIf()

jumpToStartIf(condition: Bool): void

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

Parameters

condition

Bool

Returns

void


next()

next(): T

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

Returns

T


nextHash()

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

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

Parameters

hash

Field

value

T

Returns

Field


previous()

previous(): T

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

Returns

T


create()

static create<T>(
type: WithProvable<ProvableHashable<T>>,
nextHash: (hash: Field, value: T) => Field,
emptyHash_: Field): typeof MerkleListIterator & {
empty: () => MerkleListIterator<T>;
from: (array: T[]) => MerkleListIterator<T>;
provable: ProvableHashable<MerkleListIterator<T>>;
startIterating: (list: MerkleListBase<T>) => MerkleListIterator<T>;
startIteratingFromLast: (list: MerkleListBase<T>) => MerkleListIterator<T>;
}

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

Create a Merkle array type

Type Parameters

T

Parameters

type

WithProvable<ProvableHashable<T>>

nextHash

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

emptyHash_

Field = emptyHash

Returns

typeof MerkleListIterator & { empty: () => MerkleListIterator<T>; from: (array: T[]) => MerkleListIterator<T>; provable: ProvableHashable<MerkleListIterator<T>>; startIterating: (list: MerkleListBase<T>) => MerkleListIterator<T>; startIteratingFromLast: (list: MerkleListBase<T>) => MerkleListIterator<T>; }


createFromList()

static createFromList<T>(merkleList: typeof MerkleList): (value: MerkleListIteratorBase<T>) => MerkleListIterator<T> & {
empty: () => MerkleListIterator<T>;
from: (array: T[]) => MerkleListIterator<T>;
provable: ProvableHashable<MerkleListIterator<T>>;
startIterating: (list: MerkleListBase<T>) => MerkleListIterator<T>;
startIteratingFromLast: (list: MerkleListBase<T>) => MerkleListIterator<T>;
}

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

Type Parameters

T

Parameters

merkleList

typeof MerkleList

Returns

(value: MerkleListIteratorBase<T>) => MerkleListIterator<T> & { empty: () => MerkleListIterator<T>; from: (array: T[]) => MerkleListIterator<T>; provable: ProvableHashable<MerkleListIterator<T>>; startIterating: (list: MerkleListBase<T>) => MerkleListIterator<T>; startIteratingFromLast: (list: MerkleListBase<T>) => MerkleListIterator<T>; }