Thx for your input! A few comments and questions (sorry, long post):
However, nodes will not relay transactions they consider bad, so you might not see bad transactions until they're in a block.
Aw, I see, I wasn't aware of that. Is there a reason why they don't relay those transactions? Would it hurt if they did? (provided that they make sure to first relay valid transactions). It seems this way it's indeed fairly likely to not see a bad transaction until it is in a block.
In the case where nodes don't relay bad transactions, it would actually hurt to sent the transaction out, as it creates a sort of 'wall' just around you and you are fairly likely to not notice anything else. So I guess it would be better then to not send out anything and instead only listen. And even when you receive the transaction, you don't send it out, but wait until _all_ of the nodes you are connected to have relayed the transaction. If - after some time - some of your neighbor nodes haven't done so, you can deduce from that, that they must have heard a conflicting transaction first and are therefore not forwarding the other one. Doesn't help you with Hal's attack though.
So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.
Ok, yes. But when the attacker doesn't have much CPU power he needs to rely on other nodes to include the bad transaction. The more nodes that will be working on that, the better the chances. So in that sense the race across the network is off some importance as it will make it more likely that the transaction wins, which the attacker would like to win.
The best way to ensure a past, instantanious payment is to have another system ( such as a web based payment processor) backed by bitcoin. It would mean users(and spenders) wouldhave to deposit bitcoin to their account first.
I don't find this the "best way" at all. How is this different from a world where everyone has gold, but to allow for fast, instantaneous payments you allow some payment processor - let's call them a bank - to move numbers in their system around instead? And then at some point the whole "gold-backed" thing is conveniently forgotten.
Isn't the whole point of Bitcoin that you can move the _actual_ Bitcoins around. If you are going to give that up, what have you won?
Suppose the attacker is generating blocks occasionally. in each block he generates, he includes a transfer from address A to address B, both of which he controls.
To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store and makes a payment to your address C with his address A. You wait a few seconds, don't hear anything, and transfer the goods. He broadcasts his block now, and his transaction will take precedence over yours.
Ok, that sounds like a pretty realistic attack scenario that isn't too difficult to pull off. So anything that can be done about that without waiting around for 10+ minutes? Maybe something with timestamps? My understanding is that blocks are timestamped and there are some checks regarding the timestamps (
https://en.bitcoin.it/wiki/Block_timestamp). However pretty wide time periods seem to be valid. In a world with with high-speed networks, couldn't that be made a little tighter? So that a 'precomputed' block would quickly become invalid?
One way I look at the Bitcoin network is this: A bunch of nodes want to establish a 'shared reality'. This 'shared reality' says who has how many bitcoins. They find that consensus by - in a way - voting and the more CPU power a node has, the more votes it has. If you look at it from this way, shouldn't there be more mechanisms to ensure that every node knows what is being voted about right now? I know this is hard in a best-effort network with nodes constantly joining and leaving, but might have a lot of potential. I think nodes shouldn't so readily accept a shared reality which contains decisions (transactions) that they haven't even seen before and thus weren't able to vote on.