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
|
Return-Path: <gavinandresen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D1D7A9F0
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 9 Dec 2015 01:09:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f175.google.com (mail-lb0-f175.google.com
[209.85.217.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 52B83106
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 9 Dec 2015 01:09:18 +0000 (UTC)
Received: by lbblt2 with SMTP id lt2so21165010lbb.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 08 Dec 2015 17:09:16 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
bh=2NwQhr0WpECBDv4+61CttmjUbca7k+awSzCWeOapQoE=;
b=lSWhKOmkWSevkvH2TRP0oLrCWd15WFKR65tIZO0W27nVjn8MkAiU4wDwW7ADdGN3uG
f1ZPc8yxhhqLInDhX0cqqBa6m77rVrm4MIz4W9oJCu3bK7WNx5wC850ri2/Uq9XjjjIk
cm/4n5M8WI6i4HD1Vr9ewPdLBSc/uVIqNyFFxDp+I8/SY77QQih9Qe/qGKCBL3ClF2Il
o0eGfdYlefUGG9HJIKbjKjzx2YiXeJ5AHXLJtAZ07O8wKl+0WxYkP4PQXpf9lUAn7dIJ
nhtxM/8pqo5xLcycX+H7QMyY8C3RUJtNnDcrRbZ1jtqCzt6Ftp7MulWj9wv6cXtZEWWC
VM6A==
MIME-Version: 1.0
X-Received: by 10.112.63.100 with SMTP id f4mr1177185lbs.85.1449623356599;
Tue, 08 Dec 2015 17:09:16 -0800 (PST)
Received: by 10.25.22.95 with HTTP; Tue, 8 Dec 2015 17:09:16 -0800 (PST)
In-Reply-To: <CAAS2fgTGYSiAJHZq80rD4UieV8XetS=W0b45b5onWAS9gF-F7g@mail.gmail.com>
References: <CAAS2fgQyVs1fAEj+vqp8E2=FRnqsgs7VUKqALNBHNxRMDsHdVg@mail.gmail.com>
<20151208110752.GA31180@amethyst.visucore.com>
<CABm2gDpcek=u=Rpe68EMOq6M7Bji9J=s5VvoQWKRqaQDAP5kTw@mail.gmail.com>
<CABsx9T1wga3Tandoe2mVGSKdHJytHoc9Ko7HRm2SvJXABEFk9w@mail.gmail.com>
<CAAS2fgTGYSiAJHZq80rD4UieV8XetS=W0b45b5onWAS9gF-F7g@mail.gmail.com>
Date: Tue, 8 Dec 2015 20:09:16 -0500
Message-ID: <CABsx9T1i50Gvxj18W=n2mYGNpsMrSkDT26CdA3aQqT5FFN86yw@mail.gmail.com>
From: Gavin Andresen <gavinandresen@gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary=001a11c3fe803a789f05266cbd9b
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Capacity increases for the Bitcoin system.
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 09 Dec 2015 01:09:22 -0000
--001a11c3fe803a789f05266cbd9b
Content-Type: text/plain; charset=UTF-8
On Tue, Dec 8, 2015 at 6:59 PM, Gregory Maxwell <greg@xiph.org> wrote:
> > We also need to fix the O(n^2) sighash problem as an additional BIP for
> ANY
> > blocksize increase.
>
> The witness data is never an input to sighash, so no, I don't agree
> that this holds for "any" increase.
>
Here's the attack:
Create a 1-megabyte transaction, with all of it's inputs spending
segwitness-spending SIGHASH_ALL inputs.
Because the segwitness inputs are smaller in the block, you can fit more of
them into 1 megabyte. Each will hash very close to one megabyte of data.
That will be O(n^2) worse than the worst case of a 1-megabyte transaction
with signatures in the scriptSigs.
Did I misunderstand something or miss something about the 1-mb transaction
data and 3-mb segwitness data proposal that would make this attack not
possible?
RE: fraud proof data being deterministic: yes, I see, the data can be
computed instead of broadcast with the block.
RE: emerging consensus of Core:
I think it is a huge mistake not to "design for success" (see
http://gavinandresen.ninja/designing-for-success ).
I think it is a huge mistake to pile on technical debt in
consensus-critical code. I think we should be working harder to make things
simpler, not more complex, whenever possible.
And I think there are pretty big self-inflicted current problems because
worries about theoretical future problems have prevented us from coming to
consensus on simple solutions.
--
--
Gavin Andresen
--001a11c3fe803a789f05266cbd9b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Dec 8, 2015 at 6:59 PM, Gregory Maxwell <span dir=3D"ltr"><<a hr=
ef=3D"mailto:greg@xiph.org" target=3D"_blank">greg@xiph.org</a>></span> =
wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8=
ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-sty=
le:solid;padding-left:1ex"><span class=3D"im">> We also need to fix the =
O(n^2) sighash problem as an additional BIP for ANY<br>
> blocksize increase.<br>
<br>
</span><span class=3D"im">The witness data is never an input to sighash, so=
no, I don't agree<br>
that this holds for "any" increase.<br></span></blockquote></div>=
<br>Here's the attack:</div><div class=3D"gmail_extra"><br></div><div c=
lass=3D"gmail_extra">Create a 1-megabyte transaction, with all of it's =
inputs spending segwitness-spending SIGHASH_ALL inputs.</div><div class=3D"=
gmail_extra"><br></div><div class=3D"gmail_extra">Because the segwitness in=
puts are smaller in the block, you can fit more of them into 1 megabyte. Ea=
ch will hash very close to one megabyte of data.</div><div class=3D"gmail_e=
xtra"><br></div><div class=3D"gmail_extra">That will be O(n^2) worse than t=
he worst case of a 1-megabyte transaction with signatures in the scriptSigs=
.<br><br>Did I misunderstand something or miss something about the 1-mb tra=
nsaction data and 3-mb segwitness data proposal that would make this attack=
not possible?</div><div class=3D"gmail_extra"><br></div><div class=3D"gmai=
l_extra">RE: fraud proof data being deterministic: =C2=A0yes, I see, the da=
ta can be computed instead of broadcast with the block.</div><div class=3D"=
gmail_extra"><br></div><div class=3D"gmail_extra">RE: emerging consensus of=
Core:</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra"=
>I think it is a huge mistake not to "design for success" (see=C2=
=A0<a href=3D"http://gavinandresen.ninja/designing-for-success">http://gavi=
nandresen.ninja/designing-for-success</a> ).</div><div class=3D"gmail_extra=
"><br></div><div class=3D"gmail_extra">I think it is a huge mistake to pile=
on technical debt in consensus-critical code. I think we should be working=
harder to make things simpler, not more complex, whenever possible.<br></d=
iv><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">And I th=
ink there are pretty big self-inflicted current problems because worries ab=
out theoretical future problems have prevented us from coming to consensus =
on simple solutions.</div><div class=3D"gmail_extra"><div><br></div>-- <br>=
<div class=3D"gmail_signature">--<br>Gavin Andresen<br></div>
</div></div>
--001a11c3fe803a789f05266cbd9b--
|
