Cauchyproofs: Batch-Updatable Vector Commitment with Easy Aggregation and Application to Stateless Blockchains

Stateless blockchain designs have emerged to address the challenge of growing blockchain size using succinct global states. Previous works have developed vector commitments that support proof updates and aggregation to be used as such states. However, maintaining proofs for multiple users still demands significant computational resources, particularly to update proofs with every transaction. This paper introduces Cauchyproofs, a batch-updatable vector commitment that enables proof-serving nodes to efficiently update proofs in quasilinear time relative to the number of users and transactions, utilizing an optimized KZG scheme to achieve complexity $o((\vert \vec{\alpha}\vert +\vert \vec{\beta}\vert)\log^{2}(\vert \vec{\alpha}\vert +\vert \vec{\beta}\vert))$ for $\vert \alpha\vert$ users and $\vert \beta\vert$ transactions, compared to the previous $O(\vert \vec{\alpha}\vert \cdot\vert \vec{\beta}\vert)$ approaches. This advancement reduces the computational burden on proof-serving nodes, allowing efficient proof maintenance across large user groups. We demonstrate that our approach is approximately eight times faster than the naive approach at the Ethereumlevel transaction throughput if we perform batch update every hour. Additionally, we present a novel matrix representation for KZG proofs utilizing Cauchy matrices, enabling faster all-proof computations with reduced elliptic curve operations. Finally, we propose an algorithm for history proof query, supporting retrospective proof generation with high efficiency. Our contributions substantially enhance the scalability and practicality of proof-serving nodes in stateless blockchain frameworks.