There's a tradeoff with applying the rate limit before full input validation. It will save the cost of validation when the tx wouldn't have been relayed anyway due to the rate limit (which could affect all processing), but it allows saturation of the relay rate limit with unsigned spam (which only affects respend relays).

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p4450_0da6b3fd187da3aa810aaa584d8bd197ad4fa2b9/ for binaries and test log.
This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/
Contact BlueMatt on freenode if something looks broken.

ACK. Code reviewed, and compiled and run on OSX

RE: saturating the relay rate limit: maybe I'm missing something, but I don't see how an attacker can do that because the bloom filter check is done first (and any outpoint hitting the bloom filter does not count against the relay limit).

If an attacker had a huge number of unspent outpoints they might be able to flood the filter. But they would pay for that attack in transaction fees for the first-spends of those outpoints. If they had a huge number of very old, high-priority outpoints they could flood the filter for free, once-- that mythical attacker could flood the relay-free-transaction filter, too, but as far as I know nobody has done that. Or maybe they have, and nobody noticed because blocking free transactions for a while just isn't very exciting or profitable.

Because sigs have not been checked at rate limit check, he can also submit an invalid second spend for every unconfirmed tx he has seen. Still limited though.

I tested the true and false cases for RelayableRespend. Bloom filter is initialized and functions correctly. Also I tested that first spend was relayed and added to wallet. I did not test bloom filter clear.

ACK

I think this it is a mistake to change the network invariant "double-spends not relayed" that has provided quite a lot of DoS protection since 2009. The current patch looks fine. But it could have unexpected interactions.
I have not actually tested these vulns, but I think they are possible..

1. For example, suppose an attacker has 4000 outputs that he controls. He creates 4000 txs Tx(i) (one for each prevout) with no fees and a size so they have very low priority for miners and then spread them slowly until every node has a copy. These Txs won't be included in blocks for a long long time (months?). Then it's possible to push double-spends over the network by sending three transactions A and B with 2000 inputs each for three sets of 2000 prevouts (from the original 4000 prevouts). If A and B are processed alternatively, A will reset the double-spend bloom filter for the ouputs in B with high probability. Then B will reset those for A, in a loop. With some provisions not to exceed the rate limiter, those 2000-input double spends will probably keep forever going around the network like ghosts until Tx(i) gets into a block (if it ever does), and then the attacker can launch another similar attack by using the remaining outputs.

So attack cost: fixed initial cost of creating 4000 outputs (maybe around 400 USD), periodic cost of re-creating A and B when a Tx(i) was included in a block.
Attack timespan: forever
Cost to the network: consume all available double-spend bandwidth.

Also there may be problems with orphan transactions
2. A user can slowly load hundreds of orphan double-spend txs, and then release them all at once with a single parent tx, even if all double-spend the same output. This is done by creating multiple versions of A(i) with small changes and multiple versions of B(i) with small changes, but with a missing parent, and then sending the parent, which will trigger the flooding.

Why not improve the network on-top-of Bitcoin instead of changing this golden rule?

Suppose we change the client so that, along each transaction, it sends an additional message for each input: SmallProof(i) = < Hash(tx), input(i) > but where the signatures for OP_CHECKSIG are taken over the TX hash, instead of over the transaction and SmallProofs are only generated if only sizeof(scriptSig)<180 bytes.
Then a lightweight double-spend alert system requires just to send the SmallProofs (220 bytes) and any server that wishes to detect 0-confirmation checks that the good SmallProofs exists and no other smallproof has been broadcast (if not, then the money is returned to the sender, or the sender must provide the smallproofs again). To prevent sending BTC from a client that does not support SmallProofs, we create a new kind of Bitcoin address that states "Smallproofs required" using another prefix.

So to summarize this proposal needs:

1. One new kind of inventory item (SmallProof) (current INVs/getdata system could be used)
2. A filter that prevents SmallProofs for being sent more than twice for each prevout.
3. Add the small proofs to CWalletTx to preserve them.
4. A change in CWallet::CreateTransaction() so that both the Tx and the Smallproofs are signed.
5. A new address prefix (optional) so that old-clients cannot recognize these addresses.
6. A way to inform the user if a Tx comes with SmallProofs and if is had double-spends attempts.

If done properly, none of these modifications should affect old nodes, and we'll have way to achieve 0-confirmations with much higher confidence.

Clarification: Only smallproofs are generated if the payee requires them, so the network overhead will initially be 0%, and will grow slowly as more merchants adopt the new 0-confirmation system. If all transactions required 0-conf, then the network overhead would be aprox. 50%.

Also this system is more politically correct: why the whole network should pay with less security if a bunch of merchants wants to accept 0-confs? Let THEM pay the price of upgrading their systems to this new confirmation method, and let them pay the price to convince users to upgrade their nodes to send 0-confirmation payments. Also it's not clear at all that this patch makes better or worse 0-conf, because as we're broadcasting the double-spends, we're letting miners modify their source code to choose the double-spend if the fees are high enough. With pure rational miners, we're making double-spending more easy!
If you you like the proposal of SmapllProofs (or whatever other marketing name you want to name it), I will hire a programmer and create the patch. I'll do everything I can to prevent this double-spend patch from been merged.

A core design decision of Bitcoin was to use fully-spendable outputs instead of partially-spendable accounts for the sole reason that using fully-spendable outputs prevents spamming. For every other possible metric, accounts would have been a better choice than outputs (every new alt 2.0 coin has changed this). But now we're tweaking this to let spam be forwarded again. So we end up with the worst of both designs. Let's honor S.N. and don't try to transform Bitcoin into something it is not. Let's build the double-spend alert system on top of Bitcoin, and not ruin a foundational rule that had a clear intention in the original design.

@SergioDemianLerner Thank you very much for your attention and thoughts on this. Regarding the attacks 1. and 2. that you posit:

1. Relaying A will not overcome the bloom filter, because only one output is added to the bloom filter. That is true whether A respends one output or 2000. Another respend transaction is required to get another output added, so this is the same attack that @petertodd posited. A determined attacker can overrun some nodes' rate limiters, but I don't yet see the risk of a self-perpetuating attack.
2. Maybe you have found a more fundamental problem with orphan handling: orphans respending another orphan should not be stored. But anyway, when the parent comes along, how is the "flood" different from all those txes being transmitted without the orphan step?

Regarding overall network design, the current situation is that respends split the network into realms believing one or the other was first. The network as a whole already contains both. Relaying when possible just makes the knowledge more homogeneous and actionable.

I notice #4484 is not referenced here directly. It has straightforward improvements to this. Your review of it would be greatly appreciated.

It gives more information at the cost of decreasing the advantage the first transaction had over the second.

If we don't believe this advantage should exist, and it is just about more information about the network, and double spends are perfectly acceptable, there is a much simpler solution to this problem, namely replace-by-fee.

If we believe this advantage should exist (and fow now I do, even if it's just best effort), we shouldn't help the sender of the second one (the alleged attacker) relay his transactions.

RE: not helping the second transaction get his transactions to miners:

This is the fundamental disagreement; I wonder if we can somehow measure how difficult it is for a would-be double-spend-attacker to get a transaction to miners.

If it is easy with the current rules, then I argue this change is definitely positive: it should make transaction recipients more aware that they are being attacked.

If it is difficult with the current rules, then I would agree this might be a net-negative.

My belief is that it would be easy for an attacker to find nodes that are "near" the big miners (Matt's mining backbone network would be a good place to start).

@gavinandresen I look as the source code and I see that if every input is a first double-spend, then every input will be added to the bloom filter.
Maybe the intention was do it as you say, but the code reads otherwise. The code should be:

if (pool.mapNextTx.count(outpoint) && !tx.IsEquivalentTo(*pool.mapNextTx[outpoint].ptx))
{
relayableRespend = RelayableRespend(outpoint, tx, false, doubleSpendFilter);
if (!relayableRespend)
return false;
BREAK; // <--
}

Nevertheless this may open other DoS possibilities, such as allowing sending a big Tx for each double-spent output from a single Tx. It must be analyzed..

Let's recap the method used by merchants to accept 0-conf tx.(as far as I know)

1. They monitor the network in several places.
2. They wait 10 seconds
3. They detect double-spends.

Suppose all miners are fully rational but unscrupulous. This may actually be the average case today, please forgive me if you're a miner and you're not. Then the attacker can just wait 11 seconds and rely a double-spend with much higher fees. Miners will take the second, and not the first. So the whole 0-conf detection idea does not work anymore.
The key difference between SmallProofs of double-spend and double-spend Txs is that the former does not allow a random miner to include double-spend in a block, where the later does.

@gavinandresen Regarding your 2nd point about orphans: The point is that a huge amount of traffic can be triggered by a 100 byte message. So if I connect to 1000 nodes, and send each one 1000 double-spend orphans (slowly), then In 1 second I can make 1M messages travel around the network. Who knows how the network will react to such state! It can loop....
An attacker can prevent people for making payments in a crucial time (such as when a bet is closing, or an auction is closing..)

Please give me a single argument why double-spend SmallProof notifications are worse than double-spending TXs, Forget for a moment about the code already written. There much more at stake.

Regarding information: Smallproofs provide more information, because they actually allow users to measure how many transactions are accepted by 0-conf, which is very important to compute risk of block-rollback attacks.

Regarding bandwidth: Smallproofs require a bit more but only if we're not under a massive DoS attack using double-spend Txs, which probably will be quite common. :)

Also the SmallProof system can one day be made part of each transaction by hard-forking and computing the signature hash as Hash( prevout(i) || Hash(Tx-as-is-now) ) , so there will be no bandwidth waste.

Regarding propagation time: Smallproofs propagate much faster. If small enough, they can even be pushed without the need for an INV-getdata interaction.

Regarding SPV: Some SPV may not want to receive double-spend transactions. BitcoinJ may want to, but other clients using block confirmations may not. A SPV node having 10 connection may receive a different double-spend Tx from each peer.

Regarding security: Signing two messages with the same private key MIGHT be bad, if there the signatures are not deterministic and the entropy source is bad. But if entropy source is bad this would allow nodes to predict the private keys generated in the first place (as it happened).

Regarding politics: Give merchants what they want when accepting 0-conf: reduced risk. With double-spend tx we cannot go and tell them: "we've reduced the risk, here is the proof. ". We can only tell them: "we did something we believe it might reduce the 0-conf risk, but it may actually do the opposite, we don't know, we are just playing with your money. "

Thank you for pointing me to #4484. This solves the first attack I proposed.

@SergioDemianLerner Just to clarify, by "smallproofs" you mean my proposal of relaying the scriptSig right? Do remember that proposal requires wallets to apply special-case behavior when sending an instant-confirmation payment; it doesn't work with wallets as-is.

Also "computing the signature hash as Hash( prevout(i) || Hash(Tx-as-is-now))" isn't a hard-fork if done sanely. (sane changes are almost never hard-forks)

IMHO patch #4484 is buggy. The is an old rule about bugs that states that where a bug is found, there is probably another. With this code we're probably over the fourth.. how many more we'll find?
Also I remember a brief talk with Linus Torvals I had 20 years ago, when I was developing kernel drivers for Linux and he told me the KISS principle. Don't you see this patch breaks the KISS principle?

@SergioDemianLerner : I think you meant to tag @dgenr8 RE: a possible orphan flood attack.

I've been thinking for about a year or so that storing orphan transactions is a bad idea; we could simplify the code if we got rid of mapOrphans and related, and just rely on transaction senders/receivers to rebroadcast transactions that they want mined. KISS

@petertodd I don't have your proposal at hand, can you send me the link? It seems that we're talking about the same. It requires the wallets to do something special, namely sign a small message along the transaction, and broadcast this message, before or after the transaction.

@gavinandresen Re-broadcasting transactions frequently fails when all your peers have a tx but for whatever reason miners don't; need replace-by-fee or similar in that case to ensure everyone re-propagates your tx. For instance #2340 needs to be neutered right now because we don't rebroadcast orphans when we get the block.

@SergioDemianLerner We're talking about different things I think; my scheme doesn't require signing messages of any kind. My proposal was written up here: #3883 (comment)

@gavinandresen +1

@petertodd The mempool janitor PR (#3753) and related issues (#3722, #3723) also handle that, to a certain extent.

@petertodd Your method works by preventing the use of a private key twice. I like it. But it has problems if the user has a single Bitcoin address to receive payments.

My method does not require a hard fork and can be implemented in different ways. Here is one:

First the wallet signs two messages with each private key: the tx and a smallproof msg.
We make 0-conf outputs require anything that today is non-standard, such as pushing dummy 1 value before the signature script.

scriptpub: OP_DROP OP_DUP OP_HASH160 < pubKeyHash > OP_EQUALVERIFY OP_CHECKSIG
scriptsig: < sig > < pubKey > < dummy-val >

So these transaction will not be normally relayed.
Now we add the rule add these transactions ARE relied if the the smallproof message has been previously received.
So the smallproof message "pays" for the transmission of the non-standard tx.
If an attacker wants to send two double-spending txs, he won't be able to "pay" for the transmission of both without creating to colliding smallproofs that will be detected by the merchant.

I think the smallproof idea deserves a more formal presentation because this is not the appropriate place to do it, so I will describe it in more detail in the mailing-list.

@SergioDemianLerner Your method requires a soft-fork to be secure. I could easily make a Bitcoin Core fork that treats those outputs as standard without the smallproof message; Eligius among others would happily accept them. My scriptSig relaying mechanism OTOH works regardless of what policy miners follow, and with scorched-earth, gives them incentives to "defect" and broadcast double-spend proofs to collect even higher fees.

This change has about the smallest footprint possible for what it achieves. KISS.

The problem with an as-yet unimplemented Better Solution is that it is not implemented, or even really designed. If it is implemented, it will be subject to the same level scrutiny, and it sounds like it has a MUCH larger footprint than this one. There will be more bugs, not less. There will be more risks.

I hope no one is giving too much weight to grave accusations being made which turn out to be based on fundamentally flawed assumptions and flawed reading of the actual commits.

This is a small change with outsized positive effects for the network.

These special alert ideas require the cooperation of the creating wallet? tx relay is so much better than that!

Highlighting another advantage that we discovered as we vetted and completed this change -- it works seamlessly with no additional code when a miner decides to spring a double-spend on the world in a block. Let's not be too steeped in technology to remember that we are really trying to influence a REAL WORLD event of handing-over-the-goods. Failure does not occur when the double-spend is confirmed. It occurs when the goods are handed over and the original spend is never eventually confirmed. Failure can be prevented by notification.

@dgenr8 If it works. Proof-of-stake is much better than proof-of-work, aside from that small problem that it doesn't work...

Anyway, modulo the known bugs, I don't see how tx relay is actively harmful given the throttling.

@sipa I agree that we should preserve what 0-conf reliability there is. Relaying does no harm when nodes, including miners, behave in a core-like way.

Trying to keep respends away from non-core-like nodes is a lost cause -- those miners take direct submissions. This should not prevent an effort to alert tx1 recipient, and others watching double-spends.