* [Bitcoin-development] Double Spend Notification @ 2013-05-21 0:45 Quinn Harris 2013-05-21 1:24 ` Robert Backhaus 0 siblings, 1 reply; 14+ messages in thread From: Quinn Harris @ 2013-05-21 0:45 UTC (permalink / raw) To: bitcoin-development The current BitCoin implementation is subject to relatively easy double spend attack for 0 confirmation payments. Yet 0 confirmation payments are needed for typical in person transactions like most purchases at a local business. Notably, it is easy to transmit two transactions from the same output at the same time to different sets of nodes on the network by using two instances of bitcoind with same wallet file and a spend on each daemon initiated by RPC by some easy to implement code. If the first attempt to pay the merchant doesn't go through because they received the "wrong" transaction it could be quickly followed up with another initiated spend from a different output switching which daemon sends the transaction the merchant is expecting. This means an unsophisticated attacker can reliably get away with this attack and it would be worth while for small transactions. Given this, I would be reluctant to trust 0 confirmation transactions at all though I think many do in practice. Someone could write and publish a special daemon to execute this attack further reducing the cost. Right now a node will drop any second spend of the same output in the memory pool. After the first transaction has propagated through the network issuing a second double spend transaction isn't likely to be seen by a significant number of miners as most nodes especially non miner nodes will drop this transaction. Today, it is necessary to transmit both transactions on the network nearly simultaneously to reliably get away with this simple attack. If in this case, the receiving end is quickly notified of the double spend this attack becomes more more difficult to get away with. If the second transaction is relayed instead of being dropped to notify the receiving party of the double spend, most miners will receive both transactions and it is possible that some or even many of the miners would replace the first transaction with the second if it has a higher fee as it would be in their short term interest. This can happen some time after the first transaction has propagated through the network so the receiving end wouldn't get a timely notification of the double spend. Depending on the choices of the miners, this approach to double spend notification could exacerbate the very problem it was attempting to fix compared to the current implementation. While miners might continue to drop the second spends, the easy availability of the second spends would increase the short term reward for changing this policy. This problem can be fixed if instead of sending the second transaction a new double spend message is sent with proof of the double spend but not the complete transactions. This would allow the receiving end to be quickly notified of a double spend while in no way increase the chance over the current implementation that a double spend would be successful. The proof of the double spend would include the scriptSig (input) from the original transactions and the hashes from the "simplified" transaction used by OP_CHECKSIG of the scriptPubKey (output) but not the entire transaction. This is the hash computed by the SignatureHash function in script.cpp. The double spend notification message should contain proofs of both signed transaction spending the same output ordered by hash to produce a canonical proof for a specific two transactions. To reduce DOS potential, the proof should not be relayed unless one of the original transactions has been received to ensure there is some commitment to the block chain and different double spend proofs of the same output should not be relayed. The forwarding of transactions should remain exactly the same as it is now where the second transaction is dropped but a double spend message is transmitted if appropriate. The existing block chain needs to be checked to make sure the proof of double spend couldn't have been derived from the block chain and a single spend in the memory pool. This could happen if there was already an identical transaction in the block chain. This would typically only happen if someone was paying someone else the same amount they had before and neither side changed addresses. In this case double spend detection wouldn't be reliable as it could be generated by anyone, but both the sending and receiving client could detect this situation and warn the user. It would still be possible for an attacker to send the second transaction directly to powerful miners but this is a distinctly less viable attack than the current double spend attack. I would expect this double spend notification implementation to make double spends more costly than they are worth for most cases today that 0 confirmation acceptance is needed. That said over time this provision might become less effective. As the reward for each block mined decreases, transactions fees will become a more significant part of the mining reward accordingly increasing the incentive to replace transactions with higher fees. Today most BitCoin participants have a high expectation of significant future appreciation of BitCoins and recognize anything that brings into question the integrity of the system is likely to reduce that future value so they have a long term self interest to keep up the impression of integrity. As BitCoin becomes more establish this incentive will decrease. On the other hand, non mining nodes have no incentive to replace by fee. The continued increased capital costs of mining would likely increase the proportion of non mining nodes typically run by those with an incentive to assure integrity of the network such as merchants. But increasing transaction volume is likely to increase node costs which would push out non mining nodes with lower incentive more than mining nodes. Accordingly increasing block size would have a tendency to reduce the effectiveness of double spend notification. The primary point is there are multiple counteracting forces that make predicting the future effectiveness of double spend notification uncertain. I don't believe this necessary warrants conceding that we can not provide any protection from non trusted 0 confirmations transaction as a replace by fee implementation would do. But it would still be important to work towards more robust solutions notably various forms of 3rd party trust. This could be tamper resistant devices trusted to not duplicate spends, 3rd party certificates with proof the transaction was spent by the holder of the certificate or multi signature transactions on the block chain that must be signed by a trusted 3rd party to spend. I would expect it would take significantly longer for the companies and technologies to be built to implement this on a wide scale than adding double spend proof messages to the current implementation. In addition, there will likely always be some use cases where a 3rd party (centralization) is not viable. Should a BIP and pull request implementing a double spend notification as described be accepted? - Quinn ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 0:45 [Bitcoin-development] Double Spend Notification Quinn Harris @ 2013-05-21 1:24 ` Robert Backhaus 2013-05-21 1:56 ` Pieter Wuille 2013-05-21 3:46 ` Quinn Harris 0 siblings, 2 replies; 14+ messages in thread From: Robert Backhaus @ 2013-05-21 1:24 UTC (permalink / raw) To: Quinn Harris; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 9495 bytes --] Personally, I agree, but a different decision has been made by the main devs. The issue is this: consider two transactions in the unconfirmed pool. One transaction has 2BTC input, 1.5BTC to one address (the payment), .4995 to another address (change) and .0005 standard fee. Another transaction appears - Same input, 1BTC to one address, .999 to another, and .001 fee. Which one would a miner include? On pure self interest, the second one, because it has twice the fee. Anyway, the miner has no real way of knowing which transaction was real, and which the fraudulent double-spend. The network does not keep accurate timestamps, so it has no way of really knowing which is first. A bit of artificial DDOS-type overload on the recipient's system, and the real transaction could easily appear last. So the decision has been made to make 0-conf double spends trivial, so no one will ever trust 0-confs. If a later transaction appears with a larger fee, it will be considered to be the valid one, and the first one dropped, as long as the first one has not been confirmed. This makes undoing a mistaken transaction possible. So anyone needing 0-conf-like speed will have to make other arangements, such as contracting with enough mining pool power to never drop their transactions unless confirmed multiple times. Secure 0-confs is an impossible target with blockchain cyrpto-currencies as the stand. Any ideas on how to make them work are welcome, of course - as long as we haven't heard them too many times before. On 21 May 2013 10:45, Quinn Harris <btcdev@quinnharris•me> wrote: > The current BitCoin implementation is subject to relatively easy double > spend attack for 0 confirmation payments. Yet 0 confirmation payments > are needed for typical in person transactions like most purchases at a > local business. > > Notably, it is easy to transmit two transactions from the same output at > the same time to different sets of nodes on the network by using two > instances of bitcoind with same wallet file and a spend on each daemon > initiated by RPC by some easy to implement code. If the first attempt > to pay the merchant doesn't go through because they received the "wrong" > transaction it could be quickly followed up with another initiated spend > from a different output switching which daemon sends the transaction the > merchant is expecting. This means an unsophisticated attacker can > reliably get away with this attack and it would be worth while for small > transactions. Given this, I would be reluctant to trust 0 confirmation > transactions at all though I think many do in practice. Someone could > write and publish a special daemon to execute this attack further > reducing the cost. > > Right now a node will drop any second spend of the same output in the > memory pool. After the first transaction has propagated through the > network issuing a second double spend transaction isn't likely to be > seen by a significant number of miners as most nodes especially non > miner nodes will drop this transaction. Today, it is necessary to > transmit both transactions on the network nearly simultaneously to > reliably get away with this simple attack. If in this case, the > receiving end is quickly notified of the double spend this attack > becomes more more difficult to get away with. > > If the second transaction is relayed instead of being dropped to notify > the receiving party of the double spend, most miners will receive both > transactions and it is possible that some or even many of the miners > would replace the first transaction with the second if it has a higher > fee as it would be in their short term interest. This can happen some > time after the first transaction has propagated through the network so > the receiving end wouldn't get a timely notification of the double > spend. Depending on the choices of the miners, this approach to double > spend notification could exacerbate the very problem it was attempting > to fix compared to the current implementation. While miners might > continue to drop the second spends, the easy availability of the second > spends would increase the short term reward for changing this policy. > > This problem can be fixed if instead of sending the second transaction a > new double spend message is sent with proof of the double spend but not > the complete transactions. This would allow the receiving end to be > quickly notified of a double spend while in no way increase the chance > over the current implementation that a double spend would be successful. > > The proof of the double spend would include the scriptSig (input) from > the original transactions and the hashes from the "simplified" > transaction used by OP_CHECKSIG of the scriptPubKey (output) but not the > entire transaction. This is the hash computed by the SignatureHash > function in script.cpp. The double spend notification message should > contain proofs of both signed transaction spending the same output > ordered by hash to produce a canonical proof for a specific two > transactions. To reduce DOS potential, the proof should not be relayed > unless one of the original transactions has been received to ensure > there is some commitment to the block chain and different double spend > proofs of the same output should not be relayed. The forwarding of > transactions should remain exactly the same as it is now where the > second transaction is dropped but a double spend message is transmitted > if appropriate. > > The existing block chain needs to be checked to make sure the proof of > double spend couldn't have been derived from the block chain and a > single spend in the memory pool. This could happen if there was already > an identical transaction in the block chain. This would typically only > happen if someone was paying someone else the same amount they had > before and neither side changed addresses. In this case double spend > detection wouldn't be reliable as it could be generated by anyone, but > both the sending and receiving client could detect this situation and > warn the user. > > It would still be possible for an attacker to send the second > transaction directly to powerful miners but this is a distinctly less > viable attack than the current double spend attack. > > I would expect this double spend notification implementation to make > double spends more costly than they are worth for most cases today that > 0 confirmation acceptance is needed. That said over time this provision > might become less effective. As the reward for each block mined > decreases, transactions fees will become a more significant part of the > mining reward accordingly increasing the incentive to replace > transactions with higher fees. Today most BitCoin participants have a > high expectation of significant future appreciation of BitCoins and > recognize anything that brings into question the integrity of the system > is likely to reduce that future value so they have a long term self > interest to keep up the impression of integrity. As BitCoin becomes > more establish this incentive will decrease. > > On the other hand, non mining nodes have no incentive to replace by > fee. The continued increased capital costs of mining would likely > increase the proportion of non mining nodes typically run by those with > an incentive to assure integrity of the network such as merchants. But > increasing transaction volume is likely to increase node costs which > would push out non mining nodes with lower incentive more than mining > nodes. Accordingly increasing block size would have a tendency to > reduce the effectiveness of double spend notification. The primary > point is there are multiple counteracting forces that make predicting > the future effectiveness of double spend notification uncertain. > > I don't believe this necessary warrants conceding that we can not > provide any protection from non trusted 0 confirmations transaction as a > replace by fee implementation would do. But it would still be important > to work towards more robust solutions notably various forms of 3rd party > trust. This could be tamper resistant devices trusted to not duplicate > spends, 3rd party certificates with proof the transaction was spent by > the holder of the certificate or multi signature transactions on the > block chain that must be signed by a trusted 3rd party to spend. I > would expect it would take significantly longer for the companies and > technologies to be built to implement this on a wide scale than adding > double spend proof messages to the current implementation. In addition, > there will likely always be some use cases where a 3rd party > (centralization) is not viable. > > Should a BIP and pull request implementing a double spend notification > as described be accepted? > > - Quinn > > > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 10553 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 1:24 ` Robert Backhaus @ 2013-05-21 1:56 ` Pieter Wuille 2013-05-21 3:27 ` Mike Hearn 2013-05-21 3:54 ` Gregory Maxwell 2013-05-21 3:46 ` Quinn Harris 1 sibling, 2 replies; 14+ messages in thread From: Pieter Wuille @ 2013-05-21 1:56 UTC (permalink / raw) To: Robert Backhaus; +Cc: Bitcoin Dev On Tue, May 21, 2013 at 3:24 AM, Robert Backhaus <robbak@robbak•com> wrote: > So the decision has been made to make 0-conf double spends trivial, so no > one will ever trust 0-confs. If a later transaction appears with a larger > fee, it will be considered to be the valid one, and the first one dropped, > as long as the first one has not been confirmed. This makes undoing a > mistaken transaction possible. This has been suggested, but I know of no such decision having been made. -- Pieter ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 1:56 ` Pieter Wuille @ 2013-05-21 3:27 ` Mike Hearn 2013-05-21 3:39 ` Robert Backhaus 2013-05-21 3:54 ` Gregory Maxwell 1 sibling, 1 reply; 14+ messages in thread From: Mike Hearn @ 2013-05-21 3:27 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1594 bytes --] Indeed, that has been proposed but it's a dumb idea and I'm very sceptical it will go anywhere. Certainly no decision was made. The arguments for it are based on some quite faulty thinking about economics. Double spend notifications have been proposed a long time ago, I believe Matt has indicated some interest in implementing them and that is the right way to go. On 20 May 2013 18:57, "Pieter Wuille" <pieter.wuille@gmail•com> wrote: > On Tue, May 21, 2013 at 3:24 AM, Robert Backhaus <robbak@robbak•com> > wrote: > > So the decision has been made to make 0-conf double spends trivial, so no > > one will ever trust 0-confs. If a later transaction appears with a larger > > fee, it will be considered to be the valid one, and the first one > dropped, > > as long as the first one has not been confirmed. This makes undoing a > > mistaken transaction possible. > > This has been suggested, but I know of no such decision having been made. > > -- > Pieter > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 2213 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 3:27 ` Mike Hearn @ 2013-05-21 3:39 ` Robert Backhaus 2013-05-21 13:06 ` Peter Todd 0 siblings, 1 reply; 14+ messages in thread From: Robert Backhaus @ 2013-05-21 3:39 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2091 bytes --] That's good - what I had taken away from the replace-by-fee discussions was that it was finally decided. My opinion is that we should be doing what we can to make 0-confs as reliable as possible - which will always be 'not very', but a solid system to notify on attempted double-spends is a good start. I'd like to know how Peter Todd's experiment with the 2BTC reward has gone. On 21 May 2013 13:27, Mike Hearn <mike@plan99•net> wrote: > Indeed, that has been proposed but it's a dumb idea and I'm very sceptical > it will go anywhere. Certainly no decision was made. The arguments for it > are based on some quite faulty thinking about economics. Double spend > notifications have been proposed a long time ago, I believe Matt has > indicated some interest in implementing them and that is the right way to > go. > On 20 May 2013 18:57, "Pieter Wuille" <pieter.wuille@gmail•com> wrote: > >> On Tue, May 21, 2013 at 3:24 AM, Robert Backhaus <robbak@robbak•com> >> wrote: >> > So the decision has been made to make 0-conf double spends trivial, so >> no >> > one will ever trust 0-confs. If a later transaction appears with a >> larger >> > fee, it will be considered to be the valid one, and the first one >> dropped, >> > as long as the first one has not been confirmed. This makes undoing a >> > mistaken transaction possible. >> >> This has been suggested, but I know of no such decision having been made. >> >> -- >> Pieter >> >> >> ------------------------------------------------------------------------------ >> Try New Relic Now & We'll Send You this Cool Shirt >> New Relic is the only SaaS-based application performance monitoring >> service >> that delivers powerful full stack analytics. Optimize and monitor your >> browser, app, & servers with just a few lines of code. Try New Relic >> and get this awesome Nerd Life shirt! >> http://p.sf.net/sfu/newrelic_d2d_may >> _______________________________________________ >> Bitcoin-development mailing list >> Bitcoin-development@lists•sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development >> > [-- Attachment #2: Type: text/html, Size: 3138 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 3:39 ` Robert Backhaus @ 2013-05-21 13:06 ` Peter Todd 0 siblings, 0 replies; 14+ messages in thread From: Peter Todd @ 2013-05-21 13:06 UTC (permalink / raw) To: Robert Backhaus; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 961 bytes --] On Tue, May 21, 2013 at 01:39:30PM +1000, Robert Backhaus wrote: > That's good - what I had taken away from the replace-by-fee discussions was > that it was finally decided. > > My opinion is that we should be doing what we can to make 0-confs as > reliable as possible - which will always be 'not very', but a solid system > to notify on attempted double-spends is a good start. > > I'd like to know how Peter Todd's experiment with the 2BTC reward has gone. piuk wrote a double-spender that I think meets the criteria for the reward: https://blockchain.info/create-double-spend I'll get a chance to test it properly when I'm back from vacation, but looks like he's getting the 2BTC. If it does work as intended I'm also planning on doing a demo/video at the next Toronto Bitcoin Meetup to demonstrate the attack in a real-life exchange. -- 'peter'[:-1]@petertodd.org 00000000000000f31f5cd20f915e3edb8e3fceea49580235b984fea63f1f882c [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 490 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 1:56 ` Pieter Wuille 2013-05-21 3:27 ` Mike Hearn @ 2013-05-21 3:54 ` Gregory Maxwell 2013-05-21 4:39 ` Gavin Andresen 2013-05-21 13:05 ` Peter Todd 1 sibling, 2 replies; 14+ messages in thread From: Gregory Maxwell @ 2013-05-21 3:54 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Dev On Mon, May 20, 2013 at 6:56 PM, Pieter Wuille <pieter.wuille@gmail•com> wrote: > On Tue, May 21, 2013 at 3:24 AM, Robert Backhaus <robbak@robbak•com> wrote: >> So the decision has been made to make 0-conf double spends trivial, so no >> one will ever trust 0-confs. If a later transaction appears with a larger >> fee, it will be considered to be the valid one, and the first one dropped, >> as long as the first one has not been confirmed. This makes undoing a >> mistaken transaction possible. > This has been suggested, but I know of no such decision having been made. Indeed. I've argued against it pretty aggressively, but I am starting to find arguments for and against pure fee-based replacement more equally persuasive. Regardless of the eventual outcome, fees today aren't a major motivator vs subsidy and overall network health— and even if some protection isn't 100% there are plenty of cases where the risk is averaged across many small transactions and any reduction of risk is a reduction in operating cost. (No one is going to double spend your soda machine at high speed— so you can like increase your prices by the amount of successful double spends you experience and call it done) On the other hand, it's well established that people underestimate the costs of unlikely risks. More deterministic behavior can result in safer interactions more than _better_ behavior. If we believe that in the long term self-interest will result in pure-fee based replacement being wide spread then it is also good to not build a dependency on behavior that will not last. One point that was only recently exposed to me is that replacement combined with child-pays-for-parent creates a new kind of double spend _defense_: If someone double spends a payment to an online key of yours, you can instantly produce a child transaction that pays 100% of the double spend to fees... so a double spender can hurt you but not profit from it. (and if your side of the transaction is potentially/partially reversible he will lose)... But then again, a race to burn more money is kinda ... odd and even if the benefit of resisting the double spends is only a short term benefit, a short term benefit can be greatly important in encouraging Bitcoin adoption. ... and the long term behavior is far from certain. So at least from my position it's far from clear what should be done here. I've noticed a number of people who seem to be swayed by replace by fee— or at least its inevitability if not value. So even ignoring developers there may evolve a community consensus here regardless of what I think about it. My SO pointed that that the transaction burning race described above sounds like an economists wet dream: it's one of those silly cases they use in experiments to probe human behavior... except it sounds like a possible eventual outcome in systems used by people. Perhaps it would be useful to point some graduate students at this question and see what they can come up with about it. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 3:54 ` Gregory Maxwell @ 2013-05-21 4:39 ` Gavin Andresen 2013-05-21 7:04 ` Gregory Maxwell 2013-05-21 13:05 ` Peter Todd 1 sibling, 1 reply; 14+ messages in thread From: Gavin Andresen @ 2013-05-21 4:39 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev I'm very much in favor of double-spend propagation across the network. Most of the arguments about replace-based-on-fee / child-pays-burn-coins / etc are orthogonal. Letting a merchant know ASAP that their customer is trying to cheat them is, in my opinion, strictly better than what we have now. -- -- Gavin Andresen ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 4:39 ` Gavin Andresen @ 2013-05-21 7:04 ` Gregory Maxwell 2013-05-21 8:08 ` Robert Backhaus 0 siblings, 1 reply; 14+ messages in thread From: Gregory Maxwell @ 2013-05-21 7:04 UTC (permalink / raw) To: Gavin Andresen; +Cc: Bitcoin Dev On Mon, May 20, 2013 at 9:39 PM, Gavin Andresen <gavinandresen@gmail•com> wrote: > I'm very much in favor of double-spend propagation across the network. Absolutely. (to the list:) Is there anyone who is not? (assuming that it doesn't allow arbitrary traffic multiplication, which is easily solved) ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 7:04 ` Gregory Maxwell @ 2013-05-21 8:08 ` Robert Backhaus 0 siblings, 0 replies; 14+ messages in thread From: Robert Backhaus @ 2013-05-21 8:08 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1396 bytes --] Not at all - ACK from me, fwiw. Any attempt at a double spend should be shouted from the housetops. What Miners should do with that is still up for debate, it seems. My opinion is that they should hold on and attempt to confirm the first, letting it go only if a conflicting transaction is mined elsewhere. (Let your Yes mean Yes...) But I understand the contrary arguments. On 21 May 2013 17:04, Gregory Maxwell <gmaxwell@gmail•com> wrote: > On Mon, May 20, 2013 at 9:39 PM, Gavin Andresen <gavinandresen@gmail•com> > wrote: > > I'm very much in favor of double-spend propagation across the network. > > Absolutely. > > (to the list:) Is there anyone who is not? (assuming that it doesn't > allow arbitrary traffic multiplication, which is easily solved) > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 2141 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 3:54 ` Gregory Maxwell 2013-05-21 4:39 ` Gavin Andresen @ 2013-05-21 13:05 ` Peter Todd 2013-05-21 14:26 ` David Vorick 2013-05-21 16:47 ` Quinn Harris 1 sibling, 2 replies; 14+ messages in thread From: Peter Todd @ 2013-05-21 13:05 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2100 bytes --] On Mon, May 20, 2013 at 08:54:25PM -0700, Gregory Maxwell wrote: > One point that was only recently exposed to me is that replacement > combined with child-pays-for-parent creates a new kind of double spend > _defense_: If someone double spends a payment to an online key of > yours, you can instantly produce a child transaction that pays 100% of > the double spend to fees... so a double spender can hurt you but not > profit from it. (and if your side of the transaction is > potentially/partially reversible he will lose)... You can do better than that actually: you can arrange the transaction such that the double-spender is hurt by asking them to pay an excess on top of the initial payment, and having that excess get returned to them in a subsequent transaction. Of course, that's trusting the merchant, but you're trusting the merchant to ship to a product anyway so... A really interesting example for this though would be applications where you are making a deposit. You credit the customer account immediately with half of the deposit amount, allowing them to immediately spend that portion for something transferable. (perhaps an alt-coin) If the customer tries to double-spend you burn half to fees, still leaving the other half to pay for what they did spend. If they don't double-spend, the rest of the balance becomes available after n confirmations. A BTC->alt-coin exchange could use this mechanism for instance, although it only works with widespread replace-by-fee adoption; blockchain.info's shared-send service is another application, as is SatoshiDice. (the failed bet tx can be the refund) What's nice here is even if the customer tries to pay a miner to do the dirty work, a short-term rational miner still has an incentive to screw over the customer by accepting the merchant's double-spend. Now the customer can promise the miner future business, but they've shown themselves to be dishonest... how much honor is there among thieves? -- 'peter'[:-1]@petertodd.org 00000000000000f31f5cd20f915e3edb8e3fceea49580235b984fea63f1f882c [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 490 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 13:05 ` Peter Todd @ 2013-05-21 14:26 ` David Vorick 2013-05-21 16:47 ` Quinn Harris 1 sibling, 0 replies; 14+ messages in thread From: David Vorick @ 2013-05-21 14:26 UTC (permalink / raw) Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 5912 bytes --] I've been wondering why a blockchain is necessary at all. Ripple doesn't have one (I haven't looked closely at their implementation but it seems reasonable to go without one). When you do blockchain based transaction confirmations, you give full authority to the miner that finds the transaction block. That miner gets to decide which transactions are real and which transactions are fraudulent, and even has the option to not include any particular transaction (maybe they used dirty coins, or something like that). The advantage to using a blockchain is that any tough decisions to choose between two conflicting transactions can be decided in an easy manner. The person who finds the next block picks their favorite and tells everybody else. But this has a huge downside: network confirmation can take more than 10 minutes (for an unlucky block). If you really want to be certain, a confirmation can take more than an hour (multi-block confirmations). For a transaction with no conflict, the network should be able to confirm the transaction within a few seconds, because the information can propagate to all of the nodes that quickly. The new issue is that if conflicting transactions appear on opposite sides of the network, there needs to be some way for the network to determine which transaction gets priority. Right now the method is to wait for a miner to find a block and then go with his decision, but perhaps there's some way to resolve a double spend conflict without waiting for a block. All you really need is for 51% of the nodes in the network to confirm a transaction as legitimate in order for it to be 'confirmed' by the entire network. Malicious nodes (nodes that confirm both conflicting transactions, or nodes that refuse to confirm a transaction even though there are no conflicts) can be excommunicated. The two challenges then would be 1. telling everybody when a transaction has hit 51% confirmation 2. dealing with a triple-or-more spend: A has 25% confirmation, B has 40% confirmation, C has 35% confirmation, who wins? For the first problem, each node only needs to see the transaction twice: once when the node sees it for the first time and confirms it, and a second time after the transaction hits 51% and is announced to the network as confirmed. The first node to see the transaction hit 51% will make the announcement. The second problem could be reduced to a majority-wins problem. If a node sees that 94% of votes are in, and one of the transactions is more than 6% ahead of the others, that transaction is the winner. If for whatever reason a clear majority is not hit by the time the next mining block is found, the miner could just choose the transaction that had the most votes when it saw it. It may be outdated but would clear up any issues. This delay would only occur for a transaction if the spender of the coins was attempting a double spend, and would indicate dishonesty to the merchants. They could then choose to wait and see if their account is the winner or they could just refuse to give out their goods. On Tue, May 21, 2013 at 9:05 AM, Peter Todd <pete@petertodd•org> wrote: > On Mon, May 20, 2013 at 08:54:25PM -0700, Gregory Maxwell wrote: > > One point that was only recently exposed to me is that replacement > > combined with child-pays-for-parent creates a new kind of double spend > > _defense_: If someone double spends a payment to an online key of > > yours, you can instantly produce a child transaction that pays 100% of > > the double spend to fees... so a double spender can hurt you but not > > profit from it. (and if your side of the transaction is > > potentially/partially reversible he will lose)... > > You can do better than that actually: you can arrange the transaction > such that the double-spender is hurt by asking them to pay an excess on > top of the initial payment, and having that excess get returned to them > in a subsequent transaction. Of course, that's trusting the merchant, > but you're trusting the merchant to ship to a product anyway so... > > A really interesting example for this though would be applications where > you are making a deposit. You credit the customer account immediately > with half of the deposit amount, allowing them to immediately spend that > portion for something transferable. (perhaps an alt-coin) If the > customer tries to double-spend you burn half to fees, still leaving the > other half to pay for what they did spend. If they don't double-spend, > the rest of the balance becomes available after n confirmations. A > BTC->alt-coin exchange could use this mechanism for instance, although > it only works with widespread replace-by-fee adoption; blockchain.info's > shared-send service is another application, as is SatoshiDice. (the > failed bet tx can be the refund) > > What's nice here is even if the customer tries to pay a miner to do the > dirty work, a short-term rational miner still has an incentive to screw > over the customer by accepting the merchant's double-spend. Now the > customer can promise the miner future business, but they've shown > themselves to be dishonest... how much honor is there among thieves? > > -- > 'peter'[:-1]@petertodd.org > 00000000000000f31f5cd20f915e3edb8e3fceea49580235b984fea63f1f882c > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > [-- Attachment #2: Type: text/html, Size: 7093 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 13:05 ` Peter Todd 2013-05-21 14:26 ` David Vorick @ 2013-05-21 16:47 ` Quinn Harris 1 sibling, 0 replies; 14+ messages in thread From: Quinn Harris @ 2013-05-21 16:47 UTC (permalink / raw) To: bitcoin-development What if a transaction is tagged as eligible for replace by fee possibly using the lock_time (0xFFFFFFFE) so the parties involved can decide which approach works best for them. If the receiving side doesn't see the type of transaction they want they consider it invalid. The payment protocol can be used to negotiate which method should be used. If lock_time is final as it is now for all standard transactions, the current behaviour for transaction propagation would be kept with the addition of double spend proof notifications as I described. But if the transactions are tagged appropriately, they would be replaced by fee. In the recommended implementation, once a node sees a transaction that is not eligible to be replaced by fee it would treat all successive transactions that way despite the tag. This shouldn't hurt merchants that wish to use just double spend notification while still enabling replace by fee for those who think it is preferred. I do find the burn coins and buyer pays twice with a merchant refund to be compelling solutions, but you can't always trust the merchant (face to face street merchant). Also, there is a short window of time were a block can be mined before the burn coin counter measure is received. It is isn't guaranteed this will work better than current behaviour with double spend notification especially considering notification don't cost the merchant when it works. - Quinn ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Bitcoin-development] Double Spend Notification 2013-05-21 1:24 ` Robert Backhaus 2013-05-21 1:56 ` Pieter Wuille @ 2013-05-21 3:46 ` Quinn Harris 1 sibling, 0 replies; 14+ messages in thread From: Quinn Harris @ 2013-05-21 3:46 UTC (permalink / raw) To: Robert Backhaus; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 12696 bytes --] A part of my reason for sending this email was a quick discussion I had with Gavin at the BitCoin conference. I was under the strong impression that double spend notification was something he approved of and was considering implementing himself. In the case of a double spend, If the receiving end gets a timely notification (few seconds) it isn't that important that any one of the two (or more) transactions is chosen over another. The receiving side can treat a double spend as a failed transaction as it should be proof that the buyer is acting maliciously or has had their private keys compromised. I am aware Peter Todd has implemented replace by fee and is operating a node on testnet doing this. I think he is rightly pointing out that the current behaviour of dropping all second spends is based largely on the good will of nodes and can absolutly contradict the perceived self interest of those running miners. Accordingly relying on this behaviour can be precarious. It was from reading his emails to this list or bitcointalk that I recognized how essential it was to not transmit the second transaction if double spend notification had any hope of being worth much. This is controversial because reliable 0-conf transactions are desirable but as you said there really is no way to ensure significant integrity in a decentralized way. Replace by fee would make what transactions get into blocks more predictable and eliminate any expectation of reliable 0 conf transactions. The question is if this consistency is a better choice than a double spend notification that is far from perfect but today its still useful and in practice can probably be trusted as much as credit cards. A more strict version of replace by fee could be implemented that only replaces transactions with ones that don't reduce any output quantity and accordingly require introducing a new input. This would allow increasing transaction fees on a transaction without hurting someone who trusted a 0 conf transaction. This seems like feature bloat to me but it wouldn't reduce 0 conf integrity. Unfortunately, I don't see a way to make everyone happy on this issue. Though, I expect everyone would either prefer double spend notification or always replace by higher fee over what we have now. - Quinn On 05/20/2013 07:24 PM, Robert Backhaus wrote: > Personally, I agree, but a different decision has been made by the > main devs. > > The issue is this: consider two transactions in the unconfirmed pool. > One transaction has 2BTC input, 1.5BTC to one address (the payment), > .4995 to another address (change) and .0005 standard fee. Another > transaction appears - Same input, 1BTC to one address, .999 to > another, and .001 fee. Which one would a miner include? On pure self > interest, the second one, because it has twice the fee. Anyway, the > miner has no real way of knowing which transaction was real, and which > the fraudulent double-spend. The network does not keep accurate > timestamps, so it has no way of really knowing which is first. A bit > of artificial DDOS-type overload on the recipient's system, and the > real transaction could easily appear last. > > So the decision has been made to make 0-conf double spends trivial, so > no one will ever trust 0-confs. If a later transaction appears with a > larger fee, it will be considered to be the valid one, and the first > one dropped, as long as the first one has not been confirmed. This > makes undoing a mistaken transaction possible. > > So anyone needing 0-conf-like speed will have to make other > arangements, such as contracting with enough mining pool power to > never drop their transactions unless confirmed multiple times. Secure > 0-confs is an impossible target with blockchain cyrpto-currencies as > the stand. Any ideas on how to make them work are welcome, of course - > as long as we haven't heard them too many times before. > > > On 21 May 2013 10:45, Quinn Harris <btcdev@quinnharris•me > <mailto:btcdev@quinnharris•me>> wrote: > > The current BitCoin implementation is subject to relatively easy > double > spend attack for 0 confirmation payments. Yet 0 confirmation payments > are needed for typical in person transactions like most purchases at a > local business. > > Notably, it is easy to transmit two transactions from the same > output at > the same time to different sets of nodes on the network by using two > instances of bitcoind with same wallet file and a spend on each daemon > initiated by RPC by some easy to implement code. If the first attempt > to pay the merchant doesn't go through because they received the > "wrong" > transaction it could be quickly followed up with another initiated > spend > from a different output switching which daemon sends the > transaction the > merchant is expecting. This means an unsophisticated attacker can > reliably get away with this attack and it would be worth while for > small > transactions. Given this, I would be reluctant to trust 0 > confirmation > transactions at all though I think many do in practice. Someone could > write and publish a special daemon to execute this attack further > reducing the cost. > > Right now a node will drop any second spend of the same output in the > memory pool. After the first transaction has propagated through the > network issuing a second double spend transaction isn't likely to be > seen by a significant number of miners as most nodes especially non > miner nodes will drop this transaction. Today, it is necessary to > transmit both transactions on the network nearly simultaneously to > reliably get away with this simple attack. If in this case, the > receiving end is quickly notified of the double spend this attack > becomes more more difficult to get away with. > > If the second transaction is relayed instead of being dropped to > notify > the receiving party of the double spend, most miners will receive both > transactions and it is possible that some or even many of the miners > would replace the first transaction with the second if it has a higher > fee as it would be in their short term interest. This can happen some > time after the first transaction has propagated through the network so > the receiving end wouldn't get a timely notification of the double > spend. Depending on the choices of the miners, this approach to > double > spend notification could exacerbate the very problem it was attempting > to fix compared to the current implementation. While miners might > continue to drop the second spends, the easy availability of the > second > spends would increase the short term reward for changing this policy. > > This problem can be fixed if instead of sending the second > transaction a > new double spend message is sent with proof of the double spend > but not > the complete transactions. This would allow the receiving end to be > quickly notified of a double spend while in no way increase the chance > over the current implementation that a double spend would be > successful. > > The proof of the double spend would include the scriptSig (input) from > the original transactions and the hashes from the "simplified" > transaction used by OP_CHECKSIG of the scriptPubKey (output) but > not the > entire transaction. This is the hash computed by the SignatureHash > function in script.cpp. The double spend notification message should > contain proofs of both signed transaction spending the same output > ordered by hash to produce a canonical proof for a specific two > transactions. To reduce DOS potential, the proof should not be > relayed > unless one of the original transactions has been received to ensure > there is some commitment to the block chain and different double spend > proofs of the same output should not be relayed. The forwarding of > transactions should remain exactly the same as it is now where the > second transaction is dropped but a double spend message is > transmitted > if appropriate. > > The existing block chain needs to be checked to make sure the proof of > double spend couldn't have been derived from the block chain and a > single spend in the memory pool. This could happen if there was > already > an identical transaction in the block chain. This would typically > only > happen if someone was paying someone else the same amount they had > before and neither side changed addresses. In this case double spend > detection wouldn't be reliable as it could be generated by anyone, but > both the sending and receiving client could detect this situation and > warn the user. > > It would still be possible for an attacker to send the second > transaction directly to powerful miners but this is a distinctly less > viable attack than the current double spend attack. > > I would expect this double spend notification implementation to make > double spends more costly than they are worth for most cases today > that > 0 confirmation acceptance is needed. That said over time this > provision > might become less effective. As the reward for each block mined > decreases, transactions fees will become a more significant part > of the > mining reward accordingly increasing the incentive to replace > transactions with higher fees. Today most BitCoin participants have a > high expectation of significant future appreciation of BitCoins and > recognize anything that brings into question the integrity of the > system > is likely to reduce that future value so they have a long term self > interest to keep up the impression of integrity. As BitCoin becomes > more establish this incentive will decrease. > > On the other hand, non mining nodes have no incentive to replace by > fee. The continued increased capital costs of mining would likely > increase the proportion of non mining nodes typically run by those > with > an incentive to assure integrity of the network such as merchants. > But > increasing transaction volume is likely to increase node costs which > would push out non mining nodes with lower incentive more than mining > nodes. Accordingly increasing block size would have a tendency to > reduce the effectiveness of double spend notification. The primary > point is there are multiple counteracting forces that make predicting > the future effectiveness of double spend notification uncertain. > > I don't believe this necessary warrants conceding that we can not > provide any protection from non trusted 0 confirmations > transaction as a > replace by fee implementation would do. But it would still be > important > to work towards more robust solutions notably various forms of 3rd > party > trust. This could be tamper resistant devices trusted to not > duplicate > spends, 3rd party certificates with proof the transaction was spent by > the holder of the certificate or multi signature transactions on the > block chain that must be signed by a trusted 3rd party to spend. I > would expect it would take significantly longer for the companies and > technologies to be built to implement this on a wide scale than adding > double spend proof messages to the current implementation. In > addition, > there will likely always be some use cases where a 3rd party > (centralization) is not viable. > > Should a BIP and pull request implementing a double spend notification > as described be accepted? > > - Quinn > > > > ------------------------------------------------------------------------------ > Try New Relic Now & We'll Send You this Cool Shirt > New Relic is the only SaaS-based application performance > monitoring service > that delivers powerful full stack analytics. Optimize and monitor your > browser, app, & servers with just a few lines of code. Try New Relic > and get this awesome Nerd Life shirt! > http://p.sf.net/sfu/newrelic_d2d_may > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > <mailto:Bitcoin-development@lists•sourceforge.net> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > [-- Attachment #2: Type: text/html, Size: 17089 bytes --] ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2013-05-21 16:48 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-05-21 0:45 [Bitcoin-development] Double Spend Notification Quinn Harris 2013-05-21 1:24 ` Robert Backhaus 2013-05-21 1:56 ` Pieter Wuille 2013-05-21 3:27 ` Mike Hearn 2013-05-21 3:39 ` Robert Backhaus 2013-05-21 13:06 ` Peter Todd 2013-05-21 3:54 ` Gregory Maxwell 2013-05-21 4:39 ` Gavin Andresen 2013-05-21 7:04 ` Gregory Maxwell 2013-05-21 8:08 ` Robert Backhaus 2013-05-21 13:05 ` Peter Todd 2013-05-21 14:26 ` David Vorick 2013-05-21 16:47 ` Quinn Harris 2013-05-21 3:46 ` Quinn Harris
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox