📅 Original date posted:2020-06-08
📝 Original message: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200608/562ce529/attachment.html>;
Salvatore Ingala [ARCHIVE] /
npub1lp…c74n4
2023-06-07 18:25:19
in reply to nevent1q…2ch9
Author Public Key
npub1lpkmxpl2zhk0w30vtdz7s64ml9644k785eggmjsjgs7wman3szzqac74n4Published at
2023-06-07 18:25:19Event JSON
{
"id": "6f4c6b382b52370a89a70dcf5ce6bae9102c82f87e6f9700e5bd4722d12acb57",
"pubkey": "f86db307ea15ecf745ec5b45e86abbf9755adbc7a6508dca12443cedf6718084",
"created_at": 1686162319,
"kind": 1,
"tags": [
[
"e",
"b974b28b6419ceb8d7538813dcb1d099e83930509a21f365f0743d0a8dc4def8",
"",
"reply"
],
[
"p",
"a23dbf6c6cc83e14cc3df4e56cc71845f611908084cfe620e83e40c06ccdd3d0"
]
],
"content": "📅 Original date posted:2020-06-08\n📝 Original message:Dear all,\n\nI have been working on some constructions for cryptographic accumulators\nthat optimise for quick insertion.\n\nAs a brief background, an accumulator is a data structure that maintains\ncompact commitments to a potentially very large (and dynamic) set, while\nkeeping proofs of membership short. Unsurprisingly, they are getting more\npopular, and one notable application in Bitcoin is to create light-weight\nfull nodes that do not need to store the UTXO set (Utreexo accumulator[1]).\n\nIn this work, I focus on additive accumulators that supports adding new\nelements, but not removing them. My motivation is to support extending\nScript with access to an arbitrarily large portion of the blockchain\nhistory and state (e.g., past blocks, txids, or any more complex state\nobtained from them - with all due care). The additional storage and\ncomputation cost for nodes is small, and the cost (in additional bytesize)\nfor any transaction that wishes to access state committed in the\naccumulator should be just slightly bigger than typical Merkle proofs.\n\nI have focused on:\n- An accumulator with insertion time O(1) and proof size O(log^2 n)\n- A construction with insertion time O(log log n) and proof size O(log n\nlog log n)\n\nAll the performance metrics above are in \"number of hashes\".\n\nYou can find:\n- draft writeup:\nhttps://github.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf\n- sample python code (only for the first construction at this time):\nhttps://github.com/bigspider/accumulator\n\nWhile this is still an unfinished work, the ideas in the draft are\nhopefully clear enough and easy to understand. I wanted to share it at this\nstage as it can benefit from comments to improve the constructions, to\ncover any related work or to find potential applications in Bitcoin (e.g.\nScript, layer2, side chains, etc).\n\nBest,\nSalvatore Ingala\n\n[1] - Thaddeus Dryja, Utreexo: A dynamic hash-based accumulator optimized\nfor the Bitcoin UTXO set - https://eprint.iacr.org/2019/611.pdf\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200608/562ce529/attachment.html\u003e",
"sig": "d02a07dd61640da6591d75a097fecef8e5cac09fda6db7b901fbfc4710e092b97cd9512a5cd3d11ea4675d66543d3a5388cd555034bcbf299fab79d814706e18"
}