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
|
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 2E143475
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Jul 2015 15:41:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f173.google.com (mail-lb0-f173.google.com
[209.85.217.173])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DB955290
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Jul 2015 15:41:19 +0000 (UTC)
Received: by lbbyj8 with SMTP id yj8so160539597lbb.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Jul 2015 08:41:18 -0700 (PDT)
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=Mklv3/kF1eRfO+0XQCFy5NWqC5qEYrHzgqohofFiJgM=;
b=IZNtafRSdP/zBKQVi3t/DI8bEuqbIRwnvsaDQFElI5KGa+Qf9f7szCd83u4iaDEDPn
KnXE9MOPvtzXBseyvL8806kZK65nTuf9KTbvrYCbYvm/Ddp2F4tkq/HLFesSeNVZyEUF
dn/G02DpOiJIdq0cgTfPh6iJMn/sShW9u1Od77rD0fnYn7jtjksdAOfa3Oq+b39UIVvM
DTyNQEU8GlG2WYVlI+ErgDUW17CnLuNM9G+7xYYUGvfKt5xjFsFw1yFfTI3dvfyazER7
urEvxHkBSVgbYN8ChEVY0t0F4PatuC9AYI6rlxJjKNTuRZ1Wnb2Vfj3CVXniMmE9DqgE
nVKA==
MIME-Version: 1.0
X-Received: by 10.152.22.99 with SMTP id c3mr8918296laf.32.1437666078164; Thu,
23 Jul 2015 08:41:18 -0700 (PDT)
Received: by 10.25.90.75 with HTTP; Thu, 23 Jul 2015 08:41:18 -0700 (PDT)
In-Reply-To: <CAAS2fgRBa47ye-ouV2jDe16MJFCKxYh0zF0Jw4BTwzpXVKgwOg@mail.gmail.com>
References: <CABsx9T30aUx+Leb2HXx2QrMT8R_eTXV9hiC99av957645iQm1Q@mail.gmail.com>
<CAAS2fgRBa47ye-ouV2jDe16MJFCKxYh0zF0Jw4BTwzpXVKgwOg@mail.gmail.com>
Date: Thu, 23 Jul 2015 11:41:18 -0400
Message-ID: <CABsx9T3mEYPMFfxFbM-Jj7nADWsVg9HbvQOr0JZeEjC8gOvLZA@mail.gmail.com>
From: Gavin Andresen <gavinandresen@gmail.com>
To: Gregory Maxwell <gmaxwell@gmail.com>
Content-Type: multipart/alternative; boundary=089e0158b6c0e50ebf051b8cb72c
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@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] For discussion: limit transaction size to
mitigate CVE-2013-2292
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: Thu, 23 Jul 2015 15:41:22 -0000
--089e0158b6c0e50ebf051b8cb72c
Content-Type: text/plain; charset=UTF-8
On Mon, Jul 20, 2015 at 4:55 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Mon, Jul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Mitigate a potential CPU exhaustion denial-of-service attack by limiting
> > the maximum size of a transaction included in a block.
>
> This seems like a fairly indirect approach. The resource being watched
> for is not the size (otherwise two transactions for 200k would be
> strictly worse than one 200k transactions) but the potential of N^2
> costs related to repeated hashing in checksig; which this ignores.
>
To get a feeling for the implementation complexity / correctness tradeoff,
I implemented changes to Core to count exactly how many signature operations
are performed and how many bytes are hashed to compute sighashes:
https://github.com/gavinandresen/bitcoin-git/commit/08ecd6f67d977271faa92bc1890b8f94b15c2792
I haven't benchmarked how much keeping track of the counts affects
performance (but I expect
it to be minimal compared to ECDSA signature validation, accessing inputs
from the UTXO, etc).
I like the idea of a consensus rule that directly addresses the attack--
e.g. "validating
a transaction must not require more than X megabytes hashed to compute
signature hashes."
(or: "validating a block must not require more than X megabytes hashed..."
which is
more symmetric with the current "maximum number of sigops allowed per
block")
Thinking about this and looking at block 364,292, I think I see a simple
optimization that would
speed up validation for transactions with lots of inputs: use
SIGHASH_ANYONECANPAY
for all of the inputs instead of SIGHASH_ALL.
(which would make the transaction malleable-- if that's a concern, then
make one of the inputs
SIGHASH_ALL and the rest SIGHASH_ANYONECANPAY-- I think this is a change
that
should be made to Core and other wallets should make).
---
I'd like to hear from maintainers of other full implementations: how hard
would it be for you
to keep track of the number of bytes hashed to validate a transaction or
block, and use
it as a consensus rule?
--
--
Gavin Andresen
--089e0158b6c0e50ebf051b8cb72c
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On M=
on, Jul 20, 2015 at 4:55 PM, Gregory Maxwell <span dir=3D"ltr"><<a href=
=3D"mailto:gmaxwell@gmail.com" target=3D"_blank">gmaxwell@gmail.com</a>>=
</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .=
8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On Mon, J=
ul 20, 2015 at 7:10 PM, Gavin Andresen via bitcoin-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@li=
sts.linuxfoundation.org</a>> wrote:<br>
> Mitigate a potential CPU exhaustion denial-of-service attack by limiti=
ng<br>
> the maximum size of a transaction included in a block.<br>
<br>
</span>This seems like a fairly indirect approach. The resource being watch=
ed<br>
for is not the size (otherwise two transactions for 200k would be<br>
strictly worse than one 200k transactions) but the potential of N^2<br>
costs related to repeated hashing in checksig; which this ignores.<br></blo=
ckquote><div><br></div><div>To get a feeling for the implementation complex=
ity / correctness tradeoff,</div><div>I implemented changes to Core to coun=
t exactly how many signature operations</div><div>are performed and how man=
y bytes are hashed to compute sighashes:</div><div>=C2=A0=C2=A0<a href=3D"h=
ttps://github.com/gavinandresen/bitcoin-git/commit/08ecd6f67d977271faa92bc1=
890b8f94b15c2792">https://github.com/gavinandresen/bitcoin-git/commit/08ecd=
6f67d977271faa92bc1890b8f94b15c2792</a></div><div><br></div><div>I haven=
9;t benchmarked how much keeping track of the counts affects performance (b=
ut I expect</div><div>it to be minimal compared to ECDSA signature validati=
on, accessing inputs from the UTXO, etc).</div><div><br></div><div>I like t=
he idea of a consensus rule that directly addresses the attack-- e.g. "=
;validating</div><div>a transaction must not require more than X megabytes =
hashed to compute signature hashes."</div><div>(or: "validating a=
block must not require more than X megabytes hashed..." which is</div=
><div>more symmetric with the current "maximum number of sigops allowe=
d per block")</div></div><div class=3D"gmail_extra"><br></div><div cla=
ss=3D"gmail_extra">Thinking about this and looking at block 364,292, I thin=
k I see a simple optimization that would</div><div class=3D"gmail_extra">sp=
eed up validation for transactions with lots of inputs: =C2=A0use SIGHASH_A=
NYONECANPAY</div><div class=3D"gmail_extra">for all of the inputs instead o=
f SIGHASH_ALL.</div><div class=3D"gmail_extra"><br></div><div class=3D"gmai=
l_extra">(which would make the transaction malleable-- if that's a conc=
ern, then make one of the inputs</div><div class=3D"gmail_extra">SIGHASH_AL=
L and the rest SIGHASH_ANYONECANPAY-- I think this is a change that</div><d=
iv class=3D"gmail_extra">should be made to Core and other wallets should ma=
ke).</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">-=
--</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">I&#=
39;d like to hear from maintainers of other full implementations: how hard =
would it be for you</div><div class=3D"gmail_extra">to keep track of the nu=
mber of bytes hashed to validate a transaction or block, and use</div><div =
class=3D"gmail_extra">it as a consensus rule?</div><div><br></div>-- <br><d=
iv class=3D"gmail_signature">--<br>Gavin Andresen<br></div><div class=3D"gm=
ail_signature"><br></div>
</div></div>
--089e0158b6c0e50ebf051b8cb72c--
|
