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

[sandos]

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.

[ShadowOfHarbringer]

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.

[Mike Hearn]

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.

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.

[bfever]

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

• 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:

Code:

OP_DUP OP_HASH160 <B> OP_EQUALVERIFY OP_CHECKSIGVERIFY <public key smartcard> OP_CHECKSIG

   
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 ?
  

[Gavin Andresen]

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.

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'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:

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.

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

[Gavin Andresen]

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.

[Mike Hearn]

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

[jgarzik]

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.

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.

[jav]

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

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 !

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.

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.

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.

[Gavin Andresen]

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.

[Littleshop]

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. 

[ByteCoin]

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  

[Dude65535]

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.

[mndrix]

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?

[Mike Hearn]

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:



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.

[mndrix]

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.

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

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.

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.

[jtimon]

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?

[DavinciJ15]

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.

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.

[jtimon]

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

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

[FatherMcGruder]

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

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.