Utreexo is a forest of perfect Merkle trees (binary trees) that functions as an accumulator. The accumulator implementation ideally has the following signature (Python syntax):
Proof = List[Hash] # type synonym to improve readability
verify_existence(p: Proof) -> bool # was the hash associated with the proof previously added to the forest and not deleted?
add(to_add: Hash) -> Proof # mutably add given hash to the forest, returns a proof of its existence (a path down the forest)
remove(proof: Proof) -> None # mutably remove the hash associated with the proof, such that 'verify_existence' will return false in the future until re-added.
You can see that a set would also serve as an accumulator. The advantage of Utreexo however, is, that it only needs logarithmic storage.
The first half of the talk will explain the algorithms, and the second half will talk about porting the Go implementation to Haskell, in search of 'elegance'.
Utreexo was invented for use in Bitcoin, I may talk about its application there.
The paper is at https://eprint.iacr.org/2019/611.pdf
Speakers for Utreexo: A dynamic hash-based accumulator data structure:
Metadata for Utreexo: A dynamic hash-based accumulator data structure
To be recorded: YesURLs for Utreexo: A dynamic hash-based accumulator data structure
Recording: https://www.youtube.com/watch?v=ZNPsu5sn00c
Schedule for Utreexo: A dynamic hash-based accumulator data structure
- Wednesday, Aug 12th, 2020, 16:00 (CEST) - Wednesday, Aug 12th, 2020, 17:00 (CEST) at Speakers Tent