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
|
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 B599027F3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 20 Apr 2019 03:26:18 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f68.google.com (mail-wr1-f68.google.com
[209.85.221.68])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CF52079
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 20 Apr 2019 03:26:17 +0000 (UTC)
Received: by mail-wr1-f68.google.com with SMTP id w10so8895670wrm.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 19 Apr 2019 20:26:17 -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=BHf2UcZsLOCZF9Ctu2Xzi+qQTSNrjIswNeAd/O9gAVw=;
b=tHKIYnPrF9aM9zLDLEM38W69ugm1TA51j87BaVcGwXRItUsiOTJM2x0uy2bhoBeIQ/
UZQyAHuV9w3Q7d342z4+Hrt7TvMCLJgaQcugRxa6lI+Q3jSR6Euzhtnp3cp6VrDvnYFY
6sp8Zb1mvETxd1tY+rS95y0zEDrCSnK4JctoW5As32sG35eKKmMzr6UmLLZCTeZ5JWCh
H3uxSeNrexPc5QwuezGRRamD9+IdGSDHdbzcDlSrUkgbGImMYXjuJ0nn3vnHfXDpIs00
6GCDVvmMUqC1DjjDhbZOWx9n+bb4SisDZJTweRri4c3jhi+mJfJkH6599NmF0mEfEqMf
dVSQ==
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=BHf2UcZsLOCZF9Ctu2Xzi+qQTSNrjIswNeAd/O9gAVw=;
b=XzLpjHBjxMxJbMDcm02GFDsRaVY3wQ96Mc7Il2JXxaqu7+OTtCy3075VaiUq/u75hV
k//3V/roK0V46nuciW9CBgTfpKvXtExONCJ/i5ak0d5LOZOHC7iYdGPJZaNeqovDEyJ4
+sIMyBZ6X39UL0FgfWKDdxlYleRtc5r7oOasPBHBsC/GDX+u+2BEVtjdO/l5RI3cDUcZ
wMi4XS4tzfRsakAHIRmnsSh2cBB3BKIMGJL9mpmxoWwIs10WKVNWqa75tX9nVzb9JDK6
cPEvRzjyyfyXyC2dILSldxpSXlLYOJ6tNcJAuhDFjuW+ufScY2CVT6GTVB70f9skn4YZ
B95g==
X-Gm-Message-State: APjAAAVMKm03fQ3WM6speiG7qYorAL92JjBywB/txcw96FQsNadF5VoW
VsCoIBWFlC6KaPPbBuSqmSJJoGPHYrxfSX+uDs2PG+o678g=
X-Google-Smtp-Source: APXvYqztJtgKVw0wsyvo3hPZWpDqw0xXKTIrODgg+CtMK7FzHlhgsnKzG70BuHURxm0GiWzvmJ6GxCLb/JgcoYs9AfA=
X-Received: by 2002:adf:df0f:: with SMTP id y15mr5433967wrl.175.1555730776305;
Fri, 19 Apr 2019 20:26:16 -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>
<CAPv7TjYeuCA1WDHgEpkN1K8=NM88fw43HJeP5TeRE7q0Q+Chzg@mail.gmail.com>
<EWP8Pzp8wS_Nh145H_g4w3yJaelXmm6UB12sa8MC2EsMbYFhm53C_kaOvjztksQpCNBBT0D0zuTbKHnEfEatlLKIa3whMlLZrihawZux1UY=@protonmail.com>
In-Reply-To: <EWP8Pzp8wS_Nh145H_g4w3yJaelXmm6UB12sa8MC2EsMbYFhm53C_kaOvjztksQpCNBBT0D0zuTbKHnEfEatlLKIa3whMlLZrihawZux1UY=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sat, 20 Apr 2019 05:26:03 +0200
Message-ID: <CAPv7TjbbYkXf62ApadMgOLef-Z9xTU1HQy_f+L3vNVUfRhChrw@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: Sat, 20 Apr 2019 14:21:03 +0000
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: Sat, 20 Apr 2019 03:26:18 -0000
Hi ZmnSCPxj,
>There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie
>The first option requires trust and is weaker than SPV, the second requires 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.
>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.
Again, this is not a new observation. I am just recalling the fraud
proof debate from when it was being considered for segwit (though of
course it's possible I got some details wrong).
-- Ruben Somsen
On Sat, Apr 20, 2019 at 3:59 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning,
>
>
> > > 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.
>
> There is no safe way to use UTXO sets without identifying who is telling you those sets are valid, or making it expensive to lie.
> The first option requires trust and is weaker than SPV, the second requires committing to a proof-of-work (and probably best to fold it into the Bitcoin blockchain if so).
>
> You would get the UTXO commitment from the previous block (if the UTXO commitment is in the coinbase, then all you need is the Merkle proof of the coinbase).
>
>
> >
> > > 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.
>
> This makes no sense.
> In order to validate block N, you need to know that every UTXO spent by a transaction in block N is valid.
> The UTXO you want to validate is located in some other block, not on the single block you are verifying.
>
> Thus the non-existent fraud proof can only be validated by loading the block of the UTXO purported to be spent, and every block between that and the current block you are verifying, i.e. fullnode.
> Either that or you trust that every peer you have is not omitting the proof.
>
> Regards,
> ZmnSCPxj
|
