Overview
Suppose most Bitcoin clients are installed in Windows operating systems. Suppose most people that use Windows 
does not compile the source code,
but download the 32 bit executable from Sourceforge, which is a 32-bit application. This assumptions seems probable in practice.
To process a transaction the Satoshi client loads all referred transactions inputs into RAM (see CTransaction::FetchInputs()).
Attack (1)
The attacker mines 2000 blocks. Each one containing a 1 Mbyte transaction.
Then the attacker can construct a transaction that requires 2 Gb of RAM to be processed, be linking to each one of 2000 big transactions.
All Windows clients processing this transaction will segfault. Nodes must update to recover.
How long it takes?
The fastest the attack can be made is by mining 2000 blocks as fast as possible. 2000 blocks in 10 minute intervals represents 14 days.
Because difficulty is re-computer every 2016 blocks, the attacker can also increase the total hashing power to reduce the block interval.
How much it cost to attack?
Current Bitcoin hashing power is 20000 GHash/s.
Take the Bitforce Single ‘SC’, which makes 60 GH/s for 1300 USD. Then 50% of the hashing power can be bought for
20000/60*1300 = 433K USD.
With 50% of the hashing power, the first 2000 blocks will contain half of the attacker’s blocks, and will be mined at 2x speed.
That’s 7 days. The remaining 2000 blocks (containing the other half) will be mined at a normal 1x speed.
The total atack time is therefore 21 days.
If the attacker is willing to invest more?
Investing four times that amount, or 1.7M USD, the attacker gets 80% of the hashing power.
The first 2000 blocks will contain 80% of the attackers blocks, mined in only 2.8 days.
The remaining 400 attacker blocks will take an additional 3 days.
The total attack time is therefore 5.8 days.
What if the attacker is a miner who already has 10% of the network hashing power?
We suppose the miner has already amortized his mining hardware.
We suppose than mining fees are very low compared to the 25 BTC block reward.
If we suppose that mining is profitable, then mining each block costs, on average, less than 25 BTC.
Then the attack has no cost, and it takes 140 days to store 2000 1Mb transactions in the blockchain.
Proposed Solutions
1. Limit the number of transaction bytes that a transaction can request (TxSizeRequested(Tx)<1 Mb).
TxSizeRequested() can be computed as
TxSizeRequested(Tx) = Sum( for each distinct tx2 in tx.previns: Size(Tx2.Size) )
(this is a hard fork, but is likely that there is a transaction in the current block-chain whose TxSizeRequested(Tx)>10 Kbytes)
OR
2. Free older transactions while fetching new transactions in as in a sliding window, in FetchInputs().
Reload transactions in ConnectInputs(), and dispose after verifying script.
Attack(2)
The attack can be performed as a DoS attack to a single node without using the block chain at all.
The attack cost is 240 BTC (but probably the BTC can be reused for another attack).
Suppose the attacker is connected to the victim.
This are the steps to execute the attack:
1. The attacker has 240 BTC in a specific prevout that he owns.
2. The attacker spreads the 240 BTC in 4000 tiny outputs (Out(j)), each containing 0.06 BTC.
This will cost some additional BTC in fees. An additional 10 BTC will pay for them. The attacker may use several transactions (e.g. 100) to reduce fees.
3. The attacker builds 4000 transactions Tx(i), each of size 488 Kbytes. Each Tx(i) contains a single input Out(i) and enough outputs to fill the remaining space of 488 Kbytes. The attacker builds Tx(i) so that they will not be included in a block because of low fees.
4. The attacker sends Tx(i) one by one to the victim.
5. The victim accepts this transaction to the memory pool since GetMinFee() returns 0.0501 BTC:
(note 488 Kbytes = 499999 bytes)
nBaseFee = (mode == GMF_RELAY) ? MIN_RELAY_TX_FEE : MIN_TX_FEE = MIN_RELAY_TX_FEE = 0.0001 BTC
nBytes = 1000+ 498999 = 499 999
nMinFee = (1 + (int64)nBytes / 1000) * nBaseFee = (1+499999/1000)*0.0001 = 0.0501 BTC
if (nMinFee < nBaseFee) ( 0.0501 BTC < 0.0001 BTC ? ) NO.
if (nBlockSize != 1 && nNewBlockSize >= MAX_BLOCK_SIZE_GEN/2) (499999 >=500000 ?) NO.
returned -> 0.0501 BTC
6. The victim virtual address space for the application is filled and the application segfaults.
The time required for the attack, given a connection of 50 Kbytes/sec, is 11 hours.
Attack (3)
There is a variant of this attack that does not involve mining orphans.
Instead of becoming a miner, just broadcast 4000 transactions of 500 KBytes each with enough fees to make them into any block.
Currently, 1 BTC fee for each transaction would be enough for miners to accept the attackers transactions instead of any other, since the average fee per 500 Kbytes of transactions is around 0.6 BTC (this is an estimation).
So with only 4000 BTC you can execute an attack that disconnects all Windows clients at once. The attack takes 14 days to be prepared, so that gives enough time for users to upgrade (or if the core dev develops a patch fast enough)
Attack (4)
Execute the attack 1 to a node that it loading the block-chain for the first time.
Summary
To summarize, four related attacks have been proposed:
– TFMEA Miners attack (https://bitcointalk.org/index.php?topic=135388.0)
This attack hangs every Windows/Linux-32Bit node in the network. It costs of 500K USD. Takes 21 days. 6 days if willing to waste 1.7M USD in hardware.
– TFMEA block download attack
(https://bitcointalk.org/index.php?topic=135388.msg1442235#msg1442235)
This attack hangs a peer Windows/Linux-32Bit node. Cheap.
– TFMEA peer attack
(https://bitcointalk.org/index.php?topic=135388.msg1442218#msg1442218)
This attack hangs a peer Windows/Linux-32Bit node. Costs 240 BTC. Money can be reused so cost can be amortized.
– TFMEA Fee-sponsored attack
(https://bitcointalk.org/index.php?topic=135388.msg1442807#msg1442807)
This attack hangs every Windows/Linux-32Bit node in the network, with a cost of 4000 BTC).
Disclaimer: I’m unsure if these attacks can be exploited exactly as I suggest, since I haven’t tested them.
EDIT: Whenever I said 488 Kbytes, read 245 Kbytes. It doesn’t change much the situation. Or use 488 Kbytes transactions and double the fees paid.
Suggested solution
A completely proactive and formally provable protection measure against memory exhaustion attacks in transaction processing would be to reduce the maximum transaction size to 100 Kbytes or so. That would reduce both the RAM required to load each prevout and the number of prevouts a transaction may request, totaling to 200 Mbytes. The pros for limiting the Tx size are many, apart from the memory consumption issue during Tx processing:
– Reduce network latency, allowing the verification of partially received blocks.
– Reduce the DoS surface, by limiting the amount of data that has to be sent in order to detect an invalid Tx.
– Reduce the DoS surface, by limiting the memory required for the in-memory pool.
– Reduce the DoS surface, by reducing the maximum number of signature verifications required by any Tx.
The cons are that certain kind of huge strange transactions (like multi-sigs or assurance and dominant assurance contracts).
Bitslog 