> you can still feel pretty safe with 0 confirmations if you're monitoring the > bitcoin network for double-spend attempts over the average network propagation time

The above is much easier said than done. First, you're assuming you can have a good enough coverage of the network which is hard to assess. You need to do a constant topology analysis to see how well-connected you are. Second, you need to ask a chosen set of peers for all the transactions they have in their pool. And wait until they all reply. Third, you need to be pretty good at normalizing against malleability on all those transactions.

After doing all of this, the scheme is still not bulletproof. The blockchain exists for a reason.

> There are a lot of hidden pitfalls in bitcoin security (such as - the above isn't guaranteed, if miners change their mind to be greedy and pick the transaction with the highest fee instead of the first one, that method breaks) so I'm not sure if it's bulletproof though.

Keep in mind that enabling this also opens up a counter-attack, against double spending: if User A sends 1 BTC to you with a fee of 0.0001 BTC, and you discover that, after sending this transaction to you, he sends the same 1 BTC to another address, this time with a 0.1 BTC fee, you can create a new transaction that spends the 1 BTC originally sent to you (with the 0.0001 BTC fee) which spends everything as a fee in this new transaction.

This way you don't actually get the money, the miners do, but you punish double spending. And if miners are greedy - and want to include whichever transaction makes them the most money - they will want include to include yours, as this makes them a whole 1 BTC in fees.

So in the end, while it may seem that miners including the highest-fee transaction increases the risk of double spending, it might actually prevent it, since merchants will also gain an effective way of punishing it.

Is this actually possible? You couldn't change the original transaction without the private key, nor can you spend the results of it until it is in an accepted block chain block, no? Am I wrong?

You can broadcast a valid tx that depends on an unconfirmed valid tx that was already broadcasted. The second tx will only be confirmed if the first is, this is how betting sites that accept 0conf txs (such as SatoshiDice) work.

Not sure if pool software currently selects txs as a sum of the fees of the txs that depend on them, but it seems reasonable to implement.

As you said, even if the original tx has propagated, a double spending tx with a higher fee will jump the line in a miner's mempool. Never assume miners are altruistic - they seek primarily to maximize their profit. Propogation is a useful heuristic, but its not a panacea.

For most miners at the present time this is not true. The reference code does not do this, and most mining pools are running something close to the reference code. (And furthermore, most such txes will never transit the network in any case, because most nodes will refuse to relay them.)