AccQueue
An Accumulator Queue which conforms to the implementation in AccQueue.sol. Each enqueue() operation updates a subtree, and a merge() operation combines all subtrees into a main tree.
Notice
It supports 2 or 5 elements per leaf.
Table of contents
Constructors
Properties
- MAX_DEPTH
- currentSubtreeIndex
- hashFunc
- hashLength
- leafQueue
- mainRoots
- nextSRindexToQueue
- numLeaves
- smallSRTroot
- subDepth
- subHashFunc
- subRootQueue
- subRoots
- subTreesMerged
- zeroValue
- zeros
Methods
- arrayToMap
- calcSRTdepth
- copy
- enqueue
- enqueueOp
- fill
- fillOp
- getHashLength
- getMainRoots
- getRoot
- getSmallSRTroot
- getSubDepth
- getSubRoot
- getSubRoots
- getZeros
- hasRoot
- hash
- insertSubTree
- mapToArray
- merge
- mergeDirect
- mergeSubRoots
- queueSubRoot
Constructors
constructor
• new AccQueue(subDepth
, hashLength
, zeroValue
): AccQueue
Create a new instance of AccQueue
Parameters
Name | Type | Description |
---|---|---|
subDepth | number | the depth of the subtrees |
hashLength | number | the number of leaves per node |
zeroValue | bigint | the default value for empty leaves |
Returns
Defined in
crypto/ts/AccQueue.ts:76
Properties
MAX_DEPTH
• Private
MAX_DEPTH: number
= 32
Defined in
crypto/ts/AccQueue.ts:17
currentSubtreeIndex
• Private
currentSubtreeIndex: number
= 0
Defined in
crypto/ts/AccQueue.ts:30
hashFunc
• Readonly
hashFunc: (leaves
: bigint
[]) => bigint
Type declaration
▸ (leaves
): bigint
Parameters
Name | Type |
---|---|
leaves | bigint [] |
Returns
bigint
Defined in
crypto/ts/AccQueue.ts:68
hashLength
• Private
hashLength: number
Defined in
crypto/ts/AccQueue.ts:23
leafQueue
• Private
leafQueue: Queue
Defined in
crypto/ts/AccQueue.ts:36
mainRoots
• Private
mainRoots: bigint
[] = []
Defined in
crypto/ts/AccQueue.ts:55
nextSRindexToQueue
• Private
nextSRindexToQueue: number
= 0
Defined in
crypto/ts/AccQueue.ts:42
numLeaves
• Private
numLeaves: number
= 0
Defined in
crypto/ts/AccQueue.ts:33
smallSRTroot
• Private
smallSRTroot: bigint
Defined in
crypto/ts/AccQueue.ts:44
subDepth
• Private
subDepth: number
Defined in
crypto/ts/AccQueue.ts:20
subHashFunc
• Readonly
subHashFunc: (leaves
: bigint
[]) => bigint
Type declaration
▸ (leaves
): bigint
Parameters
Name | Type |
---|---|
leaves | bigint [] |
Returns
bigint
Defined in
crypto/ts/AccQueue.ts:65
subRootQueue
• Private
subRootQueue: Queue
Defined in
crypto/ts/AccQueue.ts:46
subRoots
• Private
subRoots: bigint
[] = []
Defined in
crypto/ts/AccQueue.ts:52
subTreesMerged
• Private
subTreesMerged: boolean
= false
Defined in
crypto/ts/AccQueue.ts:62
zeroValue
• Private
zeroValue: bigint
Defined in
crypto/ts/AccQueue.ts:26
zeros
• Private
zeros: bigint
[] = []
Defined in
crypto/ts/AccQueue.ts:59
Methods
arrayToMap
▸ arrayToMap(array
): Map
<number
, Map
<number
, bigint
>>
Convert 2D array to its map representation
Parameters
Name | Type | Description |
---|---|---|
array | bigint [][] | 2D array |
Returns
Map
<number
, Map
<number
, bigint
>>
map representation of 2D array
Defined in
crypto/ts/AccQueue.ts:614
calcSRTdepth
▸ calcSRTdepth(): number
Calculate the depth of the smallest possible Merkle tree which fits all
Returns
number
the depth of the smallest possible Merkle tree which fits all
Defined in
crypto/ts/AccQueue.ts:343
copy
▸ copy(): AccQueue
Returns
a deep copy of this object
Notice
Deep-copies this object
Defined in
crypto/ts/AccQueue.ts:572
enqueue
▸ enqueue(leaf
): number
Enqueue a leaf into the current subtree
Parameters
Name | Type | Description |
---|---|---|
leaf | bigint | The leaf to insert. |
Returns
number
The index of the leaf
Defined in
crypto/ts/AccQueue.ts:185
enqueueOp
▸ enqueueOp(leaf
, level
): void
Private function that performs the actual enqueue operation
Parameters
Name | Type | Description |
---|---|---|
leaf | bigint | The leaf to insert |
level | number | The level of the subtree |
Returns
void
Defined in
crypto/ts/AccQueue.ts:226
fill
▸ fill(): void
Fill any empty leaves of the last subtree with zeros and store the resulting subroot.
Returns
void
Defined in
crypto/ts/AccQueue.ts:267
fillOp
▸ fillOp(level
): void
Private function that performs the actual fill operation
Parameters
Name | Type | Description |
---|---|---|
level | number | The level of the subtree |
Returns
void
Defined in
crypto/ts/AccQueue.ts:307
getHashLength
▸ getHashLength(): number
Get the number of inputs per hash function
Returns
number
the number of inputs
Defined in
crypto/ts/AccQueue.ts:176
getMainRoots
▸ getMainRoots(): bigint
[]
Get the root of merged subtrees
Returns
bigint
[]
the root of merged subtrees
Defined in
crypto/ts/AccQueue.ts:149
getRoot
▸ getRoot(depth
): undefined
| null
| bigint
Get the root at a certain depth
Parameters
Name | Type | Description |
---|---|---|
depth | number | The depth of the tree |
Returns
undefined
| null
| bigint
the root
Defined in
crypto/ts/AccQueue.ts:554
getSmallSRTroot
▸ getSmallSRTroot(): bigint
Get the small SRT root
Returns
bigint
small SRT root
Defined in
crypto/ts/AccQueue.ts:125
getSubDepth
▸ getSubDepth(): number
Get the subdepth
Returns
number
subdepth
Defined in
crypto/ts/AccQueue.ts:141
getSubRoot
▸ getSubRoot(index
): bigint
Get the subroot at a given index
Parameters
Name | Type | Description |
---|---|---|
index | number | The index of the subroot |
Returns
bigint
the subroot
Defined in
crypto/ts/AccQueue.ts:167
getSubRoots
▸ getSubRoots(): bigint
[]
Get the subroots
Returns
bigint
[]
subroots
Defined in
crypto/ts/AccQueue.ts:133
getZeros
▸ getZeros(): bigint
[]
Get the zero values per level. i.e. zeros[0] is zeroValue, zeros[1] is the hash of leavesPerNode zeros, and so on.
Returns
bigint
[]
zeros
Defined in
crypto/ts/AccQueue.ts:158
hasRoot
▸ hasRoot(depth
): boolean
Check if the root at a certain depth exists (subtree root)
Parameters
Name | Type | Description |
---|---|---|
depth | number | the depth of the tree |
Returns
boolean
whether the root exists
Defined in
crypto/ts/AccQueue.ts:563
hash
▸ hash(leaves
): bigint
Hash an array of leaves
Parameters
Name | Type | Description |
---|---|---|
leaves | bigint [] | The leaves to hash |
Returns
bigint
the hash value of the leaves
Defined in
crypto/ts/AccQueue.ts:623
insertSubTree
▸ insertSubTree(subRoot
): void
Insert a subtree into the queue. This is used when the subtree is already computed.
Parameters
Name | Type | Description |
---|---|---|
subRoot | bigint | The root of the subtree |
Returns
void
Defined in
crypto/ts/AccQueue.ts:359
mapToArray
▸ mapToArray(map
): bigint
[][]
Convert map to 2D array
Parameters
Name | Type | Description |
---|---|---|
map | Map <number , Map <number , bigint >> | map representation of 2D array |
Returns
bigint
[][]
2D array
Defined in
crypto/ts/AccQueue.ts:604
merge
▸ merge(depth
): void
Merge all the subroots into a tree of a specified depth. It requires this.mergeSubRoots() to be run first.
Parameters
Name | Type |
---|---|
depth | number |
Returns
void
Defined in
crypto/ts/AccQueue.ts:381
mergeDirect
▸ mergeDirect(depth
): void
Merge all the subroots into a tree of a specified depth. Uses an IncrementalQuinTree instead of the two-step method that AccQueue.sol uses.
Parameters
Name | Type |
---|---|
depth | number |
Returns
void
Defined in
crypto/ts/AccQueue.ts:415
mergeSubRoots
▸ mergeSubRoots(numSrQueueOps?
): void
Merge all subroots into the smallest possible Merkle tree which fits them. e.g. if there are 5 subroots and hashLength == 2, the tree depth is 3 since 2 ** 3 = 8 which is the next power of 2.
Parameters
Name | Type | Default value | Description |
---|---|---|---|
numSrQueueOps | number | 0 | The number of subroots to queue into the SRT |
Returns
void
Defined in
crypto/ts/AccQueue.ts:462
queueSubRoot
▸ queueSubRoot(leaf
, level
, maxDepth
): void
Queues the leaf (a subroot) into queuedSRTlevels
Parameters
Name | Type | Description |
---|---|---|
leaf | bigint | The leaf to insert |
level | number | The level of the subtree |
maxDepth | number | The maximum depth of the tree |
Returns
void
Defined in
crypto/ts/AccQueue.ts:523