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
|
Return-Path: <lf-lists@mattcorallo.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 3A896B63
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 22 Mar 2017 21:51:15 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail.bluematt.me (mail.bluematt.me [192.241.179.72])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7371F124
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 22 Mar 2017 21:51:14 +0000 (UTC)
Received: from [100.69.147.137] (unknown [172.56.16.130])
by mail.bluematt.me (Postfix) with ESMTPSA id 6AF571399F8;
Wed, 22 Mar 2017 21:51:12 +0000 (UTC)
Date: Wed, 22 Mar 2017 21:51:08 +0000
In-Reply-To: <CA+KqGkqD0z1O6+pCNaB-vCu_YW2-eO9nmrwcnQ--574t95hghg@mail.gmail.com>
References: <201703220847.31303.luke@dashjr.org>
<CA+KqGkqD0z1O6+pCNaB-vCu_YW2-eO9nmrwcnQ--574t95hghg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ"
Content-Transfer-Encoding: 7bit
To: Bram Cohen <bram@bittorrent.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
Bram Cohen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>,
Luke Dashjr <luke@dashjr.org>
From: Matt Corallo <lf-lists@mattcorallo.com>
Message-ID: <30FB8B13-135D-4905-B1B4-76D79341CA02@mattcorallo.com>
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Fraud proofs for block size/weight
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: Wed, 22 Mar 2017 21:51:15 -0000
------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ
Content-Type: text/plain;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
It works today and can be used to prove exact size: the key observation is =
that all you need to show the length and hash of a transaction is the final=
SHA256 midstate and chunk (max 64 bytes)=2E It also uses the observation t=
hat a valid transaction must be at least 60 bytes long for compression (tho=
ugh much of that compression possibility goes away if you're proving someth=
ing other than "too large")=2E
On March 22, 2017 1:49:08 PM PDT, Bram Cohen via bitcoin-dev <bitcoin-dev@=
lists=2Elinuxfoundation=2Eorg> wrote:
>Some questions:
>
>Does this require information to be added to blocks, or can it work
>today
>on the existing format?
>
>Does this count number of transactions or their total length? The block
>limit is in bytes rather than number of transactions, but transaction
>number can be a reasonable proxy if you allow for some false negatives
>but
>want a basic sanity check=2E
>
>Does this allow for proofs of length in the positive direction,
>demonstrating that a block is good, or does it only serve to show that
>blocks are bad? Ideally we'd like an extension to SPV protocol so light
>clients require proofs of blocks not being too big, given the credible
>threat of there being an extremely large-scale attack on the network of
>that form=2E
>
>
>On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev <
>bitcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote:
>
>> Despite the generalised case of fraud proofs being likely impossible,
>there
>> have recently been regular active proposals of miners attacking with
>simply
>> oversized blocks in an attempt to force a hardfork=2E This specific
>attack
>> can
>> be proven, and reliably so, since the proof cannot be broken without
>also
>> breaking their attempted hardfork at the same time=2E
>>
>> While ideally all users ought to use their own full node for
>validation
>> (even
>> when using a light client for their wallet), many bitcoin holders
>still do
>> not=2E As such, they are likely to need protection from these attacks,
>to
>> ensure
>> they remain on the Bitcoin blockchain=2E
>>
>> I've written up a draft BIP for fraud proofs and how light clients
>can
>> detect
>> blockchains that are simply invalid due to excess size and/or weight:
>>
>> =20
>https://github=2Ecom/luke-jr/bips/blob/bip-sizefp/bip-sizefp=2Emediawiki
>>
>> I believe this draft is probably ready for implementation already,
>but if
>> anyone has any idea on how it might first be improved, please feel
>free to
>> make suggestions=2E
>>
>> Luke
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists=2Elinuxfoundation=2Eorg
>> https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev
>>
------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ
Content-Type: text/html;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
<html><head></head><body>It works today and can be used to prove exact size=
: the key observation is that all you need to show the length and hash of a=
transaction is the final SHA256 midstate and chunk (max 64 bytes)=2E It al=
so uses the observation that a valid transaction must be at least 60 bytes =
long for compression (though much of that compression possibility goes away=
if you're proving something other than "too large")=2E<br><b=
r><div class=3D"gmail_quote">On March 22, 2017 1:49:08 PM PDT, Bram Cohen v=
ia bitcoin-dev <bitcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote:<blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0=2E8ex; border-=
left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div dir=3D"ltr">Some questions:<div><br /></div><div>Does this require in=
formation to be added to blocks, or can it work today on the existing forma=
t?</div><div><br /></div><div>Does this count number of transactions or the=
ir total length? The block limit is in bytes rather than number of transact=
ions, but transaction number can be a reasonable proxy if you allow for som=
e false negatives but want a basic sanity check=2E</div><div><br /></div><d=
iv>Does this allow for proofs of length in the positive direction, demonstr=
ating that a block is good, or does it only serve to show that blocks are b=
ad? Ideally we'd like an extension to SPV protocol so light clients require=
proofs of blocks not being too big, given the credible threat of there bei=
ng an extremely large-scale attack on the network of that form=2E</div><div=
><br /></div></div><div class=3D"gmail_extra"><br /><div class=3D"gmail_quo=
te">On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev <span dir=
=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists=2Elinuxfoundation=2Eorg" t=
arget=3D"_blank">bitcoin-dev@lists=2Elinuxfoundation=2Eorg</a>></span> w=
rote:<br /><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 =2E8ex;b=
order-left:1px #ccc solid;padding-left:1ex">Despite the generalised case of=
fraud proofs being likely impossible, there<br />
have recently been regular active proposals of miners attacking with simpl=
y<br />
oversized blocks in an attempt to force a hardfork=2E This specific attack=
can<br />
be proven, and reliably so, since the proof cannot be broken without also<=
br />
breaking their attempted hardfork at the same time=2E<br />
<br />
While ideally all users ought to use their own full node for validation (e=
ven<br />
when using a light client for their wallet), many bitcoin holders still do=
<br />
not=2E As such, they are likely to need protection from these attacks, to =
ensure<br />
they remain on the Bitcoin blockchain=2E<br />
<br />
I've written up a draft BIP for fraud proofs and how light clients can det=
ect<br />
blockchains that are simply invalid due to excess size and/or weight:<br /=
>
<br />
<a href=3D"https://github=2Ecom/luke-jr/bips/blob/bip-sizefp=
/bip-sizefp=2Emediawiki" rel=3D"noreferrer" target=3D"_blank">https://githu=
b=2Ecom/luke-jr/<wbr />bips/blob/bip-sizefp/bip-<wbr />sizefp=2Emediawiki</=
a><br />
<br />
I believe this draft is probably ready for implementation already, but if<=
br />
anyone has any idea on how it might first be improved, please feel free to=
<br />
make suggestions=2E<br />
<br />
Luke<br />
______________________________<wbr />_________________<br />
bitcoin-dev mailing list<br />
<a href=3D"mailto:bitcoin-dev@lists=2Elinuxfoundation=2Eorg">bitcoin-dev@l=
ists=2E<wbr />linuxfoundation=2Eorg</a><br />
<a href=3D"https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists=2Elinuxfoundation=
=2E<wbr />org/mailman/listinfo/bitcoin-<wbr />dev</a><br />
</blockquote></div><br /></div>
</blockquote></div></body></html>
------WMB90IH5HHH2R7QIVJ4S753EOBQ0KJ--
|
