Interval Merkle Tree: A Circuit-friendly Universal (Vector) Accumulator.

This documents describes the APIs, inner working of Interval Merkle Tree (IMT), a cryptographic accumulator that we use to instantiate Nullifier Set which require efficient non-membership proof and member insertion in circuit.

Complexity

For an IMT of height

$h$ of size

$N=2^h$, batch insertion size

$K=2^k,h>k$:
Both Add and BatchAdd circuit checked non-membership before inserting.

	Add	BatchAdd
Native Execution	$O(\log N)$	$O(K\cdot \log N)$
Constraint Cost	$4h$ hash + $2$ range_check	$[2hK+2(h-k)+(K-1)]$ hash + $2K$ range_check

E.g.

$h=32,k=10$ for a Zcash sized Nullifier set and a ~1024 rollup capacity, BatchAdd requires 66,603 * Hash whereas naively Add one-by-one requires 131,072 Hash, and Sparse Merkle Tree would require 524,288 Hash! An almost 8x improvement in circuit size compared to SMT (which is what Circom and Aztec Connect use)

Challenges

Compared to various non-membership constructions in the literature, our primary goal is low circuit complexity, as opposed to time & space complexity for different operations. Designing circuit-friendly data structures and their algorithms need to pay special attention to the following:

• Input independence: circuit configuration is independent of any input values (namely (pub_input, secret_witness) assignments), specifically this implies:
  • worse case complexity for loops: constraining an algorithm that contains for (i=0; i<n; i++) loop with potential early return/termination requires always checking all n iterations in circuit.
  • combined branch complexity for conditions: constraining an algorithm that contains if (cond1) {do X} else if (cond2) {do Y} else {do Z} conditional execution requires always constraining all branches and chained together in a Disjunctive Normal Form: (cond1=T AND cond2=F AND X) OR (cond1=F AND cond2=T AND Y) OR (cond1=F AND cond2=F AND Z).
• Circuit-unfriendly Operations: algebraic circuits natively execute finite field arithmetics and many operations could be expensive when translating to field operations, such as pairing in bilinear map, bit-wise operation (AND, XOR, SHL etc.), non-algebraic hash, non-native modular arithmetics. Apparently we want to minimize these operations as much as possible.

Here are some concrete implications:

• Sparse Merkle Tree (SMT) is very deep thus involves many hash operations for each Merkle path (accumulating field elements of 256 bits would require a binary SMT of height 256). Potential optimization leveraging on the observation that: "expected length of Merkle proof with
  $N$ accumulated elements is only
  $\log (N)$" leads to a rather complicated circuit logic dealing with many edge cases and occational longer paths.
• RSA accumulator requires modular arithmetics over a usually much larger modulus (for security) than that of the native field, which leads to high circuit complexity.
• Bilinear-map based accumulator usually involves pairing, another expensive operations. Worse, the number of group points in the Structured Reference String (SRS) required for these accumulators (such as [DT08]) are linear with tree size. Currently, the largest trusted setup ceremony provides about
  $2^{28}$ such points, however, even for Zcash's Nullifier set is at least
  $2^{32}$ in capacity.

Overview

Core idea 1 (interval as leaf value): transforming non-membership proof in set

$X=\{x_1,x_2,\dots ,x_n\}$ to membership proof in set

$Y=\{(-\mathrm{\infty },x_1),(x_1,x_2),\dots ,(x_{n-1},x_n)\}$.
E.g. for set

$X=\{2,7\}$, we prove non-membership for

$5$ by providing Merkle proof for the interval

$(2,7)$ (in purple), and an interval check whether

$2<5<7$ (in yellow):

Core idea 2 (replace and append): During insertion of new member, split the containing interval into two smaller intervals. Replace the old interval, then append the other.
E.g. inserting

$5$ will split

$(2,7)$ into

$(2,5),(5,7)$.

Note that:

• The tree is of fixed height, not an incremental tree.
• Intervals are bounded exclusively below and above (namely
  $2,5\notin (2,5)$).
• Intervals are unsorted/non-consecutive.
• Our IMT is a universal accumulator with dyanmic addition and deletion of elements, and support both membership and non-membership proofs.
• This accumulator is order dependent: different order of insertion of the same set may result in different tree state and digest.^[1]
  • If were not constraining correct insertion in circuit, we can enforce consecutive intervals (namely shift
    $(7,\mathrm{\infty })$ right 1 slot to make room for
    $(5,7)$), which will give order independence.
  • Unfortunately, to keep the circuit input dependent, we need to ensure a fixed number of "steps" for each insertion regardless of the state of the Merkle tree.
  • The most efficient solution is leaving these intervals unordered during insertion^[2], which necessitates another "locator" to help remember the leaf indexes of inserted intervals for fast locating. We instantiate this "locator" with a B-Tree based Map in practice. (detailed description below)
  • due to order dependence, we should view IMT as a vector accumulator scheme (rather than a set accumulator) and the accumulator value as a vector commitment.
• This IMT was proposed way earlier by Philippe et al. in 2008, but there are two problems of this data structure that potentially hinders its wider adoption in practice:
  • requiring structural integrity check: TODO (add def)
  • order dependence (as mentioned above): this results in either additional locator to help quickly locate insertion position at the cost of extra storage; or require sorting upon insertion & deletion which increase the cost of both operation to
    $O(n)$.^[3]

Construction

We adapt from the definition, syntax and notation of a trapdoorless universal accumulator from [BBF18]:

For optimization, we extend the definition above with one more algorithm:

• $\mathbf{\text{BatchAdd}}(A_t,\{x_i\})\to \{A_{t+1},\mathbf{\text{upmsg}}\}\text{batch insert new members}$

There are auxiliary output for accumulator update algorithms (namely

$\mathbf{\text{Add, Del, BatchAdd}}$) to help provers generate proof of correct update, which we highlight with .

Note that due to impossibility of batch witness update by [CH09], witness update for each time counter

$t$ is enough, since info for batch update

$\mathsf{upmsg}$ independent of number of updates (namely

$|t_j-t_i|$) doesn't exist.

We further assume the existence of an algebraic hash function

$\mathcal{H}:{\mathbb{F}}^2\mapsto \mathbb{F},{\mathcal{H}}_{\ast }:{\mathbb{F}}^3\mapsto \mathbb{F}$, which we instantiate using Rescue or Poseidon, modelled as a random oracle.
We denote

$|\mathbb{F}|$ the bit-size of a prime field

$\mathbb{F}$ with modulus

$p$, any number represents a field element unless stated otherwise.
We denote merkle path as the nodes along the path from leaf to root; merkle proof as the slibing nodes along that path.

Our locator search trees should have the following APIs:

use std::collections::BTreeMap;
let mut locator = BTreeMap::new(); // init setup

locator.insert(Fr::from(0), 0); // L=-inf at leaf index 0
locator.insert(Fr::from(2), 1); // L=2 at index 1
locator.insert(Fr::from(7), 2); // L=7 at index 2
locator.insert(Fr::from(5), 3); // L=5 at index 3
// leaves are now: (0,2), (2,5), (7,p-1), (5,7)

// task 1: checking if certain field element is a member
assert!(!locator.contains_key(&Fr::from(6)));
assert!(locator.contains_key(&Fr::from(5)));

// task 2: find the leaf index of a member
let idx = locator.get(&Fr::from(7)).unwrap();
asset_eq!(idx, 2);

// task 3: find the index of the interval a new member should insert into.
let idx = locator.range(Fr::from(6)).next().unwrap();
asset_eq!(idx, 3); // index 3 or 4th leaf is (5, 7) where 6 should insert

Setup

• Inputs:
  • security param:
    $\lambda =(|\mathbb{F}|,N)$
  • initial set elements:
    $z=\{(0,p-1)\}$
• Outputs:
  • public param:
    $\mathsf{pp}=(\mathbb{F},N,\mathcal{H},{\mathcal{H}}_{\ast })$ include field
    $\mathbb{F}$, tree size
    $N$, hash function for internal nodes
    $\mathcal{H}$, for leaves
    ${\mathcal{H}}_{\ast }$,
  • initial accumulator value:
    $A_0=(\mathsf{rt}\mathsf{,}\mathsf{ctr})$ contains the root value plus a counter keeping track of number of non-empty leaves in the tree.
• Algorithms:
  • Initialize locator tree: let locator = BTreeMap::new();
  • Initialize IMT of size
    $N=2^h$ with the first leaf being
    $(0,p-1)$ to represent the ideal
    $(-\mathrm{\infty },+\mathrm{\infty })$ using field elements; and populate the rest with
    $(0,0)$ as EMPTY leaves.
  • Derive the merkle root rt, and assign the initial accumulator value
    $A_0=(rt,1)$ to signify currently only 1 non-empty leaves.
  • Update locator tree: locator.insert(F::from(0), 0);.

Add

• Inputs
  • current accumulator:
    $A_t$
  • a new element:
    $x$
• Outputs
  • updated accumlator:
    $A_{t+1}$
  • info used to update proof:
    $\mathsf{upmsg}$
  • prover witness:
    $w_{+x}$
• Algorithms
  • Query replacement index: idx = locator.range(x).next().unwrap() (idx=0, ELEMS[idx]=(0,p-1) in this example)
  • Prepare new leaf
    $(L,R)$ to be inserted:
    • $L=x$,
      $R=$ELEMS[idx].R
  • Prepare replaced leaf
    $(L^{\prime },R^{\prime })$:
    • $L^{\prime }=$ELEMS[idx].L,
      $R^{\prime }=x$
  • Insert new leaf
    $(L,R)$ at position
    $A_t.\mathsf{ctr}$:
    • add the Merkle proof of ELEMS[ctr] (exclude root) AND the new leaf to prover witenss:
      $w_{+x}||=(L,R)||{\pi }_{+}$ (purple nodes in diagram)
    • append new leaf
      $(L,R)$ at position
      $A_t.\mathsf{ctr}$, update internal nodes, and finally compute the new root value
      ${\mathsf{rt}}_{+}$
    • append to proof update info:
      $\mathsf{upmsg}||=(ctr,pat{h}_{ctr})$ where
      $path$ is the merkle path of ELEMS[ctr]
      • in our example, path consists of update values (w.r.t.
        ${\mathsf{rt}}_{\mathsf{+}}$)
    • update locator: locator.insert((L,ctr)).unwrap();
  • Replace LEAVES[idx] with
    $(L^{\prime },R^{\prime })$:
    • add the Merkle proof of LEAVES[idx] (exclude root which is
      ${\mathsf{rt}}_{\mathsf{+}}$) to prover witness:
      $w_{+x}||={\pi }_{\circlearrowleft }$ (dashed nodes in the diagram, note that purple-dashed nodes were updated in the last step during insertion)
      • note:
        ${\pi }_{\circlearrowleft }$ is basically the non-membership proof. It might be a little counterintuitive to see such a non-membership proof from an updated tree (with new leaf inserted) instead of the original tree. The main rationale is to unify circuit logic with
        $\mathbf{\text{BatchAdd}}$ procedure
    • replace LEAVES[idx] with
      $(L^{\prime },R^{\prime })$, update internal nodes, and compute the new root value
      ${\mathsf{rt}}^{\prime }$ (transition from
      ${\mathsf{rt}}_{\mathsf{+}}$)
    • append to proof update info:
      $\mathsf{upmsg}||=(idx,pat{h}_{idx})$
  • Output
    $A_{t+1}=({\mathsf{rt}}^{\prime }\mathsf{,}\mathsf{ctr}\mathtt{+}\mathtt{+}),\mathsf{upmsg},w_{+x}$

BatchAdd

• Inputs
  • current accumulator:
    $A_t$
  • a batch of new elements:
    $\{x_i\}$
    • we assume each batch has fixed size of
      $K=2^k$ for simpler circuit later, here we assume
      $K=4$
    • we further assume
      $A_t.\mathsf{ctr}=a\cdot K-1$ for some
      $a\in {\mathbb{N}}_{+}$, namely there are in total
      $a\cdot K$ intervals/leaves.
      (the problem with initial (0,p-1) leaf during setup can be dealt with using some "genesis block" mechanism to pad into multiple of
      $K$)
• Outputs
  • updated accumlator:
    $A_{t+1}$
  • info used to update proof:
    $\mathsf{upmsg}$
  • prover witness:
    $w_{+X}$
• Algorithm
  • Prepare new leaves
    $\{(L_i^{new},R_i^{new}){\}}_{i\in [K]}$ to be inserted:
    • $L_i^{new}=x_i,R_i^{new}=min\{L_j:j<i\wedge L_j>L_i^{new}\}$
    • update locator: locator.insert((L_i^new, ctr+i-1)).unwrap();
      • these intervals might be updated, but their L bound won't, thus it's safe to insert their positions to locator now
  • Prepare leaves
    $\{(id{x}_j^{rep},L_j^{rep},R_j^{rep}){\}}_{j\in [K]}$ to be replaced:
    • query idx_j = locator.range(x_j).next().unwrap();
    • $L_j^{rep}=$LEAVES[idx_j].L,
      $R_j^{rep}=x_j$
  • Batch insert all new leaves:
    • add merkle proof of the entire subtree to prover witness:
      $w_{+X}||={\pi }_{+}$ (red nodes in diagrams)
      • note the root of the empty subtree is a public parameter and can be pre-computed
    • insert
      $\{(L_i^{new},R_i^{new}){\}}_{i\in [K]}$, compute the new subtree root, then update the overall tree root
    • add all new leaves to prover witness:
      $w_{+X}||=\{(L_i^{new},R_i^{new}){\}}_{i\in [K]}$
  • Replace leaves: for each
    $j\in [K]$, and its respective idx_j (searched during step 2):
    • add merkle proof of LEAVES[idx_j] (against updated roots) to prover witness:
      $w_{+X}||={\pi }_{\circlearrowleft }^j$ (green nodes)
    • replace leaf with
      $(L_j^{rep},R_j^{rep})$, update roots
    • add all replaced leaves to prover witness:
      $w_{+X}||=\{(id{x}_j^{rep},L_j^{rep},R_j^{rep}){\}}_{j\in [K]}$
  • TODO: upmsg
  • Output
    $A_{t+1}=({\mathsf{rt}}^{\prime }\mathsf{,}\mathsf{ctr}\mathtt{+}\mathtt{=}K),\mathsf{upmsg},w_{+X}$

Del

• Inputs
  • current accumulator:
    $A_t$
  • element to be removed:
    $x$
• Outputs
  • updated accumlator:
    $A_{t+1}$
  • info used to update proof:
    $\mathsf{upmsg}$
  • prover witness:
    $w_{-x}$ (TODO: will specify this later)
• Algorithm
  • Query replacement positions: idx_0 = locator.range(&9-1).next().unwrap(); idx_1 = locator.get(&9).unwrap(); (in our example, idx_0=1, idx_1=3)
  • Replace LEAVES[idx_0] withx(LEAVES[idx_0].L, LEAVES[idx_1].R)`, updax Merkle root
    • append updated nodes:
      $\mathsf{upmsg}||=(id{x}_0,pat{h}_{id{x}_0})$
  • Replace LEAVES[idx_1] with LEAVES[ctr-1], update Merkle root
    • append updated nodes:
      $\mathsf{upmsg}||=(id{x}_1,pat{h}_{id{x}_1})$
    • update locator: locator.insert((LEAVES[ctr-1].L, idx_1)).unwrap(); and locator.remove(x).unwrap();
  • Replace LEAVES[ctr-1] with (0,0), update Merkle root
    • append updated nodes:
      $\mathsf{upmsg}||=(ctr-1,pat{h}_{ctr-1})$
  • Decrement total non-empty leaves count: ctr--
  • Output
    $A_{t+1}=({\mathsf{rt}}^{\prime }\mathsf{,}\mathsf{ctr}\mathtt{-}\mathtt{-}),\mathsf{upmsg},w_x$

MemWitCreate

• Inputs
  • accumulator at time
    $t$:
    $A_t$
  • claimed member:
    $x$
  • vector of elements inserted:
    $S=\mathrm{\varnothing }$ (unnecessary for us)
• Outputs
  • membership witness:
    $w_x^t$
• Algorithm
  • Query position: idx = locator.get(9).unwrap(); (idx=3 in our example)
  • Return the merkle proof of LEAVES[idx] (marked in purple) as
    $w_x^t$

NonMemWitCreate

• Inputs
  • accumulator at time
    $t$:
    $A_t$
  • claimed non-member:
    $x$
  • vector of elements inserted:
    $S=\mathrm{\varnothing }$ (unnecessary for us)
• Outputs
  • non-membership witness:
    $u_x^t$
• Algorithm
  • Query containing interval position: idx = locator.get(12).unwrap(); (idx=3 in our example, checking
    $12\notin S$ in the same diagram above)
  • Return the merkle proof of LEAVES[idx] (marked in purple) as
    $u_x^t$

MemWitUp & NonMemWitUp (same algorithm)

• Inputs
  • old accumulator:
    $A_t$
  • old (non)-membership proof:
    $w_x^t$ or
    $u_x^t$
  • claimed (non)-member:
    $x$
  • update info:
    ${\mathsf{upmsg}}_{t\to t+1}$
• Outputs
  • new (non)-membership proof:
    $w_x^{t+1}$ or
    $u_x^t$
• Algorithm
  • Query index of (non)-member: let idx = locator.get(x).unwrap();
  • ​​​​​​ // note: merkle_path is NOT merkle_proof, 
    ​​​​​​ // path: from leaf to root; proof: silbings of nodes along the path.
    ​​​​​​ for (pos, merkle_path) in upmsg {
    ​​​​​​     // e.g. the updated leaf `pos` is 010, `idx` of member is 000
    ​​​​​​     // then the 0-prefix of `pos XOR idx` (which is first 0 in 010)
    ​​​​​​     // indicates which node in `merkle_proof` should be updated.
    ​​​​​​     // in this case: `merkle_proof[depth=1] = merkle_path[depth=1]`.
    ​​​​​​     // 
    ​​​​​​     // Also always update the root: `merkle_proof[rt] = merkle_path[rt]`
    ​​​​​​     update_merkle_proof(idx, &mut merkle_proof, pos, &merkle_path);
    ​​​​​​     
    ​​​​​​     // another e.g.
    ​​​​​​     // updated leaf `pos` is 010, `idx` of member is 011
    ​​​​​​     // then `010 ^ 011 = 001`, thus `merkle_proof[depth=1,2]` would be
    ​​​​​​     // updated with values `merkle_path[depth=1,2]`.
    ​​​​​​     // finally, `merkle_proof[rt] = merkle_path[rt]`
    ​​​​​​ }     
    

  • TODO: this algorithm is not complete, it's possible your non-membership leaf position gets updated. the above two steps only deal with situation where leaf position wasn't changed (such as all membership proof)

VerMem

• Inputs
  • accumulator at time
    $t$:
    $A_t$
  • claimed member:
    $x$
  • membership witness:
    $w_x^t$
• Outputs
  • success:
    $b\in \{0,1\}$
• Algorithm
  • Verify Merkle proof
    $w_x^t$ of leaf
    $(L,R)$
  • Check
    $x\stackrel{?}{=}L\wedge L\ne 0$

VerNonMem

• Inputs
  • accumulator at time
    $t$:
    $A_t$
  • claimed member:
    $x$
  • non-membership witness:
    $u_x^t$
• Outputs
  • success:
    $b\in \{0,1\}$
• Algorithm
  • Verify Merkle proof
    $u_x^t$ of leaf
    $(L,R)$
  • Check
    $L<x<R$

Constraints

Building blocks

• recompute_root(pos, leaf, proof) -> root: given the leaf position pos, leaf value leaf and siblings of its path proof, recompute the root of this subtree
  • cost: len(proof) * Hash
• compute_root(leaves) -> root: given
  $K=2^k$ leaves, compute the tree root.
  • cost:
    $\sum _{i=1}^{k-1}{2}^i=2^k-1=K-1$ * Hash

Batch Check & Insert Gadget

• Statement: Given a correctly computed old accumulator
  $A_t$ of the IMT, there exists a vector of
  $K=2^k$ new non-members such that applying
  $\mathbf{\text{BatchAdd}}(A_t,\{x_i{\}}_{i\in [K]})$ will result in new accumulator value
  $A_{t+1}$.
• Public Input:
  • Old accumulator:
    $A_t$
  • New accumulator:
    $A_{t+1}$
  • Root of empty subtree of size
    $K$:
    $h_{\mathrm{\varnothing }}^K$
• Secret Witness:
  • New vector of non-members:
    $\{x_i{\}}_{i\in [K]}$
  • Prover witness from BatchAdd:
    $w_{+X}$
• Circuit Logic:
  • Verify correct
    $K$-subtree to insert:
    • parse
      ${\pi }_{+}$ from
      $w_{+X}$ (red nodes)
    • enforce:
      $A_t.\mathsf{rt}==\mathtt{recompute}\mathtt{\_}\mathtt{root}(A_t.\mathsf{ctr}\gg k,h_{\mathrm{\varnothing }}^K,{\pi }_{+})$
  • Batch insert and update merkle root:
    • parse
      $\{(L_i^{new},R_i^{new}){\}}_{i\in [K]}$ from
      $w_{+X}$ (red dashed nodes)
    • check
      $L_i^{new}<R_i^{new}\wedge L_i^{new}=x_i$ for
      $\mathrm{\forall }i\in [K]$
    • compute new
      $K$-subtree root:
      $h^K=\mathtt{compute}\mathtt{\_}\mathtt{root}(\{(L_i^{new},R_i^{new}){\}}_{i\in [K]})$
    • compute new root upon insertion:
      ${\mathsf{rt}}_{+}=\mathtt{recompute}\mathtt{\_}\mathtt{root}(A_t.\mathsf{ctr}\gg k,h^K,{\pi }_{+})$
  • Check and replace, parse
    $\{(id{x}_j^{rep},L_j^{rep},R_j^{rep}){\}}_{j\in [K]}$ (blue dashed nodes) and LEAVES[idx_j] (parent of blue dashed nodes) from
    $w_{+X}$ , let
    ${\mathsf{rt}}^{\prime }={\mathsf{rt}}_{+}$,
    for each
    $j\in [K]$, do:
    • Verify non-membership:
      • enforce
        ${\mathsf{rt}}^{\prime }==\mathtt{recompute}\mathtt{\_}\mathtt{root}(id{x}_j^{rep},(L_j^{rep},R_j^{rep}),{\pi }_{\circlearrowleft }^j)$
      • enforce (LEAVES[idx_j].L
        $<x_j$) AND (LEAVES[idx_j].R
        $=R_j^{new}$)
        • note: we don't need to check
          $x_j<R_j$ because we effectively cover that during insertion
    • Check correct replacement: LEAVES[idx_j].L
      $=L_j^{rep}\wedge R_j^{rep}=x_j$
    • compute updated root after replacement:
      ${\mathsf{rt}}^{\prime }=\mathtt{recompute}\mathtt{\_}\mathtt{root}(id{x}_j^{rep},(L_j^{rep},R_j^{rep}),{\pi }_{\circlearrowleft }^j)$
  • Finally, check new accumulator:
    • check
      $({\mathsf{rt}}^{\prime }==A_{t+1}.\mathsf{rt})\wedge (A_t.\mathsf{ctr}+K=A_{t+1}.\mathsf{ctr})$

Security Proofs

We show that the structure integrity of our IMT can be captured by the following 3 invariants:

1. All left range include all member exactly once plus a negative infinity represented by 0:
   $\{L_i\}=\{x_i\}\cup \{0\}$
2. All right range include all member exactly once plus a positive infinity represented by p-1:
   $\{R_i\}=\{x_i\}\cup \{0\}$
3. $L_i<R_i$ for
   $\mathrm{\forall }i<A_t.\mathsf{ctr}$

Then we proceed to prove that our Add, BatchAdd, Del preserves all 3 invariants.

TBD

Finally, we argue that our constraints sufficiently enforce the BatchAdd algorithm.

TBD

TODO: losing adaptive security (but still sufficient for our use cases) where adv hands you the accumulator and provide valid proof of membership AND non-membership.

Caching Strategies

Given the locator B-Tree, we are able to deterministically reconstruct the IMT.
By caching some Merkle path in the IMT, we can achieve space-time efficiency tradeoff during tree update.

When using IMT in a non-universal setting (specifically insertion only, no deletion, such as our Nullifier set), we could enjoy the following pruning:

The main observation is that

• "smaller the interval, less likely the leaf will be updated, so are the nodes on its Merkle path to the root".
  • On one extreme, leaves with interval value such as
    $(23,24)$ won't be updated.
• Merkle frontier will always gets updated during insertion, thus should be kept in cache.

Adapting to Different Arity

Given different arity (i.e. number of children per internal node) of the Merkle Tree, we need to adapt all algorithms and constraints above.
We first demonstrate 3-ary tree:

Related Work

TBD: simply literature review/related work, plus some comparison to justify our design and advantanges.
SMT, Balaced Tree, RSA accumulators, Bilinear-map accumulators.

---

1. If deterministic reproducing of the accumulator state is required, then order dependent accumulator would be problematic without total ordering of historical insertion instructions. In our intended use case of Nullifier set in Blockchain, the total ordering is established externally since every transaction binds the order of nullifiers inside, and all transactions are further ordered using distributed consensus. Therefore all nullifiers to be inserted are ordered and every honest node can deterministically replay and get the same accumulator state.
   Order independence is more formally referred to as quasi ↩︎

2. Otherwise we need to accommodate for the worst-case shift for every insertion since we can't have a variable number of shift per insertion. This solution is horrendously expensive. ↩︎

3. In [CHKO08], the IMT is an incremental, balanced but NOT sorted tree, therefore, the insertion cost is already

   $O(n)$. ↩︎