From: Salvatore Ingala <salvatore.ingala@gmail•com>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] Hash-based accumulators with quick insertion
Date: Mon, 8 Jun 2020 11:28:28 +0200 [thread overview]
Message-ID: <CAMhCMoELX-=9N08KE499yjPNzH6xPqBB+gAKgQMTxbnsWQuV1w@mail.gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1990 bytes --]
Dear all,
I have been working on some constructions for cryptographic accumulators
that optimise for quick insertion.
As a brief background, an accumulator is a data structure that maintains
compact commitments to a potentially very large (and dynamic) set, while
keeping proofs of membership short. Unsurprisingly, they are getting more
popular, and one notable application in Bitcoin is to create light-weight
full nodes that do not need to store the UTXO set (Utreexo accumulator[1]).
In this work, I focus on additive accumulators that supports adding new
elements, but not removing them. My motivation is to support extending
Script with access to an arbitrarily large portion of the blockchain
history and state (e.g., past blocks, txids, or any more complex state
obtained from them - with all due care). The additional storage and
computation cost for nodes is small, and the cost (in additional bytesize)
for any transaction that wishes to access state committed in the
accumulator should be just slightly bigger than typical Merkle proofs.
I have focused on:
- An accumulator with insertion time O(1) and proof size O(log^2 n)
- A construction with insertion time O(log log n) and proof size O(log n
log log n)
All the performance metrics above are in "number of hashes".
You can find:
- draft writeup:
https://github.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf
- sample python code (only for the first construction at this time):
https://github.com/bigspider/accumulator
While this is still an unfinished work, the ideas in the draft are
hopefully clear enough and easy to understand. I wanted to share it at this
stage as it can benefit from comments to improve the constructions, to
cover any related work or to find potential applications in Bitcoin (e.g.
Script, layer2, side chains, etc).
Best,
Salvatore Ingala
[1] - Thaddeus Dryja, Utreexo: A dynamic hash-based accumulator optimized
for the Bitcoin UTXO set - https://eprint.iacr.org/2019/611.pdf
[-- Attachment #2: Type: text/html, Size: 2309 bytes --]
next reply other threads:[~2020-06-08 9:28 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-06-08 9:28 Salvatore Ingala [this message]
2020-06-08 22:01 German Luna
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAMhCMoELX-=9N08KE499yjPNzH6xPqBB+gAKgQMTxbnsWQuV1w@mail.gmail.com' \
--to=salvatore.ingala@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox