Published on: 2020-06-08T22:01:09+00:00
A mathematician named Germán expressed interest in a piece of work and suggested a method to indirectly support addition and removal by formulating it as a difference of sets, similar to collision-resistant replicated data types (CRDTs). This suggestion involves checking for membership through CheckMembershipInAdditionSet && !CheckMembershipInRemovalSet. Germán also mentioned the possibility of supporting multiple addition/removal by attaching a count of how many times an item has been added, but this may disrupt some aspects of the paper.The author has been focusing on cryptographic accumulators that optimize for quick insertion. Accumulators are data structures that maintain compact commitments to a potentially large set while keeping proofs of membership short. The author's focus is on additive accumulators that support adding new elements but not removing them. The motivation behind this is to enable Script to access 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 for these constructions are available on Github. Although the ideas presented in the draft are still unfinished, they are clear and easy to understand. The author is sharing the work at this stage to receive feedback for improving the constructions, covering related work, and exploring potential applications in Bitcoin. One notable application in Bitcoin is the creation of lightweight full nodes that do not require storing the UTXO set, known as the Utreexo accumulator.Overall, the mathematician's comment sparked interest in the work, and the author has been working on cryptographic accumulators that optimize for quick insertion. The author has developed two constructions and is seeking feedback to enhance the constructions, explore related work, and uncover potential applications in Bitcoin, such as lightweight full nodes using the Utreexo accumulator. The draft writeup and sample python code are available on Github for further examination.
Updated on: 2023-08-02T02:21:51.434361+00:00