I added additional information regarding this vulnerability:  an additional timing attack to find the Bitcoin address of a peer, using spent outputs (before, I had discussed how to do it using only unspent outputs).

The report is on my blog: https://bitslog.wordpress.com/2013/01/23/new-bitcoin-vulnerability-get-your-peer-public-addresses/

Sergio.

Global Pool Mining Proposal and a fast light tx verification system

Pooled mining is a mining approach where multiple generating clients contribute to the generation of a block, and then split the block reward according the contributed processing power. Pooled mining effectively reduces the granularity of the block generation reward, spreading it out more smoothly over time.

A share is awarded by the mining pool to the clients who present a valid proof of work of the same type as the proof of work that is used for creating blocks, but of lesser difficulty, so that it requires less time on average to generate.  [https://en.bitcoin.it/wiki/Pooled_mining]

I'm thinking of the idea of a protocol change to allow the possibility (and encourage it via incentives) that all Bitcoin miners form a Global Pool, without requesting additional trust:

1. Each share contains a PoW and a coinbase (to be sent a partial block reward)
2. Shares are included in a block as transactions (but they must go at the end of the list).
3. Shares contribute to the PoW of the block. For example, 10 shares, each containing 5% of the difficulty target contribute as 50% of the requested PoW of the block. (for the sake of simplicity I may be overlooking the correct way account for partial PoWs taking account probabilities)
4. Each share miner is also payed proportionally to the contributed work.
5. Shares are constructed as blocks and the only difference is the target difficulty. Normally, each miner tries to solve the block and during this process, a number of shares may be produced and transmitted.
6. Each share (like a block) includes a root of a Merkle tree of transactions.
7. The share lists the first 10% of the transactions specified on the merkle tree (the rest of the tree is supplied by terminal hashes). Miners can never surpass this limit. The partial list cannot include references to other shares.
8. Each share PoW is no less than 10% of the total PoW required.
9. A miner has the obligation to include in the block the transactions listed in the share in order to use the share.
10. Whenever a share is transmitted, it's split in two parts: header and partial transaction list specified by the merkle root. If the destination node already has the transaction list, only the header is transmitted. The transaction list is defined by the merkle root hash. This allows miners to send many shares using the same transaction list, without incurring on the network overhead of seeding the same list multiple times.
11. A miner should never produce two shares with conflicting transactions (it goes against his own interest)
12. A miner may include his own shares in a block.

Using these properties we can make a system where transactions are “lightly verified” by the network 10 times faster, without reducing the block interval and so avoiding rising parallel chains competition probability. This light verification system emerges because miners have an incentive to include in the block whatever share they see.

So a merchant may accept a payment of low value if:

1. It is confirmed OR
2. It sees it listed in the merkle tree of a share and 10 seconds have elapsed (time for the share to arrive to every miner)

The drawback is that network bandwidth consumption is doubled. The PoW target of a share does not affect the protocol much, since only partial merkle root lists are sent (in the same proportion). E.g. Share with 1% target PoW would only send 1% of the transaction list.

One possible alternative is that the share gets paid not by the PoW percentage but for the fees contained in the transactions specified by its partial list. Nevertheless I see this alternative lees attractive.

Note than work each miner has to do remains equal to the work done by a normal Bitcoin miner.
Also note that since shares do not contain other shares in the partial transaction list, there is no share-chain competition.
Note that the minimum percentage chosen for each share is unimportant: it could be as low as 1%. The network bandwidth use is always doubles with respect to a normal Bitcoin node, and does not depend much on the share percentage chosen.(with the exception of the small header overhead, and the hash operation to verify the PoW).


Best regards, Sergio.

Also, signature verification (that take a long time and can be repeatedly requested by an attacker), can be used as an oracle to distinguish between two or more different transaction processing results. Without the cache, for instance, attacks like this https://bitcointalk.org/index.php?topic=135856.0 can be executed faster, since the time it takes to process a transaction can be used to locate the exact prevout that fails, in a transaction with thousands of inputs. The cache tries to mitigate the timing side-channel.

I read a transcript of  #bitcoin-dev (http://bitcoinstats.com/irc/bitcoin-dev/logs/2012/11/09) where jgarzik and, Sipa debated whether the signature cache was a performance optimization or a DoS protection and why.
The sig cache is both of them. But the sig cache was included before performance was a problem because of the DoS protection requirement.

The following attack against versions prior 0.6.3, e-mailed to Gavin on May-2012, explains it:

1. The attacker creates a transaction that pays 0.01 BTC to 100 different addresses. (The attacker must have 1 BTC). To avoid paying fees, the attacker can divide the transaction into slices, each one below 1 kilobyte.The attacker broadcasts the transactions and waits for confirmation.

2. Afterwards the attacker builds transactions grabbing 100 of his own prevouts and adding an additional prevout that he does not own.  This prevout is a coinbase that has not been matured (it does not need to have a valid signature, since the method exit point is before the script verification). To create many fake transactions, the order of the first 100 inputs is randomized.

3. The attacker sends these transactions to the victim. The transaction size would be around 18 Kbytes. The transaction would take around 0.36 seconds to arrive (with a 50 Kbytes/sec connection).

4. The victim's client app will go with the transaction straight through ConnectInputs() and successfully connect the first 100, and then fail to connect the last. The time required for this check in an average PC is approximately 100 * 4 msec = 400 msec  (an estimation). Then the attacker can hang the vitims app by sending these fake transactions at a rate of around 3 per second. The number of inputs used for the attack is arbitrary (can be as low as 10, giving 10! unique possible transactions).

Note that if the connection bandwidth is higher, then the attack is stronger. If the victim's CPU is slower, then also the attack also get stronger.

I proposed the solution of a signature cache to Gavin at that time. It turned out that Satoshi himself had thought about adding the sig cache, but I think it was mainly for performance reasons.

Best regards,
 Sergio.

I disagree.
Suppose you are implementing the following two-party protocol for an antivirus web server:

1. Client. Uploads a file.
2. Server. Checks the file for viruses and sends a respond to the user with the result

Would you let the user send files as long as 4 Gb ?
Why? What implications would that have to your antivirus infrastructure?
What would be the additional cost and complexity of designing an antivirus checking module that can handle such files, assuming such files won't fit in RAM.
What if some programmer forgets that such a file can be uploaded?
What if many users sends such big files at the same time?
There are too many "whats if" for such an unused "feature".

You see, Bitcoin has the same problem. Transactions can required more than 4 Gb to be processed by any existing client. You can either handle it by reducing very little the transaction size, or you can wait to see when a smart hacker notices how to exploit the problem.

To "inform the audience", first you have to make them think for themselves about something. I have no authority to make ANY decision. I'm nobody, not a core dev, not a mining pool owner, not a merchant. I don't even own BTC, apart from the ones in my testnet.

I'm here because I like Bitcoin.
 

I'm testing the poll system to see if it can be used to achieve consensus. It's more an experiment with the Bitcoin community than a voting on any change.

If I see a pattern on the answers for smaller sizes, then that justifies writing a Bitcoin Improvement Proposal (BIP) to do a soft-fork to reduce the maximum size, which can protect the clients from memory exhaustion problems.

Thanks you for your participation!

I realized that the attack can also be mounted using much smaller transactions, as long as you keep sending them fast enough to trigger penny flooding algorithm.
So just a single disconnection may be required to detect a remote public address.
No need to do any binary search. Just send each Out(i) in a single Tx(j).


Sergio.

I really thought this had been fixed, because I commented the problem of using IsFromMe / IsMine to the developers in the github forums (https://github.com/bitcoin/bitcoin/pull/1648), but no. Not fixed, so I'd better alert people before they can be tracked...

The attack requires you to connect and be disconnected from the same node almost 11 times. Nodes do ban DoS offenders for some time, so the attack can take some days mounted from a single IP. Nevertheless, if you can control 11 different IPs (very easy), and you can re-connect to the peer, you cant still mount a successful attack in a few minutes.

The attack allows only to know the Bitcoin public address related to an IP. If a peer is using Tor, then there is no loss of anonymity.

Affected Systems
-----------------

The problem affects all versions of the Satoshi Bitcoin Client.

Summary
---------

The method CTxMemPool::accept() has a protection against 'penny-flooding'. The protection prevents a transaction with very low fees and big size to be forwarded or even stored in the memory pool.

The problem is that this protection tests if a transaction is from a wallet owned by the user, and if it's the case, then the protection is skipped. This fact can be used by the attacker as an oracle.

There are currently around 1M addresses with non-zero balance (an estimation based on http://bitcoin.stackexchange.com/questions/3524/how-many-unspent-transaction-outputs-are-there).

An attacker can discover which of the addresses are owned by a peer by the following procedure:

1. For each address, the attacker choose one unspent output Out(i)

2. Group the 1M unspent outputs in 1632 transactions Tx(j), each one containing 613 previns. Each transaction would be approximately 26999 Kbytes long. Add one output. Put zero fees. (GetMinFee() will return zero)

3. Send each Tx(j) one by one to the victim node.

4. After sending each transaction, the victim node may:

- Reject the transaction because it penny-floods (normally). In this case you will be still able to send more transactions.

- Disconnect you (DoS detection) you since you are not providing the correct signature scripts (this is the case when you have hit an owned address)


5. If you have been disconnected, repeat recursively a binary search grouping the prevouts of this transaction until you find a single one that disconnects you. Note that you may need to add additional dummy previns or prevouts to the transaction if it becomes too small to be blocked by the peer with the penny-flooding protection system.

With a 54 Kb/sec link, sending each Tx takes 1/2 sec so finding the first tx takes in the worst case, 13 minutes. Afterwards each binary search step takes 1/2 seconds in the worst case, so with 10 additional tests you can find an prevout with the desired property in 2^10 prevouts, more than the 613 originally contained, in a few seconds.

I haven´t tested the attack but, check for yourself. The explanation is clear enough. But without testing the attack, I can be mistaken.

You can protect very easily from the attack by rising the "-limitfreerelay" value to something like 1000000. Of course, that will also disable the penny-flooding protection.

Until the next vuln report,
  Yours sincerely,  Sergio.

Second, there are other solutions to the tragedy of the commons "problem" with fees. One of the is fee confiscation. This is another excerpt of the paper:

10.6.1. Fee confiscation. In this scheme, part of the fees collected by a miner get “confiscated”. When a transaction with fee f is included in a block, the miner applies a predefined multiplier x to the fee f. The miner can only collect x ∗ f and the rest is confiscated. The multiplier x is always lower or equal to 1.The longer the message, the lower the multiplier. The slower the cryptographic operations required by the transaction, the lower the multiplier.
As an example, if CPU usage was the only factor to consider to calculate the cost of a transaction to the network, then a transaction which requires 100 times more time to evaluate than other would have a multiplier that is 100 times lower. Because miners always choose the transactions that give them the higher reward, then users would be forced to compensate the punishment of confiscation by increasing the fees by the same factor for those commands.
CPU usage is not the only factor to consider when calculating the cost of a transaction to the network as a whole. All expensive resources already  described must be considered to design a realistic function that takes into account average costs and tries to anticipate how those costs will evolve in the future.
As fees are reduced by the multipliers, is necessary to restore the remaining money (1 − x) ∗ f to the network to avoid destroying it. One possible solution is to accumulate all the remaining fees and setup a price to be awarded to the miner of the following block. To prevent the miner from trying to delay broadcasting a block in order to mine the next, we can setup the price to be awarded to the miner of some blocks ahead (e.g. ten blocks).
This automatic prize generation may give an incentive for the casual miner not to include so many transactions, since a fixed reward (higher than the transaction fees) may exist. But since including transactions in a block requires very little resources, here is no reason not to include all known transaction and collect all possible fees. For the miners who have a high percentage of network computing power (like mining pools) obviously no such incentive exists, since including less transaction imply being awarded less money as prices in following mined blocks.

Anyone would like to write a book with the discussions of these threads? I imagine the book be called  something like
"Agreement without Trust, Inside the Bitcoin P2P community" (by P2PMaster, 2013) 0.99 BTC, paperback.

I will add my grain of salt to the discussion.
First, regarding miner´s incentives, this is an excerpt of my paper "Mavepay".
(It adds little new matter to what was said, only the idea tha miners could be required to do more work than the rest of the nodes)

From the game-theoretic point of view, Bitcoin miners do not have a strong incentive to protect end-users resources. In the long term miners may want to protect the end-users in order to maintain the value of their savings in the virtual coin, and the fixed cost of the infrastructure acquired for mining. But miners can at any time sell their coins and start mining for other P2P currencies, so the incentive is not strong enough. In the short term, they compete to collect fees, even if the transactions included in a block impose a high workload on the end-users. If miners were forced to store, transfer or compute much more data than end-users, then they would choose transactions of shorter length and lower CPU usage. In Bitcoin transactions are checked only once before the block mining process can start, and the quality and quantity of the transactions included in a block does not alter the winning probability significantly for a miner. The block size may affect slightly the dispersion time of a block across the network, and so may reduce the chances of a miner winning over a currently competing short-sized block. But currently this is not a limiting factor on miners, since blocks travel fast, and the diameter of the Bitcoin network is low. Also if a greater time is required to check a transaction, then the time when the block mining can effectively begin is postponed in that same amount. But transactions are checked only once, and each block mined requires a hashing effort orders of magnitude higher than the time required for transaction verification. So the CPU resources used in transaction verification during mining have little effect on the block cost and almost no effect on miners revenue.

IMHO, there is no drawback.

The only purpose I can imagine for 1Mb transactions to be created is for mixing coins from 20K different sources, to anatomize them. But the same could be accomplished by 10 smaller transactions. Maybe 1 Mb transaction could be used for crowdfunding by 10K users, in an all-of-nothing funding, although I don't know if currently the Bitcoin protocol allows such a thing.

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.


No, they don't have to be. Everything can be serialized. A clever re-design of the tx processing code could use a prevout cache to store only a small subset of of them in memory at any time. Pieter's 0.8 code is the right direction.

But why force any implementation ever made or future Bitcoin client to make such a twisted design choice if we can correct this today with very little effort?

I have to say that most other variables that can consume resources have been tightly limited (such as the maximum number of signature verifications, the properties of "standard" transactions, etc.)

I have reviewed the current Master branch (which is the base of the 0.8 release) and I found that the vulnerability is still present.
- tx.HaveInputs(view) in CTxMemPool::accept() retrieves the compressed format of all transactions referred by prevouts.

The main difference is that referred prevouts must not have been spent.

None of the 4 possible attacks listed requires prevouts to be spent. Since the attacke is prepared by sending big transactions, and these transactions contain many outputs to make them big, they are almost incompressible with the CTxOutCompressor class.

The only drawback is that in 0.8, if the attacker wants to redo the attack, a new attack could required a new preparation stage (since the attacking transaction could have spent the prepared prevouts).  

Pieter's 0.8 code is based on the assumption that transactions get shorter as outputs gets consumed in time.
The TFMEA attack uses a transaction that refer to parent transactions that have none of their outputs spent, so basically no compression can be applied.
Even if a transaction is dissected into independent cached prevouts (instead of a single CCoins for the whole transaction), then the attacker could create a non-standard transaction with a single prevout with a huge output script. This reduces the 4 TFMEA attacks to an attacker capable of issuing non-standard transactions in blocks (which is possible today using direct connections to miners).

My conclusion: 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.

We are still capable of doing it now, using the delayed hard fork feature Gavin has added.

EDIT: Apparently reducing the max  Tx size is NOT a hardfork but a softfork ("changes which strictly reduce the set of acceptable things" (gmaxwell, 2013))

Keep in mind that there will be many people who will implement the Bitcoin protocol in a variety of languages, and most of them will not pay attention to memory consumption.

I urge people to vote for reduction of the maximum transaction size from 1 Mb to 100 Kbytes.
"That's one small step for Bitcoin now, one giant leap for its future"

Right


Version 0.8 of the Satoshi client uses a different method to handle transactions, so FetchINputs() is not present anymore.
And it's probably protected against this specific attack. I'm going to review the new code.

Yes your are right. 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.


Ok, good point.

Ok. I will, when I have some spare time. Prepare your Windows to trash! 

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

Well, 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)

This is the cheapest attack to the whole network ever seen.

I remember some hero member that said that the first connection (from which the Satoshi client downloads the blockchain) should be trusted, or many other vectors of attack are possible.

What about the checkpoints? When are they verified?

I don't know if transactions are verified before or after the checkpoint is reached.
If transactions are verified before, then we may have a serious problem.

Oops.

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.

Is this correct? Did I computed GetMinFee() correctly?

Best regards, Sergio.