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:83
Properties
data
data: Unconstrained<WithHash<T>[]>;
Implementation of
MerkleListBase.data
Source
lib/provable/merkle-list.ts:81
hash
hash: Field;
Implementation of
MerkleListBase.hash
Source
lib/provable/merkle-list.ts:80
_emptyHash
static _emptyHash: undefined | Field;
Source
lib/provable/merkle-list.ts:297
_innerProvable
static _innerProvable: undefined | ProvableHashable<any>;
Source
lib/provable/merkle-list.ts:300
_nextHash
static _nextHash: undefined | (hash: Field, t: any) => Field;
Source
lib/provable/merkle-list.ts:296
_provable
static _provable: undefined | ProvableHashable<MerkleList<any>>;
Source
lib/provable/merkle-list.ts:299
Accessors
Constructor
get Constructor(): typeof MerkleList
Returns
typeof MerkleList
Source
lib/provable/merkle-list.ts:302
innerProvable
get innerProvable(): ProvableHashable<T>
Returns
ProvableHashable\<T>
Source
lib/provable/merkle-list.ts:319
emptyHash
get static emptyHash(): Field
Returns
Source
lib/provable/merkle-list.ts:314
Methods
clone()
clone(): MerkleList<T>
Returns
MerkleList\<T>
Source
lib/provable/merkle-list.ts:189
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:203
isEmpty()
isEmpty(): Bool
Returns
Source
lib/provable/merkle-list.ts:88
nextHash()
nextHash(hash: Field, value: T): Field
Parameters
• hash: Field
• value: T
Returns
Source
lib/provable/merkle-list.ts:306
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:154
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:139
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:173
push()
push(element: T): void
Push a new element to the list.
Parameters
• element: T
Returns
void
Source
lib/provable/merkle-list.ts:95
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:107
startIterating()
startIterating(): MerkleListIterator<T>
Returns
Source
lib/provable/merkle-list.ts:217
startIteratingFromLast()
startIteratingFromLast(): MerkleListIterator<T>
Returns
Source
lib/provable/merkle-list.ts:222
create()
static create<T>(
type: 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: 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])
) {}