MerkleList
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
MerkleListBase\<T>
Constructors
new MerkleList()
new MerkleList<T>(__namedParameters: MerkleListBase<T>): MerkleList<T>
Parameters
• __namedParameters: MerkleListBase\<T>
Returns
MerkleList\<T>
Source
lib/provable/merkle-list.ts:84
Properties
data
data: Unconstrained<WithHash<T>[]>;
Implementation of
MerkleListBase.data
Source
lib/provable/merkle-list.ts:82
hash
hash: Field;
Implementation of
MerkleListBase.hash
Source
lib/provable/merkle-list.ts:81
_emptyHash
static _emptyHash: undefined | Field;
Source
lib/provable/merkle-list.ts:350
_innerProvable
static _innerProvable: undefined | ProvableHashable<any>;
Source
lib/provable/merkle-list.ts:353
_nextHash
static _nextHash: undefined | (hash: Field, t: any) => Field;
Source
lib/provable/merkle-list.ts:349
_provable
static _provable: undefined | ProvableHashable<MerkleList<any>>;
Source
lib/provable/merkle-list.ts:352
Accessors
Constructor
get Constructor(): typeof MerkleList
Returns
typeof MerkleList
Source
lib/provable/merkle-list.ts:355
innerProvable
get innerProvable(): ProvableHashable<T>
Returns
ProvableHashable\<T>
Source
lib/provable/merkle-list.ts:372
emptyHash
get static emptyHash(): Field
Returns
Source
lib/provable/merkle-list.ts:367
Methods
clone()
clone(): MerkleList<T>
Returns
MerkleList\<T>
Source
lib/provable/merkle-list.ts:223
forEach()
forEach(length: number, callback: (element: T, isDummy: Bool, i: number) => void): void
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
Returns
void
Source
lib/provable/merkle-list.ts:237
isEmpty()
isEmpty(): Bool
Returns
Source
lib/provable/merkle-list.ts:89
lengthUnconstrained()
lengthUnconstrained(): Unconstrained<number>
Returns
Unconstrained\<number>
Source
lib/provable/merkle-list.ts:267
nextHash()
nextHash(hash: Field, value: T): Field
Parameters
• hash: Field
• value: T
Returns
Source
lib/provable/merkle-list.ts:359
pop()
pop(): T
Remove the last element from the list and return it.
If the list is empty, returns a dummy element.
Returns
T
Source
lib/provable/merkle-list.ts:155
popExn()
popExn(): T
Remove the last element from the list and return it.
This proves that the list is non-empty, and fails otherwise.
Returns
T
Source
lib/provable/merkle-list.ts:140
popIf()
popIf(condition: Bool): T
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
Source
lib/provable/merkle-list.ts:174
popIfUnsafe()
popIfUnsafe(shouldPop: Bool): T
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
Source
lib/provable/merkle-list.ts:200
push()
push(element: T): void
Push a new element to the list.
Parameters
• element: T
Returns
void
Source
lib/provable/merkle-list.ts:96
pushIf()
pushIf(condition: Bool, element: T): void
Push a new element to the list, if the condition is true.
Parameters
• condition: Bool
• element: T
Returns
void
Source
lib/provable/merkle-list.ts:108
startIterating()
startIterating(): MerkleListIterator<T>
Returns
Source
lib/provable/merkle-list.ts:251
startIteratingFromLast()
startIteratingFromLast(): MerkleListIterator<T>
Returns
Source
lib/provable/merkle-list.ts:256
toArrayUnconstrained()
toArrayUnconstrained(): Unconstrained<T[]>
Returns
Unconstrained\<T[]>
Source
lib/provable/merkle-list.ts:261
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>>;
}
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= undefined
• 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])
) {}