Best practice for fast transaction acceptance - how high is the risk?

[ShadowOfHarbringer]

What about just having an account with the supermarket or bar? Just load it up before you go shopping or drinking.

Not going to work.

Now imaging today having to transfer money to supermarket's account, just so you can go shopping & drinking.

1. Would you trust such institution with your money (of which not all will be spent) ? I would not.
2. This is not convenient at all

[AmnesicWeasel]

I guess Nefario has a good point about audits being easier with Bitcoins and that is definitely and advantage compared to gold. But it also requires a bunch of people to be vigilant and to understand all the pitfalls of money systems. I'd much rather see these protections against money creation baked into the system that will actually be in use by everyone.

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.

[FatherMcGruder]

1. Would you trust such institution with your money (of which not all will be spent) ? I would not.

I already trust their products.

2. This is not convenient at all

What about keeping an account at a local mutual bank then? Associations of them would allow for instant transactions outside of your locality. You could skip the banks if you had associations of businesses.

[Steve]

That's all an immediate-settlement payment processor is -- an escrow service.

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

[casascius]

To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store...

I think the real danger is that a large mining operator would create a side business selling space in their blocks for these types of intentional double-spends.  When they generate a block they could send a text message to a bunch of people saying "try to spend NOW".

I wonder if there's some way to discourage that kind of anti-social behavior; could the network detect that was being done and "shun" that miner's blocks?

I do not believe there will ever be a scenario where a supermarket accepts Bitcoin and runs the Bitcoin client and broadcasts anything to the block chain.  To me, this danger is sort of like wondering whether we should be bringing pepper spray to combat the risk of getting raped while visiting the moon, or whether we should start a separate sex offender registry for the astronauts in space.

I think many of us agree the Bitcoin P2P network is not scalable enough to sustain the kind of transaction volume that the world's grocery stores would generate.  Millions of dollars worth of groceries are sold every minute - it is silly to expect that every cash register is going to be participating in a block chain that is growing by gigabytes per minute and registering transactions for the entire world's commerce.  The block chain doesn't have room for everybody's Snickers bar purchase, while still keeping it at a size where it could still actually be downloaded.

The only way grocery stores could get on the network would be to have some sort of "MYBITCOIN"-like intermediary that does all the transaction processing, most of which would have to happen off the block chain.

[Gavin Andresen]

The only way grocery stores could get on the network would be to have some sort of "MYBITCOIN"-like intermediary that does all the transaction processing, most of which would have to happen off the block chain.

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

[ShadowOfHarbringer]

1. Would you trust such institution with your money (of which not all will be spent) ? I would not.

I already trust their products.

Well, i don't trust all of supermarket's products. I simply choose the ones i trust from all avaiable.
I certainly know, that they are trying to rip me off with some of them.

2. This is not convenient at all

What about keeping an account at a local mutual bank then? Associations of them would allow for instant transactions outside of your locality. You could skip the banks if you had associations of businesses.

1. Supermarkets creating currency-associations... isn't this too far-fetched ?
2. I would still have to have an account at multiple places/supermarkets since i visit many supermarkets so no, this is far from satisfactory & convenient...
3. The situation when all supermarkets are associated, will simply not happen.

[FatherMcGruder]

The only way grocery stores could get on the network would be to have some sort of "MYBITCOIN"-like intermediary that does all the transaction processing, most of which would have to happen off the block chain.

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

[Mike Hearn]

I'd be very careful about making assumptions about BitCoins non-scalability. See the wiki page I wrote about that. I think it's not at all unimaginable to have all transactions that credit cards handle today handled by BitCoin.

Now many people don't use credit/debit cards to buy groceries (or whatever) but many do ... even if only 10% do, BitCoin can scale with sufficient work to handle all that extra traffic.

[theymos]

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

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.

[Gavin Andresen]

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.

Excellent point.  Although there should be a meta-incentive to make the bitcoin system successful, so there are lots of transactions (and lots of transaction fees for the miners).  Certainly big payment clearing houses that want instant payments to work have the right incentives...

[Mike Hearn]

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.

[casascius]

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?

How about simply rejecting blocks that don't include an appropriate selection of the known transactions (based on age and/or transaction fee)?  If a block arrives that isn't full of known transactions that clearly deserved to be in that block (for reasons other than space and/or tx fee too low, and with a minimum age), miners should work on replacing the block rather than adding to it.  Then there would be no reason to blacklist miners - ones who were trying to exclude specific transactions would, after not too long, not be able to produce blocks that would stick.

[casascius]

The only way grocery stores could get on the network would be to have some sort of "MYBITCOIN"-like intermediary that does all the transaction processing, most of which would have to happen off the block chain.

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

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.

[FatherMcGruder]

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.

Actually, if a service like MyBitcoin conducted a bitcoin transfer with every user's purchase, they'd eventually have empty wallets waiting for confirmations to replenish them. They could get by that if they maintained a queue, but they'd still have to deal with transaction fees. MyBitcoin already probably does it the best way, by keeping minimal wallets and maintaining a ledger.

Anyway, yeah, bitcoin banks would just have to work together and issue cards or mobile apps.

[ByteCoin]

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

[BitterTea]

What are the tradeoffs that resulted in the selection of a 6 blocks per hour target rate?

Block chain size? Network traffic? Just guesses.

[Mike Hearn]

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.

[theymos]

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

This proposal is interesting. It does seem to help against many attacks that assume miners can't be blacklisted.

Some thoughts:
- An attacker could stockpile many valid keys over a long period of time.
- It would slow the network in regaining control after an attack of >50% CPU. Big Bitcoin-based businesses might want to put some machines online in such a case, but they wouldn't be able to do so right away without some sort of pooling.
- The entire network needs to act in a coordinated way to prevent frequent chain splits. However, some section of the network might not get the double-spend transaction.

[Gavin Andresen]

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.

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.