summaryrefslogtreecommitdiff
path: root/0e/2002c4cc479fed92bf5ffacf1d0b4aea9714db
blob: c5dcae4a269b53493f7a67a4220e4a5f805850db (plain)
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
Return-Path: <elombrozo@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 97A78A58
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 23 Feb 2017 03:30:40 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yb0-f195.google.com (mail-yb0-f195.google.com
	[209.85.213.195])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 49B54148
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 23 Feb 2017 03:30:39 +0000 (UTC)
Received: by mail-yb0-f195.google.com with SMTP id d88so250289ybi.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 22 Feb 2017 19:30:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=ynDB3Hu7zDzI9B0OLoQ3oGWT85W6tUtun4UUCug92cE=;
	b=GRONbWJQzZX354DgyzvE5UdeaxWkWsiMkliyMKSy83jpcDRcb829Jm+xhuzgQtEoT4
	XCMJqBQpxVxdylltTdjKrxPJXNu110reAeLQMBeuQSQ97TdFkpwmUHW2LzYrSFs3u7cH
	lPwQevaHLO9tjzozrkKqFfmlRT7h6O722H3JnC3+vDntD0JApVg3qv4YcgvD/QmoU4Yf
	Iju3tofIMsNKKsqhHBuTZz/fGQ9lDiE9/XR0wgDDvmUo4aL2Ndtb7wJ4CDS+5ZSHo/3E
	pw8ckEPMvJWfR6+j9B1VgB7oHMvuR4tXp8h8J6EfVfnc8TZQJY8CZbKZHXDxr73rCKH0
	+bmA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=ynDB3Hu7zDzI9B0OLoQ3oGWT85W6tUtun4UUCug92cE=;
	b=cmSfwhPz5qtX1H7KzyNE4hb1kwUgyg99bzOwbtt/oQwGKb5bkcNKRCGlW7WR9uDCi3
	4Yjnl9jvI0hlSgSIgdrvYBHN7Nhf80t+nxq4XWqVp8ZfTWPBzMNczGEFKMOxLBh//ITH
	TUA0Lxp6haoRLIMzzqVhJyHJSm9ZR1QpvL8cPIVWP9Pk4BoaL/4LzqTNkjg7ZPMrp+Ol
	2+UJVqBflyJCVkXZumQMQqYJJ42DQfA/sQlCW90+fCAb1PHA/3wAfGSwMXmk/4PgJPUV
	EuyEkVxxuqS1ntwsxuEF8L3/HIBa6QLbT7P0Xvm7Kobe36Wdg/qE33h2QLqPtWyVUBzT
	FbMQ==
X-Gm-Message-State: AMke39n1z60aNoKZTolWgOvcePKf3MGBYOY+C++h/74jYNKde2Qx7toMi1/SFhgKeffWm8Kl41zeo3sHRix0Nw==
X-Received: by 10.37.8.65 with SMTP id 62mr26547823ybi.73.1487820638099; Wed,
	22 Feb 2017 19:30:38 -0800 (PST)
MIME-Version: 1.0
Received: by 10.37.113.195 with HTTP; Wed, 22 Feb 2017 19:30:37 -0800 (PST)
In-Reply-To: <20170223011147.GB905@savin.petertodd.org>
References: <20170223011147.GB905@savin.petertodd.org>
From: Eric Lombrozo <elombrozo@gmail.com>
Date: Wed, 22 Feb 2017 19:30:37 -0800
Message-ID: <CABr1YTfSak2d199=_-ifRAmZkx6X3d5pMRqsU0ke_QwDmsiOnA@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a113db3c09fa0e405492a3c45
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] TXO commitments do not need a soft-fork to be
	useful
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Thu, 23 Feb 2017 03:30:40 -0000

--001a113db3c09fa0e405492a3c45
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

This kind of thing is long overdue!

I think it=E2=80=99s a great idea to attempt this without soft forking TXO
commitments yet so we can see what works best.


- E

On Wed, Feb 22, 2017 at 5:11 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Something I've recently realised is that TXO commitments do not need to b=
e
> implemented as a consensus protocol change to be useful. All the benefits
> they
> provide to full nodes with regard to allowing for old UTXO data to be
> pruned -
> and thus solving the UTXO bloat problem - can be implemented even without
> having miners commit to the TXO commitment itself. This has a significant
> deployment advantage too: we can try out multiple TXO commitment schemes,
> in
> production, without the need for consensus changes.
>
>
> # Reasoning
>
> 1) Like any other merkelized data structure, a TXO commitment allows a
> data set
> - the TXO set - to be securely provided by an untrusted third party,
> allowing
> the data itself to be discarded. So if you have a valid TXO commitment,
> you can
> discard the TXO data itself, and rely on untrusted entities to provide yo=
u
> that
> data on demand.
>
> 2) The TXO set is a super-set of the UTXO set; all data in the UTXO set i=
s
> also
> present in the TXO set. Thus a TXO commitment with spent TXO's pruned is
> equivalent to a UTXO set, doubly so if inner nodes in the commitment tree
> commit to the sum-unspent of their children.
>
> 3) Where a outpoint-indexed UTXO set has a uniform access pattern, an
> insertion-ordered TXO set has a delibrately *non-uniform* access pattern:
> not
> only are new entries to the TXO set always appended to the end - an
> operation
> that requires a known, log2(n), sized set of merkle tips - but due to los=
t
> coins alone we can guarantee that older entries in the TXO set will be le=
ss
> frequently updated than newer entries.
>
> 4) Thus a full node that doesn't have enough local storage to maintain th=
e
> full
> UTXO set can instead keep track of a TXO commitment, and prune older UTXO=
's
> from it that are unlikely to be spent. In the event those UTXO's are spen=
t,
> transactions and blocks spending them can trustlessly provide the necessa=
ry
> data to temporarily fill-in the node's local TXO set database, allowing t=
he
> next commitment to be calculated.
>
> 5) By *not* committing the TXO commitment in the block itself, we obsolet=
e
> my
> concept of delayed TXO commitments: you don't need to have calculated the
> TXO
> commitment digest to validate a block anyway!
>
>
> # Deployment Plan
>
> 1) Implement a TXO commitment scheme with the ability to efficiently stor=
e
> the
> last n versions of the commitment state for the purpose of reorgs (a
> reference-counted scheme naturally does this).
>
> 2) Add P2P support for advertising to peers what parts of the TXO set
> you've
> pruned.
>
> 3) Add P2P support to produce, consume, and update TXO unspentness proofs
> as
> part of transaction and block relaying.
>
> 4) Profit.
>
>
> # Bootstrapping New Nodes
>
> With a TXO commitment scheme implemented, it's also possible to produce
> serialized UTXO snapshots for bootstrapping new nodes. Equally, it's
> obviously
> possible to distribute those snapshots, and have people you trust attest
> to the
> validity of those snapshots.
>
> I argue that a snapshot with an attestation from known individuals that y=
ou
> trust is a *better* security model than having miners attest to validity:
> the
> latter is trusting an unknown set of unaccountable, anonymous, miners.
>
> This security model is not unlike the recently implemented -assumevalid
> scheme(1), in that auditing the validity of the assumed valid TXO
> commitments
> is something anyone can do provided they have a full node. Similarly, we
> could
> ship Bitcoin nodes with an assumed-valid TXO commitment, and have those
> nodes
> fill in the UTXO data from their peers.
>
> However it is a weaker security model, in that a false TXO commitment can
> more
> easily be used to trick a node into accepting invalid transactions/blocks=
;
> assumed valid blocks requires proof-of-work to pull off this attack. A
> compromise may be to use assumed valid TXO commitments, extending my
> partial
> UTXO set(2) suggestion of having nodes validate the chain backwards, to
> eventually validate 100% of the chain.
>
>
> # References
>
> 1) https://github.com/bitcoin/bitcoin/pull/9484
> 2) [Bitcoin-development] SPV bitcoind? (was: Introducing
> BitcoinKit.framework),
>    Peter Todd, Jul 17th 2013, Bitcoin development mailing list,
>    https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
> 2013-July/002917.html
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

--001a113db3c09fa0e405492a3c45
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">







<p class=3D"gmail-p1"><span class=3D"gmail-s1">This kind of thing is long o=
verdue!</span></p>
<p class=3D"gmail-p2">I think it=E2=80=99s a great idea to attempt this wit=
hout soft forking TXO commitments yet so we can see what works best.</p><p =
class=3D"gmail-p2"><br></p>
<p class=3D"gmail-p1"><span class=3D"gmail-s1">- E</span></p></div><div cla=
ss=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Feb 22, 2017 at 5=
:11 PM, Peter Todd via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:=
bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.=
linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
>Something I&#39;ve recently realised is that TXO commitments do not need t=
o be<br>
implemented as a consensus protocol change to be useful. All the benefits t=
hey<br>
provide to full nodes with regard to allowing for old UTXO data to be prune=
d -<br>
and thus solving the UTXO bloat problem - can be implemented even without<b=
r>
having miners commit to the TXO commitment itself. This has a significant<b=
r>
deployment advantage too: we can try out multiple TXO commitment schemes, i=
n<br>
production, without the need for consensus changes.<br>
<br>
<br>
# Reasoning<br>
<br>
1) Like any other merkelized data structure, a TXO commitment allows a data=
 set<br>
- the TXO set - to be securely provided by an untrusted third party, allowi=
ng<br>
the data itself to be discarded. So if you have a valid TXO commitment, you=
 can<br>
discard the TXO data itself, and rely on untrusted entities to provide you =
that<br>
data on demand.<br>
<br>
2) The TXO set is a super-set of the UTXO set; all data in the UTXO set is =
also<br>
present in the TXO set. Thus a TXO commitment with spent TXO&#39;s pruned i=
s<br>
equivalent to a UTXO set, doubly so if inner nodes in the commitment tree<b=
r>
commit to the sum-unspent of their children.<br>
<br>
3) Where a outpoint-indexed UTXO set has a uniform access pattern, an<br>
insertion-ordered TXO set has a delibrately *non-uniform* access pattern: n=
ot<br>
only are new entries to the TXO set always appended to the end - an operati=
on<br>
that requires a known, log2(n), sized set of merkle tips - but due to lost<=
br>
coins alone we can guarantee that older entries in the TXO set will be less=
<br>
frequently updated than newer entries.<br>
<br>
4) Thus a full node that doesn&#39;t have enough local storage to maintain =
the full<br>
UTXO set can instead keep track of a TXO commitment, and prune older UTXO&#=
39;s<br>
from it that are unlikely to be spent. In the event those UTXO&#39;s are sp=
ent,<br>
transactions and blocks spending them can trustlessly provide the necessary=
<br>
data to temporarily fill-in the node&#39;s local TXO set database, allowing=
 the<br>
next commitment to be calculated.<br>
<br>
5) By *not* committing the TXO commitment in the block itself, we obsolete =
my<br>
concept of delayed TXO commitments: you don&#39;t need to have calculated t=
he TXO<br>
commitment digest to validate a block anyway!<br>
<br>
<br>
# Deployment Plan<br>
<br>
1) Implement a TXO commitment scheme with the ability to efficiently store =
the<br>
last n versions of the commitment state for the purpose of reorgs (a<br>
reference-counted scheme naturally does this).<br>
<br>
2) Add P2P support for advertising to peers what parts of the TXO set you&#=
39;ve<br>
pruned.<br>
<br>
3) Add P2P support to produce, consume, and update TXO unspentness proofs a=
s<br>
part of transaction and block relaying.<br>
<br>
4) Profit.<br>
<br>
<br>
# Bootstrapping New Nodes<br>
<br>
With a TXO commitment scheme implemented, it&#39;s also possible to produce=
<br>
serialized UTXO snapshots for bootstrapping new nodes. Equally, it&#39;s ob=
viously<br>
possible to distribute those snapshots, and have people you trust attest to=
 the<br>
validity of those snapshots.<br>
<br>
I argue that a snapshot with an attestation from known individuals that you=
<br>
trust is a *better* security model than having miners attest to validity: t=
he<br>
latter is trusting an unknown set of unaccountable, anonymous, miners.<br>
<br>
This security model is not unlike the recently implemented -assumevalid<br>
scheme(1), in that auditing the validity of the assumed valid TXO commitmen=
ts<br>
is something anyone can do provided they have a full node. Similarly, we co=
uld<br>
ship Bitcoin nodes with an assumed-valid TXO commitment, and have those nod=
es<br>
fill in the UTXO data from their peers.<br>
<br>
However it is a weaker security model, in that a false TXO commitment can m=
ore<br>
easily be used to trick a node into accepting invalid transactions/blocks;<=
br>
assumed valid blocks requires proof-of-work to pull off this attack. A<br>
compromise may be to use assumed valid TXO commitments, extending my partia=
l<br>
UTXO set(2) suggestion of having nodes validate the chain backwards, to<br>
eventually validate 100% of the chain.<br>
<br>
<br>
# References<br>
<br>
1) <a href=3D"https://github.com/bitcoin/bitcoin/pull/9484" rel=3D"noreferr=
er" target=3D"_blank">https://github.com/bitcoin/<wbr>bitcoin/pull/9484</a>=
<br>
2) [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framewo=
rk),<br>
=C2=A0 =C2=A0Peter Todd, Jul 17th 2013, Bitcoin development mailing list,<b=
r>
=C2=A0 =C2=A0<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin=
-dev/2013-July/002917.html" rel=3D"noreferrer" target=3D"_blank">https://li=
sts.linuxfoundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2013-July/002917.ht=
ml</a><br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
--<br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
</font></span><br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div><br></div>

--001a113db3c09fa0e405492a3c45--