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
|
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 0D0272348
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 19 Apr 2019 13:24:08 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm1-f68.google.com (mail-wm1-f68.google.com
[209.85.128.68])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 389FC14D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 19 Apr 2019 13:24:07 +0000 (UTC)
Received: by mail-wm1-f68.google.com with SMTP id a184so6228110wma.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 19 Apr 2019 06:24:07 -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; bh=eQa4eSATGZdb4StNCZA18HOJZZH6vSOdV4hZwbnDWsw=;
b=O4Ucdsnly0rZ1d22sDyyP/IyLdiIFFPsAAwAEtUZXaI1eWYLfTJVGLyuBQ2LS+qD6a
aShtn55uUnvaeoChuaeRktIKtYk2/F6ZWmh/FvyGuMqTZIsV+psH98W9zomEesX/rheC
eKsYFVQfRN6VEC6H/lX4l7+FLzowrShbPXv5IlermvMd7+IOX+pdc8N9Ab5XBMOeydSW
X4wdEW4TkLarHwLlVlIz5SM7STsGvqofGZohKw+WjGRYZUngbGrz/wQrpx+sljYa4LwT
mm2i4aDhQNMbZAIb0zmSdnXw0x0pcnmrkJbanRoCwIP0S/PGmvzaZKTK7N4kF+IXZ60G
L5FA==
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=eQa4eSATGZdb4StNCZA18HOJZZH6vSOdV4hZwbnDWsw=;
b=N2zM/PJRfCIj3CMUkp+X6vUAyPkrmto6JjwZ+ojVZDvIEyLHsnjriE+Kg+DXevPz2U
0U9jODVmFZw40ZoU//8RODvSkP68ieVhSXqypn3aG35JrzdAUz+sj7BMbNoxubCeQW4s
DC/DbL+h7aTYiDoQBztkp4tiPkbnUYh/LS6AKxSJfvz/iUjBlY9Oz42AO9KbzQ2OuP6Y
yrL60NybvlrnnM8kW31g10pReTs5Ao0BsdHzKVQO5Sj1W9yvZzaweOGBmR5dfe5iXma5
RJrt2SqwSHQ2fi0B41ftmG2jbykXCmfMJocBVaFDzfLc5rW2OvZ/ydtR5bY2aSClpidL
3dkw==
X-Gm-Message-State: APjAAAVJ/sTCklEpWW44borsWQ1cTrk05Jd/zdxAIrJhcvDKpfVGCgCS
EGQr3IroVpyzd/1usYX5CAXKm7Ompf/4TvMK+Z88+Pbk
X-Google-Smtp-Source: APXvYqwEkXDfwAIUxzEUgdeU2HWO9rsOKTA8z+uY43Ya9DjK4+i/Ke750a4aMCLn5k1WJnN15ji+cVo7ThCD181EQE8=
X-Received: by 2002:a1c:415:: with SMTP id 21mr2806821wme.109.1555680245504;
Fri, 19 Apr 2019 06:24:05 -0700 (PDT)
MIME-Version: 1.0
References: <CAPv7TjYspkc1M=TKmBK8k0Zy857=bR7jSTarRDCr_5m2ktYHDQ@mail.gmail.com>
<-tCD0qh97dAiz-VGkDQTwSbSQIm9cLF1kOzaWCnUDTI4dKdsmMgHJsGDntQhABZdE2_yBYpPAAdulm8EpdNxOB8o3lI6ZQJBJZWF1INzUrE=@protonmail.com>
<CAEM=y+W==_+AW6ga9WMf=aAX-xPGUfhEJQFvUtdFodGGv-6eAg@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>
In-Reply-To: <SHsLdVIPZcn9yyZN9Hx3moQmWXY-2yC99tEsFllksV-66ZrJNMQfDr0qHK_rCZuBcEa8gIcnThkvgRDkU6BYQ_mxX7JxfI_uM6ndOF26ofk=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Fri, 19 Apr 2019 15:23:50 +0200
Message-ID: <CAPv7TjYeuCA1WDHgEpkN1K8=NM88fw43HJeP5TeRE7q0Q+Chzg@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
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: Fri, 19 Apr 2019 13:57:18 +0000
Cc: tdryja@media.mit.edu
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: Fri, 19 Apr 2019 13:24:08 -0000
Hi ZmnSCPxj and Ethan,
I apologize if my initial explanation was confusing, but it looks like
you figured it out. For every fork, SPV clients only have to download
one block. If there is a fork after block N, this means there are two
blocks at N+1. You only download and verify N+1 from the longer chain.
>Mining a block which will never be accepted is an expensive way to make SPV clients download validate and discard ~2-4 megabytes of data
Absolutely, hence the name "PoW fraud proof". It gets naturally
created by honest miners and is prohibitively expensive to forge.
>SPV clients may not even learn about these splits because it requires that someone relay the split to them. Honest full nodes should not relay such splits.
You could perform a fully valid repeated 1-block reorg from the top of
the chain. So at least theoretically you could get an honest network
to relay every split.
>Having SPV clients slow down or become full nodes when a malicious miner with significant mining power is attempting to disrupt the network is probably a best case outcome.
That is an excellent point.
>As I understand it, this requires that UTXO commitments be mandatory.
Perhaps UTXO sets can be made useful without committing them. I have
some very loose thoughts on the subject, I consider it an open
question.
> More difficult is: how can an SPV node acquire the UTXO set at a particular block?
I think you are asking fair questions about how the UTXO set
commitments would work in practice, and how viable that makes it. I'm
not sure. The most comprehensive work I have seen on this topic has
been the utreexo proposal by Tadge Dryja:
https://www.youtube.com/watch?v=edRun-6ubCc
Actually, now that I think about it... As an alternative to UTXO set
commitments, the old fraud proofs idea for segwit can be applied here.
We get miners to commit to the location of the UTXOs that are being
spent (e.g. transaction 5 in block 12). This allows full nodes to
succinctly prove invalidity to SPV clients in the following ways:
- a committed location does not contain the stated UTXO
- the UTXO has already been spent in a prior block
If no fraud proofs are given, then the inputs can be assumed to be valid.
As you may recall, these kinds of fraud proofs were abandoned mainly
because the data unavailability claim could only be verified by
downloading the data, resulting in a DoS vector where all blocks had
to be downloaded. This problem does not seem to apply here, because we
are only interested in blocks which have forks, so it's more doable to
download them.
-- Ruben Somsen
On Fri, Apr 19, 2019 at 6:48 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
> > My above email contains an error. The SPV client needs to only
> > download S+1, not S+1 and S+2.
> >
> > I agree with you that a weakness of this approach is a miner can make
> > SPV clients do substantially more work. However:
> >
> > 1. Mining a block which will never be accepted is an expensive way to
> > make SPV clients download, validate and discard ~2-4 megabytes of
> > data. There are far less expensive ways of wasting the resources of
> > SPV clients. Its unclear why someone would want to do this instead of
> > just packeting full nodes or SPV servers like we saw with the recent
> > DDoS attacks against electrum servers.
> >
> > 2. SPV clients may not even learn about these splits because it
> > requires that someone relay the split to them. Honest full nodes
> > should not relay such splits. To their bitcoin's worth the attacker
> > must also connect to lots of SPV clients.
> >
> > 3. Having SPV clients slow down or become full nodes when a malicious
> > miner with significant mining power is attempting to disrupt the
> > network is probably a best case outcome. I would prefer this failure
> > mode to the current SPV behavior which is to just go with the
> > "longest" chain.
>
>
> I understand.
> It seems a reasonable point to do so.
>
> As I understand it, this requires that UTXO commitments be mandatory.
> In particular, if UTXO commitments were not mandatory, it would be trivial to force chainsplits at heights where a UTXO commitment was not made, and force an SPV node to download more blocks backwards until a block with a UTXO commitment is found.
>
> More difficult is: how can an SPV node acquire the UTXO set at a particular block?
> Fullnodes automatically update their UTXO set at each block they accept as tip.
> Reversing the blocks to update the UTXO set at a particular past time would require a good amount of CPU and memory.
> Thus any service that can provide the actual UTXO set at each block would potentially be attackable by simply requesting enough past blocks.
>
>
> Regards,
> ZmnSCPxj
|
