Author: Salvatore Ingala 2020-06-08 09:28:28
Published on: 2020-06-08T09:28:28+00:00
The author has been working on cryptographic accumulators that optimize for quick insertion. Accumulators are data structures that maintain compact commitments to a potentially very large set while keeping proofs of membership short. The author focuses on additive accumulators that support adding new elements but not removing them. The motivation behind this is to support extending Script with access to an arbitrarily large portion of the blockchain history and state. The author has developed two constructions: 1. An accumulator with insertion time O(1) and proof size O(log^2 n).2. A construction with insertion time O(log log n) and proof size O(log n log log n).The draft writeup and sample python code are available on Github. The ideas in the draft are still unfinished, but clear enough and easy to understand. The author is sharing it at this stage to benefit from comments for improving the constructions, covering any related work, or finding potential applications in Bitcoin. One notable application in Bitcoin is to create lightweight full nodes that do not need to store the UTXO set (Utreexo accumulator).
Updated on: 2023-05-20T23:23:34.326795+00:00