Skip to main content
Version: v1.3_alpha

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

Methods

Constructors

constructor

new AccQueue(subDepth, hashLength, zeroValue): AccQueue

Create a new instance of AccQueue

Parameters

NameTypeDescription
subDepthnumberthe depth of the subtrees
hashLengthnumberthe number of leaves per node
zeroValuebigintthe default value for empty leaves

Returns

AccQueue

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
NameType
leavesbigint[]
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
NameType
leavesbigint[]
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

NameTypeDescription
arraybigint[][]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

AccQueue

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

NameTypeDescription
leafbigintThe 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

NameTypeDescription
leafbigintThe leaf to insert
levelnumberThe 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

NameTypeDescription
levelnumberThe 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

NameTypeDescription
depthnumberThe 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

NameTypeDescription
indexnumberThe 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

NameTypeDescription
depthnumberthe 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

NameTypeDescription
leavesbigint[]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

NameTypeDescription
subRootbigintThe root of the subtree

Returns

void

Defined in

crypto/ts/AccQueue.ts:359


mapToArray

mapToArray(map): bigint[][]

Convert map to 2D array

Parameters

NameTypeDescription
mapMap<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

NameType
depthnumber

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

NameType
depthnumber

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

NameTypeDefault valueDescription
numSrQueueOpsnumber0The 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

NameTypeDescription
leafbigintThe leaf to insert
levelnumberThe level of the subtree
maxDepthnumberThe maximum depth of the tree

Returns

void

Defined in

crypto/ts/AccQueue.ts:523