Bitcoin Forum

Scenario: You, as a merchant, would like to allow for quick payment with Bitcoins - for example at a supermarket - and therefore can't wait around for one or several confirmation blocks. Instead, you receive the transaction, broadcast it to nodes you know and wait for a couple of seconds to see if you notice any double-spend attempts. If not, you accept the payment right away.

I know that this scenario has been discussed already to some extend in the snack machine thread (http://bitcointalk.org/index.php?topic=423.msg3647#msg3647 (http://bitcointalk.org/index.php?topic=423.msg3647#msg3647)) but it went a little off-topic there I thought, with people suggesting central or semi-central solutions to accomplish this. Central solutions are what we have today, they are not the answer. Whatever is needed to do fast transaction confirmation will need to be decentral.

In any case, I would like to hear your thoughts and attack scenarios on the procedure outlined above. How high is the risk of accepting transactions in this way? My assumption is, that the attacker does not have more than 50% of the CPU power of the network available to him, but might be able to control a large number of IP addresses.

Once the transaction is broadcasted to all nodes, they will start working on including it in the next block. The attacker can not outpace that (see assumption) so his only chance is to get his double-spend transaction to spread through the network faster and thus have more nodes working on including his second transaction. In that case though, I - as the merchant - will also receive the second transaction in a matter of seconds and notice the double-spend attempt. So I can only think of one attack scenario: The attacker controls a large number of IP addresses and - after waiting for a while - hopes that I am only connected to nodes controlled by the attacker. The attacker is now free to selectively forward transactions from the rest of the network to me and thus be able to prevent me from seeing the double-spend transaction too early.

Is this really the only attack scenario? Am I missing other risks that I would expose myself too?

You need >50% of the computational power to get 6 confirmations. For 1 confirmation, 1% of CPU power will give you about a 1% chance of being able to reverse the transaction, regardless of how well the original transaction propagated.

If the attacker can't do that, then broadcasting and waiting a few seconds does give a good chance that there will be no double-spending. However, nodes will not relay transactions they consider bad, so you might not see bad transactions until they're in a block. This is why a centralized "super node" with many connections is desired. And Bitcoin doesn't currently warn you about double-spends, anyway.

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.

In the current Bitcoin scheme, one can't accept transactions until it has been incorporated into a block. Suppose two transactions "spending the same coins" enter the network at different points. On average, half the network will have one transaction and half the other. The only way out of this deadlock is which happens to make it into a block first. So you can see that the race across the network is unimportant but the race to get into a block is the deciding factor.

Hal's attack above would yield a reliable income.

ByteCoin

Presumably, a commercial bitcoin payment processor would spend the bucks to enter the network at a wide array of points, implementing their own double-spending detection and prevention.

This is my own presumption. One may, in a sense, view modern credit cards as a secondary currency backed by and pegged to e.g. USD. "Bitcoin credit cards" would, I expect, be the same.

The current situation blinds people to the fact that eventually, most BTC users would likely not be concerned with things like "addresses" and "blocks", they would use credit cards, bank accounts, etc. not terribly unlike they do now, trusting (hah) the finanical institutions to get it right in the background, as they have historically.

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.

This gets rid of the need to worry about doublespending or any of those other problems, and changes to the question of "do I trust the system provider to have all the bitcoins he says he has?"

just pay the fee

That does nothing to solve the problem of standing in a grocery store waiting up to 10+ minutes for a new block to be generated. This is not a problem one can solve by blindly throwing money at it.

We could update bitcoin client with the following modifications:
- if 2 double-spend transactions received within 20 seconds of each other ==> ordering unknown. Accept blocks with either transaction, and build on top of the longest chain. (Current implementation)
- if 2 double-spend transactions received more than 20 seconds apart ==> ordering known. Reject all blocks that include the later, non-original transaction(s). Do not build on top of the rejected block.
- stop rejecting blocks containing double-spend transactions if the block receives 6 confirmations (to prevent a permanent chain fork)
- clients should relay double spend transactions to alert the recipients that there was a double spend attempt.

If we do this, then fast payments will be possible using the method laid out by the original poster.

My thinking is that the amount of resources you would have to amass to pull off double spending means that it isn't going to be profitable to attempt such a thing for a few transactions of small value.  In fact, I think the transactions would need to be on the order of $10k or more in value for it to be worthwhile...in which case waiting a little while for the transaction to confirm won't be a problem.  And, as others have said, peripheral networks that clear instantly and centrally and are backed btc are likely to arise.  In fact, the various exchanges are already good examples of that (as is youtipit)...you deposit your btc in a trading account and trust they don't run off with the money (and trades settle instantly).

So, I guess in a nutshell, I think this is a non-issue (though it is certainly worthwhile to explore the topic in depth).

Thx for your input! A few comments and questions (sorry, long post):


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.


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.


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?


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

What makes you think you've given anything up? You can still move bitcoins around yourself through the network. All we're saying is that high-speed, on-the-spot transactions will still need a trusted third party to facilitate.

So long as people are capable of evil, various forms of escrow services will continue to exist. That's all an immediate-settlement payment processor is -- an escrow service.

It is an important point about sites "backed" with bitcoin, that like many bank in history cheat, and issue more currency than they have backing for.

The reason banks can easily do this is (originally) gold was kept in a vault, and it's existence could not be verified by any outsider.

But bitcoins are digital, we can instantly audit for the presence of bitcoins, so that as soon as the "bank" started inflating we would know.

At the moment we dont have any payment system backed by bitcons like this, but one of the requirements for my trust is instant auditing and verification. An outside auditor can be used, where at the end of the trading day to bank sends all their bitcoins to an address the auditor has, auditor confirms the presence of said bitcoins, signs with their privste key a certificate for that day. As long as you trust the auditor this works. You could even have multiple auditors.

It does not eliminate the risk, but reduces it, making it much more difficult and expensive to commit fraud.

Ideally, a supermarket is going to be using a payment device like a credit card machine, which will interact with a payment processor like MYBITCOIN that can capture the funds and hold them immediately.

There is already a pretty strong consensus that having every bitcoin node be a full node is unscalable and unsustainable, so to me, the problem of how fast a grocery store can prevent a double spend in the current client is moot.

Since I have a SDK for a very popular payment platform, I've been tempted to sell a few of the devices for BTC and see if the open source community could come up with a way to compile to them based on anecdotal information I can share without pirating the SDK.  (These devices use ARM processors and the proprietary OS has been made to be as POSIX-like as possible, so this isn't too unimaginable... plus much of the hardware inside is third party and full specs can be obtained freely)

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?

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

I can also move my gold around today. But my salary is paid in a currency that isn't backed and so is everyone's salary around me, so the gold doesn't really help in preventing a crash.

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.

I think that was Joe's suggestion: if a block shows up that turns one or more previously-broadcast transactions into double-spends, you don't count it. Maybe we could give it a negative difficulty penalty, so that the block chain with this block would have lower cumulative difficulty than without it; that way it would stay an orphan and not be added to the chain. Then if it was all a big mix-up and other nodes kept building on this one, eventually they would overcome the negative difficulty and it would be accepted, as Joe proposed with his 6-block rule.

Obviously changing the voting rules like this would need careful analysis.

Maybe another example of why a node should be suspicious of blocks that contain transactions it hasn't seen before. I thought joe had a good suggestion in this regard:


This sounds like an interesting idea to me. It would change the rule 'nodes work on the longest chain' to 'nodes work on the longest chain which doesn't include transactions they consider invalid' (with the important exception mentioned by joe that a chain that is 6 blocks longer can convince the node that the transactions are in fact valid).

What are possible problems with this? I guess it would make the network vulnerable to an attack which slows down block creation: Different parts of the network could be fed conflicting transactions and the block chain would then start to split up as nodes only work on what they consider the valid transactions. This would continue for a while as now 6 blocks are needed to break the tie and a single part of the network needs to produce all of them. Pretty big vulnerability I guess - any way around this?

[Edit: Didn't mean to ignore Hal's response, only saw it after posting]

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

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.

I already trust their products.

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

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.

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

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.


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.

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

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.

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

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.

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.

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.

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

Block chain size? Network traffic? Just guesses.

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.

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.

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.

I feel most scaling-related discussions seems to gravitate toward the network needing "supernodes", maybe not in name but in practice anyway. Supernodes very efficiently spread data across the network, for one, and they make it much less likely we will have too many hops.

The problem with these of course are trust, its easy to control the network if you control too much cpu-power or connections.

In the future, large corporations & countries are likely to become such supernodes.
And competition between them should guarantee BTC network neutrality & independence.

There also will be other super-powerful nodes of hardcore geeks, hackers & "cyber-freedom-fighters", so i don't think that any of the major players will be able to take over most of the network for himself, not for long at least.

OK, you're right, the requirement that you didn't see the double spend transaction in the block yet does seem to solve this.

The only thing that bugs me is what if there's a race condition such that I can overlap this with the discovery of a new block. Thinking out loud here. Let's say I directly connect to as many mining nodes as possible. I can create two transactions, A->X and A->Y and pick one transaction for half the nodes, another for the other half. I then send all those transactions simultaneously. Chances are good half the nodes end up with A->X in their memory pool/rejecting A->Y from their peers and vice-versa, because relaying a transaction involves verifying it and that's kind of slow. So chances are good I can get my transactions to nodes before they send it on to each other.

This doesn't help me directly because in the next time period, all nodes will talk to each other and observe that there was a double spend attempt on coin A. They'll drop the other transaction but record the fact that they saw it, so when they see a block that picks one of them randomly that won't be treated as suspicious.

But what if I have lots and lots of coins and constantly repeat this attack. Eventually I'll overlap with the discovery of a new block. That is, in the time after nodes accepting the tx I sent them, and before they complete the inv handshake and send each other the new transaction, a node discovers a block and broadcasts it. Now that nodes peers will receive a block containing a double spend transaction they did not see before and reject it at suspicious. The propagation of the block won't continue and progress will be halted.

I'm not sure this is really a practical attack. For one I'd need lots of coins. For another, perhaps it can be solved by just saying that nodes should always relay blocks even if they find them to be suspicious. In the time period during which the block is moving between the solving node and its peers, everyone else is exchanging the new set of transactions I generated so if the block propagates everywhere anyway, most nodes will accept it. The nodes next to the solving block will split onto a side chain temporarily, but everyone else will build upon the new block correctly.

I have given this problem of fast transaction acceptance also a lot of thought, and up to now the only solution with the current transactions is that you have to wait for at least a few block confirmations to be sure the transaction will never be undone (if you have no trust in the other person sending you the coins).
So changing the block generation rate doesn't really help if you need to wait several minutes (instead of 1 hour) at the store before you can leave with your newly bought goods.

Adding the factor of trust or some centralized node/unit/trusted party is against the nature of the whole system, so I think that path should be abandoned too.
I think the way to go is to start using the crypto (= signing) power of the system, on which in fact relies the whole bitcoin idea !

So I was thinking is the following direction (see also my post on "proton" like payments here: http://bitcointalk.org/index.php?topic=2898.0 (http://bitcointalk.org/index.php?topic=2898.0)):
 

• You have a smartcard that holds in its private area (non readable by the outside world) the private key of one of your bitcoin addresses "A". It also holds the corresponding public key.
• Each (grocery) store has a public bitcoin address easily obtainable (by visiting their website, ...), call it "B"
• You like the store and decide you'll be shopping there in the near future (in 1 hour or later). From your normal PC/smartphone, you send some coins (let us say 100) from your wallet to your bitcoin address "A", with the following output script:

   
Call this transaction "T1". What this means is that the coins can only be spent if a signature of both the grocery store and your smartcard is provided.

• You wait long enough so that "T1" is accepted and burried in enough blocks (let's say 6 confirmations or more, so about 1 hour or more)
• You arrive at the store, do your shopping and pay with your smartcard as follows: you insert the smartcard in a reader, the amount to pay is input (let's say 25 BTC) in the client running at the store, this is displayed on a small display on your smartcard, you push the accept button on your smart card, and the client now sends the necessay data for signing to the smartcard, which returns the signature SA using the private key. The client itself adds its own signature SB so we get as script: <SA> <SB> <pubKey grocery>
• You can leave the store immediately because:
  
  • the bitcoins to spend are already "waiting" with at least 6 confirmations;
  • a double spend is not possible as both parties must sign the transaction at the same time: you cannot spend at another store as that will have another bitcoin address, so the coins can't be transferred to that one, and the store can't claim the coins because it doesn't have your private key to sign in your behalf.
  • the change of 75BTC can be send back to your address (like a standard transaction to "A"), or again to the combination of your card and the store (so you can shop again after this new "T2" transaction has enough confirmations)
  Only issues I see:
   a. You have to prepare "T1" a while before you go shopping (but 1 hour before will be ok, so not a real problem I think);
   b. The coins are "blocked" in a way that you can only spend them in that store. Therefore, a mecanism in the script should be added so that you can reclaim the output all by yourself after some time (for instance by adding some OP_SAFEHEIGHT operator that returns the current block number - y (where y>6) ) and adding an IF clause to the script that says: IF OP_SAFEHEIGHT > 120000 DROP grocery address, so you could reclaim your unspend bitcoins after block 120000+y without the grocery signature.
  
  Of course, a new or modified client is needed to incorporate these kind of transactions, but it could be made a "lightweight" client as it only needs to record these new kind of transactions (which could be tagged with a small "message" like "smartTX" for easy recognition by the client). Would the standard client and miners accept these transactions already ? Or are they rejected because the scripting is non standard ?
  
  Any thoughts ?
  Can these transactions be exploited in some way ?
  

I'm lost.  Who are X and Y?  You're going to spam the network with payments to X == yourself and Y == the corner grocery store in the hopes of... what?

Remember the original attack:
Again, it seems to me some rules that make attempted double-spends more costly to those who attempt to pull off double-spends might be a good idea.

theymos' objection (that there's no real incentive for miners to try to detect/punish double spends) is worth thinking about.  Is there enough "interest in the common good" for miners to spend some CPU cycles so that the bitcoin system as a whole is more robust, or would self-interest lead to a tragedy of the commons where miners do the absolute minimum to just get their blocks accepted?


bfever:  my gut reaction is that the "fast payment problem" won't be solved by more complicated transactions.  And my gut reaction to more complicated transactions is that that the more complicated something is the more likely it is to have security holes....

One more thought:  the "finney attack" can only be profitable if the reward from cheating is greater than (reward of mining times the probability your block will be rejected because you delay announcing it while you "run down to the store").

Reward for block is currently $50, that will (hopefully!) continue to rise for the next decade or two.

Say it takes you 5 minutes to complete a transaction at the corner store (half the average block gen time)... today you'd have to make a $25-or-greater purchase just to break even.

Seems likely this attack will be completely impractical for transactions under $200 when the block reward is worth more than $400.  0-confirmations (just wait N seconds to look for a quick double-spend) for any transaction under $200 seems "good enough" to me.

X and Y are both addresses I control. The point of what I was describing is not to double spend, it's to screw about with the network by exploiting this new idea of rejecting suspicious blocks. As Hal said any change to the voting rules needs really careful thought to avoid opening up exotic attacks, including new types of DoS.

But yeah, just ignoring this problem sounds good to me :-)

That's my conclusion.  One of the websites I'm planning on releasing RSN will feature 0-confirmations.  Average transaction will be ~2 BTC.

I also think people will notice if double-spends start appearing with any frequency.

Many important discussions in this thread. :-) Some more thoughts:


What you are proposing is definitely a nice way of using Bitcoin's feature of additional constraints for transactions, I like it. But your suggestion really just boils down to depositing money somewhere. Either at the grocery store itself or a third party, mybitcoin-like service. And the whole (trust) problem with depositing money has been pointed out before.

I find it worth repeating though ( :-P ): I'm still not convinced that a mybitcoin-like payment processor is something to look forward to. I agree that having it backed by Bitcoins and being easy to audit is a step in the right direction, but that only solves some of the problems with today's central payment processors. You just have to look at the current situation: Even if PayPal was backed by Bitcoins (in theory not too far-fetched), it could still shut down accounts at random and be a headache to deal with. And to those who argue that there could be several mybitcoin-like services which interact with each other: There is also no reason why Google-Checkout couldn't also accept Amazon Payments and then just transfer any outstanding differences directly between Google and Amazon. Doesn't happen though. As soon as a payment processor is big enough, it rather tries to compete than to cooperate.


I have been thinking the same thing, that 10 minutes maybe really is just too much on the conservative side. I mean in terms of money flow the current situation could be kept (seems to work fine right now, so no reason to change it). But instead of 50 BTC per block, there could be 5 BTC per block and then a block every minute. It would allow for a more fine-grained decision on how many confirmations one need. If you want the old level of security you would then just have to wait for 60 blocks.

I guess the block rate has been discussed before frequently and there are many good arguments for the different sides. What this really makes me wonder: Is there even a chance of this ever changing? How would it change? Someone with access to the official repository committing it and releasing it? and would that result in an immediate fork from people who think it's a stupid idea? I wonder if Bitcoin needs some sort of democratic organ to make a decision like that.

First, "potentially forking" changes like that would be structured as:

if (block number < SOME_BLOCK_NUMBER_IN_THE_FUTURE)
  ...old rules
else
  ...new rules

Assuming a super-majority of people agree with the change and upgrade before we get to SOME_BLOCK_NUMBER_IN_THE_FUTURE, the switch will happen smoothly.

Is there a chance of changing?  Sure, but I think anybody who wants to make such a fundamental change would need to do a LOT of testing-- maybe spin up or recruit a few hundred machines all over the world on a test network, have them mine and simulate transactions to each other (ideally with similar volume to the real network) while going through the transition and making sure there weren't any unintended consequences.  And convince a super-majority of people that the benefit of their potentially forking change outweighs the risk of disrupting the network if there's some consequence they didn't think of or that their test network didn't simulate properly.

Practically, would dropping the block time from 10 minutes to 1 minute be worth the risk?  I doubt it.  1-10 minutes (1 would be the average, get unlucky and it could take 10) is still too long to wait for small-value in-person transactions.

RE: democratic organ:  bitcoin is a kind of a democracy.  Whatever code the majority of miners/nodes is running makes the rules.

So far all of this discussion has pointed out one fact to me.  On small transaction sizes these attacks are not worth it.  On larger transactions you can usually wait. 

With cash you can get counterfeits  (I have lost a few $20 bills due to that)
With checks they can bounce (and this is MUCH easier to do then with bitcoin)
With credit cards they can be charged back (while rare, this has happened to most merchants)

I think most people can take the risk of a double spend attack on $50 or less.  You would as a merchant also know (by face at least) the person who did this to you and you would not deal with them again. 

Edit:I should acknowledge http://bitcointalk.org/index.php?topic=3168 where jav advocates something amounting to shunning.

An effective way to discourage double spending attempts would be to propagate both attempted transactions and then "shun" the inputs.

"Shunning" is where the network mutually agrees that it will never accept as valid any transactions or blocks which contain a shunned address or shunned TxOut. If shunning is not unanimous then any transactions by non-participants, which transfer money from a shunned address or use a shunned TxOut as an input to a transaction, are themselves shunned.

In the shunning community, the value of these shunned transactions or addresses can be redistributed among themselves as they wish or (preferably) considered forever gone in an even more irrevocable fashion than if the private key had merely been lost.

If a merchant has accepted a transaction and has handed over the goods before a transaction has been incorporated into a block then it's cold comfort that the double spender's money is shunned after the double spend is detected. The merchant is still owed payment for the goods. The solution is as follows:

Firstly, the merchant should require that the transaction paying him for the goods should be from a TxOut or an address that holds many more bitcoins than the value of the transaction. That is, the "change" portion of the transaction that returns the "unspent" portion of the TxOuts referenced back to the payer should be much larger than the value transferred to the payee. If the payer attempts a double spend then the payer runs the risk that all the bitcoins will be shunned even though the value of the attempted fraud is much lower. This scheme has the advantage that it requires little change to the existing infrastructure.

Optionally, in the event of a double spend, the network could elect to honour the payment part of the transaction and shun the "change". This means that the merchant is not out of pocket while the fraudster is punished. In order to signal which is payment and which is "change", the payer structures the transaction such that the "change" is paid to an address that was also used to sign the crediting transaction. Care needs to be taken with such schemes to make sure that double spending remains uneconomical when the double spender acts in undetectable collusion with one or more of the double-spent merchants.

A supplemental scheme would give the sender feedback about the propagation of the transaction across the network but it involves much more infrastructure change and network traffic. We observe that a minority of miners generate the majority of blocks. If the merchant can see that the transaction has been accepted by these miners then he is confident it will not be double spent. The proof of a miner's power is the number of blocks it generates in a given time. If the generated blocks always credited the same address for a particular miner then we would know who the biggest miners were (at the cost of a big loss of pseudonymity for the miner). The merchant would require that the payer construct a transaction which also requires some proportion of the largest miners to sign that they have received the transaction and will include it in their next block, in return for some fee. When the merchant sees the miner's receipts arrive across the network then he is comfortable handing over the goods.

Note that the last supplemental scheme is tentatively included merely to spark off ideas as it is ugly. I would also warn against shunning as, although simple and powerful it easily results in fragmentation and I feel that the schisms it facilitates could weaken or even destroy Bitcoin.

ByteCoin  

For supermarkets it would seem that there is enough time between deciding to go there and checkout to make sending coins ahead the best solution. A supermarket is no more likely to fail to send your excess bitcoins back than it is to fail to give you the change from your $100 bill after all. However places like gas stations would be much more likely to need a faster solution.

The question of accepting transactions without confirmation is important for a service I'm working on.  I can't require confirmations for only purchases above $50 because a buyer could structure his purchase as two $25 purchases and I'd have no way to detect it.  So given the current Bitcoin network, would something like the following work?

• Generate a new Bitcoin address for the purchase
• Wait for a payment transaction (T) to that address to arrive
• Wait 1 minute for the transaction to propagate through much of the network
• Choose N random nodes in the network
• Ask each one if it knows about T
• Using statistical sampling calculations, determine a confidence level (P) that T is known to all nodes
• if the probable loss from a double-spend is less than the probable profit, the purchase is allowed without confirmations; otherwise, confirmations are required

I admit to knowing little about the technical details of possible double-spend strategies, so can someone point out how this technique could be circumvented?

You're still open to the 'finney attack' described earlier, if whatever you're selling is worth having somebody mine on an ATI 5970 for a while it's possible you could be defrauded. For that attack to work the attacker has to be able to choose the time of his transaction, and you have to accept it very quickly.

As the mining difficulty goes up, this attack becomes harder and harder to pull off. And it's going up very fast right now:

http://bitcoin.sipa.be/speed-lin.png

So I guess you could try and weigh up the cost of defrauding you vs the cost of being able to successfully mine blocks.

I'd suggest re-examining the idea that you can't detect if it's the same user making two smaller transactions to get below the limit. It's rare that a business really can't have any trust in its customers at all.

Thanks [mike].  The new service will have an API for executing purchases, so an attacker could easily choose the time of his attack and execute the purchase very rapidly.  It looks like I'll be waiting for confirmation blocks :)


In my particular case, a customer only needs an email address, so I'm not sure I can do much to prevent transaction splitting without also ruining the experience for legitimate customers.  I'll definitely give it some more thought though.

I don't know if it would be feasible, but here's a proposal for real time confirmation:

http://bitcointalk.org/index.php?topic=4382.0

If it won't work, can you explain why?

Read through all of this and here is the solution to fast transactions without the fear of loss due to double spends.  Simply accept any transaction with the value below REWARD * Gold value/2.  (NOTE: I hate valuing items with no intrinsic value with another item with no intrinsic value - Gold is the real constant here not dollars.)

So long as minners are getting paid fairly for the job they do it's not a problem.

I don't get what gold has to do with fast transactions.
There's no such thing as intrinsic value, but there's no need to discuss it here.
It's being discussed here (http://forum.bitcoin.org/index.php?topic=6392.0) and here (http://forum.bitcoin.org/index.php?topic=30321).

The units don't matter. As long as T<R*(t/10), where T is the value of the transaction, R is the value of the block reward, and t is the time to conduct the transaction in minutes, a seller can safely accept payment at zero transactions. Just make sure that you measure T and R with the same units.

I think the problem here is, that there can potentially be much more than just one double-spent transaction. The incentive for the attacker comes from the combined gain from all duplicate transactions he manages to pull off from addresses he is going to publish within the delayed block - no?
Therefore a seller cannot safely accept payments at zero confirmations - even for very small payments.

Well, it's detectable, no? The ripped-off merchants will complain and we will likely find out (at least if the operation is continued), which pool is the bad guy. (I'm assuming it will be a pool operator doing this side-business). People would leave the pool and therefore harm it, likely more substantially than can be made up through the side business. Therfore pool ops are unlikely to pull this off.

In case of a large solo-miner it's not so simple, because identifying the block source would be a lot harder, especially if he takes precautions (no?) and also because he doesn't suffer any harm from "people leaving the pool". In this case the only option might be to "shun" this miners blocks. Not so easy. The blocks might be detected by using a rogue customer using the "service" and looking for the specific transaction. Unfortunately, it would be easy to identify the rogue customer, because we'd need a way to broadcast this information and the bad guy could listen to that as well and simply block our rogue customer, right? Also there might be possibilities to abuse the system to harm competing miners.

While I can't think of a straightforward way to protect against this kind of anti-social behaviour, I also think this kind of behaviour is currenlty very unlikely to occur. This might change in the future, though.

Note though, that the attacker - depending on the situation - might be able to use multiple small transactions to get around this. So you will need to limit this on a global level, rather than on a per-transaction level. This puts an upper limit on the number of zero-confirmation transactions you can accept in a given time span.

I also don't agree that it can be put in an easy formula like that. It depends on the situation and what kind of service or product is being sold. Especially if the attacker can try lots of times (maybe because it's very easy to refund the product that he bought when the attack wasn't successful), there are some realistic attacks to consider. More thoughts on this can be found in this thread: http://forum.bitcoin.org/index.php?topic=27417.msg347403#msg347403 .

I'm sorry for posting in a zombie thread. Anyone looking for a solution for accepting 0 confirmation payments may check blockcypher api: http://dev.blockcypher.com/reference.html#zero_confirmations

It's not mine but I think it's worth mention here since I was also struggling looking for a simple solution for this matter.

A better way would be to push the TX to the pools themselves.

Once you have a TX sent to you on your node (or you can view it on a block explorer), you have access to the raw, signed TX. You simply copy and paste the raw TX into a form that many pools have to have a particular TX included in the pools next block.

f2pool claims that any TX pushed via it's form will be given priority regardless of fee. (it is always a good practice to only accept a 0/unconfirmed TX if it included an appropriate fee)