Skip to main content
Version: v1.3_alpha

AccQueue

This contract defines a Merkle tree where each leaf insertion only updates a subtree. To obtain the main tree root, the contract owner must merge the subtrees together. Merging subtrees requires at least 2 operations: mergeSubRoots(), and merge(). To get around the gas limit, the mergeSubRoots() can be performed in multiple transactions.

MAX_DEPTH

uint256 MAX_DEPTH

Queue

A Queue is a 2D array of Merkle roots and indices which represents nodes in a Merkle tree while it is progressively updated.

struct Queue {
uint256[4][33] levels;
uint256[33] indices;
}

subDepth

uint256 subDepth

hashLength

uint256 hashLength

subTreeCapacity

uint256 subTreeCapacity

isBinary

bool isBinary

currentSubtreeIndex

uint256 currentSubtreeIndex

leafQueue

struct AccQueue.Queue leafQueue

subRootQueue

struct AccQueue.Queue subRootQueue

subRoots

mapping(uint256 => uint256) subRoots

mainRoots

uint256[33] mainRoots

subTreesMerged

bool subTreesMerged

treeMerged

bool treeMerged

smallSRTroot

uint256 smallSRTroot

nextSubRootIndex

uint256 nextSubRootIndex

numLeaves

uint256 numLeaves

SubDepthCannotBeZero

error SubDepthCannotBeZero()

custom errors

SubdepthTooLarge

error SubdepthTooLarge(uint256 _subDepth, uint256 max)

InvalidHashLength

error InvalidHashLength()

DepthCannotBeZero

error DepthCannotBeZero()

SubTreesAlreadyMerged

error SubTreesAlreadyMerged()

NothingToMerge

error NothingToMerge()

SubTreesNotMerged

error SubTreesNotMerged()

DepthTooLarge

error DepthTooLarge(uint256 _depth, uint256 max)

DepthTooSmall

error DepthTooSmall(uint256 _depth, uint256 min)

InvalidIndex

error InvalidIndex(uint256 _index)

InvalidLevel

error InvalidLevel()

constructor

constructor(uint256 _subDepth, uint256 _hashLength) internal payable

Create a new AccQueue

Parameters

NameTypeDescription
_subDepthuint256The depth of each subtree.
_hashLengthuint256The number of leaves per node (2 or 5).

hashLevel

function hashLevel(uint256 _level, uint256 _leaf) internal virtual returns (uint256 _hash)

Hash the contents of the specified level and the specified leaf. This is a virtual function as the hash function which the overriding contract uses will be either hashLeftRight or hash5, which require different input array lengths.

Parameters

NameTypeDescription
_leveluint256The level to hash.
_leafuint256The leaf include with the level.

Return Values

NameTypeDescription
_hashuint256The hash of the level and leaf.

hashLevelLeaf

function hashLevelLeaf(uint256 _level, uint256 _leaf) public view virtual returns (uint256 _hash)

Hash the contents of the specified level and the specified leaf. This is a virtual function as the hash function which the overriding contract uses will be either hashLeftRight or hash5, which require different input array lengths.

Parameters

NameTypeDescription
_leveluint256The level to hash.
_leafuint256The leaf include with the level.

Return Values

NameTypeDescription
_hashuint256The hash of the level and leaf.

getZero

function getZero(uint256 _level) internal virtual returns (uint256 zero)

Returns the zero leaf at a specified level. This is a virtual function as the hash function which the overriding contract uses will be either hashLeftRight or hash5, which will produce different zero values (e.g. hashLeftRight(0, 0) vs hash5([0, 0, 0, 0, 0]). Moreover, the zero value may be a nothing-up-my-sleeve value.

Parameters

NameTypeDescription
_leveluint256The level at which to return the zero leaf.

Return Values

NameTypeDescription
zerouint256The zero leaf at the specified level.

enqueue

function enqueue(uint256 _leaf) public returns (uint256 leafIndex)

Add a leaf to the queue for the current subtree.

Parameters

NameTypeDescription
_leafuint256The leaf to add.

Return Values

NameTypeDescription
leafIndexuint256The index of the leaf in the queue.

_enqueue

function _enqueue(uint256 _leaf, uint256 _level) internal

Updates the queue at a given level and hashes any subroots that need to be hashed.

Parameters

NameTypeDescription
_leafuint256The leaf to add.
_leveluint256The level at which to queue the leaf.

fill

function fill() public

Fill any empty leaves of the current subtree with zeros and store the resulting subroot.

_fill

function _fill(uint256 _level) internal virtual

A function that queues zeros to the specified level, hashes, the level, and enqueues the hash to the next level.

Parameters

NameTypeDescription
_leveluint256The level at which to queue zeros.

insertSubTree

function insertSubTree(uint256 _subRoot) public

Insert a subtree. Used for batch enqueues.

calcMinHeight

function calcMinHeight() public view returns (uint256 depth)

Calculate the lowest possible height of a tree with all the subroots merged together.

Return Values

NameTypeDescription
depthuint256The lowest possible height of a tree with all the

mergeSubRoots

function mergeSubRoots(uint256 _numSrQueueOps) public

Merge all subtrees to form the shortest possible tree. This function can be called either once to merge all subtrees in a single transaction, or multiple times to do the same in multiple transactions.

Parameters

NameTypeDescription
_numSrQueueOpsuint256The number of times this function will call queueSubRoot(), up to the maximum number of times necessary. If it is set to 0, it will call queueSubRoot() as many times as is necessary. Set this to a low number and call this function multiple times if there are many subroots to merge, or a single transaction could run out of gas.

queueSubRoot

function queueSubRoot(uint256 _leaf, uint256 _level, uint256 _maxDepth) internal

Queues a subroot into the subroot tree.

Parameters

NameTypeDescription
_leafuint256The value to queue.
_leveluint256The level at which to queue _leaf.
_maxDepthuint256The depth of the tree.

merge

function merge(uint256 _depth) public returns (uint256 root)

Merge all subtrees to form a main tree with a desired depth.

Parameters

NameTypeDescription
_depthuint256The depth of the main tree. It must fit all the leaves or this function will revert.

Return Values

NameTypeDescription
rootuint256The root of the main tree.

getSubRoot

function getSubRoot(uint256 _index) public view returns (uint256 subRoot)

Returns the subroot at the specified index. Reverts if the index refers to a subtree which has not been filled yet.

Parameters

NameTypeDescription
_indexuint256The subroot index.

Return Values

NameTypeDescription
subRootuint256The subroot at the specified index.

getSmallSRTroot

function getSmallSRTroot() public view returns (uint256 smallSubTreeRoot)

Returns the subroot tree (SRT) root. Its value must first be computed using mergeSubRoots.

Return Values

NameTypeDescription
smallSubTreeRootuint256The SRT root.

getMainRoot

function getMainRoot(uint256 _depth) public view returns (uint256 mainRoot)

Return the merged Merkle root of all the leaves at a desired depth.

_merge() or merged(depth) must be called first.

Parameters

NameTypeDescription
_depthuint256The depth of the main tree. It must first be computed using mergeSubRoots() and merge().

Return Values

NameTypeDescription
mainRootuint256The root of the main tree.

getSrIndices

function getSrIndices() public view returns (uint256 next, uint256 current)

Get the next subroot index and the current subtree index.