[Bitcoin-development] Double spend detection to speed up transaction trust

public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [Bitcoin-development] Double spend detection to speed up transaction trust
@ 2011-08-04 13:23 Andy Parkins
  2011-08-04 17:45 ` Matt Corallo
  0 siblings, 1 reply; 23+ messages in thread
From: Andy Parkins @ 2011-08-04 13:23 UTC (permalink / raw)
  To: Bitcoin Dev

[-- Attachment #1: Type: Text/Plain, Size: 3096 bytes --]

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
-- 
Dr Andy Parkins
andyparkins@gmail•com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 13:23 [Bitcoin-development] Double spend detection to speed up transaction trust Andy Parkins
@ 2011-08-04 17:45 ` Matt Corallo
  2011-08-04 18:22   ` Andy Parkins
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 17:45 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 5440 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 17:45 ` Matt Corallo
@ 2011-08-04 18:22   ` Andy Parkins
  2011-08-04 18:39     ` Matt Corallo
  0 siblings, 1 reply; 23+ messages in thread
From: Andy Parkins @ 2011-08-04 18:22 UTC (permalink / raw)
  To: bitcoin-development

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

-- 
Dr Andy Parkins
andyparkins@gmail•com

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 18:22   ` Andy Parkins
@ 2011-08-04 18:39     ` Matt Corallo
  2011-08-04 19:42       ` Andy Parkins
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 18:39 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 6000 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 18:39     ` Matt Corallo
@ 2011-08-04 19:42       ` Andy Parkins
  2011-08-04 20:07         ` Andrew Schaaf
                           ` (3 more replies)
  0 siblings, 4 replies; 23+ messages in thread
From: Andy Parkins @ 2011-08-04 19:42 UTC (permalink / raw)
  To: bitcoin-development

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

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 19:42       ` Andy Parkins
@ 2011-08-04 20:07         ` Andrew Schaaf
  2011-08-04 20:38           ` Matt Corallo
  2011-08-04 20:08         ` Gregory Maxwell
                           ` (2 subsequent siblings)
  3 siblings, 1 reply; 23+ messages in thread
From: Andrew Schaaf @ 2011-08-04 20:07 UTC (permalink / raw)
  To: bitcoin-development


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&reg; 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




^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 20:07         ` Andrew Schaaf
@ 2011-08-04 20:38           ` Matt Corallo
  2011-08-04 22:10             ` Stefan Thomas
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 20:38 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 817 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 20:38           ` Matt Corallo
@ 2011-08-04 22:10             ` Stefan Thomas
  2011-08-04 22:18               ` Gregory Maxwell
  0 siblings, 1 reply; 23+ messages in thread
From: Stefan Thomas @ 2011-08-04 22:10 UTC (permalink / raw)
  To: bitcoin-development

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

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 22:10             ` Stefan Thomas
@ 2011-08-04 22:18               ` Gregory Maxwell
  2011-08-04 22:21                 ` Matt Corallo
  0 siblings, 1 reply; 23+ messages in thread
From: Gregory Maxwell @ 2011-08-04 22:18 UTC (permalink / raw)
  To: Stefan Thomas; +Cc: bitcoin-development

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.

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 22:18               ` Gregory Maxwell
@ 2011-08-04 22:21                 ` Matt Corallo
  2011-08-05  0:07                   ` Gavin Andresen
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 22:21 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 596 bytes --]

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?

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 22:21                 ` Matt Corallo
@ 2011-08-05  0:07                   ` Gavin Andresen
  0 siblings, 0 replies; 23+ messages in thread
From: Gavin Andresen @ 2011-08-05  0:07 UTC (permalink / raw)
  To: Matt Corallo; +Cc: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 1020 bytes --]

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)
-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 1163 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 19:42       ` Andy Parkins
  2011-08-04 20:07         ` Andrew Schaaf
@ 2011-08-04 20:08         ` Gregory Maxwell
  2011-08-04 20:33         ` Matt Corallo
  2011-08-04 21:36         ` Mike Hearn
  3 siblings, 0 replies; 23+ messages in thread
From: Gregory Maxwell @ 2011-08-04 20:08 UTC (permalink / raw)
  To: Andy Parkins; +Cc: 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

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 19:42       ` Andy Parkins
  2011-08-04 20:07         ` Andrew Schaaf
  2011-08-04 20:08         ` Gregory Maxwell
@ 2011-08-04 20:33         ` Matt Corallo
  2011-08-04 21:36         ` Mike Hearn
  3 siblings, 0 replies; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 20:33 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 7051 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 19:42       ` Andy Parkins
                           ` (2 preceding siblings ...)
  2011-08-04 20:33         ` Matt Corallo
@ 2011-08-04 21:36         ` Mike Hearn
  2011-08-04 22:16           ` Matt Corallo
  3 siblings, 1 reply; 23+ messages in thread
From: Mike Hearn @ 2011-08-04 21:36 UTC (permalink / raw)
  To: Andy Parkins; +Cc: bitcoin-development

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

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 21:36         ` Mike Hearn
@ 2011-08-04 22:16           ` Matt Corallo
  2011-08-05  0:14             ` Stefan Thomas
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-04 22:16 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 1475 bytes --]

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.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-04 22:16           ` Matt Corallo
@ 2011-08-05  0:14             ` Stefan Thomas
  2011-08-05 11:05               ` Mike Hearn
  2011-08-05 12:00               ` Matt Corallo
  0 siblings, 2 replies; 23+ messages in thread
From: Stefan Thomas @ 2011-08-05  0:14 UTC (permalink / raw)
  To: bitcoin-development

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.

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05  0:14             ` Stefan Thomas
@ 2011-08-05 11:05               ` Mike Hearn
  2011-08-05 11:58                 ` Andy Parkins
  2011-08-05 12:00               ` Matt Corallo
  1 sibling, 1 reply; 23+ messages in thread
From: Mike Hearn @ 2011-08-05 11:05 UTC (permalink / raw)
  To: Stefan Thomas; +Cc: bitcoin-development

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

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05 11:05               ` Mike Hearn
@ 2011-08-05 11:58                 ` Andy Parkins
  2011-08-05 12:06                   ` Matt Corallo
  0 siblings, 1 reply; 23+ messages in thread
From: Andy Parkins @ 2011-08-05 11:58 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: Text/Plain, Size: 1231 bytes --]

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

-- 
Dr Andy Parkins
andyparkins@gmail•com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05 11:58                 ` Andy Parkins
@ 2011-08-05 12:06                   ` Matt Corallo
  2011-08-05 13:03                     ` Andy Parkins
  0 siblings, 1 reply; 23+ messages in thread
From: Matt Corallo @ 2011-08-05 12:06 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 574 bytes --]

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.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05 12:06                   ` Matt Corallo
@ 2011-08-05 13:03                     ` Andy Parkins
  2011-08-05 21:23                       ` Gregory Maxwell
  2011-08-05 21:30                       ` Matt Corallo
  0 siblings, 2 replies; 23+ messages in thread
From: Andy Parkins @ 2011-08-05 13:03 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: Text/Plain, Size: 2133 bytes --]

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
-- 
Dr Andy Parkins
andyparkins@gmail•com

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05 13:03                     ` Andy Parkins
@ 2011-08-05 21:23                       ` Gregory Maxwell
  2011-08-05 21:30                       ` Matt Corallo
  1 sibling, 0 replies; 23+ messages in thread
From: Gregory Maxwell @ 2011-08-05 21:23 UTC (permalink / raw)
  To: Andy Parkins; +Cc: bitcoin-development

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.



^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05 13:03                     ` Andy Parkins
  2011-08-05 21:23                       ` Gregory Maxwell
@ 2011-08-05 21:30                       ` Matt Corallo
  1 sibling, 0 replies; 23+ messages in thread
From: Matt Corallo @ 2011-08-05 21:30 UTC (permalink / raw)
  To: Andy Parkins

[-- Attachment #1: Type: text/plain, Size: 968 bytes --]

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

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

* Re: [Bitcoin-development] Double spend detection to speed up transaction trust
  2011-08-05  0:14             ` Stefan Thomas
  2011-08-05 11:05               ` Mike Hearn
@ 2011-08-05 12:00               ` Matt Corallo
  1 sibling, 0 replies; 23+ messages in thread
From: Matt Corallo @ 2011-08-05 12:00 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 634 bytes --]

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.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

^ permalink raw reply	[flat|nested] 23+ messages in thread

end of thread, other threads:[~2011-08-05 21:31 UTC | newest]

Thread overview: 23+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-08-04 13:23 [Bitcoin-development] Double spend detection to speed up transaction trust Andy Parkins
2011-08-04 17:45 ` Matt Corallo
2011-08-04 18:22   ` Andy Parkins
2011-08-04 18:39     ` Matt Corallo
2011-08-04 19:42       ` Andy Parkins
2011-08-04 20:07         ` Andrew Schaaf
2011-08-04 20:38           ` Matt Corallo
2011-08-04 22:10             ` Stefan Thomas
2011-08-04 22:18               ` Gregory Maxwell
2011-08-04 22:21                 ` Matt Corallo
2011-08-05  0:07                   ` Gavin Andresen
2011-08-04 20:08         ` Gregory Maxwell
2011-08-04 20:33         ` Matt Corallo
2011-08-04 21:36         ` Mike Hearn
2011-08-04 22:16           ` Matt Corallo
2011-08-05  0:14             ` Stefan Thomas
2011-08-05 11:05               ` Mike Hearn
2011-08-05 11:58                 ` Andy Parkins
2011-08-05 12:06                   ` Matt Corallo
2011-08-05 13:03                     ` Andy Parkins
2011-08-05 21:23                       ` Gregory Maxwell
2011-08-05 21:30                       ` Matt Corallo
2011-08-05 12:00               ` Matt Corallo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox