1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
Return-Path: <salvatore.ingala@gmail.com>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id C29F0C016F
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 8 Jun 2020 09:28:43 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by silver.osuosl.org (Postfix) with ESMTP id A579A2052B
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 8 Jun 2020 09:28:43 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id og0oV4exTog9
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 8 Jun 2020 09:28:42 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-lj1-f194.google.com (mail-lj1-f194.google.com
[209.85.208.194])
by silver.osuosl.org (Postfix) with ESMTPS id C771D2051A
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 8 Jun 2020 09:28:41 +0000 (UTC)
Received: by mail-lj1-f194.google.com with SMTP id y11so17911730ljm.9
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 08 Jun 2020 02:28:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=88WSRCxVkAX9LtoIW14+VJJwdS0Qzo2bK/UdgMEeq+o=;
b=LK18xC5DPMrECNBnSCFENcv7uCqgZvTmqOEWr6A+0K5R1nvj4jK6A2dB73P7jdD4bI
ETMFkKGnsJkqnIbdmsuMXsO4rIaRGcXSudH2LRTjkEKuOP+9ZeVRJ/FldpLiL8HNCEAI
ausw+7+ETzNubW9Ph3nPG5Ja8TL504eFc1fH6ZPKMOgKSnjiFewiI/uV+agr1brKqnn/
YlyZF/3heMlSQfNNxhugHpCJcuzcwJi9p3fTBmLt1xwUxNsXleBBRh312KUt9ETY/czb
DA5QQ3z6vg4h4whReotqJbAt4Q6JOygkH/m2QDGXC0Kesu/jZRg/chMuz+LGV39CXyv9
Zg6g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=88WSRCxVkAX9LtoIW14+VJJwdS0Qzo2bK/UdgMEeq+o=;
b=g54YN2Ojtd/w8rXKTVAx/IkrSdPKBRwU1ZAeKTGosdudB8mr0GBiSsKAr17kk7w9pZ
9g+HlKfcOerwbBzmxOsjmv9A3jp4erpBllYEUFgBJ49rD5/5ee2ff+e/RMEwSyPr528H
DJPeJhTxYb60FuIxisnZDdkfUQp6JyvZop1A8/kTm+YY7ze5bItW+ruz4RMfq2iWUNFh
M9mswpkaHL5LHlTc09yBMIcsJiNaaDREp3VyKEJul2ggjO3+mS/sK6KiBOiGq1OzWBdf
pbO/Hrkhipa+R+tIIluy6ee3+rQz2Xo3b7bM1qiFLG4NU2fXfeXPtzdbsqK6LtaNRm+I
+Dcg==
X-Gm-Message-State: AOAM531Uxj5oLfwlwq3V030u66UNXgU/QqYN9XWPJ/9Hk+NsiEVGfD6q
uM1zQE595hdGotaRbH/psZSqWQaMqAQyrC9pOCGkE7Q/9xo7vw==
X-Google-Smtp-Source: ABdhPJy6AyYwMHolWhqQQwe+GxiNX3J9jcIxabnzrvajQp8JV2ecV2FRzh7K/E/TAIEKbuwr758y6d/+CoXoWjs3HL8=
X-Received: by 2002:a2e:81d4:: with SMTP id s20mr10422968ljg.248.1591608519522;
Mon, 08 Jun 2020 02:28:39 -0700 (PDT)
MIME-Version: 1.0
From: Salvatore Ingala <salvatore.ingala@gmail.com>
Date: Mon, 8 Jun 2020 11:28:28 +0200
Message-ID: <CAMhCMoELX-=9N08KE499yjPNzH6xPqBB+gAKgQMTxbnsWQuV1w@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="0000000000006d7f0d05a78f3c1a"
X-Mailman-Approved-At: Mon, 08 Jun 2020 09:33:42 +0000
Subject: [bitcoin-dev] Hash-based accumulators with quick insertion
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 08 Jun 2020 09:28:43 -0000
--0000000000006d7f0d05a78f3c1a
Content-Type: text/plain; charset="UTF-8"
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
--0000000000006d7f0d05a78f3c1a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Dear all,<br><br>I have been working on some constructions=
for cryptographic accumulators that optimise for quick insertion. <br><br>=
As a brief background, an accumulator is a data structure that maintains co=
mpact commitments to a potentially very large (and dynamic) set, while keep=
ing proofs of membership short. Unsurprisingly, they are getting more popul=
ar, and one notable application in Bitcoin is to create light-weight full n=
odes that do not need to store the UTXO set (Utreexo accumulator[1]).<br><b=
r>In this work, I focus on additive accumulators that supports adding new e=
lements, but not removing them. My motivation is to support extending Scrip=
t 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 t=
hem - with all due care). The additional storage and computation cost for n=
odes is small, and the cost (in additional bytesize) for any transaction th=
at wishes to access state committed in the accumulator should be just sligh=
tly bigger than typical Merkle proofs.<br><br>I have focused on: <br>- An a=
ccumulator with insertion time O(1) and proof size O(log^2 n)<br>- A constr=
uction with insertion time O(log log n) and proof size O(log n log log n)<d=
iv><br></div><div>All the performance metrics above are in "number of =
hashes".<br><br>You can find:<br>- draft writeup: <a href=3D"https://g=
ithub.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf">https://g=
ithub.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf</a><br>- s=
ample python code (only for the first construction at this time): <a href=
=3D"https://github.com/bigspider/accumulator">https://github.com/bigspider/=
accumulator</a><br><br>While this is still an unfinished work, the ideas in=
the draft are hopefully clear enough and easy to understand. I wanted to s=
hare it at this stage as it can benefit from comments to improve the constr=
uctions, to cover any related work or to find potential applications in Bit=
coin (e.g. Script, layer2, side chains, etc).<br><br>Best,<br>Salvatore Ing=
ala<br><br>[1] - Thaddeus Dryja, Utreexo: A dynamic hash-based accumulator =
optimized for the Bitcoin UTXO set - <a href=3D"https://eprint.iacr.org/201=
9/611.pdf">https://eprint.iacr.org/2019/611.pdf</a><br></div></div>
--0000000000006d7f0d05a78f3c1a--
|
