Skip to main content

MerkleListIterator

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>

Parameters​

• value: MerkleListIteratorBase\<T>

Returns​

MerkleListIterator\<T>

Source​

lib/provable/merkle-list.ts:426

Properties​

currentHash​

currentHash: Field;

Implementation of​

MerkleListIteratorBase.currentHash

Source​

lib/provable/merkle-list.ts:423

currentIndex​

currentIndex: Unconstrained<number>;

Implementation of​

MerkleListIteratorBase.currentIndex

Source​

lib/provable/merkle-list.ts:424

data​

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

Implementation of​

MerkleListIteratorBase.data

Source​

lib/provable/merkle-list.ts:419

hash​

readonly hash: Field;

Implementation of​

MerkleListIteratorBase.hash

Source​

lib/provable/merkle-list.ts:420

_emptyHash​

static _emptyHash: undefined | Field;

Source​

lib/provable/merkle-list.ts:722

_innerProvable​

static _innerProvable: undefined | ProvableHashable<any>;

Source​

lib/provable/merkle-list.ts:725

_nextHash​

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

Source​

lib/provable/merkle-list.ts:721

_provable​

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

Source​

lib/provable/merkle-list.ts:724

Accessors​

Constructor​

get Constructor(): typeof MerkleListIterator

Returns​

typeof MerkleListIterator

Source​

lib/provable/merkle-list.ts:727

Unsafe​

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

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;

Source​

lib/provable/merkle-list.ts:556

innerProvable​

get innerProvable(): ProvableHashable<T>

Returns​

ProvableHashable\<T>

Source​

lib/provable/merkle-list.ts:744

emptyHash​

get static emptyHash(): Field

Returns​

Field

Source​

lib/provable/merkle-list.ts:739

Methods​

_index()​

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

Parameters​

• direction: "next" | "previous"

• i?: number

Returns​

number

Source​

lib/provable/merkle-list.ts:483

_updateIndex()​

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

Parameters​

• direction: "next" | "previous"

Returns​

void

Source​

lib/provable/merkle-list.ts:491

assertAtEnd()​

assertAtEnd(message?: string): void

Parameters​

• message?: string

Returns​

void

Source​

lib/provable/merkle-list.ts:452

assertAtStart()​

assertAtStart(): void

Returns​

void

Source​

lib/provable/merkle-list.ts:430

clone()​

clone(): MerkleListIterator<T>

Returns​

MerkleListIterator\<T>

Source​

lib/provable/merkle-list.ts:613

isAtEnd()​

isAtEnd(): Bool

Returns​

Bool

Source​

lib/provable/merkle-list.ts:434

isAtStart()​

isAtStart(): Bool

Returns​

Bool

Source​

lib/provable/merkle-list.ts:459

jumpToEnd()​

jumpToEnd(): void

Returns​

void

Source​

lib/provable/merkle-list.ts:438

jumpToEndIf()​

jumpToEndIf(condition: Bool): void

Parameters​

• condition: Bool

Returns​

void

Source​

lib/provable/merkle-list.ts:443

jumpToStart()​

jumpToStart(): void

Returns​

void

Source​

lib/provable/merkle-list.ts:463

jumpToStartIf()​

jumpToStartIf(condition: Bool): void

Parameters​

• condition: Bool

Returns​

void

Source​

lib/provable/merkle-list.ts:470

next()​

next(): T

Returns​

T

Source​

lib/provable/merkle-list.ts:529

nextHash()​

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

Parameters​

• hash: Field

• value: T

Returns​

Field

Source​

lib/provable/merkle-list.ts:731

previous()​

previous(): T

Returns​

T

Source​

lib/provable/merkle-list.ts:498

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>;
}

Create a Merkle array type

Type parameters​

• T

Parameters​

• type: WithProvable\<ProvableHashable\<T>>

• nextHash= undefined

• 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>; }

Source​

lib/provable/merkle-list.ts:627

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>;
}

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>; }

Source​

lib/provable/merkle-list.ts:712