Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of robbak.com
	designates 209.85.128.177 as permitted sender)
	client-ip=209.85.128.177; envelope-from=robbak@robbak.com;
	helo=mail-ve0-f177.google.com; 
MIME-Version: 1.0
In-Reply-To: <519AC3A8.1020306@quinnharris.me>
References: <519AC3A8.1020306@quinnharris.me>
Date: Tue, 21 May 2013 11:24:22 +1000
Message-ID: <CA+i0-i_+Tes+ePRqmDGEXDQ_L=S5y8gHBKk77zaLgTGOS3OMyA@mail.gmail.com>
From: Robert Backhaus <robbak@robbak.com>
To: Quinn Harris <btcdev@quinnharris.me>
Content-Type: multipart/alternative; boundary=20cf307d04ae1eb9ca04dd304f6c
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Double Spend Notification
Precedence: list

--20cf307d04ae1eb9ca04dd304f6c
Content-Type: text/plain; charset=ISO-8859-1

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
>

--20cf307d04ae1eb9ca04dd304f6c
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div><div>Personally, I agree, but a different decisi=
on has been made by the main devs.<br><br></div>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 a=
ddress, .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, t=
he miner has no real way of knowing which transaction was real, and which t=
he 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&#39;s system, and the real transaction coul=
d easily appear last.<br>
<br></div>So the decision has been made to make 0-conf double spends trivia=
l, 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 d=
ropped, as long as the first one has not been confirmed. This makes undoing=
 a mistaken transaction possible.<br>
<br></div>So anyone needing 0-conf-like speed will have to make other arang=
ements, such as contracting with enough mining pool power to never drop the=
ir transactions unless confirmed multiple times. Secure 0-confs is an impos=
sible target with blockchain cyrpto-currencies as the stand. Any ideas on h=
ow to make them work are welcome, of course - as long as we haven&#39;t hea=
rd them too many times before.<br>
</div><div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On 21 M=
ay 2013 10:45, Quinn Harris <span dir=3D"ltr">&lt;<a href=3D"mailto:btcdev@=
quinnharris.me" target=3D"_blank">btcdev@quinnharris.me</a>&gt;</span> wrot=
e:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">The current BitCoin implementation is subjec=
t to relatively easy double<br>
spend attack for 0 confirmation payments. =A0Yet 0 confirmation payments<br=
>
are needed for typical in person transactions like most purchases at a<br>
local business.<br>
<br>
Notably, it is easy to transmit two transactions from the same output at<br=
>
the same time to different sets of nodes on the network by using two<br>
instances of bitcoind with same wallet file and a spend on each daemon<br>
initiated by RPC by some easy to implement code. =A0If the first attempt<br=
>
to pay the merchant doesn&#39;t go through because they received the &quot;=
wrong&quot;<br>
transaction it could be quickly followed up with another initiated spend<br=
>
from a different output switching which daemon sends the transaction the<br=
>
merchant is expecting. =A0This means an unsophisticated attacker can<br>
reliably get away with this attack and it would be worth while for small<br=
>
transactions. =A0Given this, I would be reluctant to trust 0 confirmation<b=
r>
transactions at all though I think many do in practice. =A0Someone could<br=
>
write and publish a special daemon to execute this attack further<br>
reducing the cost.<br>
<br>
Right now a node will drop any second spend of the same output in the<br>
memory pool. =A0After the first transaction has propagated through the<br>
network issuing a second double spend transaction isn&#39;t likely to be<br=
>
seen by a significant number of miners as most nodes especially non<br>
miner nodes will drop this transaction. =A0Today, it is necessary to<br>
transmit both transactions on the network nearly simultaneously to<br>
reliably get away with this simple attack. =A0If in this case, the<br>
receiving end is quickly notified of the double spend this attack<br>
becomes more more difficult to get away with.<br>
<br>
If the second transaction is relayed instead of being dropped to notify<br>
the receiving party of the double spend, most miners will receive both<br>
transactions and it is possible that some or even many of the miners<br>
would replace the first transaction with the second if it has a higher<br>
fee as it would be in their short term interest. This can happen some<br>
time after the first transaction has propagated through the network so<br>
the receiving end wouldn&#39;t get a timely notification of the double<br>
spend. =A0Depending on the choices of the miners, this approach to double<b=
r>
spend notification could exacerbate the very problem it was attempting<br>
to fix compared to the current implementation. =A0While miners might<br>
continue to drop the second spends, the easy availability of the second<br>
spends would increase the short term reward for changing this policy.<br>
<br>
This problem can be fixed if instead of sending the second transaction a<br=
>
new double spend message is sent with proof of the double spend but not<br>
the complete transactions. =A0This would allow the receiving end to be<br>
quickly notified of a double spend while in no way increase the chance<br>
over the current implementation that a double spend would be successful.<br=
>
<br>
The proof of the double spend would include the scriptSig (input) from<br>
the original transactions and the hashes from the &quot;simplified&quot;<br=
>
transaction used by OP_CHECKSIG of the scriptPubKey (output) but not the<br=
>
entire transaction. =A0This is the hash computed by the SignatureHash<br>
function in script.cpp. =A0 The double spend notification message should<br=
>
contain proofs of both signed transaction spending the same output<br>
ordered by hash to produce a canonical proof for a specific two<br>
transactions. =A0To reduce DOS potential, the proof should not be relayed<b=
r>
unless one of the original transactions has been received to ensure<br>
there is some commitment to the block chain and different double spend<br>
proofs of the same output should not be relayed. =A0The forwarding of<br>
transactions should remain exactly the same as it is now where the<br>
second transaction is dropped but a double spend message is transmitted<br>
if appropriate.<br>
<br>
The existing block chain needs to be checked to make sure the proof of<br>
double spend couldn&#39;t have been derived from the block chain and a<br>
single spend in the memory pool. =A0This could happen if there was already<=
br>
an identical transaction in the block chain. =A0This would typically only<b=
r>
happen if someone was paying someone else the same amount they had<br>
before and neither side changed addresses. =A0In this case double spend<br>
detection wouldn&#39;t be reliable as it could be generated by anyone, but<=
br>
both the sending and receiving client could detect this situation and<br>
warn the user.<br>
<br>
It would still be possible for an attacker to send the second<br>
transaction directly to powerful miners but this is a distinctly less<br>
viable attack than the current double spend attack.<br>
<br>
I would expect this double spend notification implementation to make<br>
double spends more costly than they are worth for most cases today that<br>
0 confirmation acceptance is needed. =A0That said over time this provision<=
br>
might become less effective. =A0As the reward for each block mined<br>
decreases, transactions fees will become a more significant part of the<br>
mining reward accordingly increasing the incentive to replace<br>
transactions with higher fees. =A0Today most BitCoin participants have a<br=
>
high expectation of significant future appreciation of BitCoins and<br>
recognize anything that brings into question the integrity of the system<br=
>
is likely to reduce that future value so they have a long term self<br>
interest to keep up the impression of integrity. =A0As BitCoin becomes<br>
more establish this incentive will decrease.<br>
<br>
On the other hand, non mining nodes have no incentive to replace by<br>
fee. =A0The continued increased capital costs of mining would likely<br>
increase the proportion of non mining nodes typically run by those with<br>
an incentive to assure integrity of the network such as merchants. =A0But<b=
r>
increasing transaction volume is likely to increase node costs which<br>
would push out non mining nodes with lower incentive more than mining<br>
nodes. =A0Accordingly increasing block size would have a tendency to<br>
reduce the effectiveness of double spend notification. =A0The primary<br>
point is there are multiple counteracting forces that make predicting<br>
the future effectiveness of double spend notification uncertain.<br>
<br>
I don&#39;t believe this necessary warrants conceding that we can not<br>
provide any protection from non trusted 0 confirmations transaction as a<br=
>
replace by fee implementation would do. =A0But it would still be important<=
br>
to work towards more robust solutions notably various forms of 3rd party<br=
>
trust. =A0This could be tamper resistant devices trusted to not duplicate<b=
r>
spends, 3rd party certificates with proof the transaction was spent by<br>
the holder of the certificate or multi signature transactions on the<br>
block chain that must be signed by a trusted 3rd party to spend. =A0I<br>
would expect it would take significantly longer for the companies and<br>
technologies to be built to implement this on a wide scale than adding<br>
double spend proof messages to the current implementation. =A0In addition,<=
br>
there will likely always be some use cases where a 3rd party<br>
(centralization) is not viable.<br>
<br>
Should a BIP and pull request implementing a double spend notification<br>
as described be accepted?<br>
<br>
- Quinn<br>
<br>
<br>
<br>
---------------------------------------------------------------------------=
---<br>
Try New Relic Now &amp; We&#39;ll Send You this Cool Shirt<br>
New Relic is the only SaaS-based application performance monitoring service=
<br>
that delivers powerful full stack analytics. Optimize and monitor your<br>
browser, app, &amp; servers with just a few lines of code. Try New Relic<br=
>
and get this awesome Nerd Life shirt! <a href=3D"http://p.sf.net/sfu/newrel=
ic_d2d_may" target=3D"_blank">http://p.sf.net/sfu/newrelic_d2d_may</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</blockquote></div><br></div>

--20cf307d04ae1eb9ca04dd304f6c--