Paper: https://eprint.iacr.org/2024/1259.pdf

The paper presents a key observation: as the arity (the number of branches per node) increases, the probability of collisions drops significantly. This leads to a proposed sketch of a tree construction based on multicollision hardness, which results in a near 2-fold reduction in the depth of the tree compared to traditional constructions. The depth of the tree, in this case, is approximately equal to the security parameter $\lambda$, offering a substantial improvement.

To improve both (non-)membership proof complexity and insertion complexity, the authors propose a construction for storing nullifiers that relies on the random oracle model. The random oracle model introduces post-factum randomness and rate-limiting to prevent malicious actors from querying the oracle before inserting keys. This randomness, combined with rate-limiting, improves security by making it difficult for an adversary to precompute key collisions.

Efficiency Gains (Section 4.2)

• Depth reduction: By constraining the sample space of each epoch, the authors achieve a 4-fold reduction in tree depth for specific parameters, which is particularly useful in enterprise blockchains with relatively few users.
• Rate-limiting with post-factum randomization: This method reduces the number of samples to match the system's throughput, leading to a 5-fold depth reduction for practical instantiations with 245 transactions.

The authors also explore more general-purpose constructions, such as:

• Authority accumulator: Useful in non-adversarial cases, this construction leverages hash functions that adversaries cannot learn (e.g., universal or keyed hash functions).
• VRF-based key index derivation: Suitable for malicious key choices, ensuring efficient and secure key derivation.
• VDF-based construction: Another alternative for adversarial settings, using verifiable delay functions (VDFs) to derive the key index.

Components

1. Addressable Binary Hash Tree (Depth $d_a$): This tree stores the top-level structure, directing key-value pairs to a particular bucket. The depth $d_a$ represents how far into the tree we travel before hitting a bucket.
2. Buckets: Each bucket can hold up to $s-1$ elements, where $s$ represents the threshold for collision. A collision here means two or more elements hashing to the same bucket. By increasing the number of elements a bucket can hold, the likelihood of collision is reduced. The bucket itself serves as a smaller container to hold elements after the top-level tree path has directed the input there.

Insertion Process

To insert a key-value pair $(k, v)$:

1. The system hashes the key $k$ into an index $h=H(k)$.
2. The first $d_a$ bits of this index dictate the path to the correct bucket.