đNew paper: Private Delegation of (Non-)Membership Proof Updates in Cryptographic Accumulators
Ever tried to use accumulators in practice? Then youâve hit the wall: every update breaks everyoneâs proofs.
We fix that.
đ§ľ1/n
@0xSooki @BotiGlasz đĽThe core problem:
Cryptographic accumulators compress huge sets (e.g., set of unspent coins) into tiny digests.
But⌠when the set changes:
âĄď¸ ALL membership proofs become outdated
âĄď¸ Clients must recompute them
This kills usability for mobile/offline users.
2/n
Cryptographic accumulators compress huge sets (e.g., set of unspent coins) into tiny digests.
But⌠when the set changes:
âĄď¸ ALL membership proofs become outdated
âĄď¸ Clients must recompute them
This kills usability for mobile/offline users.
2/n
This isnât just annoying â itâs fundamental.
Recent lower bounds show:
đ You canât avoid frequent proof updates without blowing up the state size.
So the question becomes:
Can we privately outsource (non-)membership proof updates?
3/n
Recent lower bounds show:
đ You canât avoid frequent proof updates without blowing up the state size.
So the question becomes:
Can we privately outsource (non-)membership proof updates?
3/n
@0xSooki @BotiGlasz Naively outsourcing fails!â
If you send your (non-)membership proof to a server:
đ it can brute-force which element you own.
Privacy = gone.
Even worse in systems like Zcash, anonymous credentials, or key transparency.
4/n
If you send your (non-)membership proof to a server:
đ it can brute-force which element you own.
Privacy = gone.
Even worse in systems like Zcash, anonymous credentials, or key transparency.
4/n
@0xSooki @BotiGlasz đĄOur idea:
Let clients delegate (non-)membership proof updates to an untrusted serverâŚ
BUT:
đ without revealing which element they care about
⥠with constant client work
â and publicly verifiable correctness
5/n
Let clients delegate (non-)membership proof updates to an untrusted serverâŚ
BUT:
đ without revealing which element they care about
⥠with constant client work
â and publicly verifiable correctness
5/n
@0xSooki @BotiGlasz We introduce a new primitive:
đ Private delegation of accumulator proof updates
Formalized with:
⢠correctness
⢠delegation soundness
⢠(strong + weak) privacy guarantees
6/n
đ Private delegation of accumulator proof updates
Formalized with:
⢠correctness
⢠delegation soundness
⢠(strong + weak) privacy guarantees
6/n
@0xSooki @BotiGlasz đ§ Key trick:
Before sending a (non-)membership proof to the server, the client:
đ blinds it
The server updates the blinded (non-)membership proof
â learns nothing about the underlying element
7/n
Before sending a (non-)membership proof to the server, the client:
đ blinds it
The server updates the blinded (non-)membership proof
â learns nothing about the underlying element
7/n
@0xSooki @BotiGlasz Then:
â Server returns updated blinded proof
â Anyone can verify the update was correct
â Client unblinds â gets valid fresh (non-)membership proof
All without revealing the element x đ
8/n
â Server returns updated blinded proof
â Anyone can verify the update was correct
â Client unblinds â gets valid fresh (non-)membership proof
All without revealing the element x đ
8/n
@0xSooki @BotiGlasz âĄPerformance highlight:
Client update cost:
đ O(1) (constant time!)
Previous work:
đ O(k) or even O(sqrt(k))
This is a huge win for resource-constrained devices.
9/n
Client update cost:
đ O(1) (constant time!)
Previous work:
đ O(k) or even O(sqrt(k))
This is a huge win for resource-constrained devices.
9/n
@0xSooki @BotiGlasz đ We build concrete schemes for:
⢠RSA accumulators
⢠Bilinear accumulators
Both supporting efficient private delegation for (non-)membership proofs.
10/n
⢠RSA accumulators
⢠Bilinear accumulators
Both supporting efficient private delegation for (non-)membership proofs.
10/n
@0xSooki @BotiGlasz For RSA accumulators:
⨠Simple but powerful trick:
Randomize proof â exponentiate â prove consistency with NIZKs
Result:
â efficient
â practical
â ~7% overhead vs non-private baseline
11/n
⨠Simple but powerful trick:
Randomize proof â exponentiate â prove consistency with NIZKs
Result:
â efficient
â practical
â ~7% overhead vs non-private baseline
11/n
@0xSooki @BotiGlasz We also support:
â membership proofs
â non-membership proofs
â batching of updates
All privately delegated.
12/n
â membership proofs
â non-membership proofs
â batching of updates
All privately delegated.
12/n
@0xSooki @BotiGlasz 𧞠Public verifiability is key:
The server can produce a proof that:
đ âI updated this correctlyâ
Anyone can check it.
This enables:
đ° markets for proof-serving nodes.
13/n
The server can produce a proof that:
đ âI updated this correctlyâ
Anyone can check it.
This enables:
đ° markets for proof-serving nodes.
13/n
đ§ Why this matters:
Applications include:
⢠Stateless blockchains
⢠Anonymous credentials (revocation)
⢠Registration-based encryption
⢠Transparency logs
14/n
Applications include:
⢠Stateless blockchains
⢠Anonymous credentials (revocation)
⢠Registration-based encryption
⢠Transparency logs
14/n
@0xSooki @BotiGlasz Example: stateless blockchains
Without our approach:
đ you must stay online to keep proofs fresh
With us:
đ go offline, come back, outsource updates privately
It turns out that running a server for delegating proofs in a stateless blockchain is pretty cheap.
15/n
Without our approach:
đ you must stay online to keep proofs fresh
With us:
đ go offline, come back, outsource updates privately
It turns out that running a server for delegating proofs in a stateless blockchain is pretty cheap.
15/n
@0xSooki @BotiGlasz đ§ŞBonus:
We built an open-source implementationđ§
đ First real system for private accumulator proof delegation
3...2...1...Delegate! github.com/GlaszBoti/privâŚ
16/n
We built an open-source implementationđ§
đ First real system for private accumulator proof delegation
3...2...1...Delegate! github.com/GlaszBoti/privâŚ
16/n
@0xSooki @BotiGlasz Open problems, directions
Private delegation for other authenticated data structures: vector commitments, authenticated dictionaries, etc.
Private delegation for PQ-secure accumulators
Multi-server private delegation schemes for better liveness
17/n
Private delegation for other authenticated data structures: vector commitments, authenticated dictionaries, etc.
Private delegation for PQ-secure accumulators
Multi-server private delegation schemes for better liveness
17/n
@0xSooki @BotiGlasz Let us know if you have any comments, feedback, critique, etc.
Tolle, lege: eprint.iacr.org/2026/832.pdf
Q.E.D.
Fin!
18/18
Tolle, lege: eprint.iacr.org/2026/832.pdf
Q.E.D.
Fin!
18/18
Generated by Thread Navigator
Press â + S to quick-export