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
Properties
MAX_DEPTH
• Private MAX_DEPTH: number = 32
Defined in
currentSubtreeIndex
• Private currentSubtreeIndex: number = 0
Defined in
hashFunc
• Readonly hashFunc: (leaves: bigint[]) => bigint
Type declaration
▸ (leaves): bigint
Parameters
| Name | Type |
|---|---|
leaves | bigint[] |
Returns
bigint
Defined in
hashLength
• Private hashLength: number
Defined in
leafQueue
• Private leafQueue: Queue
Defined in
mainRoots
• Private mainRoots: bigint[] = []
Defined in
nextSRindexToQueue
• Private nextSRindexToQueue: number = 0
Defined in
numLeaves
• Private numLeaves: number = 0
Defined in
smallSRTroot
• Private smallSRTroot: bigint
Defined in
subDepth
• Private subDepth: number
Defined in
subHashFunc
• Readonly subHashFunc: (leaves: bigint[]) => bigint
Type declaration
▸ (leaves): bigint
Parameters
| Name | Type |
|---|---|
leaves | bigint[] |
Returns
bigint
Defined in
subRootQueue
• Private subRootQueue: Queue
Defined in
subRoots
• Private subRoots: bigint[] = []
Defined in
subTreesMerged
• Private subTreesMerged: boolean = false
Defined in
zeroValue
• Private zeroValue: bigint
Defined in
zeros
• Private zeros: bigint[] = []
Defined in
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
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
copy
▸ copy(): AccQueue
Returns
a deep copy of this object
Notice
Deep-copies this object
Defined in
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
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
fill
▸ fill(): void
Fill any empty leaves of the last subtree with zeros and store the resulting subroot.
Returns
void
Defined in
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
getHashLength
▸ getHashLength(): number
Get the number of inputs per hash function
Returns
number
the number of inputs
Defined in
getMainRoots
▸ getMainRoots(): bigint[]
Get the root of merged subtrees
Returns
bigint[]
the root of merged subtrees
Defined in
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
getSmallSRTroot
▸ getSmallSRTroot(): bigint
Get the small SRT root
Returns
bigint
small SRT root
Defined in
getSubDepth
▸ getSubDepth(): number
Get the subdepth
Returns
number
subdepth
Defined in
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
getSubRoots
▸ getSubRoots(): bigint[]
Get the subroots
Returns
bigint[]
subroots
Defined in
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
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
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
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
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
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
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
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
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