summaryrefslogtreecommitdiff
path: root/98/645cda4515473910d78ae177be35463c75e4aa
blob: 359266113d59dc5423437088f077059363f91c64 (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
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 C23C6E5D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 29 Jul 2019 02:20:09 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com
	[209.85.221.41])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5C93C5E4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 29 Jul 2019 02:20:08 +0000 (UTC)
Received: by mail-wr1-f41.google.com with SMTP id 31so60054581wrm.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 28 Jul 2019 19:20:08 -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
	:cc; bh=lGMPxF7OBJlHbUkXZ51JwXqngiUR6MBnsSpo5QA9oJ4=;
	b=RP11zCAyp2RZGicT+86j4mwpR7uOAhzdqoFufYkxcE0npze79KpS7g444D64KjlFp4
	w84XcYIeiC3GVhlTa/ljMd4/O0Z8knjffDPsKysXIengTkizpOCO4icLSIGLbdFLKa4Q
	b5kCr3cvg1LOHMx8fS+w71K2Aul1L/X6MFULIFQ8spzAomTg3gIu6FvibC/Hg8aMtwBD
	52n0AvyNBADXiYYAG0RwpPHW+UjSYAvs/He5M4Z98wv+DyJqO8ARaKXBeJlOo5KorTCf
	tNLPcAHWNC0suqdpO/8N1u4w+bR8K+Y5okAns0ubJVMgGtzIcj7Sz/g2VdTwxH2h8OU6
	HMhg==
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:cc;
	bh=lGMPxF7OBJlHbUkXZ51JwXqngiUR6MBnsSpo5QA9oJ4=;
	b=UeU7n+9XmVxOO8cl0c50tq+LlWDRqjYu4VsafNfIAygnA3sN8z++GtvlTwlbQLDNxu
	LRClkmO+X7a01pHagJORG8DTi6NB4HMJ68MAz/D4vzXH7xyywNJQwmbHdz1wPuvzBLJt
	O41Ke1XTmmWTqJLEA5g5WX0+Zh+4Run444NHmR7lr7xmqHEcjiQEJ/1p3L33ZCzP2362
	iYQPgR6hGzRLPyJLgqxMf8qJFgsMaS02yg0Jcbm1M7nsVvml0uGEFhxW3KPY4bmm0RHN
	2fX/DUa/UE6M8+jXOdhSDH+WFnJC9a+qvXEA9yoE/wiTOI5YpFlWDbBI8FQy2olYdUu6
	HOoA==
X-Gm-Message-State: APjAAAUnEQSFBkj6wC6JSTyLQWIDkRFA0nJTg2MPNrvP3z6JhTRso4Nd
	NeJeYdmKOlWQsnI4KcrfXO7Ke0J/+8q/zfIp8IA=
X-Google-Smtp-Source: APXvYqxbkshNMP028EQx2KySho0vIZNJ241CPxP2wGXbooy7QssnIAr5OeTreoGNQRhppIs51KcYT1ElwzZF4TJUDx0=
X-Received: by 2002:adf:dfc4:: with SMTP id q4mr113864639wrn.54.1564366806891; 
	Sun, 28 Jul 2019 19:20:06 -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>
In-Reply-To: <dW426iyRLdy0-CbpWL9pG7dG8qvmyQizPrwuBVHpblJBCBDSMjeIuFMiTjNHOaMfUzjaW2btTiFD9PiozOt9Cv5DQUZG0o22hYndr2wk3SI=@protonmail.com>
From: Mike Brooks <m@ib.tc>
Date: Sun, 28 Jul 2019 19:19:55 -0700
Message-ID: <CALFqKjTfFJATAELn4F0vBGsjorH3a8nzwwtKfXNz_vgWC5XPTg@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000d2d171058ec887f7"
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 02:53:15 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	"pieter.wuille@gmail.com" <pieter.wuille@gmail.com>
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 02:20:09 -0000

--000000000000d2d171058ec887f7
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

ZmnSCPxj,

 I think that this implication affects other applications built on the
blockchain, not just the PubRef proposal:

 > 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.  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.  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.

Best Regards,
Mike

On Sun, Jul 28, 2019 at 6:46 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Mike,
>
>
> Sent with ProtonMail Secure Email.
>
> =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original =
Message =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90
> On Sunday, July 28, 2019 4:03 AM, Mike Brooks <m@ib.tc> wrote:
>
> > Hey ZmnSCPxj,
> >
> > As to your first point.  I wasn't aware there was so much volatility at
> the tip, also 100 blocks is quite the difference!  I agree no one could
> references a transaction in a newly formed blocks, but I'm curious how th=
is
> number was chosen. Do you have any documentation or code that you can sha=
re
> related to how re-orgs are handled? Do we have a kind of 'consensus
> checkpoint' when a re-org is no longer possible? This is a very interesti=
ng
> topic.
> >
>
> Miner coinbases need 100 blocks for maturity, which is the basis of my
> suggestion to use 100 blocks.
> It might be too high, but I doubt there will be good reason to be less
> than 100.
>
> 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 f=
or
> this also.
> Whether 100 is too high or not largely depends on your risk appetite.
>
> >  A validator only needs an array of PUSHDATA elements and can then
> validate any given SCRIPT at O(1).
>
> Data derived from > 220Gb of perpetually-growing blockchain is hardly, to
> my mind, "only needs an array".
> Such an array would not fit in memory for many devices that today are
> practical for running fullnodes.
> It is keeping that array and indexing it which is the problem, i.e. the
> devil in the details.
>
> Reiterating also, current pruned nodes did not retain that data and would
> be forced to re-download the entire blockchain.
> Unless you propose that we can refer only to `OP_PUSHDATA` after
> activation of `OP_PUSHREF`.
>
> Regards,
> ZmnSCPxj
>

--000000000000d2d171058ec887f7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>ZmnSCPxj,</div><div><br></div><div>=C2=A0I think that=
 this implication affects other applications built on the blockchain, not j=
ust the PubRef proposal:</div><div><br></div><div>=C2=A0&gt; There is a pot=
ential for a targeted attack where a large payout going to a `scriptPubKey`=
 that uses `OP_PUBREF` on a recently-confirmed transaction finds that recen=
tly-confirmed transaction is replaced with one that pays to a different pub=
lic key, via a history-rewrite attack.<br>=C2=A0&gt; Such an attack is doab=
le by miners, and if we consider that we accept 100 blocks for miner coinba=
se maturity as &quot;acceptably low risk&quot; against miner shenanigans, t=
hen we might consider that 100 blocks might be acceptable for this also.<br=
>=C2=A0&gt; Whether 100 is too high or not largely depends on your risk app=
etite.<br></div><div><br></div>I agree 100% this attack is unexpected and v=
ery interesting.=C2=A0 However, I find the arbitrary &#39;100&#39; to be un=
satisfying - I&#39;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 a=
nyone has pushed these limits?=C2=A0 I am so taken by this attack I might a=
ttempt it.<div><br></div><div>=C2=A0&gt; Data derived from &gt; 220Gb of pe=
rpetually-growing blockchain is hardly, to my mind, &quot;only needs an arr=
ay&quot;.</div><div><br></div><div>There are other open source projects tha=
t have to deal with larger data sets and have accounted for the real-world =
limits on computability. Apache HTTPD&#39;s Bucket-Brigade comes to mind, w=
hich has been well tested and can account for limited RAM when accessing li=
near data structures. For a more general purpose utility leveldb (bsd-licen=
se) provides random access to arbitrary data collections.=C2=A0 Pruning can=
 also be a real asset for PubRef.=C2=A0 If all transactions for a wallet ha=
ve been pruned, then there is no need to index this PubRef - a validator ca=
n safely skip over it.</div><div><br></div><div>Best Regards,</div><div>Mik=
e</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Sun, Jul 28, 2019 at 6:46 PM ZmnSCPxj &lt;<a href=3D"mailto:ZmnSC=
Pxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; wrote:<br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1p=
x solid rgb(204,204,204);padding-left:1ex">Good morning Mike,<br>
<br>
<br>
Sent with ProtonMail Secure Email.<br>
<br>
=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original Me=
ssage =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90<br>
On Sunday, July 28, 2019 4:03 AM, Mike Brooks &lt;<a href=3D"mailto:m@ib.tc=
" target=3D"_blank">m@ib.tc</a>&gt; wrote:<br>
<br>
&gt; Hey ZmnSCPxj,<br>
&gt;<br>
&gt; As to your first point.=C2=A0 I wasn&#39;t aware there was so much vol=
atility at the tip, also 100 blocks is quite the difference!=C2=A0 I agree =
no one could references a transaction in a newly formed blocks, but I&#39;m=
 curious how this number was chosen. Do you have any documentation or code =
that you can share related to how re-orgs are handled? Do we have a kind of=
 &#39;consensus checkpoint&#39; when a re-org is no longer possible? This i=
s a very interesting topic.<br>
&gt;<br>
<br>
Miner coinbases need 100 blocks for maturity, which is the basis of my sugg=
estion to use 100 blocks.<br>
It might be too high, but I doubt there will be good reason to be less than=
 100.<br>
<br>
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 fi=
nds that recently-confirmed transaction is replaced with one that pays to a=
 different public key, via a history-rewrite attack.<br>
Such an attack is doable by miners, and if we consider that we accept 100 b=
locks for miner coinbase maturity as &quot;acceptably low risk&quot; agains=
t miner shenanigans, then we might consider that 100 blocks might be accept=
able for this also.<br>
Whether 100 is too high or not largely depends on your risk appetite.<br>
<br>
&gt;=C2=A0 A validator only needs an array of PUSHDATA elements and can the=
n validate any given SCRIPT at O(1).=C2=A0=C2=A0<br>
<br>
Data derived from &gt; 220Gb of perpetually-growing blockchain is hardly, t=
o my mind, &quot;only needs an array&quot;.<br>
Such an array would not fit in memory for many devices that today are pract=
ical for running fullnodes.<br>
It is keeping that array and indexing it which is the problem, i.e. the dev=
il in the details.<br>
<br>
Reiterating also, current pruned nodes did not retain that data and would b=
e forced to re-download the entire blockchain.<br>
Unless you propose that we can refer only to `OP_PUSHDATA` after activation=
 of `OP_PUSHREF`.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--000000000000d2d171058ec887f7--