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)
Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics
 for generalized MAST
Precedence: list


--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--