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
|
Return-Path: <rsomsen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 4FCB92B00
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 21 Apr 2019 09:13:17 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f66.google.com (mail-wr1-f66.google.com
[209.85.221.66])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8E4D685B
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 21 Apr 2019 09:13:14 +0000 (UTC)
Received: by mail-wr1-f66.google.com with SMTP id a3so2670269wrx.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 21 Apr 2019 02:13:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc:content-transfer-encoding;
bh=SJJ0NWvCLHtwb0Rlto8tvWjjD32ugYg/01NnKKWDPpo=;
b=tAkePUpbPrJGdiwM5MlepTvZJuzUt4TJZSZ0rFJlZUGgukL/Pig0cL9RprVr9QRmwS
Lx5eyPZd1WFESZOT3Q5YLzSwiKsr8TdLMYV81Y+xqgpcbmbxgNkpHFWFqvH8GZkYwPt5
uUXKlFOLkFjXsoR5nO+DKdnRThas/idFcLmmwxQ1XNx3iwQJiYS3HzGdrEUa8T+SNZnm
k4owJv/7OTqOqvwZACpZiZN3wf+jNz03KfdaEgjrRSErbxyUcBkLH0fq9U6y89tkffjZ
L94P6UajR7Kwvqk6SSr5EjhePGL6AIu7NjEylVh3XGLjWUG9B4dMssDnsCpfZObq0ETF
L0jw==
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:content-transfer-encoding;
bh=SJJ0NWvCLHtwb0Rlto8tvWjjD32ugYg/01NnKKWDPpo=;
b=nUzRivUa0IpaQqYsXHdUcEQ0Jiz/ILp9gdotMVu82R2NgGcYFOAqrUDK12ziCRy5NW
F3rdv9w+bJ1e9XiZhH+CG6mqtMFNrilQJsFGQdypfM28MukKWu642KCWPNyVuXJgurYA
QrHgzI7M83vXtl3WPLNp8MdOpBZPnxH+ye6mX1bDx7nKE6TZTVMP0YApfWgkGlmWPa/v
TQ8pyKa1jUtPpCQJ5rDI/gUvn5nb7SM58vc/phBPy7iqo0Vb+W+7BRs/vrTTsrHdocYO
MaFQrhJk89xoBcGMDTcIg+Y+Nhl1+zyrl5ABsh84Cx+M1edXOsbUMdEdGQUuNHXIzekM
vAIw==
X-Gm-Message-State: APjAAAUjryJ96IbzgT0W+sv3v6+2x+PcqfrxUq/GJVdHkAXBrYhtg8VI
QXGPezMP+bk91p1v1C3GFB0RSlpip5CHjpbFuuY=
X-Google-Smtp-Source: APXvYqx8k4V8Z5MDMfHVjXPppFriJTFuQZWHEx7qmi/BYaAU0CXwm98xxWWrfCwYWLEYFrpb2WHFMz0gqkuwdTPwUbE=
X-Received: by 2002:adf:e407:: with SMTP id g7mr9043814wrm.47.1555837993097;
Sun, 21 Apr 2019 02:13:13 -0700 (PDT)
MIME-Version: 1.0
References: <CAPv7TjYspkc1M=TKmBK8k0Zy857=bR7jSTarRDCr_5m2ktYHDQ@mail.gmail.com>
<xqVUmHu0RXeogboFL8ivsZywPQKEqLCsUZTV1NbsxNB4CYqrNqS8TpYsP8PJSowIGUeq8Nu1XPVd9N9Exg5Is11767ytI0Sq4lVp9MGdII4=@protonmail.com>
<CAEM=y+WVQz5x916sjCjWVmeEbRp4NoTyryxSH7uKNTHYz+Sdnw@mail.gmail.com>
<xNr214GpQ7_9duD4RV0j2nufLLMff4ipqPcZEAsDIsjLwWDan9UijTADW0iJ76pUuaXgYth_BHla-p6G3SOksaySbDZXKhQPLvIfLqo0JeA=@protonmail.com>
<CAEM=y+V0tMYBBLJhePfGUzyFNXVe9hr0F3QrX9JYFrDg5N1qXg@mail.gmail.com>
<SHsLdVIPZcn9yyZN9Hx3moQmWXY-2yC99tEsFllksV-66ZrJNMQfDr0qHK_rCZuBcEa8gIcnThkvgRDkU6BYQ_mxX7JxfI_uM6ndOF26ofk=@protonmail.com>
<CAPv7TjYeuCA1WDHgEpkN1K8=NM88fw43HJeP5TeRE7q0Q+Chzg@mail.gmail.com>
<EWP8Pzp8wS_Nh145H_g4w3yJaelXmm6UB12sa8MC2EsMbYFhm53C_kaOvjztksQpCNBBT0D0zuTbKHnEfEatlLKIa3whMlLZrihawZux1UY=@protonmail.com>
<CAPv7TjbbYkXf62ApadMgOLef-Z9xTU1HQy_f+L3vNVUfRhChrw@mail.gmail.com>
<IbAS3IZpoD0wJKQvVekHDjHJL0R97CSGKwyy3ScU5yl2NIDSqBsmUJqvU_M7b0MRRu2u9aQXaof0zTs1OC562vkYu8LzV7vSDM6Pj5j55yI=@protonmail.com>
In-Reply-To: <IbAS3IZpoD0wJKQvVekHDjHJL0R97CSGKwyy3ScU5yl2NIDSqBsmUJqvU_M7b0MRRu2u9aQXaof0zTs1OC562vkYu8LzV7vSDM6Pj5j55yI=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sun, 21 Apr 2019 11:13:00 +0200
Message-ID: <CAPv7TjbFqJHL+OajCKMNkd=wYhO49g=s2qCjEOROygMTj7DLqQ@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
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, 22 Apr 2019 13:33:20 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs
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: Sun, 21 Apr 2019 09:13:17 -0000
Hi ZmnSCPxj,
Allow me to reply to your post in mixed order (fraud proofs first):
>But peers can be set up to allow you to hear of all chains while denying y=
ou proof of the invalidity of some UTXO.
I don't believe this is fundamentally different. In either scenario
you end up on the wrong chain if all your peers are lying to you. One
happens by omission of a fraud proof, while the other happens by
omission of a valid longest chain.
>This is precisely the "data unavailability claim" that shot down the previ=
ous fraud proofs
The "data unavailability" issue I was referring to, and which I
believe is the reason why fraud proofs were abandoned, is the
following:
- Alice downloads a block with her full node, but the block is
incomplete (e.g. a transaction is missing).
- Alice reports this to Bob's SPV fraud proof client, who verifies
this by requesting the transaction from the network.
- If Bob can't download it, he rejects the block.
- If Bob can download it, either Alice was malicious, or a miner was
temporarily withholding the data.
- Since Bob can't be certain Alice was being malicious, Bob can't ban
her, which results in a DoS vector where SPV fraud proof clients can
be forced to download all blocks.
We circumvent the data unavailability problem here completely, since
we are only questioning the validity of blocks which are involved in a
fork (expensive and/or rare), and we are simply always downloading
them in full.
If my arguments above hold up, we can use fraud proof commitments as
described in segwit BIP141 [0] instead of UTXO set commitments, which
seems like the more elegant way to achieve the desired outcome.
>Perhaps in combination with BIP157/158 it may be possible, if the filters =
contain UTXO spends and a BIP158 filter was committed to on-chain. Then a p=
roof of absence could be done by revealing all the BIP158 filters from the =
UTXO creation to the block being validated, as well as the blocks whose BIP=
158 filters matched the UTXO and revealing that no, they actually do not sp=
end the UTXO.
Yes, I mentioned something similar to Laolu, but it does seem
computationally expensive to run every input in a block through the
filter of every past block. The fact that BIP157/158 can function
without commitments is also why I suspected we may not necessarily
need UTXO set commitments.
>UTXO sets can only be validated by actually running the entire blockchain,=
i.e. fullnoding.
It seems to me you can validate uncommitted UTXO sets by comparing
them. Download and compare UTXO set hashes from multiple peers. If
they disagree on a certain block, download that block and the relevant
merkle path(s) from the previous block's UTXO set, and then verify who
is right. Ban the peer who lied. Note that unlike fraud proofs, it is
not possible to lie by omission, but it does assume one of your peers
is honest. Of course this does nothing to dispute your earlier point
that this may not be all that efficient (e.g. full nodes keeping
merkle paths of all prior states).
>What BIP157 does is summarize data that is within a block, thus validating=
them can be done simply by downloading the block in question.
>UTXO sets summarize data in the entire blockchain, hence proper validation=
requires downloading the entire blockchain.
Thus it cannot be a comparison point.
It's still possible to lie by omission. Let's say a miner spends some
coins in block N, and spends the exact same coins again in block N+1,
making block N+1 invalid. If the filter for block N is maliciously
constructed, you won't notice the spend in block N, causing you to
think block N+1 is valid. In short, you're still relying on one of
your peers to give you a correct filter. If all your peers lie, you
can always be deceived.
>Tangentially, we cannot just magically commit to anything on the blockchai=
n. [...] if you are adding new information to be committed, that may increa=
se the resource usage of fullnodes. [...] This is probably still better tha=
n BIP37 but we should still be aware the additional load on fullnodes.
I agree with all this.
To summarize, this is my current understanding of our options for
enabling light clients to verify a single block in isolation:
1. UTXO set commitments (complex, more resource usage to full nodes)
2. BIP157/158 commitments (expensive for clients to check all filters
to get exclusion proofs)
3. BIP141 fraud proof commitments (assumes fraud proofs will be passed
on to the SPV client)
The debate is still open on whether the options above can be done
without actually committing them into blocks via a soft fork. My
current hunch is "yes" for 1 and 2, and "no" for 3, which would be
unfortunate, because 3 currently seems to me like the more elegant
solution.
-- Ruben Somsen
[0] https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Compact_=
fraud_proof_for_SPV_nodes
>UTXO sets can only be validated by actually running the entire blockchain,=
i.e. fullnoding.
>What BIP157 does is summarize data that is within a block, thus validating=
them can be done simply by downloading the block in question.
UTXO sets summarize data in the entire blockchain, hence proper
validation requires downloading the entire blockchain.
Thus it cannot be a comparison point.
> > This makes no sense
> > or you trust that every peer you have is not omitting the proof.
>
> It's the latter, you trust every peer you have is not omitting the
> proof. It requires one honest peer. The reason this is acceptable is
> because you're already making that assumption. If none of your peers
> are honest, you have no guarantee of hearing about the chain with the
> most PoW.
But peers can be set up to allow you to hear of all chains while
denying you proof of the invalidity of some UTXO.
This is precisely the "data unavailability claim" that shot down the
previous fraud proofs (i.e. absence of proof is not proof of absence,
and proof of UTXO validity was defined by proof of absence of any
intervening spend of the UTXO).
Perhaps in combination with BIP157/158 it may be possible, if the
filters contain UTXO spends and a BIP158 filter was committed to
on-chain.
Then a proof of absence could be done by revealing all the BIP158
filters from the UTXO creation to the block being validated, as well
as the blocks whose BIP158 filters matched the UTXO and revealing that
no, they actually do not spend the UTXO.
--
Tangentially, we cannot just magically commit to anything on the blockchain=
.
Header blocks commit to block data and commit to some other header block.
All those header blocks and the block data need to be stored and
transmitted over the network somehow, even though they are "only"
being committed to.
Thus, if you are adding new information to be committed, that may
increase the resource usage of fullnodes.
So if UTXO set commitments, or utreexo commitments, or BIP158 filter
digests, etc. are committed to in the coinbase, they have to be stored
somehow in fullnodes the entire UUTXO set, or the actual utreexo
structure, or the actual BIP158 filter, etc. at each block.
Otherwise it would be pointless to store those commitments since it
would not be possible to somehow acquire the data being committed to
after-the-fact.
This is probably still better than BIP37 but we should still be aware
the additional load on fullnodes.
Regards,
ZmnSCPxj
On Sat, Apr 20, 2019 at 6:45 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ruben,
>
> > Hi ZmnSCPxj,
> >
> > > There is no safe way to use UTXO sets without identifying who is tell=
ing you those sets are valid, or making it expensive to lie
> > > The first option requires trust and is weaker than SPV, the second re=
quires committing to a proof-of-work
> >
> > Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
> > "If the client receives conflicting filter headers from different
> > peers for any block and filter type, it SHOULD interrogate them to
> > determine which is faulty."
> >
> > I am wondering if the same logic can be applied to UTXO sets or the
> > fraud proofs I just described.
>
> UTXO sets can only be validated by actually running the entire blockchain=
, i.e. fullnoding.
>
> What BIP157 does is summarize data that is within a block, thus validatin=
g them can be done simply by downloading the block in question.
>
> UTXO sets summarize data in the entire blockchain, hence proper validatio=
n requires downloading the entire blockchain.
> Thus it cannot be a comparison point.
>
>
> > > This makes no sense
> > > or you trust that every peer you have is not omitting the proof.
> >
> > It's the latter, you trust every peer you have is not omitting the
> > proof. It requires one honest peer. The reason this is acceptable is
> > because you're already making that assumption. If none of your peers
> > are honest, you have no guarantee of hearing about the chain with the
> > most PoW.
>
> But peers can be set up to allow you to hear of all chains while denying =
you proof of the invalidity of some UTXO.
> This is precisely the "data unavailability claim" that shot down the prev=
ious fraud proofs (i.e. absence of proof is not proof of absence, and proof=
of UTXO validity was defined by proof of absence of any intervening spend =
of the UTXO).
>
> Perhaps in combination with BIP157/158 it may be possible, if the filters=
contain UTXO spends and a BIP158 filter was committed to on-chain.
> Then a proof of absence could be done by revealing all the BIP158 filters=
from the UTXO creation to the block being validated, as well as the blocks=
whose BIP158 filters matched the UTXO and revealing that no, they actually=
do not spend the UTXO.
>
> --
>
> Tangentially, we cannot just magically commit to anything on the blockcha=
in.
> Header blocks commit to block data and commit to some other header block.
> All those header blocks and the block data need to be stored and transmit=
ted over the network somehow, even though they are "only" being committed t=
o.
> Thus, if you are adding new information to be committed, that may increas=
e the resource usage of fullnodes.
>
> So if UTXO set commitments, or utreexo commitments, or BIP158 filter dige=
sts, etc. are committed to in the coinbase, they have to be stored somehow =
in fullnodes the entire UUTXO set, or the actual utreexo structure, or the =
actual BIP158 filter, etc. at each block.
> Otherwise it would be pointless to store those commitments since it would=
not be possible to somehow acquire the data being committed to after-the-f=
act.
>
> This is probably still better than BIP37 but we should still be aware the=
additional load on fullnodes.
>
> Regards,
> ZmnSCPxj
|