A ~600KB block attack against Bitcoin XT / BIP101

[basil00]

This is a simple idea that attempts to attack the new XT/BIP101 resource counting limits introduced in the commit:

https://github.com/bitcoinxt/bitcoinxt/commit/cc1a7b53629b265e1be6e212d64524f709d27022

Basically, post-fork XT/BIP101 enforces two new resource limits: (1) an accurate sigOp count of 80,000 per 8MB block, and (2) a max-bytes-hashed of 1.28GB per 8MB block.  The motivation of these limits was to mitigate the attack described in CVE-2013-2292.  A block that violates either limit is invalid, so just like the size limit, this can prevent more transactions from being included in a block.  The basic idea is to exploit max-bytes-hashed limit to prematurely "fill" 8MB blocks with much less than 8MB of data.

For example, consider a transaction input that spends a 1-of-15 P2SH multisig address.  Suppose the attacker rigs the input so it is always the last public key that matches the signature (so all 15 sigOps will be performed).  A 1-of-15 P2SH redeem script consumes (1+15*34+1+1)=513bytes.  The transaction input therefore consumes (41+1+74 +514)=630bytes.  The attacker can therefore fit (100KB/629B)=158 such inputs into a standard 100KB transaction.  The transaction performs (158*15)=2370 sigOps, less than the 4000 sigOp-per-tx.  Such a transaction is therefore allowable under current IsStandard() rules, so the attacker can create and broadcast the transactions in the usual way.

The bitcoin protocol hashes the entire transaction (less other signature data) for every sigOp performed.  This means that such a transaction will hash (100000 - 158*74) * 2370 = ~209MB worth of data.  An attacker therefore only needs to generate 1.28GB / 209MB = ~6 such transactions to near exhaust the max-bytes-hashed limit of 1.28GB per 8MB block.  This equates to a little over ~600KB of standard transaction data.

Are my sums correct?

EDIT: To answer my own question, no.  The correct value for bytes hashed is (100000 - 158*(74 +514)) * 2370 = ~17MB worth of data since the entire P2SH script for each input is excluded when calculating the hash.

Nevertheless, the attack is still possible with some more exotic P2SH scripts with higher sigOp-per-byte densities (e.g. using OP_DUP on public keys).  A transaction with the standard 4000 sigOps on 50KB of worth of transaction outputs will consume at least 50000 * 4000 = 200MB of data.  Such transactions will not violate the current IsStandard rules, but would be more obvious than 1-of-15 multisig addresses.

[DannyHamilton]

But how does the attacker convince the miners to actually include the transaction in their block?  Won't most miners simply skip the transaction, and include other transactions instead?

[newIndia]

But how does the attacker convince the miners to actually include the transaction in their block?  Won't most miners simply skip the transaction, and include other transactions instead?

The miner, might himself be the attacker.

[basil00]

But how does the attacker convince the miners to actually include the transaction in their block?  Won't most miners simply skip the transaction, and include other transactions instead?

The transactions obey the current IsStandard() test, so will be included by default (provided the attacker pays an appropriate transaction fee of course).  BTW, this is how the current coinwallet-eu spam-attack transaction get mined.

[DannyHamilton]

But how does the attacker convince the miners to actually include the transaction in their block?  Won't most miners simply skip the transaction, and include other transactions instead?

The transactions obey the current IsStandard() test, so will be included by default (provided the attacker pays an appropriate transaction fee of course).

It seems like this "attack" won't be very successful.

The protocol rule doesn't require the miner to include the transaction, it simply allows them to include it if they want to.

You might manage to get a few blocks forced to a smaller size as miners using the "default" setup get tricked into including the transaction, but rather quickly they will realize that they can write software to watch for this situation and improve their profitability by simply ignoring these transactions unless there aren't many other transactions available to confirm anyhow.

[basil00]

Keep in mind that the attacker can also adapt.

Also, if a transaction is not mined it will sit in the mempool indefinitely (if dropped it can be rebroadcast).  This can be the basis of a memory exhaustion attack against nodes.