Score:0

Crypto

Non-pruned accumulators with asymptotic worst space $O(\log_2 n)$, or cheaper?

caveman

6/16/23, 9:15 AM

The only accumulator that I know is the Merkle tree, which has these asymptotic worst:

Space non-pruned: $O(n)$.
Time insertion/removal: $O(\log_2 n)$.
Time verification: $O(\log_2 n)$.

My question is: is there any accumulator that its non-pruned version has an asymptotic worst-space that is cheaper than $O(n)$? E.g. perhaps $O(\log_2 n)$?

0 + 0

accumulators

Alin Tomescu

1/23/23, 6:11 AM

Define "non-pruned." Also, when you say "accumulator", do you mean a commitment to an unordered set of elements? Or do you mean something else?

caveman

1/30/23, 12:51 AM

@AlinTomescu updated.

István András Seres

1/30/23, 7:21 AM

Constant-sized accumulators (e.g, based on RSA groups or bilinear groups) would satisfy your requirement?

Alin Tomescu

2/5/23, 1:10 AM

Thank you @caveman. I am still confused by your terminology to answer your question. When you say "checkpoint" or "reference", you are referring to the digest, correct? e.g., if this were a Merkle tree, you would mean the Merkle root hash, correct?

caveman

2/10/23, 5:38 PM

@AlinTomescu - Yes, the root hash would be an option, or whatever common node hash two parties agree with. E.g. if person A and person B agree on some common node's hash, which is not the root, person A can prove to him that his item is in the set by offering a sub-tree of hashes from that links to that node's hash which they commonly agree (even if they don't necessarily agree all the way to the up-to-date root). I think this can be the basis of some pruning method (deleting nodes that are relate to too-old entries which are no longer getting updated since, say, years).

caveman

2/10/23, 5:41 PM

@IstvánAndrásSeres - I have to read about it first. I'd appreciate references/links if you enjoy giving people links :). Otherwise I'm Duckduckgo-ing it anyway.

Alin Tomescu

2/11/23, 6:52 PM

@caveman, for sure, it can be the basis of pruning. This is well understood. Consider a tree of exactly $2^{k+1}$ leaves. If you do not need the first $2^k$ leaves, you can prune their left subtree and end up with just the right subtree of size also $2^k$. Note that in the process you reduced the height from $k+1$ to $k$ which can be helpful. To generalize this, see the notion of "frozen" nodes in _"[CW09] Efficient Data Structures for Tamper-Evident Logging; by Crosby, Scott A. and Wallach, Dan S.; in Proceedings of the 18th Conference on USENIX Security Symposium; 2009"_

caveman

2/11/23, 7:18 PM

@AlinTomescu - Thanks. I know that part, and this is what I meant by not wanting a solution with pruning. Because this is an optimisation that benefits ones that have already downloaded the entire transactions and built the Merkle tree from the start. I'm trying to find a way to optimise it for new comers, so that they don't have to download the whole thing from the start (as it happens with every cryptocurrency today).

Score:1

Crypto

Alin Tomescu

2/5/24, 1:27 AM

Assuming that you are correctly using the term "accumulator" to mean a commitment to a set (i.e., unordered) of elements, one simple answer is "no."

There cannot be such an accumulator scheme because, in order to construct membership proofs for any element in the accumulated set, one needs to have the full set of $n$ elements which requires $O(n)$ storage.

I cannot point to any paper that proves this, but it seems like a natural result that could be proven.

On the other hand, suppose you do not care about the ability to compute proofs. Perhaps all you care about is keeping the digest up to date as new elements are appended to the accumulator. (e.g., perhaps proofs can be maintained by interesting parties, such as in stateless cryptocurrencies [RMCI17, CPZ18])

Then, many schemes would satisfy your requirement. Some of them are even able to deal with deleting elements.

Append-only Merkle trees or forest (e.g., Utreexo [Dryj19])
- i.e., keep a $O(\log{n})$-sized digest around and you can update it
RSA accumulators [Bd93]
- i.e., keep a $O(1)$-sized digest around and you can update it
Lattice-based accumulators [PSTY13]
- i.e., keep a $O(1)$-sized digest around and you can update it

Some of these schemes have caveats though: e.g., for RSA accumulators, if you want to update the digest after one or more deletes, you need to additionally have the membership proof(s) for the removed element(s).

References

[Bd93] One-Way Accumulators: A Decentralized Alternative to Digital Signatures; by Benaloh, Josh and de Mare, Michael; in EUROCRYPT '93; 1994

[CPZ18] Edrax: A Cryptocurrency with Stateless Transaction Validation; by Alexander Chepurnoy and Charalampos Papamanthou and Yupeng Zhang; 2018; https://eprint.iacr.org/2018/968

[Dryj19] Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set; by Thaddeus Dryja; 2019; https://eprint.iacr.org/2019/611

[PSTY13] Streaming Authenticated Data Structures; by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto and Yi, Ke; in EUROCRYPT 2013; 2013

[RMCI17] Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies; by Reyzin, Leonid and Meshkov, Dmitry and Chepurnoy, Alexander and Ivanov, Sasha; in FC'17; 2017

+ 2

caveman

2/10/24, 7:42 PM

Care to shed some light on the proof why it is impossible? I wonder what are the assumptions taken to reach the impossibility.

Alin Tomescu

2/11/24, 6:53 PM

I keep running into folks who want a proof for this, including myself :) Let me see if I can write a simple one down and post it here...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Non-pruned accumulators with asymptotic worst space $O(\log_2 n)$, or cheaper?

TH: ตัวสะสมที่ไม่ถูกตัดด้วยพื้นที่ที่แย่ที่สุดแบบซีมโทติค $O(\log_2 n)$ หรือถูกกว่า

RO: Acumulatoare netulate cu cel mai rău spațiu asimptotic $O(\log_2 n)$ sau mai ieftine?

RU: Аккумуляторы без обрезки с асимптотическим наихудшим пространством $O(\log_2 n)$ или дешевле?

VI: Bộ tích lũy không được cắt tỉa có không gian tiệm cận xấu nhất $O(\log_2 n)$ hoặc rẻ hơn?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.