Nostr Web Client

Ecash mint without an every-growing database of spent tokens but a comparatively tiny accumulator. Sounds cool but tmk, a perfect accumulator hasn't been found yet.

If the accumulator has a false-positive rate like a bloom filter, it would falsely flag unspent ecash as "already spent" effectively randomly buring some few of the user's tokens (you can control how little).

It can be improved if the mint shares this accumulator publicly. When wallets want to mint tokens, they could "mine" for secrets that don't trigger a false positive hit with the accumulator. It's still not perfect because the accumulator is likely to change between the mint event and the spend (melt) event - which can again lead to new false positives.

Reply to this note

Please Login to reply.

Discussion

Erik 2y ago

The main problem of acculators is requiring witness updates for provers.

If I have a coin with mint A, the proof P will need to be updated every once in a while. The interval tends to be exponentially decaying, but existing.

This is the main challenge of building a bridgeless Utreexo network, wallets would need to download block proofs and update their proofs.

calle 2y ago

I see! I think the ecash case is a bit different though:

The accumulator is merely used by the mint to compress its database and elements never need to be removed. The accumulator can be shared with everyone (no privacy leak) but that's not the intent. In fact, there is nobody who needs to keep the "full database" to convince anyone else by proving membership. The accumulator is created and used only by the mint.

This is what an ecash accumulator needs to be able to do:

1) Check if incoming example is member of the accumulator

2) If not, add to accumulator

3) If member already, deny transaction (prevent double-spend)

In Utreexo, there is a global accumulator and everyone needs to prove membership of their utxo's in that accumulator to convince other users, right?

Erik 2y ago

Yes, there's a global accumulator, but just because there's a global utxo set. You can have purpose specific accumulators if you want.

However, all acculators I know need to update the witness on both add and del. I need to look at the paper again, but there's a provable tradeoff between update rate and size. You can't get a succinct acculator that also doesn't update the witness, so if you can't assume witness updates, IFAIK acculators won't do. (I might be wrong though, I'm not a cryptographer)

↗️ Promoted 2y ago

This is nothing I've spent even 2 minutes thinking about, but could you combine the Bloom filter with a Cuckoo filter and get better (perfect?) accuracy?

calle 2y ago

I'll check it out, I don't know!

Erik 2y ago

Only if you can prove that the false-positive cases for each construction have a negligible chance of overlapping (both filters saying " maybe yes" at the same time).