What you're asking for is effectively perfect, instantaneous peer-to-peer communications between everyone using the currency at all times. It's just not gonna happen.

In life, you have to trust somebody, at least a little bit, even if that "somebody" is actually the collective consciousness embodied in a few hundred people. People who don't trust anyone at all end up hermits. Technology can't fix that for you.

+1 insightful...however I don't know if I'd call that an escrow service.  Maybe more generally a trusted third party, immediate settlement service (escrow to me generally means you don't want immediate settlement...you need time for both parties and the trusted third party to agree that the exchange of some good or service is satisfactory before settling the payment). 

Immediate payment accounts could have minimal bitcoins on deposit...enough to cover the maximum value of transactions anticipated over some period that would allow for reasonable verification in the bitcoin network.  The accounts might not even need that minimum if the settlement service is comfortable extending momentary credit to the payer for an amount that covers the transaction.  The payee would trust the settlement service.  The payer would make a bitcoin transfer into the settlement account and the settlement service would immediately transfer that amount to the payee.  The payee trusting the settlement service and the settlement service either trusting the payer or requiring the payer to have a prior balance of bitcoin on deposit would allow the entire transaction to be conducted immediately.

Edit: let me add that the three accounts involved are all just regular bitcoin wallets...one the payee controls, one that the trusted third party controls (and is held on behalf of the payer) and one that the payer controls.  Payment goes from the payer wallet to the 3rd party wallet and from the third party wallet to the payee wallet.  Payee trusts that the 3rd party won't double spend and third party trusts that the payer won't double spend (and third party indemnifies the payee against any double spending by the payer).

Right... so then the question is "will the MYBITCOIN-like intermediary be able to verify transactions quickly without opening themselves up to systematic fraud."

Without requiring users to pre-deposit funds with them, because users ain't gonna do that.

Here's another possible simple rule for miners that might work (but, as Hal said, requires Deep Thought):

"When I see a new block with transactions that I didn't see broadcast previously, mark those transactions as suspicious.  If I see double-spends of those transactions, stop building on that block-- assume it is cheating.  Switch to the previous block (or alternate block if there's a block race going on)."

Miners won't try to rip off a grocery store for $50 worth of groceries if doing so makes their $50+ bitcoin reward for finding a block disappear.

This rule would also give miners a strong incentive to detect and refuse to include EITHER side of a double-spend in their blocks (if they get both spends while they're working on the block).

What's to stop a service like mybitcoin from transferring between the wallets it maintains with every supermarket purchase?

There are no incentives for doing that. If 98% of the network "discourages" a block, then those miners have a small chance of losing their blocks to the 2% that does not discourage the block. However, not discouraging a block has no penalty at all.

OK, here's a strawman proposal. Knock it down :-)

The key problem is that of untrustworthy miners. Being able to "shun" miners who are trying to screw with the system would work, if only there was a way to do it. But the problem is how do you make it hard for a shunned miner to re-enter the community under a new identity?

Perhaps proof of work can offer the answer again. If you wanted to start mining, you have to "announce" yourself to the network by solving a difficult proof of work. Much harder than solving a block. Perhaps a few days worth of work with a high end GPU. Or better, somehow self adjusting like the regular chain is.

This PoW is solved over a message containing a public key. Once you find this proof, it is effectively your identity pass for being a miner .... anonymous yet difficult to create. When a miner solves a block, they sign it with their public key before broadcasting it.

If a miner is found to be repeatedly performing what for lack of a better name I'll call the Finney attack, other honest nodes blacklist that public key. Now to do the fraud again, the miner must create a new identity which is hard. This acts as a natural rate limit on how much of this fraud you can do.

It might be possible to retrofit this in a backwards compatible way. The miner announcement PoW could just be a regular block with a hash that is lower than a separate target. The block would contain space in the coinbase data for a block signature and a new public key (it'd have to be different to the coinbase target key as that has to be different every time, to ensure every mining node scans independent keyspace). The signature space would be initialized to zero, the whole block signed, and the sig substituted in. This block is then broadcast as normal.

If a block is received that is not signed by a miner of known good reputation, it is ignored. In this way you have to join the mining club by doing a PoW.

This scheme would not have made sense in the early days of BitCoin when mining was easy and the network needed lots of them. But these days if you aren't serious about mining, you aren't going to get anywhere unless you're in a pool and then it's the pool operators reputation that counts rather than your own anyway.

The way I see it, this is absolutely what would need to happen.

And further, if my merchant account were at MYBITCOIN and your bitcoins were at YOURBITCOIN, chances are good that there'd be an API call between them to "make" the funds transfer, which wouldn't actually transfer on the block chain, but would rather just be added to an IOU tally between the two bitcoin "banks" that was offset by funds travelling the opposite direction (MYBITCOIN to YOURBITCOIN), which got auto-settled in a single bulk transaction via the block chain at the end of the day.

When you start talking about "discouraging" blocks based on whether you think the miner is doing something dishonest you're undermining one of the central mechanisms for stopping the network fragmenting. The rule so far is that the block chain with the highest difficulty wins, full stop. If the rules for whether a block is adopted are changed to something where different bits of the network could have different opinions about the block's suitability based on the transactions they have seen then that's a recipe for network fragmentation.

What you're really trying to do is to get transactions to confirm more quickly which you could do by increasing the block rate target.
What are the tradeoffs that resulted in the selection of a 6 blocks per hour target rate?

ByteCoin

Propagation time for transactions across very large networks is where the 10 minutes came from. I think it's an open question if this was a good choice, but the goal is really to increase certainty for transaction verification in seconds. Even if the block target was reduced to one minute, probability dictates on occasion it could still take an hour, which brings us back to the vending machine thread.

The conclusion from that thread was that for small amounts you could just monitor the network for double spends, and that works, unless there's a Finney attack going on in. It's complicated and very timing dependent but could be problematic for some merchants especially if automated.

Systems that reject blocks based on fixed rules like observed transactions do seem open to exploitation. If a new block is found and broadcast 30 seconds after the previous, and it has none of the transactions you recently observed, does that mean it was prepared in advance for double spending purposes or does that just mean the network is now large enough that it takes longer than 30 seconds to propagate across the network?

Bear in mind that for some very large transactions with lots of inputs or outputs, it could easily take 100msec to verify them, more if the tx ends up in a queue waiting for CPU time. If you're connected to a node on the other side of the world and that node receives a tx with 15 inputs, that's 100 msec to verify, 60 msec to send the inv across the ocean, 60 msec for the node to send the getdata back asking for it, then at least another 60-120msec to transfer the tx across the ocean. Pretty quickly we're up to a third of a second to traverse a single hop. In the pathological case where all nodes end up being far away from each other 100 hops is enough to reach that 30 second limit (of course it's a flood fill in practice).

That time can probably be increased by an attacker who is flooding the network with spam.

Rejecting blocks based on observed double spends also seems problematic. It would let me freeze the block chain by generating lots of double spends  and sending them directly to major miner nodes in random order. Every miner would then generate a block that contained some transactions other nodes would perceive as double spends and so every node would reject the block, allowing me to catch up with the head of the chain.

Rejecting blocks based on manually written (?) blacklists of known bad miner identities is less problematic because there'd be some human oversight. If such a list was signed, distributed centrally, and used in an opt-in basis, the worst case scenario is that the whoever maintains the list somehow ends up adding enough miners to cause a massive drop in network power, allowing an attacker to outrun the chain until news spreads that the blacklist has been compromised and miners opt out.

I think it is a reasonable assumption that major miners will be well-connected with each other.  There is certainly a strong incentive for miners to be well-connected in general (better connected == more likely to win 'block races').

So I don't see how you could freeze the block chain-- if you generate lots of double-spends, the miners will quickly see both of spends and will drop those transactions like hot potatoes.  The "finney attack" only works if the first double-spend is generated by a miner that finds a block and includes it in the block without transmitting it.

Also, my proposal was to only reject blocks containing 'suspicious' transactions that you hadn't seen transmitted that have a double-spend attempt before the next block.