Skip to main content
Version: v1.x

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​

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.