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
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 1B1F18F5
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 13 Sep 2017 09:42:26 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149077.authsmtp.com (outmail149077.authsmtp.com
[62.13.149.77])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5657CE0
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 13 Sep 2017 09:42:25 +0000 (UTC)
Received: from mail-c245.authsmtp.com (mail-c245.authsmtp.com [62.13.128.245])
by punt23.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v8D9fCts084512;
Wed, 13 Sep 2017 10:41:12 +0100 (BST)
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v8D9f92b001104
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Wed, 13 Sep 2017 10:41:09 +0100 (BST)
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 886C1400E0;
Wed, 13 Sep 2017 09:41:08 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id C73CA20435; Wed, 13 Sep 2017 05:41:07 -0400 (EDT)
Date: Wed, 13 Sep 2017 05:41:07 -0400
From: Peter Todd <pete@petertodd.org>
To: Karl Johan Alm <karljohan-alm@garage.co.jp>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20170913094107.GA1527@savin.petertodd.org>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
<26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
<2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
<DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
<61D84B62-0F3F-48E1-B749-F628AD91BC12@friedenbach.org>
<CALJw2w49t5Wt1Czf4VTNj10opzPOS8ZDrRgoAwmeVFTeWWzBLg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="LZvS9be/3tNcYl/X"
Content-Disposition: inline
In-Reply-To: <CALJw2w49t5Wt1Czf4VTNj10opzPOS8ZDrRgoAwmeVFTeWWzBLg@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: ac9955e3-9867-11e7-801f-9cb654bb2504
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aQdMdwEUC1AEAgsB AmEbWlReVFx7WGM7 bghPaBtcak9QXgdq
T0pMXVMcUg0cCEoI BEweUhhzdwEIeX95 Z0MsDyNSVUF/IEVg
S0ZSEnAHZDJndWgf URZFflAGdgZOLE1H b1B7GhFYa3VsNCMk
FAgyOXU9MCtqYAFY WAIJIBoYW08NFT50 WR0YHDsuFkQZRiI1
Z1JuNlcdGAMaO0E2 eUAsXFseLx4ZEW8W EUZXSCBUIVQbTi4q Hw5WFWs3KwE1
X-Authentic-SMTP: 61633532353630.1039:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-0.7 required=5.0 tests=RCVD_IN_DNSWL_LOW
autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics
for generalized MAST
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, 13 Sep 2017 09:42:26 -0000
--LZvS9be/3tNcYl/X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Wed, Sep 13, 2017 at 08:27:36AM +0900, Karl Johan Alm via bitcoin-dev wr=
ote:
> On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >> Without the limit I think we would be DoS-ed to dead
> >
> > 4MB of secp256k1 signatures takes 10s to validate on my 5 year old
> > laptop (125,000 signatures, ignoring public keys and other things that
> > would consume space). That's much less than bad blocks that can be
> > constructed using other vulnerabilities.
>=20
> Sidenote-ish, but I also believe it would be fairly trivial to keep a
> per UTXO tally and demand additional fees when trying to respend a
> UTXO which was previously "spent" with an invalid op count. I.e. if
> you sign off on an input for a tx that you know is bad, the UTXO in
> question will be penalized proportionately to the wasted ops when
> included in another transaction later. That would probably kill that
> DoS attack as the attacker would effectively lose bitcoin every time,
> even if it was postponed until they spent the UTXO. The only thing
> clients would need to do is to add a fee rate penalty ivar and a
> mapping of outpoint to penalty value, probably stored as a separate
> .dat file. I think.
Ethereum does something quite like this; it's a very bad idea for a few
reasons:
1) If you bailed out of verifying a script due to wasted ops, how did you k=
now the
transaction trying to spend that txout did in fact come from the owner of i=
t?
2) How do you verify that transactions were penalized correctly without *al=
l*
nodes re-running the DoS script?
3) If the DoS is significant enough to matter on a per-node level, you're g=
oing
to have serious problems anyway, quite possibly so serious that the attacker
manages to cause consensus to fail. They can then spend the txouts in a blo=
ck
that does *not* penalize their outputs, negating the deterrent.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--LZvS9be/3tNcYl/X
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJZuP0wAAoJECSBQD2l8JH7buUIALn5AaPxEeuXS12RItdeD/lJ
VbKBr6BKeaxGHWRWUTfX/kHGmH0KUrRwc5cHu2qlQsnZ5PTAWavwa/lbspVNOhpv
eXU9BCSzQ4rQ831Ws3Cy4hjZT7BwaQNSXnka9WyP7WJLuC/BikONdXYICekU0/8U
TkwfUvtteLvM2CosBKWm8d7fE5IvriEN1AcRIBitH9QhpwdSs0Vih6Kw8Ue3sefP
yqBEsyExi07Cw2WVQ9I6vkIGk9Sk4qfF0yLNgMTXeXjAXOsdTlICcR8szxYC1DF1
/aDDAneqI80HBoDKCIkkUOYZyQ+mjvZaTol8YF91rCgosnVgoR6ux/NUFd6rbDo=
=D5C3
-----END PGP SIGNATURE-----
--LZvS9be/3tNcYl/X--
|