How I Learned to Stop Hashing and

Love the Accumulator (from Roberto)

Alin Tomescu

Research Scientist @ Aptos Labs

alinush.org

Friday, Oct 24th, 2025, RobertoFest, Brown University

"Spooky action advising at a distance"

• Read Roberto's papers since 2015
• Have not met Roberto until today
• But I've been his student for the last 10+ years

What a great honor to be here!

🙏 🙏

🎉 Authenticated data structures are eating the world!

Blockchains

• State synchronization [Dryj19]
• Light client proofs [AGT01]
• Stateless validation [RMCI17, SCP+22, PTT08]

Privacy & ZKPs

• ZK accumulators [LY10, GOP+15, CH22]
• Nullifier sets [PSTY13]
• Group signature schemes [LNWX17]

​

Transparency logs

• Key transparency [AGT01]
• Binary transparency [AGT01]
• Proof of liabilities [DBB+15]

Others

• Verifiable databases [ZKP15, ZGK+17]
• Outsourced file systems [GPTT08]
• <???>*

*This talk will most certainly miss very important works. Some of these works may be yours. My apologies in advance: I'm no longer a diligent PhD student.

Theme: structured commitment schemes ⇒ versatile ADSs

Accumulation trees (a.k.a. V(ery short M)erkle trees) [PTT08, Kusz18]

Generalized hash trees (a.k.a. H(omorphic M)erkle trees) [PSTY13, TCZ+20, CPZ18, SCP+22]

​

RSA-based authenticated dictionaries [GTH02, AR20, TXN20]

• Digest updates: d' = d + DigestUpd(j, δ_j)?
• Proof updates: π_i' = π_i + ProofUpd(j, δ_j)?
• (Cross-)aggregation of proofs

Append-only authenticated dictionaries [TBP+19, HSBB25]

Aggregatable-and-maintainable vector commitments [SCP+22, WUP22, LJGK25]

Structure-preserving vector commitments [KMS24]

Outline

Part 1: PST commitments [PST13]

Part 2: Accumulation trees [PTT08]

Part 3: Generalized hash trees [PSTY13]

Part 1: PST multivariate polynomial commitment scheme (PCS)

Note: Let G be a generator of 𝔾₁ and let [a]₁ = a · G

(Additive group notation)

∈ 𝔾₁

∈ 𝔾₁

Commitment key (CK)

The elegant PST decomposition lemma ⇒ PCS opening proofs

Many uses of PST

MLE PCS for sumcheck-based SNARKs [CMT12, GKR08, CBBZ22, …]

vSQL [ZGK+17]

vRAM [ZGK+18]

Aggregatable and maintainable vector commitments [SCP+22]

Data availability sampling (DAS) [BNNP25]

Range proofs [BDF+25]

< ??? > (I'm sure I missed some)

Since [PST13], there's been a zoo of other MLE PCSs

Knowledge-sound PST [ZGK+17, ZGK+18]

Hyrax [WTS+18]

Dory [Lee21]

Gemini [BCHO22]

HyperKZG? [CBBZ22]

Testudo [CGG+23]

Zeromorph [KT23]

Boomy [LL23]

Shplemini [GK25]

KZH [KZHB25]

Samaritan [GPS25]

Mercury [EG25]

Plus, many other hash-based schemes:

Basefold, Blaze, PolyFRIM, WHIR

Plus, a few more I missed: https://x.com/alinush/status/1990524159525339474

Part 2: Accumulation trees [PTT08] → Verkle trees [Kusz18]

It started as a theoretical question about accumulators (in the 2/3-party setting):

If we hold proof size & verification time O(1), can we both:

1. answer queries in O(1) time

2. update all proofs in o(n)? (Or vice versa?)

How it ended?

Reduce Merkle tree proof size from log₂n to log_kn! [Kusz18]

⇒ Ethereum community interest¹ and deployment².

[1]: Verkle trees, by Vitalik Buterin, https://vitalik.ca/general/2021/06/18/verkle.html

[2]: Ethereum roadmap / Verkle trees, https://ethereum.org/roadmap/verkle-trees/

k-ary Merkle

(k = 8)

= H(y₁, y₂, …, y₈)

k-ary Merkle

(k = 8) bad?

h₁

h₂

h₃

h₅

h₆

h₇

h₈

w₁

w₂

w₄

w₅

w₆

w₇

w₈

y₁

y₂

y₃

y₄

y₅

y₇

y₈

h₄

H(h₁, h₂, …, h₈)

H(w₁, w₂, …, w₈)

H(y₁, y₂, …, y₈)

[PTT08]

Accumulation trees

(k = 8)

z

y₁

y₂

y₃

y₄

y₅

y₆

y₇

y₈

= Acc.Commit({y₁, y₂, …, y₈})

[PTT08]

Accumulation trees

(k = 8)

z

y₁

y₂

y₃

y₄

y₅

y₆

y₇

y₈

(π_y,1, …, π_y,8) = Acc.ProveAll({y₁, y₂, …, y₈})

[PTT08]

Accumulation trees

(k = 8)

z

y₁

y₂

y₃

y₄

y₅

y₆

y₇

y₈

(π_y,1, …, π_y,8) = Acc.ProveAll({y₁, y₂, …, y₈})

= Acc.Commit({y₁, y₂, …, y₈})

Notice something? Verkle [Kusz18] only changes three things:

1. Replaces the KZG-based accumulator with a KZG-based vector commitment
2. Assumes a KZG trusted setup s.t. nobody knows the trapdoor τ
3. Assumes nothing about the tree structure (e.g., can be a prefix tree)

[PTT08]

Accumulation tree

proofs

h₄

Acc.Verify(w₃, h₄, π_h,4)

Acc.Verify(y₆, w₃, π_w,3)

z

y₆

w₃

Acc.Verify(z, y₆, π_y,6)

π_w,3

π_y,6

π_h,4

[Kusz18, Feis21]

Accumulation tree

proofs

h₄

Acc.CrossVerify(

[w₃, y₆, z ],

[h₄, w₃, y₆],

π

)

z

y₆

w₃

π

The impact of accumulation trees (a.k.a. Verkle)

Ethereum wants to validate blocks statelessly w.r.t. root of Merkle trie over the state.

Challenge: Currently, proofs for 1000 locations would be ~3.5 MB.

Solution: Reduce proof sizes via accumulation/Verkle trees to ~150 kB

⇒ "Verkle tree testnets are already up and running"

Part 3: Generalized hash trees [PSTY13]

Research question: Can we design a Merkle tree such that, given:� 1. the Merkle root r,

2. a leaf index i (or any node i),

3. the amount δ_i it changed by

…anyone can compute the updated r' = r + Upd(i, δ_i)?

​

Initial motivation:

Authenticate data with "streaming" updates [PSTY13]

​

Evolving motivation:

More efficient stateless validation (e.g., TXN from A to B) [TCZ+20, SCP+22]

[PSTY13]

h₁

h₂

h₃

h₄

h₅

h₆

h₇

h₈

[PSTY13]

h₁

Lh₁ + Rh₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

LLh₅+ LRh₆+ RLh₇ + RRh₈

LLLh₁ + LLRh₂ + LRLh₃ + LRRh₄ +

RLLh₅ + RLRh₆ + RRLh₇ + RRRh₈

+ Rδ₂

+ LRδ₂

+ LLRδ₂

h₂ + δ₂

The future impact of generalized hash trees (a.k.a. Herkle)

1. SNARK-friendly ADSs
2. Nullifier sets for anonymous cryptocurrencies (Zcash, AZTEC, Aleo)
3. Sharded cryptocurrencies
4. Statelessly-validated cryptocurrencies
5. Faster on-disk Merkle trees

Conclusion

Grazie Roberto for these amazing contributions:

1. [PST13]: the first multivariate PCS, ahead of its time (2011)
1. Tree of all MLE opening proofs [SCP+22]
2. Supports batch proofs [LL23]
2. [PTT08]: Very short Merkle trees
• log₂k times smaller proofs
• Adopted in Ethereum testnet for statelessness
3. [PSTY13]: Homomorphic Merkle trees
• Research is still needed
• Big potential to help scale storage services for nullifiers

References

Roberto (cited)

[AGT01] Persistent Authenticated Dictionaries and Their Applications; by Anagnostopoulos, Aris and Goodrich, Michael T. and Tamassia, Roberto; in Information Security'01

[GOP+15] Zero-Knowledge Accumulators and Set Operations; by Esha Ghosh and Olga Ohrimenko and Dimitrios Papadopoulos and Roberto Tamassia and Nikos Triandopoulos; 2015;

[GPTT08] Athos: Efficient Authentication of Outsourced File Systems; by Goodrich, Michael T. and Papamanthou, Charalampos and Tamassia, Roberto and Triandopoulos, Nikos; in Information Security; 2008

[PST13], Signatures of Correct Computation; by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto, in TCC'13

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

[PTT08] Authenticated hash tables; by Charalampos Papamanthou and Roberto Tamassia and Nikos Triandopoulos; in CCS'08

Roberto (uncited)

[GPT07] On the Cost of Persistence and Authentication in Skip Lists; by Goodrich, Michael T. and Papamanthou, Charalampos and Tamassia, Roberto; in Experimental Algorithms; 2007

[GTH02] An Efficient Dynamic and Distributed Cryptographic Accumulator; by Goodrich, Michael T. and Tamassia, Roberto and Hasic, Jasminka; in ICIS' 2002

[GTS01] Implementation of an authenticated dictionary with skip lists and commutative hashing; by Goodrich, M.T. and Tamassia, R. and Schwerin, A.; in DISCEX'01

[PTT11] Optimal Verification of Operations on Dynamic Sets; by Papamanthou, Charalampos and Tamassia, Roberto and Triandopoulos, Nikos; in CRYPTO 2011

[PTT10] Optimal Authenticated Data Structures with Multilinear Forms; by Papamanthou, Charalampos and Tamassia, Roberto and Triandopoulos, Nikos; in Pairing-Based Cryptography 2010

[PTT15] Authenticated Hash Tables Based on Cryptographic Accumulators; by Papamanthou, Charalampos and Tamassia, Roberto and Triandopoulos, Nikos; in Algorithmica'16

PCS references

[BCHO22] Gemini: Elastic SNARKs for Diverse Environments; by Bootle, Jonathan and Chiesa, Alessandro and Hu, Yuncong and Orrú, Michele; in EUROCRYPT 2022

[BNNP25] Data Availability Sampling with Repair; by Dan Boneh and Joachim Neu and Valeria Nikolaenko and Aditi Partap; 2025;

[CBBZ22] HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates; by Binyi Chen and Benedikt Bünz and Dan Boneh and Zhenfei Zhang; 2022;

[CGG+23] Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup; by Matteo Campanelli and Nicolas Gailly and Rosario Gennaro and Philipp Jovanovic and Mara Mihali and Justin Thaler; 2023;

[EG25] MERCURY: A multilinear Polynomial Commitment Scheme with constant proof size and no prover FFTs; by Liam Eagen and Ariel Gabizon; 2025;

[GK25] A note on the soundness of an optimized $\mathsf{gemini}$ variant; by Ariel Gabizon and Nishat Koti; 2025

[GPS25] Samaritan: Linear-time Prover SNARK from New Multilinear Polynomial Commitments; by Chaya Ganesh and Sikhar Patranabis and Nitin Singh; 2025

[KT23] Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments; by Tohru Kohrita and Patrick Towa; 2023

[KZHB25] KZH-Fold: Accountable Voting from Sublinear Accumulation; by George Kadianakis and Arantxa Zapico and Hossein Hafezi and Benedikt Bünz; 2025;

[Lee21] Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments; by Lee, Jonathan; in Theory of Cryptography; 2021

[LL23] Boomy: Batch Opening Of Multivariate polYnomial commitment; by Thomas Lavaur and Jérôme Lacan; 2023;

[WTS+18] Doubly-Efficient zkSNARKs Without Trusted Setup; by R. S. Wahby and I. Tzialla and A. Shelat and J. Thaler and M. Walfish; in SP'18

Structured ADSs references

[AR20] KVaC: Key-Value Commitments for Blockchains and Beyond; by Shashank Agrawal and Srinivasan Raghuraman; 2020

[CPZ18] Edrax: A Cryptocurrency with Stateless Transaction Validation; by Alexander Chepurnoy and Charalampos Papamanthou and Yupeng Zhang; 2018;

[Feis21] Verkle trie for Eth1 state, by Dankrad Feist

[GRWZ20] Pointproofs: Aggregating Proofs for Multiple Vector Commitments; by Gorbunov, Sergey and Reyzin, Leonid and Wee, Hoeteck and Zhang, Zhenfei; in CCS'20

[HSBB25] IronDict: Transparent Dictionaries from Polynomial Commitments; by Hossein Hafezi and Alireza Shirzad and Benedikt Bünz and Joseph Bonneau; 2025;

[LJGK25] Cauchyproofs: Batch-Updatable Vector Commitment with Easy Aggregation and Application to Stateless Blockchains; by Zhongtang Luo and Yanxue Jia and Alejandra Victoria Ospina Gracia and Aniket Kate

[LNWX17] Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease; by San Ling and Khoa Nguyen and Huaxiong Wang and Yanhong Xu; 2017

[LY10] Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs; by Libert, Benoît and Yung, Moti; in TCC'10; 2010

[Kusz18] Verkle Trees: V(ery short M)erkle Trees; by John Kuszmaul; in MIT PRIMES Conference '18; 2018

[KMS24] Structure-Preserving Compressing Primitives: Vector Commitments, Accumulators and Applications; by Stephan Krenn and Omid Mir and Daniel Slamanig; 2024;

[PPS21] Vector and Functional Commitments from Lattices; by Chris Peikert and Zachary Pepin and Chad Sharp; 2021

[SCP+22] Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments; by Shravan Srinivasan and Alexander Chepurnoy and Charalampos Papamanthou and Alin Tomescu and Yupeng Zhang; in USENIX Security'22

[TBP+19] Transparency Logs via Append-Only Authenticated Dictionaries; by Tomescu, Alin and Bhupatiraju, Vivek and Papadopoulos, Dimitrios and Papamanthou, Charalampos and Triandopoulos, Nikos and Devadas, Srinivas; in ACM CCS'19

[TCZ+20] Towards Scalable Threshold Cryptosystems; by Alin Tomescu and Robert Chen and Yiming Zheng and Ittai Abraham and Benny Pinkas and Guy Golan Gueta and Srinivas Devadas; in IEEE S&P'20

[WUP22] BalanceProofs: Maintainable Vector Commitments with Fast Aggregation; by Weijie Wang and Annie Ulichney and Charalampos Papamanthou; 2022

Other references

[BDF+25e] DekartProof: Efficient Vector Range Proofs and Their Applications; by Dan Boneh and Trisha Datta and Rex Fernando and Kamilla Nazirkhanova and Alin Tomescu; 2025

[CH22] Curve Trees: Practical and Transparent Zero-Knowledge Accumulators; by Matteo Campanelli and Mathias Hall-Andersen; 2022;

[CMT12] Practical Verified Computation with Streaming Interactive Proofs; by Cormode, Graham and Mitzenmacher, Michael and Thaler, Justin; in TCC 2012

[DBB+15] Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges; by Gaby G. Dagher and Benedikt Bünz and Joseph Bonneau and Jeremy Clark and Dan Boneh; in CCS'15

[Dryj19] Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set; by Thaddeus Dryja; 2019

[GKR08] Delegating Computation: Interactive Proofs for Muggles; by Goldwasser, Shafi and Kalai, Yael Tauman and Rothblum, Guy N.; in STOC'08;

[Merk87] A Digital Signature Based on a Conventional Encryption Function; by Merkle, Ralph C.; in CRYPTO '87; 1988

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

[TKPS22] Transparency Dictionaries with Succinct Proofs of Correct Operation; by Tzialla, Ioanna and Kothapalli, Abhiram and Parno, Bryan and Setty, Srinath; in NDSS 2022

[ZGK+17] vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases; by Y. Zhang and D. Genkin and J. Katz and D. Papadopoulos and C. Papamanthou; in IEEE SP'17

[ZGK+18] vRAM: Faster Verifiable RAM with Program-Independent Preprocessing; by Y. Zhang and D. Genkin and J. Katz and D. Papadopoulos and C. Papamanthou; in IEEE SP'18

[ZKP15] IntegriDB; by Yupeng Zhang and Jonathan Katz and Charalampos Papamanthou; in CCS'15;

Uncited but relevant

[CFM08] Zero-Knowledge Sets with Short Proofs; by Catalano, Dario and Fiore, Dario and Messina, Mariagrazia; in EUROCRYPT'08; 2008

Appendix

Stateless validation

Validation in cryptocurrencies requires storing large state

33

Grows over time

Slows down sharding

High storage & download cost

Stateless validation only requires digest of the state

34

new block

A ➝ B, 5 π_A

C ➝ D, 10 π_B

A ➝ C, 5 π_A

new

state

previous

state

​

​

​

​

​

A: 20 ETH

B: 55 ETH

C: 30 ETH

​

A: 10 ETH

B: 60 ETH

C: 25 ETH

D: 10 ETH

digest of

digest of

state = vector

digest = vector commitment (VC)

Grows over time

Slows down sharding

High storage & download cost

Accumulation trees

[PTT08]

Accumulation trees

(k = 8)

36

z

y₁

y₂

y₃

y₄

y₅

y₆

y₇

y₈

w₁

w₂

w₃

w₄

w₅

w₆

w₇

w₈

h₁

h₂

h₃

h₄

h₅

h₆

h₇

h₈

= Acc.Commit({y₁, y₂, …, y₈})

[PTT08]

Accumulation trees

(k = 8)

37

z

y₁

y₂

y₃

y₄

y₅

y₆

y₇

y₈

w₁

w₂

w₃

w₄

w₅

w₆

w₇

w₈

h₁

h₂

h₃

h₄

h₅

h₆

h₇

h₈

π_y,1

π_y,2

π_y,3

π_y,4

π_y,5

π_y,6

π_y,7

π_y,8

e.g., (π_y,1, …, π_y,8) = Acc.ProveAll({y₁, y₂, …, y₈})

Generalized hash trees

Lattice-based VCs

[PSTY13]

39

[PSTY13]

h₁

h₂

h₃

h₄

h₅

h₆

h₇

h₈

[PSTY13]

h₁

Lh₁ + Rh₂

h₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

L(Lh₁+ Rh₂) + R(Lh₃ + Rh₄)

[PSTY13]

h₁

Lh₁ + Rh₂

h₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

[PSTY13]

h₁

Lh₁ + Rh₂

h₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

LLh₅+ LRh₆ + RLh₇ + RRh₈

[PSTY13]

h₁

Lh₁ + Rh₂

h₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

LLh₅+ LRh₆ + RLh₇ + RRh₈

L(LLh₁ + LRh₂ + RLh₃ + RRh₄) +

R(LLh₅ + LRh₆ + RLh₇ + RRh₈)

[PSTY13]

h₁

Lh₁ + Rh₂

h₂

h₃

h₄

h₅

h₆

h₇

h₈

Lh₃ + Rh₄

Lh₅ + Rh₆

Lh₇ + Rh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

LLh₅+ LRh₆ + RLh₇ + RRh₈

LLLh₁ + LLRh₂ + LRLh₃ + LRRh₄ +

RLLh₅ + RLRh₆ + RRLh₇ + RRRh₈

[PSTY13]

Lh₁ + Rh₂

h₃

h₄

Lh₃ + Rh₄

LLLh₁ + LLRh₂ + LRLh₃ + LRRh₄ +

RLLh₅ + RLRh₆ + RRLh₇ + RRRh₈

LLh₁+ LRh₂ + RLh₃ + RRh₄

LLh₅+ LRh₆ + RLh₇ + RRh₈

2 log n-sized proof

(Why? A bit more going on than is depicted in the slide: i.e., a projection function)

Other thoughts

Things I did not touch upon

FRI

PADs

Some folks want post-quantum Verkle: Perkle?

Can we get Herkle+Verkle and make it post-quantum? Pherkle? [PPS21]

3-party model of authenticated data structures in blockchains

Source: The "blockchain" (i.e., the BFT replicated state machine)

Server: Any full node in the network

Clients: Users, wallets, other full nodes