Understanding Accumulators

[nicola]

The aim of to understand a different type of authenticated data structure primitive.

The scope is to learn how to have proof of membership in constant size. Why is this inefficient?

Background

Pre-reading (context)

• [x] Authenticated Hash Tables
• [x] On the cost of Authenticated Data Structures - not related to accumulators but shows several authenticated dictionaries.
• [ ] Zero Knowledge Sets

General understanding

• [x] Wikipedia on Accumulators
• [x] Accumulators for everyone

Academic review

• From 0 to 1 of accumulators
• Recent long review on accumulators
• Zero knowledge arguments for accumulators
• Bilinear non-membership

Usage

• [ ] See how it is used in ZeroCoin
• [ ] See the use of accumulators on IntegriDB - slides

Recent/Relevant

• [ ] Accumulators with no trapdoors (1999)
• [x] ⭐️ Accumulators for Authenticated Hash Table
• [ ] An Expressive (Zero-Knowledge) Set Accumulator

---

cc @jbenet

[whyrusleeping]

@nicola your link to the IntegriDB thing is broken for me

[nicola]

@whyrusleeping updated that now! thanks!

[nicola]

Adding Accumulators for Authenticated Hash Table <- 2016 :)

[nicola]

Adding An Expressive (Zero-Knowledge) Set Accumulator <- 2017