Skip to main content
Version: 2.15.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​

T

Implements​

Constructors​

Constructor​

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: Field | undefined;

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

_innerProvable​

static _innerProvable: 
  | ProvableHashable<any>
  | undefined;

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

_nextHash​

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

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

_provable​

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

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()​
next(): {
  element: T;
  isDummy: Bool;
};

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()​
previous(): {
  element: T;
  isDummy: Bool;
};

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​

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>;
  _emptyHash: Field | undefined;
  _innerProvable:   | ProvableHashable<any>
     | undefined;
  _nextHash:   | ((hash: Field, value: any) => Field)
     | undefined;
  _provable:   | ProvableHashable<MerkleListIterator<any>>
     | undefined;
  prototype: MerkleListIterator<any>;
  get emptyHash(): Field;
  create: 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: { new (value: MerkleListIteratorBase<T>): MerkleListIterator<T>; prototype: MerkleListIterator<any>; ... 6 more ...; readonly emptyHash: Field; } & { ...; };
} & {
  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​

T

Parameters​

merkleList​

typeof MerkleList

Returns​