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
|
Return-Path: <m@ib.tc>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 031ECEC4
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jul 2019 03:07:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm1-f54.google.com (mail-wm1-f54.google.com
[209.85.128.54])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C25052C6
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jul 2019 03:07:13 +0000 (UTC)
Received: by mail-wm1-f54.google.com with SMTP id a15so52410584wmj.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jul 2019 20:07:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ib.tc; s=google;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=FsL7Iz382nwBbSqCw3MYv1dpBP7xw49VoD5bI3JExFU=;
b=O1yd6TJ32WCGu7OE54ZMXGmvxdcgienalx2pPu46AD1u/Zf+7S9OakDCm+/5epTQIQ
d+/cuCq7DnXv+3d25pUxQsOT1Ts2s6sgr5hkzL6HU3xegIH4QduNpOcmsowNVGI1V1Ui
rSkFD2vNWtrzFgoryxBsVOMgyOTI66yPyGWTKEGdsmc76Ljktz/KCWMoq7rtH3zldqqA
EqZAlEq9wcVTvYYEktx8/4yMmpHmbdzlrguqSEQcKJ0fSq3ch9WZ9qvIoak4U7dc8F0x
0dp5P3g+McX5Hjef3+MN9kivdy9DEBpZntTLzeK6L1jT9c81yf6DHCQawZYd8yyIgTqo
o7ng==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=FsL7Iz382nwBbSqCw3MYv1dpBP7xw49VoD5bI3JExFU=;
b=hfL6Inc9GXc9u8ylL9VWw+nPm6QR7W5EXF8+fTffY/yce3gZGsO7AVpoaK+CXdRsEL
tOoCEUoYcasAHrKW7Q9oeXXlRrJHhhV1d3c9pKY2CQ7entKnJ+JSUUav2SKAIFrU77QW
cymA9ZczEXNsIW9r3fgEluv0NWX4roR9uOaw66L8z8D77EkGXwFuecH8H+9gC9u+X8Mz
Bzes6eLDdWz/XA0dlNikV6LvN+wSIZHWLKxiZ7gOoiiE7DSDmLc0+ilkvfqRTsjxvQYS
31HnVH5NtlUVY3ssYzhTRqQy1ppDky3wWwLSG7FTCEnt+hLyAOWEzrbFTLeOW/v5kLqy
/X8Q==
X-Gm-Message-State: APjAAAUmlOhsXOtpKmopUuygXlB+xcFufJTmwZHguxW/tUwzYI0a+g2m
YJXNtMjM+lyhaE1wr+MwolI6ZJWHDwetDziWClMlLZGEF6Q=
X-Google-Smtp-Source: APXvYqz1bihE21VxdIeNRBq4VgUgao6KTZ13WLa7/+d5aKAortjIE/icwwNFc3/3hIj6oPq3nv/xZSczNvTZkmlcLcY=
X-Received: by 2002:a05:600c:225a:: with SMTP id
a26mr101463885wmm.81.1564369632307;
Sun, 28 Jul 2019 20:07:12 -0700 (PDT)
MIME-Version: 1.0
References: <CALFqKjQkQwuxjeYkGWO_Y_HhNQmJgrjqF3m04hbORV7FSbsi3Q@mail.gmail.com>
<nk8ihWbf71QT6w-wVbnunppF_DjS8ywDoDAugBj5mYM_LCpSzec0j6lkaTKBK4t3CsXwRSXWmzbWiW7nmqT4y0W2fn8X-3oXv-TAYXwP1R4=@protonmail.com>
<CALFqKjQoA+4XKGePHEK9OAZv2+qg=Q669v=f=MpDtg4F3Fx4kQ@mail.gmail.com>
<dW426iyRLdy0-CbpWL9pG7dG8qvmyQizPrwuBVHpblJBCBDSMjeIuFMiTjNHOaMfUzjaW2btTiFD9PiozOt9Cv5DQUZG0o22hYndr2wk3SI=@protonmail.com>
<CALFqKjTfFJATAELn4F0vBGsjorH3a8nzwwtKfXNz_vgWC5XPTg@mail.gmail.com>
<dNlv6xp0FTd29mczIiw3uOIoDYcTMV44Az0UZ53XQs_8PGzmnMIBhses0kU_SpOZGUcNzWRlerJEZm-p3YQ8USNIxPBouVZdWYCa7HcxDG0=@protonmail.com>
In-Reply-To: <dNlv6xp0FTd29mczIiw3uOIoDYcTMV44Az0UZ53XQs_8PGzmnMIBhses0kU_SpOZGUcNzWRlerJEZm-p3YQ8USNIxPBouVZdWYCa7HcxDG0=@protonmail.com>
From: Mike Brooks <m@ib.tc>
Date: Sun, 28 Jul 2019 20:07:01 -0700
Message-ID: <CALFqKjT=6aYGqTkzqcf2c5dwApPDTTVGuyGt=Vxi6Ms43m-4nQ@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>,
bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000003b47e4058ec930f6"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, 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
X-Mailman-Approved-At: Mon, 29 Jul 2019 07:24:16 +0000
Subject: Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References
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: Mon, 29 Jul 2019 03:07:15 -0000
--0000000000003b47e4058ec930f6
Content-Type: text/plain; charset="UTF-8"
ZmnSCPxj,
> Lightning uses a "short channel ID" which is basically an index of block
number + index of transaction + index of output to refer to channels.
Oh wow, this is very similar to the PUBREF proposal. In fact the OP_PUBREF4
operation could be modified to take the tuple: (block number, index of
transaction, index of PUSHDATA) and it would be functionally equivalent.
It looks like the construction of the short channel ID was chosen for the
performance needed to resolve the lookup.
> The problem with transaction being pruned is that the data in them
might now be used in a *future* `OP_PUBREF`.
I can see how pruning is needed for scalability, and pruning can be made
compatible with a reference to a transaction. If a transaction is pruned,
then the key material used in a prune'ed block's PUSHDATA operations are of
no value. A user of the network shouldn't need to make this kind of
PUBREF, and if a user did want to bring a wallet back from the dead - then
the utility of PUBREF wouldn't be available to them.
Best Regards,
Mike
On Sun, Jul 28, 2019 at 7:49 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> Good morning Mike,
>
> > I think that this implication affects other applications built on the
> blockchain, not just the PubRef proposal:
> >
>
> I believe not?
> Current applications use txids to refer to previous transactions, so even
> a short-ranged history rewrite will mostly not affect them --- they can
> just rebroadcast the transactions they are spending and get those
> reconfirmed again.
> There is admittedly a risk of double-spending, but each individual
> application can just spend deeply-confirmed transactions, and tune what it
> considers "deeply-confirmed" depending on how large the value being spent
> is.
> The point is that history rewrites are costly, but if the value being put
> in a `scriptPubKey` that uses `OP_PUBREF` is large enough, it may justify
> the cost of history rewrites --- but if the value is small, the individual
> application (which refers to transactions by their txid anyway) can
> generally assume miners will not bother to history-rewrite.
>
> Since `OP_PUBREF` would be a consensus rule, we need to select a
> "deeply-confirmed" point that is deep enough for *all* cases, unlike
> applications **on top of the blockchain** which can tune their rule of
> "deeply-confirmed" based on value.
> Thus my suggestion to use 100, which we consider "deep enough" to risk
> allowing miners to sell their coins.
>
> Lightning uses a "short channel ID" which is basically an index of block
> number + index of transaction + index of output to refer to channels.
> This is not a problem, however, even in case of short-ranged history
> rewrites.
> The short channel ID is only used for public routing.
> Between the channel counterparties, no security is based on short channel
> ID being stable; it just loses you potential routing fees from the channel
> (and can be fixed by increasing your "deeply-confirmed" enough level before
> you announce the channel for public routing).
>
> > > There is a potential for a targeted attack where a large payout going
> to a `scriptPubKey` that uses `OP_PUBREF` on a recently-confirmed
> transaction finds that recently-confirmed transaction is replaced with one
> that pays to a different public key, via a history-rewrite attack.
> > > Such an attack is doable by miners, and if we consider that we accept
> 100 blocks for miner coinbase maturity as "acceptably low risk" against
> miner shenanigans, then we might consider that 100 blocks might be
> acceptable for this also.
> > > Whether 100 is too high or not largely depends on your risk appetite.
> >
> > I agree 100% this attack is unexpected and very interesting.
>
> It is precisely because of this possibility that we tend to avoid making
> SCRIPT validity dependent on anything that is not in the transaction.
> We would have to re-evaluate the SCRIPT every time there is a chain tip
> reorganization (increasing validation CPU load), unless we do something
> like "only allow `OP_PUBREF` to data that is more than 100 blocks
> confirmed".
>
> > However, I find the arbitrary '100' to be unsatisfying - I'll have to
> do some more digging. It would be interesting to trigger this on the
> testnet to see what happens. Do you know if anyone has pushed these
> limits? I am so taken by this attack I might attempt it.
> >
> > > Data derived from > 220Gb of perpetually-growing blockchain is
> hardly, to my mind, "only needs an array".
> >
> > There are other open source projects that have to deal with larger data
> sets and have accounted for the real-world limits on computability. Apache
> HTTPD's Bucket-Brigade comes to mind, which has been well tested and can
> account for limited RAM when accessing linear data structures. For a more
> general purpose utility leveldb (bsd-license) provides random access to
> arbitrary data collections.
>
> Which is the point: we need to use something, the details need to be
> considered during implementation, implementation details may leak in the
> effective spec (e.g. DER-encoding), etc.
>
> > Pruning can also be a real asset for PubRef. If all transactions for a
> wallet have been pruned, then there is no need to index this PubRef - a
> validator can safely skip over it.
>
> What?
> The problem with transaction being pruned is that the data in them might
> now be used in a *future* `OP_PUBREF`.
>
> Further, pruned nodes are still full validators --- transactions may be
> pruned, but the pruned node will ***still*** validate any `OP_PUBREF` it
> uses, because it is still a full validator, it just does not archive old
> blocks in local storage.
>
> Regards,
> ZmnSCPxj
>
--0000000000003b47e4058ec930f6
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div><br></div><div>ZmnSCPxj,</div><div>=C2=A0=C2=A0</div>=
<div>> Lightning uses a "short channel ID" which is basically =
an index of block number + index of transaction + index of output to refer =
to channels.<br></div><div><br></div><div>Oh wow, this is very similar to t=
he PUBREF proposal. In fact the OP_PUBREF4 operation could be modified to t=
ake the tuple: (block number, index of transaction, index of PUSHDATA) and =
it would be functionally equivalent.=C2=A0 It looks like the construction o=
f the short channel ID was chosen for the performance needed to resolve the=
lookup.</div><div><br></div>=C2=A0 > The problem with transaction being=
pruned is that the data in them might now be used in a *future* `OP_PUBREF=
`.<br><div><br></div><div>I can see how pruning is needed for scalability, =
and pruning=C2=A0can be made compatible with a reference to a transaction. =
If a transaction is pruned, then the key material used in a prune'ed bl=
ock's PUSHDATA operations are of no value.=C2=A0 A user of the network =
shouldn't need to make this kind of PUBREF, and if a user did want to b=
ring a wallet back from the dead - then the utility of PUBREF wouldn't =
be available to them.</div><div><br></div><div>Best Regards,</div><div>Mike=
</div><div><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" =
class=3D"gmail_attr">On Sun, Jul 28, 2019 at 7:49 PM ZmnSCPxj <<a href=
=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>> wrote:<=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex">Good morning Mik=
e,<br>
<br>
> =C2=A0I think that this implication affects other applications built o=
n the blockchain, not just the PubRef proposal:<br>
><br>
<br>
I believe not?<br>
Current applications use txids to refer to previous transactions, so even a=
short-ranged history rewrite will mostly not affect them --- they can just=
rebroadcast the transactions they are spending and get those reconfirmed a=
gain.<br>
There is admittedly a risk of double-spending, but each individual applicat=
ion can just spend deeply-confirmed transactions, and tune what it consider=
s "deeply-confirmed" depending on how large the value being spent=
is.<br>
The point is that history rewrites are costly, but if the value being put i=
n a `scriptPubKey` that uses `OP_PUBREF` is large enough, it may justify th=
e cost of history rewrites --- but if the value is small, the individual ap=
plication (which refers to transactions by their txid anyway) can generally=
assume miners will not bother to history-rewrite.<br>
<br>
Since `OP_PUBREF` would be a consensus rule, we need to select a "deep=
ly-confirmed" point that is deep enough for *all* cases, unlike applic=
ations **on top of the blockchain** which can tune their rule of "deep=
ly-confirmed" based on value.<br>
Thus my suggestion to use 100, which we consider "deep enough" to=
risk allowing miners to sell their coins.<br>
<br>
Lightning uses a "short channel ID" which is basically an index o=
f block number + index of transaction + index of output to refer to channel=
s.<br>
This is not a problem, however, even in case of short-ranged history rewrit=
es.<br>
The short channel ID is only used for public routing.<br>
Between the channel counterparties, no security is based on short channel I=
D being stable; it just loses you potential routing fees from the channel (=
and can be fixed by increasing your "deeply-confirmed" enough lev=
el before you announce the channel for public routing).<br>
<br>
> =C2=A0> There is a potential for a targeted attack where a large pa=
yout going to a `scriptPubKey` that uses `OP_PUBREF` on a recently-confirme=
d transaction finds that recently-confirmed transaction is replaced with on=
e that pays to a different public key, via a history-rewrite attack.<br>
> =C2=A0> Such an attack is doable by miners, and if we consider that=
we accept 100 blocks for miner coinbase maturity as "acceptably low r=
isk" against miner shenanigans, then we might consider that 100 blocks=
might be acceptable for this also.<br>
> =C2=A0> Whether 100 is too high or not largely depends on your risk=
appetite.<br>
><br>
> I agree 100% this attack is unexpected and very interesting.<br>
<br>
It is precisely because of this possibility that we tend to avoid making SC=
RIPT validity dependent on anything that is not in the transaction.<br>
We would have to re-evaluate the SCRIPT every time there is a chain tip reo=
rganization (increasing validation CPU load), unless we do something like &=
quot;only allow `OP_PUBREF` to data that is more than 100 blocks confirmed&=
quot;.<br>
<br>
>=C2=A0 However, I find the arbitrary '100' to be unsatisfying -=
I'll have to do some more digging. It would be interesting to trigger =
this on the testnet to see what happens.=C2=A0 Do you know if anyone has pu=
shed these limits?=C2=A0 I am so taken by this attack I might attempt it.<b=
r>
><br>
> =C2=A0> Data derived from > 220Gb of perpetually-growing blockch=
ain is hardly, to my mind, "only needs an array".<br>
><br>
> There are other open source projects that have to deal with larger dat=
a sets and have accounted for the real-world limits on computability. Apach=
e HTTPD's Bucket-Brigade comes to mind, which has been well tested and =
can account for limited RAM when accessing linear data structures. For a mo=
re general purpose utility leveldb (bsd-license) provides random access to =
arbitrary data collections.<br>
<br>
Which is the point: we need to use something, the details need to be consid=
ered during implementation, implementation details may leak in the effectiv=
e spec (e.g. DER-encoding), etc.<br>
<br>
>=C2=A0 Pruning can also be a real asset for PubRef.=C2=A0 If all transa=
ctions for a wallet have been pruned, then there is no need to index this P=
ubRef - a validator can safely skip over it.<br>
<br>
What?<br>
The problem with transaction being pruned is that the data in them might no=
w be used in a *future* `OP_PUBREF`.<br>
<br>
Further, pruned nodes are still full validators --- transactions may be pru=
ned, but the pruned node will ***still*** validate any `OP_PUBREF` it uses,=
because it is still a full validator, it just does not archive old blocks =
in local storage.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>
--0000000000003b47e4058ec930f6--
|