Welcome to the resource topic for 2022/864
Title:
BalanceProofs: Maintainable Vector Commitments with Fast Aggregation
Authors: Weijie Wang, Annie Ulichney, and Charalampos Papamanthou
Abstract:We present BalanceProofs, the first vector commitment scheme that is maintainable (i.e., supporting sublinear updates) while also supporting fast proof aggregation and verification. The basic version of BalanceProofs has O(\sqrt{n}\log n) update time and O(\sqrt{n}) query time and its constant-size aggregated proofs can be produced and verified in milliseconds. In particular, BalanceProofs improves the aggregation time and aggregation verification time of the only known maintainable and aggregatable vector commitment scheme, HyperProofs (USENIX SECURITY 2022), by up to 1000$\times$. Fast verification of aggregated proofs is particularly useful for applications such as stateless cryptocurrencies (and was a major bottleneck for Hyperproofs), where an aggregated proof of balances is produced once but must be verified multiple times and by a large number of nodes. As a limitation, BalanceProofs’ update time compared to Hyperproofs roughly doubles, but always stays in the range from 2 to 3 seconds. BalanceProofs can be viewed as a compiler that transforms any non-maintainable vector commitment with fast aggregation to a maintainable one with the aforementioned complexities. We finally study useful tradeoffs in BalanceProofs between (aggregate) proof size, update time and (aggregate) proof computation and verification, by introducing a bucketing technique, and present an extensive evaluation, including a comparison to Hyperproofs as well as applications of BalanceProofs to Verkle trees.
ePrint: https://eprint.iacr.org/2022/864
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .