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
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
emptyHash
Get Signature
get static emptyHash(): Field
Defined in: lib/provable/merkle-list.ts:362
Returns
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
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
value
T
Returns
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
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
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
element
T
Returns
void
startIterating()
startIterating(): MerkleListIterator<T>
Defined in: lib/provable/merkle-list.ts:259
Returns
startIteratingFromLast()
startIteratingFromLast(): MerkleListIterator<T>
Defined in: lib/provable/merkle-list.ts:264
Returns
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])
) {}