Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.148.112 as permitted sender)
	client-ip=62.13.148.112; envelope-from=pete@petertodd.org;
	helo=outmail148112.authsmtp.co.uk; 
Date: Thu, 7 Aug 2014 01:03:50 +0000
From: Peter Todd <pete@petertodd.org>
To: bitcoin-development@lists.sourceforge.net
Message-ID: <20140807010350.GC9272@localhost.localdomain>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="32u276st3Jlj2kUU"
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
Subject: [Bitcoin-development] SIGHASH_ANYONECANPAY extra inputs DoS attack
Precedence: list


--32u276st3Jlj2kUU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

tl;dr: Transactions with SIGHASH_ANYONECANPAY-using inputs can be DoS
attacked by attackers adding extra inputs to them that make the fee/byte
paid unfavorable to miners, while still being high enough to be relayed.
While just a nuisance DoS attack, this is a serious obstacle towards
using ANYONECANPAY.


Background: What uses ANYONECANPAY?
-----------------------------------

1) Crowdfunds/assurance contracts: e.g. Hearn's upcoming Lighthouse, as
well as Armory's implementation.

2) Fee bumping: receiver or sender can add inputs w/ ANYONECANPAY to get
a tx confirmed without the (expensive) overhead of a second CPFP tx.

3) Privacy: inputs are more deniable in some cases, e.g. dust used for
fees, which anyone could have added.

4) Replace-by-fee scorched earth: best implementations(1) depend on fee
bumping.


Partial defense: replace-by-fee
-------------------------------

The attacker's modified transaction will usually, but not always, be
replaced by the intended one as the latter will have higher fees.
However replace-by-fee implementations must charge adequately for
network bandwidth consumed, so there will be edge-cases where the
replacement does not happen.


Transaction fee/byte optimization
---------------------------------

Each input that does not use SIGHASH_ALL can be evaluated in terms of
whether or not it increases the fees/byte paid by the transaction. Thus
we can optimize a transaction to pay the highest fees/byte by doing the
following:

    def optimize_tx(tx):
        tx2 = CTransaction(vin=[], vout=tx.vout, nLockTime=tx.nLockTime)

        for txin in <tx.vin sorted by fees/byte>:
            if <txin depends on other txins>:
                continue

            if <tx2 is valid>:
                prev_fee_per_byte = tx2.fees / len(tx2.serialized())
                tx2.vin.append(txin)
                if tx2.fees / len(tx2.serialized()) < prev_fee_per_byte:
                    # adding txin decreased fees/byte
                    tx2.vin.pop()
                    return tx2

            else:
                tx2.vin.append(txin)

        return tx

Essentially txin's that reduce the profitability of the transaction are
dropped, including the attacker's added txins. Meanwhile txins that
increase the profitability can be added by anyone.


1) "[Bitcoin-development] Replace-by-fee scorched-earth without child-pays-for-parent",
   Apr 28th 2014, Peter Todd,
   https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg05211.html


--32u276st3Jlj2kUU
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJT4tB0AAoJEH+rEUJn5PoEG/kH/2WZsBsdwjtplpPpf/Wv7VKM
uN0wrkXiaboYHMoCw5qXXgl+ehvMeDq3OBh1pweQN4XJbJKcyMt5OwbFD5eS/bCh
ZzssZcXvlMNYZKRYWnrSXfdm/CLD6DrhhG2Qj2oxpUpWzoVbFvC89JFbsdO4BwgA
SKDS486j6zzirG2reaJwqU+uMipQZW9aOg4aHP0jqCvY4OsC4hNHr3W7PZLIBJ0y
M0HoECI+WHEvEUFkmJsjHRmNbrAkEtzlp8vA/xqly2CTWaXeLaM3bPAACUzKNe8/
trLWclZpgvjDMQmw+OsCWZ56Ytl6P0pORO4gZIW9rUsxd9OnVAoXbafBcpyGoBE=
=VC4C
-----END PGP SIGNATURE-----

--32u276st3Jlj2kUU--