Double spend detection to speed up transaction trust

Hello,

Here's a scenario (it's contrived to make the players easy to identify, more likely this would be low value automated vendors):

Two scammers get together to buy two Ferraris using only one set of BTC. They travel to opposite ends of the world to two car dealerships that accept bitcoins without waiting for confirmations. They are in contact by mobile. They each buy the car and come to pay. At exactly the same moment, they both spend the same coins. They both walk away with a car.

The current solution is the recommendation that vendors wait for six confirmations before releasing goods. That's a long time though; more than most would be willing to wait.

Some points:
 - The bitcoin network is essentially honest
 - If a block chain fork happens, the transactions that are orphaned get added
   to the pending transaction list again, meaning ...
 - A valid transaction will _eventually_ make it into the (longest) block
   chain.
 - Actual distribution time for a transaction through the network is in the
   order of seconds not minutes
 - A double spend attempt has to enter the network near simulateously at
   different places, otherwise the second spend will be rejected instantly by
   the whole network.

New transactions propagate through the network if they are found to be valid. If they aren't valid, they are silently dropped. In the event of a double spend attempt one of those transactions goes to (say) half the network, the other goes to the other half. Whichever one reaches a node first is seen as the real one, the second being seen as invalid. One or other of these will therefore end up in the "longest" chain; but there is no way to know which.

Here's my proposal then: when a node drops a transaction, it should not be silent. It should be broadcast just as it always was going to be had it been valid. Only it is broadcast with a new "inv" type, let's say "MSG_DOUBLESPEND" instead of "MSG_TX".

Now run the Ferrari test again. The vendor sees the transaction that pays for the car appear near instantly (within the propagation time of the network). A short while later they also see a MSG_DOUBLESPEND of the same coins that they have just accepted. They can then operate whatever policy they want: wait for six, ten, twenty confirmations. Call the police. Whatever. Miners can also significantly lower the priority of any transactions that get flagged in this way.

When there isn't a double spend attempt message within the network propagation time, they can be sure that their transaction is the one that miners are working on, and they'll eventually get their money. In other words, they can accept the payment on zero confirmations.

At first I was concerned that this would make it possible to DOS a transaction, but of course it doesn't -- the transaction has to be internally- valid to result in a MSG_DOUBLESPEND, meaning it can only be DOSed by someone with the appropriate private keys.

Andy

There really is no reason to add the extra network complexity for this.

First of all (as you point out) no one buying a Ferrari will refuse to wait an hour for the payment to confirm. If someone is attempting to pull a similar trick on, say, a vending machine however it might make sense. But that changes the equation. In order for these two scammers to pull it off, some effort is required in terms of communicating the time to send the coins and the nodes of the targets (vending machines or whatever) must be figured out. So now its less of "make it impossible" and more of "make it really hard to the point that it is no where near worth the effort".

Lets simplify the scenario a bit so that one scammer can pull it off. Send one copy of your transaction to the target node and another to large mining operations so that the payment transaction is considered invalid to miners and a transaction which pays you is confirmed.

If you are the vending machine, your goal is not to figure out any transactions which are yours, but to figure out which transactions which are yours are going to be confirmed. So, you peer with the largest miners (a "Bitcoin backbone" or large miners and merchants has been suggested over and over again and really hasn't happened) and modify your client to, instead of dropping transactions which are double-spends, keep both in memory pool and consider them both invalid until one of them confirms.

This will work with 1, 2, or n scammers, doesn't require any additional network messages, and offers just as good, if not better security over a double spend message.

Additionally, in the future, when(/if) Bitcoin payment processors exist, most merchants will rely on those, which can handle such double-spend checks and tell a merchant a transaction is confirmed in ten seconds for small transactions, an hour for large ones, or anywhere in between. Such payment processors could also mine or have contracts with large miners which allows them to influence the transactions which are to be confirmed, allowing for even quicker confirmations and the offering of insurance against unconfirmed transactions being invalidated.

Matt

On Thu, 2011-08-04 at 14:23 +0100, Andy Parkins wrote:

> Hello,
>
> Here's a scenario (it's contrived to make the players easy to identify, more
> likely this would be low value automated vendors):
>
> Two scammers get together to buy two Ferraris using only one set of BTC.  They
> travel to opposite ends of the world to two car dealerships that accept
> bitcoins without waiting for confirmations.  They are in contact by mobile.
> They each buy the car and come to pay.  At exactly the same moment, they both
> spend the same coins.  They both walk away with a car.
>
> The current solution is the recommendation that vendors wait for six
> confirmations before releasing goods.  That's a long time though; more than
> most would be willing to wait.
>
> Some points:
>  - The bitcoin network is essentially honest
>  - If a block chain fork happens, the transactions that are orphaned get added
>    to the pending transaction list again, meaning ...
>  - A valid transaction will _eventually_ make it into the (longest) block
>    chain.
>  - Actual distribution time for a transaction through the network is in the
>    order of seconds not minutes
>  - A double spend attempt has to enter the network near simulateously at
>    different places, otherwise the second spend will be rejected instantly by
>    the whole network.
>
> New transactions propagate through the network if they are found to be valid.
> If they aren't valid, they are silently dropped.  In the event of a double
> spend attempt one of those transactions goes to (say) half the network, the
> other goes to the other half.  Whichever one reaches a node first is seen as
> the real one, the second being seen as invalid.  One or other of these will
> therefore end up in the "longest" chain; but there is no way to know which.
>
> Here's my proposal then: when a node drops a transaction, it should not be
> silent.  It should be broadcast just as it always was going to be had it been
> valid.  Only it is broadcast with a new "inv" type, let's say
> "MSG_DOUBLESPEND" instead of "MSG_TX".
>
> Now run the Ferrari test again.  The vendor sees the transaction that pays for
> the car appear near instantly (within the propagation time of the network).  A
> short while later they also see a MSG_DOUBLESPEND of the same coins that they
> have just accepted.  They can then operate whatever policy they want: wait for
> six, ten, twenty confirmations.  Call the police.  Whatever.  Miners can also
> significantly lower the priority of any transactions that get flagged in this
> way.
>
> When there isn't a double spend attempt message within the network propagation
> time, they can be sure that their transaction is the one that miners are
> working on, and they'll eventually get their money.  In other words, they can
> accept the payment on zero confirmations.
>
> At first I was concerned that this would make it possible to DOS a
> transaction, but of course it doesn't -- the transaction has to be internally-
> valid to result in a MSG_DOUBLESPEND, meaning it can only be DOSed by someone
> with the appropriate private keys.
>
>
>
> Andy

On Thursday 04 August 2011 18:45:17 Matt Corallo wrote:

> There really is no reason to add the extra network complexity for this.

It's hardly complex. It's exactly as it is now, with exactly the messages there are now, but with an extra type added to the inventory list. A transaction _already_ propagates using inv messages with MSG_TX, is it really so "complex" to add MSG_DOUBLESPEND to the enum? What's more it's backward compatible because clients that don't understand MSG_DOUBLESPEND will ignore the inv ending up exactly where we are now.

> First of all (as you point out) no one buying a Ferrari will refuse to
> wait an hour for the payment to confirm.  If someone is attempting to
> pull a similar trick on, say, a vending machine however it might make
> sense.  But that changes the equation.  In order for these two scammers

Vending machine, newspaper salesman, ice creams, a beer. The list of small vendors is endless. I picked Ferrari's out of the air.

> to pull it off, some effort is required in terms of communicating the
> time to send the coins and the nodes of the targets (vending machines or
> whatever) must be figured out.  So now its less of "make it impossible"
> and more of "make it really hard to the point that it is no where near
> worth the effort".

I think you've missed the point. Double spend transactions that enters the network at two reasonably evenly connected points are each only seen by half the network, since the first one locks out the second from propagation.

> Lets simplify the scenario a bit so that one scammer can pull it off.
> Send one copy of your transaction to the target node and another to
> large mining operations so that the payment transaction is considered
> invalid to miners and a transaction which pays you is confirmed.

There is no "target" node. There is only a vending machine listening for transactions. It's unlikely that vending machines will even have incoming connections enabled. They certainly won't be keeping a full copy of the block chain or be mining.

> If you are the vending machine, your goal is not to figure out any
> transactions which are yours, but to figure out which transactions which

It is a little bit. Your job is _first_ to figure out which are yours; then, as you say, to see which are going to be confirmed. Well: once you've seen a transaction on the net you know it's going to be confirmed... unless a matching double spend transaction was accepted by the next miner to generate a block.

> are yours are going to be confirmed.  So, you peer with the largest
> miners (a "Bitcoin backbone" or large miners and merchants has been
> suggested over and over again and really hasn't happened) and modify

It hasn't happened, and yet it seems to be that this non-existant thing is your solution to the problem.

> your client to, instead of dropping transactions which are
> double-spends, keep both in memory pool and consider them both invalid
> until one of them confirms.

Well that's what happens now. But that doesn't help the poor sap who's just handed over some goods. I want it so that small businesses can use the client to give them practical answers instead of this "0/unconfirmed" stuff which requires understanding of the system.

> This will work with 1, 2, or n scammers, doesn't require any additional
> network messages, and offers just as good, if not better security over a
> double spend message.

I'm not really trying to prevent double spends -- bitcoin _already_ prevents double spends. Also: the only difference between your suggestion (don't drop) and my suggestion (don't drop but mark with MSG_DOUBLESPEND) is a single number in the inv. I really don't get the objection.

> Additionally, in the future, when(/if) Bitcoin payment processors exist,

"In the future" is all well and good. What if there is no future because bitcoin is still too difficult for average joe to use?

Andy

On Thu, 2011-08-04 at 19:22 +0100, Andy Parkins wrote:

> On Thursday 04 August 2011 18:45:17 Matt Corallo wrote:
> > There really is no reason to add the extra network complexity for this.
>
> It's hardly complex.  It's exactly as it is now, with exactly the messages
> there are now, but with an extra type added to the inventory list.  A
> transaction _already_ propagates using inv messages with MSG_TX, is it
> really so "complex" to add MSG_DOUBLESPEND to the enum?  What's more it's
> backward compatible because clients that don't understand MSG_DOUBLESPEND
> will ignore the inv ending up exactly where we are now.

But why? It results in slightly more network traffic which is exactly what we don't want, and it adds yet another message people have to know about.

>
> > First of all (as you point out) no one buying a Ferrari will refuse to
> > wait an hour for the payment to confirm.  If someone is attempting to
> > pull a similar trick on, say, a vending machine however it might make
> > sense.  But that changes the equation.  In order for these two scammers
>
> Vending machine, newspaper salesman, ice creams, a beer.  The list of small
> vendors is endless.  I picked Ferrari's out of the air.

Ferraris aren't exactly small ;)

>
> > to pull it off, some effort is required in terms of communicating the
> > time to send the coins and the nodes of the targets (vending machines or
> > whatever) must be figured out.  So now its less of "make it impossible"
> > and more of "make it really hard to the point that it is no where near
> > worth the effort".
>
> I think you've missed the point.  Double spend transactions that enters the
> network at two reasonably evenly connected points are each only seen by half
> the network, since the first one locks out the second from propagation.

No one cares about what the network thinks is the right transaction, its only what miners believe that matters.

>
> > Lets simplify the scenario a bit so that one scammer can pull it off.
> > Send one copy of your transaction to the target node and another to
> > large mining operations so that the payment transaction is considered
> > invalid to miners and a transaction which pays you is confirmed.
>
> There is no "target" node.  There is only a vending machine listening for
> transactions.  It's unlikely that vending machines will even have incoming
> connections enabled.  They certainly won't be keeping a full copy of the
> block chain or be mining.

Even if the vending machine doesn't keep the full chain and doesn't accept incoming connections, its still the target node. What other nodes on the network think doesn't matter as long as you get the target to think a transaction that won't be confirmed will be. If it doesn't accept incoming connections you want to find nodes that do that are connected to your target.

>
> > If you are the vending machine, your goal is not to figure out any
> > transactions which are yours, but to figure out which transactions which
>
> It is a little bit.  Your job is _first_ to figure out which are yours;
> then, as you say, to see which are going to be confirmed.  Well: once you've
> seen a transaction on the net you know it's going to be confirmed... unless
> a matching double spend transaction was accepted by the next miner to
> generate a block.

That is exactly my point.

>
> > are yours are going to be confirmed.  So, you peer with the largest
> > miners (a "Bitcoin backbone" or large miners and merchants has been
> > suggested over and over again and really hasn't happened) and modify
>
> It hasn't happened, and yet it seems to be that this non-existant thing is
> your solution to the problem.

Its much easier to create than to change the network code to relay info on double-spend transactions.

>
> > your client to, instead of dropping transactions which are
> > double-spends, keep both in memory pool and consider them both invalid
> > until one of them confirms.
>
> Well that's what happens now.  But that doesn't help the poor sap who's just
> handed over some goods.  I want it so that small businesses can use the
> client to give them practical answers instead of this "0/unconfirmed" stuff
> which requires understanding of the system.

No, thats not what happens now. Currently if your node gets a transaction which conflicts with one it already knows about, it silently drops it without a second thought. My point is if you actually dealt with such cases and made good connections, you would be able to prevent double spends nearly perfectly.

>
> > This will work with 1, 2, or n scammers, doesn't require any additional
> > network messages, and offers just as good, if not better security over a
> > double spend message.
>
> I'm not really trying to prevent double spends -- bitcoin _already_ prevents
> double spends.  Also: the only difference between your suggestion (don't
> drop) and my suggestion (don't drop but mark with MSG_DOUBLESPEND) is a
> single number in the inv.  I really don't get the objection.

No, my suggestion is not to relay the second transaction. The second transaction should continue to not be relayed as it currently is, however receiving such a transaction should trigger the node to notify the user that the transaction should not be accepted until it makes it into a block (in fact, you could already do this if you implemented a debug.log parser and made well-placed connections).

>
> > Additionally, in the future, when(/if) Bitcoin payment processors exist,
>
> "In the future" is all well and good.  What if there is no future because
> bitcoin is still too difficult for average joe to use?

Bitcoin is absolutely still an experiment and no one thinks that any kind of future is guaranteed. This was not meant as an argument, but simply as "if bitcoin does end up going somewhere, it will likely be done like this".

Matt

On Thursday 04 August 2011 19:39:56 Matt Corallo wrote:

> But why? It results in slightly more network traffic which is exactly
> what we don't want, and it adds yet another message people have to know
> about.

"Slightly" is an understatement. It add more network traffic for every double spend attempt. Which don't happen very often.

Also, I'm not proposing a new message, heaven forbid that we add a new message type, I'm proposing that we do this:

 enum
 {
     MSG_TX = 1,
     MSG_BLOCK,
+    MSG_DOUBLESPEND,
 };

Also, people don't "have" to know about it. And it's not "people" it's an addition to the _one_ official client. _and_ it's backward compatible because if they don't know about it, nothing changes... the TX gets dropped just as it is now.

> > I think you've missed the point.  Double spend transactions that enters
> > the network at two reasonably evenly connected points are each only
> > seen by half the network, since the first one locks out the second
> > from propagation.
>
> No one cares about what the network thinks is the right transaction, its
> only what miners believe that matters.

They do care because the network as a whole is what makes the eventual decision about which is the block-chain-to-rule-them-all. Chain forks, and eventual reorgs are also far less disruptive when each leg of a double spend isn't on each potential chain. "Half the network" includes half of the miners. It's perfectly possible for half the miners to be working on one leg, half on the other. That means it's 50/50 which leg eventually gets confirmed.

> Even if the vending machine doesn't keep the full chain and doesn't
> accept incoming connections, its still the target node.  What other
> nodes on the network think doesn't matter as long as you get the target
> to think a transaction that won't be confirmed will be.  If it doesn't
> accept incoming connections you want to find nodes that do that are
> connected to your target.

Well that's true enough; but how on earth you're going to identify an IP address of a particular vending machine that isn't accepting incoming connections is beyond me. If it is a target it's pretty close to invisible.

> Its much easier to create than to change the network code to relay info
> on double-spend transactions.

What? It's easier to trigger massive adoption and organisation of an inherently disorgainsed network of miners than it is to write a few lines of code? If that's true, then the bitcoin source is even more impenetrable than I imagine.

> > Well that's what happens now.  But that doesn't help the poor sap who's
> > just handed over some goods.  I want it so that small businesses can
> > use the client to give them practical answers instead of this
> > "0/unconfirmed" stuff which requires understanding of the system.
>
> No, thats not what happens now.  Currently if your node gets a
> transaction which conflicts with one it already knows about, it silently
> drops it without a second thought.  My point is if you actually dealt
> with such cases and made good connections, you would be able to prevent
> double spends nearly perfectly.

It's not about prevention, they are already prevented. It's about detection. Quickly.

> > I'm not really trying to prevent double spends -- bitcoin _already_
> > prevents double spends.  Also: the only difference between your
> > suggestion (don't drop) and my suggestion (don't drop but mark with
> > MSG_DOUBLESPEND) is a single number in the inv.  I really don't get
> > the objection.
>
> No, my suggestion is not to relay the second transaction.  The second
> transaction should continue to not be relayed as it currently is,
> however receiving such a transaction should trigger the node to notify
> the user that the transaction should not be accepted until it makes it
> into a block (in fact, you could already do this if you implemented a
> debug.log parser and made well-placed connections).

How is this second transaction going to end up anywhere but on a few isolated nodes if it isn't propagated? The only way _both_ can be in a pool is if they are both received. If they aren't both forwarded then it won't be in most pools. If it isn't in most pools then which how is the relevant user going to get notified?

> Bitcoin is absolutely still an experiment and no one thinks that any
> kind of future is guaranteed.  This was not meant as an argument, but

If it's still an experiment why is there such huge objection to pretty much every change anyone proposes? Bitcoin is one of the most conservative projects I've ever seen, even for the most passive of changes. I can understand wanting to prevent potential financial loss, but it's not like I'm suggesting we start broadcasting private keys on the network.

> simply as "if bitcoin does end up going somewhere, it will likely be
> done like this".

When you're using it as an argument for why a suggestion is unnecessary that's not how it sounds.

Anyway; it's fine. You don't think it's a good idea; and I suspect none of the other official client developers will either, they don't like protocol changes. So be it; it was only a suggestion and I'm a nobody around here.

Andy

One double-spend fighting option is for each mining pool to offer a realtime feed of accepted TXs.

I am hoping to complete the following later this month:

	(1) A minimal bitcoind patch that writes raw accepted TXs and BLOCKs to stdout with a prefix of ("2naXaRQj--TX\n%d\n" % (data_length))
		(Proof-of-concept done — I'll submit a pull request with "--print-accepted-txs-and-blocks" when I get a chance to clean it up)

	(2) A minimal NodeJS app which invokes bitcoind as a subprocess, parses the TXs and BLOCKs, and offers a realtime feed

On Aug 4, 2011, at 3:42 PM, Andy Parkins wrote:

> On Thursday 04 August 2011 19:39:56 Matt Corallo wrote:
>
>> But why? It results in slightly more network traffic which is exactly
>> what we don't want, and it adds yet another message people have to know
>> about.
>
> "Slightly" is an understatement.  It add more network traffic for every
> double spend attempt.  Which don't happen very often.
>
> Also, I'm not proposing a new message, heaven forbid that we add a new
> message type, I'm proposing that we do this:
>
> enum
> {
>     MSG_TX = 1,
>     MSG_BLOCK,
> +    MSG_DOUBLESPEND,
> };
>
> Also, people don't "have" to know about it.  And it's not "people" it's an
> addition to the _one_ official client.  _and_ it's backward compatible
> because if they don't know about it, nothing changes... the TX gets dropped
> just as it is now.
>
>>> I think you've missed the point.  Double spend transactions that enters
>>> the network at two reasonably evenly connected points are each only
>>> seen by half the network, since the first one locks out the second
>>> from propagation.
>>
>> No one cares about what the network thinks is the right transaction, its
>> only what miners believe that matters.
>
> They do care because the network as a whole is what makes the eventual
> decision about which is the block-chain-to-rule-them-all.  Chain forks, and
> eventual reorgs are also far less disruptive when each leg of a double spend
> isn't on each potential chain.  "Half the network" includes half of the
> miners.  It's perfectly possible for half the miners to be working on one
> leg, half on the other.  That means it's 50/50 which leg eventually gets
> confirmed.
>
>> Even if the vending machine doesn't keep the full chain and doesn't
>> accept incoming connections, its still the target node.  What other
>> nodes on the network think doesn't matter as long as you get the target
>> to think a transaction that won't be confirmed will be.  If it doesn't
>> accept incoming connections you want to find nodes that do that are
>> connected to your target.
>
> Well that's true enough; but how on earth you're going to identify an IP
> address of a particular vending machine that isn't accepting incoming
> connections is beyond me.  If it is a target it's pretty close to invisible.
>
>> Its much easier to create than to change the network code to relay info
>> on double-spend transactions.
>
> What?  It's easier to trigger massive adoption and organisation of an
> inherently disorgainsed network of miners than it is to write a few lines of
> code?  If that's true, then the bitcoin source is even more impenetrable
> than I imagine.
>
>>> Well that's what happens now.  But that doesn't help the poor sap who's
>>> just handed over some goods.  I want it so that small businesses can
>>> use the client to give them practical answers instead of this
>>> "0/unconfirmed" stuff which requires understanding of the system.
>>
>> No, thats not what happens now.  Currently if your node gets a
>> transaction which conflicts with one it already knows about, it silently
>> drops it without a second thought.  My point is if you actually dealt
>> with such cases and made good connections, you would be able to prevent
>> double spends nearly perfectly.
>
> It's not about prevention, they are already prevented.  It's about
> detection.  Quickly.
>
>>> I'm not really trying to prevent double spends -- bitcoin _already_
>>> prevents double spends.  Also: the only difference between your
>>> suggestion (don't drop) and my suggestion (don't drop but mark with
>>> MSG_DOUBLESPEND) is a single number in the inv.  I really don't get
>>> the objection.
>>
>> No, my suggestion is not to relay the second transaction.  The second
>> transaction should continue to not be relayed as it currently is,
>> however receiving such a transaction should trigger the node to notify
>> the user that the transaction should not be accepted until it makes it
>> into a block (in fact, you could already do this if you implemented a
>> debug.log parser and made well-placed connections).
>
> How is this second transaction going to end up anywhere but on a few
> isolated nodes if it isn't propagated?  The only way _both_ can be in a pool
> is if they are both received.  If they aren't both forwarded then it won't
> be in most pools.  If it isn't in most pools then which how is the relevant
> user going to get notified?
>
>> Bitcoin is absolutely still an experiment and no one thinks that any
>> kind of future is guaranteed.  This was not meant as an argument, but
>
> If it's still an experiment why is there such huge objection to pretty much
> every change anyone proposes?  Bitcoin is one of the most conservative
> projects I've ever seen, even for the most passive of changes.  I can
> understand wanting to prevent potential financial loss, but it's not like
> I'm suggesting we start broadcasting private keys on the network.
>
>> simply as "if bitcoin does end up going somewhere, it will likely be
>> done like this".
>
> When you're using it as an argument for why a suggestion is unnecessary
> that's not how it sounds.
>
> Anyway; it's fine.  You don't think it's a good idea; and I suspect none of
> the other official client developers will either, they don't like protocol
> changes.  So be it; it was only a suggestion and I'm a nobody around here.
>
>
>
> Andy
>
> --
> Dr Andy Parkins
> andyparkins@gmail•com
>
> ------------------------------------------------------------------------------
> BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
> The must-attend event for mobile developers. Connect with experts.
> Get tools for creating Super Apps. See the latest technologies.
> Sessions, hands-on labs, demos & much more. Register early & save!
> http://p.sf.net/sfu/rim-blackberry-1
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

On Thu, Aug 4, 2011 at 3:42 PM, Andy Parkins <andyparkins@gmail•com> wrote:

> On Thursday 04 August 2011 19:39:56 Matt Corallo wrote:
>
>> But why? It results in slightly more network traffic which is exactly
>> what we don't want, and it adds yet another message people have to know
>> about.
>
> "Slightly" is an understatement.  It add more network traffic for every
> double spend attempt.  Which don't happen very often.

But they can be trivially generated on demand, and potentially result in unbounded flooding.

Even if you carefully don't duplicate an announcement I can easily generate an unlimited number of double-spends for the network to flood. The normal anti-DDOS logic doesn't work because there can be no additional proof-of-workish costs for the double spend (they'd share whatever anti-ddos fees the first txn had).

This is somewhat soluble, I guess. Rather than NAK the transaction the way it would work is propagating conflicts on each of the conflicted inputs. "I've seen at least two transactions recently trying to spend input X, here is proof: (two txn IDs)". Even if there are more spends of that input you don't need to hear about them, knowing about two spends of an input is enough to consider that input (and perhaps all inputs with an identical script to that one) temporarily suspect. Though it would have to be done input by input.

This might be an interesting feature if not for the fact that the software already waits a fair number of confirms before considering something confirmed. Of course, a sybil can just filter these messages diminishing their usefulness.

I suppose I could add this as a (7) to this list: https://bitcointalk.org/index.php?topic=28565.msg359948#msg359948

On Thu, 2011-08-04 at 20:42 +0100, Andy Parkins wrote:

> On Thursday 04 August 2011 19:39:56 Matt Corallo wrote:
>
> > But why? It results in slightly more network traffic which is exactly
> > what we don't want, and it adds yet another message people have to know
> > about.
>
> "Slightly" is an understatement.  It add more network traffic for every
> double spend attempt.  Which don't happen very often.

Exactly, why add more network traffic for something that you can get better without doing that?

>
> Also, I'm not proposing a new message, heaven forbid that we add a new
> message type, I'm proposing that we do this:
>
>  enum
>  {
>      MSG_TX = 1,
>      MSG_BLOCK,
> +    MSG_DOUBLESPEND,
>  };
>
> Also, people don't "have" to know about it.  And it's not "people" it's an
> addition to the _one_ official client.  _and_ it's backward compatible
> because if they don't know about it, nothing changes... the TX gets dropped
> just as it is now.

Again though, adding more crap to the protocols is something we want to avoid, especially if it offers no gain.

>
> > > I think you've missed the point.  Double spend transactions that enters
> > > the network at two reasonably evenly connected points are each only
> > > seen by half the network, since the first one locks out the second
> > > from propagation.
> >
> > No one cares about what the network thinks is the right transaction, its
> > only what miners believe that matters.
>
> They do care because the network as a whole is what makes the eventual
> decision about which is the block-chain-to-rule-them-all.  Chain forks, and
> eventual reorgs are also far less disruptive when each leg of a double spend
> isn't on each potential chain.  "Half the network" includes half of the
> miners.  It's perfectly possible for half the miners to be working on one
> leg, half on the other.  That means it's 50/50 which leg eventually gets
> confirmed.

Nope, the network decides nothing, only the miners decide.

>
> > Even if the vending machine doesn't keep the full chain and doesn't
> > accept incoming connections, its still the target node.  What other
> > nodes on the network think doesn't matter as long as you get the target
> > to think a transaction that won't be confirmed will be.  If it doesn't
> > accept incoming connections you want to find nodes that do that are
> > connected to your target.
>
> Well that's true enough; but how on earth you're going to identify an IP
> address of a particular vending machine that isn't accepting incoming
> connections is beyond me.  If it is a target it's pretty close to invisible.

Then your whole attack scenario is broken and it becomes a 50/50 (or more likely less) guess.

>
> > Its much easier to create than to change the network code to relay info
> > on double-spend transactions.
>
> What?  It's easier to trigger massive adoption and organisation of an
> inherently disorgainsed network of miners than it is to write a few lines of
> code?  If that's true, then the bitcoin source is even more impenetrable
> than I imagine.

No, its easier for people who care to make sure they are peered with well-connected nodes than for us to change the network protocol.

>
> > > Well that's what happens now.  But that doesn't help the poor sap who's
> > > just handed over some goods.  I want it so that small businesses can
> > > use the client to give them practical answers instead of this
> > > "0/unconfirmed" stuff which requires understanding of the system.
> >
> > No, thats not what happens now.  Currently if your node gets a
> > transaction which conflicts with one it already knows about, it silently
> > drops it without a second thought.  My point is if you actually dealt
> > with such cases and made good connections, you would be able to prevent
> > double spends nearly perfectly.
>
> It's not about prevention, they are already prevented.  It's about
> detection.  Quickly.

Yep, which is what my suggestion does.

>
> > > I'm not really trying to prevent double spends -- bitcoin _already_
> > > prevents double spends.  Also: the only difference between your
> > > suggestion (don't drop) and my suggestion (don't drop but mark with
> > > MSG_DOUBLESPEND) is a single number in the inv.  I really don't get
> > > the objection.
> >
> > No, my suggestion is not to relay the second transaction.  The second
> > transaction should continue to not be relayed as it currently is,
> > however receiving such a transaction should trigger the node to notify
> > the user that the transaction should not be accepted until it makes it
> > into a block (in fact, you could already do this if you implemented a
> > debug.log parser and made well-placed connections).
>
> How is this second transaction going to end up anywhere but on a few
> isolated nodes if it isn't propagated?  The only way _both_ can be in a pool
> is if they are both received.  If they aren't both forwarded then it won't
> be in most pools.  If it isn't in most pools then which how is the relevant
> user going to get notified?

If it only ends up on a few isolated nodes, then you dont care as the ones that you dont know about will never be confirmed. If it ends up on a node you peer with, you will be able to fetch both transactions and then you know about the double spend. Hence why you have to have well-connected peers.

>
> > Bitcoin is absolutely still an experiment and no one thinks that any
> > kind of future is guaranteed.  This was not meant as an argument, but
>
> If it's still an experiment why is there such huge objection to pretty much
> every change anyone proposes?  Bitcoin is one of the most conservative
> projects I've ever seen, even for the most passive of changes.  I can
> understand wanting to prevent potential financial loss, but it's not like
> I'm suggesting we start broadcasting private keys on the network.

No one is against making changes if they offer clear incentive. This one doesnt. Additionally, whether its an experiment or not, people have money stored in it and a mistake could mean the loss of tens of thousands or hundreds of thousands of dollars. Lastly, no one is (yet) paid to work on Bitcoin, sorry the developers dont spend enough time merging for your liking.

>
> > simply as "if bitcoin does end up going somewhere, it will likely be
> > done like this".
>
> When you're using it as an argument for why a suggestion is unnecessary
> that's not how it sounds.
>
> Anyway; it's fine.  You don't think it's a good idea; and I suspect none of
> the other official client developers will either, they don't like protocol
> changes.  So be it; it was only a suggestion and I'm a nobody around here.

I think having the ability to detect double-spends rapidly is something that is needed, my point is that you already can with relatively little effort, no point adding more stuff to make it no easier.

Matt

On Thu, 2011-08-04 at 16:07 -0400, Andrew Schaaf wrote:

> One double-spend fighting option is for each mining pool to offer a realtime feed of accepted TXs.
>
> I am hoping to complete the following later this month:
>
> 	(1) A minimal bitcoind patch that writes raw accepted TXs and BLOCKs to stdout with a prefix of ("2naXaRQj--TX\n%d\n" % (data_length))
> 		(Proof-of-concept done — I'll submit a pull request with "--print-accepted-txs-and-blocks" when I get a chance to clean it up)
>
> 	(2) A minimal NodeJS app which invokes bitcoind as a subprocess, parses the TXs and BLOCKs, and offers a realtime feed

They already do if they provide the IP of their node (or a proxy node on top of theirs which would be recommended for security). This has been my whole point the entire time.

Matt

> If it's still an experiment why is there such huge objection to pretty much
> every change anyone proposes?

I don't think there are huge objections to every change. You've only really argued about this with Matt ;)

The vending machine/detecting double spends issue was discussed by Satoshi in July 2010:

   https://bitcointalk.org/index.php?topic=423.msg3819#msg3819

He mentioned payment processors that could "alert the transaction is bad".

Gregorys idea looks sound to me. It'd be useful, though, to have a NAK message for transactions anyway (not propagated). It's possible to get yourself into a situation today where you connect to nodes that refuse to relay your transaction for some reason (perhaps your peers are using old fee rules, or you are) but you think the transaction was relayed. The user is left wondering why the spend didn't confirm.

If nodes sent a message saying "I refuse to process this tx because <reason>" it'd make debugging and testing easier as well.

Since nobody else has mentioned it: There is another (more pragmatic?) way to detect double spends:

1. Connect to lots of clients 2a. If they all send you the same transaction -> double spend unlikely 2b. If some don't send you the transaction (or send a conflicting one) -> double spend in progress

Obviously not everyone will run a double spend detector - it's much more easily realized as a service (just like mining.) Jan put up a proof of concept: http://www.transactionradar.com/

Would network support like a MSG_DOUBLESPEND be better? I used to think yes, but looking at the reality of Transaction Radar, I'm not so sure. Nothing stops such a service from scaling up and connecting to thousands of random nodes (especially when the network itself grows bigger), pushing the probabilities of missing a double spend "in the wild" to near zero. It could also connect directly to important miners/pools as others have suggested.

Of course this doesn't help against double spends where the attacker does his own mining*, but neither would MSG_DOUBLESPEND. Given the added network load I'd argue that network support for double spends is unnecessary and potentially damaging. DoS is more scary to me than non-instant transactions.

* In this case of course the hacker will be exposed to some randomness, and I doubt many attackers will buy 100 televisions, newspaper subscriptions or MP3s to get one for free. So this is only a problem for liquid goods with tiny spreads (any investment or stored value instrument.)

On Thu, 2011-08-04 at 23:36 +0200, Mike Hearn wrote:

> The vending machine/detecting double spends issue was discussed by
> Satoshi in July 2010:
>
>    https://bitcointalk.org/index.php?topic=423.msg3819#msg3819
>
> He mentioned payment processors that could "alert the transaction is bad".

I stand with satoshi here. No need to add more stuff to the network protocol, a well-connected node can easily monitor the miners(/network) for double-spends and alert whoever may need to know that the transaction should not be accepted. True, not everyone has the resources to try to implement this, however the number of people who have the resources to implement a Bitcoin storefront and not implement this (vs those who will/do use a payment processor who handles such things), I would think, are fairly small. Additionally, keep in mind that many storefronts don't need to care if a transaction confirms in 10 seconds or 1 hour. Only digital goods and physical purchases could benefit from such speed increases.

On Fri, 2011-08-05 at 00:10 +0200, Stefan Thomas wrote: Since nobody else has mentioned it: There is another (more pragmatic?)

> way to detect double spends:
>
> 1. Connect to lots of clients
> 2a. If they all send you the same transaction -> double spend unlikely
> 2b. If some don't send you the transaction (or send a conflicting one)
> -> double spend in progress

This is exactly what I've been suggesting this whole time.

On Thu, Aug 4, 2011 at 6:10 PM, Stefan Thomas <moon@justmoon•de> wrote:

> Would network support like a MSG_DOUBLESPEND be better? I used to think
> yes, but looking at the reality of Transaction Radar, I'm not so sure.
> Nothing stops such a service from scaling up and connecting to thousands
> of random nodes (especially when the network itself grows bigger),

Except for the fact that such a party is a DOS attack on the network which is already short on functioning listeners. I don't have much doubt that people doing the "connect to everyone" are already causing harm. There are some nodes in .ru/.ua which aggressively connect to me (instant reconnects if I hang up on them) which have never passed me a transaction in all my available logs.

Alerts scale better— both can have a place in the ecosystem, they're actually complementary: Alerts are vulnerable to filtering by sibyl attackers but they have deeper network penetration and where filtering doesn't prevent them you don't need a connection to hear them.

On Thu, 2011-08-04 at 18:18 -0400, Gregory Maxwell wrote:

> I don't have much
> doubt that people doing the "connect to everyone" are already causing
> harm. There are some nodes in .ru/.ua which aggressively connect to me
> (instant reconnects if I hang up on them) which have never passed me a
> transaction in all my available logs.

I've been thinking about going through my logs to see how many nodes I am connected to that are clearly bad (like those), but I suppose you beat me to it. Should such connections not be dropped over time as they are clearly not functioning nodes?

Couple of semi-random thoughts:

RE: detecting double spends: I agree that extending the protocol to make double-spend detection better is probably a bad idea.

That said, I could see extending the information reported by the listtransactions/gettransaction API calls to report detected double spends ( == transaction uses the same inputs as another transaction in the block chain or memory pool). IIRC, now the code just drops double spends, so if this was done the implementation would have to be careful about being vulnerable to a "fill memory with bogus transactions" attack.

RE: badly-behaved nodes: I'd really like somebody to start experimenting with algorithms for detecting well-behaved and ill-behaved nodes-- maybe starting with a dns-seed implementation. I suspect people are starting to experiment with various types of Sybil attacks, which might explain why network connectivity has been so bad.

(sent from the Sydney airport, before a very LOOONG flight back to Massachusetts)

On 8/5/2011 12:18 AM, Gregory Maxwell wrote:

> Except for the fact that such a party is a DOS attack on the network
> which is already short on functioning listeners.

To the transaction radar it doesn't much matter whether its connections are outgoing or incoming (assuming it can keep its nodes' IPs secret and it has reasonable uptime). So you could say that this is an argument *for* this kind of double spend protection if it means the creation of nodes/clusters accepting 10000+ incoming connections while making few outgoing connections. My point is, the amount of connections a node has has nothing to do with its effect on the in/out balance.

Some words on the shortage of listeners itself:

Could this be because the network right now consists largely of end users with residential type networks? With BitTorrent a lot of users go through the trouble of opening up ports in their router manually in order to get more peers and better download speeds - this is not (yet?) a widespread practice with Bitcoin. (I know Bitcoin has UPnP support, but I haven't found any numbers on how widely the IGD protocol is actually deployed. Wikipedia says that "some NAT routers" support it and that it's not an IETF standard. All routers I've actually seen in real life had it disabled by default.)

In the long term all the trends favor more clients allowing incoming connections: End users will tend to move towards lighter clients and the ones that stick with full nodes will tend to configure them better - meaning opening ports etc. - as documentation improves.

As for downright malicious nodes: It should be possible to come up with some sensible policies to temp ban nodes that don't relay any useful messages or try to flood you. This is an ongoing optimization problem in any peer-to-peer network and I expect us to make progress with this over time.

On 8/5/2011 12:16 AM, Matt Corallo wrote:

> This is exactly what I've been suggesting this whole time.

I had only seen you mention a "miner backbone" which is sort of a more long-term vision, whereas Transaction Radar exists today. I didn't read everything though, so if you mentioned this idea specifically, please just consider my post as further support for your position.

> Could this be because the network right now consists largely of end
> users with residential type networks?

Probably.

How many connections "should" a node use? We faced this decision in BitCoinJ recently and I asked the patch writer to reduce the number. It seems pretty arbitrary to me - if you aren't going to relay, a single connection should be good enough. Yes, it makes sybil easier, but if you pick the one node randomly enough it might be ok?

> actually deployed. Wikipedia says that "some NAT routers" support it and
> that it's not an IETF standard. All routers I've actually seen in real
> life had it disabled by default.)

Hmm, I don't recall ever enabling it in my router but it's on and the Bitcoin support works. UPnP is used by all kinds of common programs like Skype and Xbox Live.

On 2011 August 05 Friday, Mike Hearn wrote:

> How many connections "should" a node use? We faced this decision in
> BitCoinJ recently and I asked the patch writer to reduce the number.
> It seems pretty arbitrary to me - if you aren't going to relay, a
> single connection should be good enough. Yes, it makes sybil easier,
> but if you pick the one node randomly enough it might be ok?

I don't really see that "number of connections" is the relevant metric. For a well designed bit of software the number of connections shouldn't matter. There's a bit of overhead in the operating system per connection, but I'd be surprised if that ever became a limiting factor in a stateless system like bitcoin. In fact, bitcoin would work perfectly well as a UDP system (I'm not advocating that of course), and then there would be no such thing as a connection.

Bandwidth is the measure that's relevant.

Therefore if bandwidth is the measure, just pick a bandwidth you like and add/accept connections until you hit that bandwidth limit (probably averaged). This has the advantage that it can be measured automatically, or sensibly set by a user.

Andy

On Fri, 2011-08-05 at 02:14 +0200, Stefan Thomas wrote:

> (I know Bitcoin has UPnP support,
> but I haven't found any numbers on how widely the IGD protocol is
> actually deployed. Wikipedia says that "some NAT routers" support it and
> that it's not an IETF standard. All routers I've actually seen in real
> life had it disabled by default.)

It used to be enabled by default on virtually all routers a couple years ago, but too many "security researchers" complained that it was a "huge security vulnerability" (I guess they hadn't heard of stun or outgoing connections) so its not typically disabled on most routers.

On Fri, 2011-08-05 at 12:58 +0100, Andy Parkins wrote:

> On 2011 August 05 Friday, Mike Hearn wrote:
>
> I don't really see that "number of connections" is the relevant metric.

Number of connections is something that needs serious thought. Too many and you fill everyone's connection slots and no one can make connections. Too few and you don't have a network but just a bunch of islands which would also cause serious problems. If you aren't relaying, each connection takes almost no bandwidth, so the question is how many do you need to be considered secure.

On 2011 August 05 Friday, Matt Corallo wrote:

> On Fri, 2011-08-05 at 12:58 +0100, Andy Parkins wrote:
> > I don't really see that "number of connections" is the relevant metric.
>
> Number of connections is something that needs serious thought.  Too many
> and you fill everyone's connection slots and no one can make
> connections.  Too few and you don't have a network but just a bunch of
> islands which would also cause serious problems.
> If you aren't relaying, each connection takes almost no bandwidth, so
> the question is how many do you need to be considered secure.

I'm arguing that "number of connection slots" isn't the best metric; so that wouldn't matter. Just keep accepting incoming connections (with some sanity limit of course) until you've allocated your bandwidth, not your number of connections.

If I connect to a thousand nodes and never send anything, I'm not using up very much of their resources. If _they_ want to use up resources by relaying, then that is their choice, but again they can do that based on bandwidth calculations rather than connection counts. If I am sending, then that adds to their bandwidth and gets included in whatever limit they've chosen.

For example: the client could simply maintain an average bandwidth over all connections. If that average is less than threshold0, then make new outgoing connections. If that average exceeds threshold1, then stop accepting incoming connections. If it exceeds threshold2, start dropping established incoming connections. If it exceeds theshold3, start dropping established outgoing connections.

The actual rules don't matter so much; I'm just saying bandwidth is a better metric than connection count. If you limit by connection count, then you'll just end up filled with non-relaying listeners, since they (in the future) will be the most commonplace. You'll have no incoming relays, and therefore nothing to forward, so your bandwidth will be zero, but your connection count at maximum -- you've locked yourself out.

Andy

On Fri, Aug 5, 2011 at 9:03 AM, Andy Parkins <andyparkins@gmail•com> wrote:

> The actual rules don't matter so much; I'm just saying bandwidth is a better
> metric than connection count.

I'm sure many people would be interested in patches that solve the ~O(N) peak memory usage with additional connections.

On Fri, 2011-08-05 at 14:03 +0100, Andy Parkins wrote:

> I'm arguing that "number of connection slots" isn't the best metric; so that
> wouldn't matter.  Just keep accepting incoming connections (with some sanity
> limit of course) until you've allocated your bandwidth, not your number of
> connections.

Mike and me were talking about outgoing connection count, not incoming, which is another thing entirely. However, to your point: having 1000 Bitcoin connection is still almost no traffic, the only timt you really hit much traffic is when you get a peer with a client who doesn't have the full chain as they will start downloading the chain maxing your bandwidth. My bandwidth of Bitcoin is something like avg 3GB/month for 125 connections which is nothing. However it has very brief spikes of my entire outgoing bandwidth. Thus, neither bandwidth nor connection count are really good metrics for choosing your number of incoming slots.

Matt