[Bitcoin-development] DS Deprecation Window

[Bitcoin-development] DS Deprecation Window

[Tom Harding]

Greetings Bitcoin Dev,

This is a proposal to improve the ability of bitcoin users to rely on 
unconfirmed transactions.  It can be adopted incrementally, with no hard 
or soft fork required.

https://github.com/dgenr8/out-there/blob/master/ds-dep-win.md

Your thoughtful feedback would be very much appreciated.

It is not yet implemented anywhere.

Cheers,
Tom Harding
CA, USA

Re: [Bitcoin-development] DS Deprecation Window

[Matt Corallo]

It is a very bad idea to delay relaying/accepting blocks based on
information which is only local to your node (ie would create the
ability for people to split the network by sending out lots of
double-spends to different parts of the network at the same time). Thus,
miners are incentivized to go connect to everyone on the network and
look for double-spends, not including them in their blocks to avoid
being delayed (which is OK, except having to connect to everyone is bad).
There is a related concept of "discouraging" blocks which generally only
refers to mining on a previous block, but you have to be careful doing
that so you dont break consensus.

On 10/27/14 19:58, Tom Harding wrote:
> Greetings Bitcoin Dev,
> 
> This is a proposal to improve the ability of bitcoin users to rely on 
> unconfirmed transactions.  It can be adopted incrementally, with no hard 
> or soft fork required.
> 
> https://github.com/dgenr8/out-there/blob/master/ds-dep-win.md
> 
> Your thoughtful feedback would be very much appreciated.
> 
> It is not yet implemented anywhere.
> 
> Cheers,
> Tom Harding
> CA, USA
> 
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] DS Deprecation Window

[Tom Harding]

Matt,

You're right, thanks.  Without double-spend relay, miner won't know that 
some txes conflict with anything.  I'll add that first-double-spends are 
relayed per #4570.

Miner has to be very careful including a double-spend in his block -- he 
hopes:

  - that based on his measured time offset from the first spend he 
received, at most a tiny fraction of the network will delay his block

  - that not too many nodes saw an earlier spend that he didn't see, 
which could increase that fraction

  - that most other nodes saw his tx.  Any who didn't will only learn 
about it by receiving his block, and they will assign it the time when 
they receive the block.  That's likely to be more than T (30 seconds) 
after an earlier spend, so they would delay the block.

The best course of action is intended to be for miner to exclude fast (< 
2 hours) double spends completely.


On 10/27/2014 1:17 PM, Matt Corallo wrote:
> miners are incentivized to go connect to everyone on the network and
> look for double-spends
>
> On 10/27/14 19:58, Tom Harding wrote:
>> https://github.com/dgenr8/out-there/blob/master/ds-dep-win.md

Re: [Bitcoin-development] DS Deprecation Window

[Gregory Maxwell]

On Tue, Oct 28, 2014 at 2:26 AM, Tom Harding <tomh@thinlink.com> wrote:
> Matt,
>
> You're right, thanks.  Without double-spend relay, miner won't know that
> some txes conflict with anything.

Even with that, the miner cannot tell, his only safe option is to
include no transactions at all.

Consider a malicious miner can concurrently flood all other miners
with orthogonal double spends (which he doesn't mine himself). These
other miners will all be spending some amount of their time mining on
these transactions before realizing others consider them
double-spends.

Re: [Bitcoin-development] DS Deprecation Window

[Thomas Zander]

On Monday 27. October 2014 19.26.48 Tom Harding wrote:
> Miner has to be very careful including a double-spend in his block -- he 
> hopes:

How does it help the zero-confirmation to not include a payment? Doesn't that 
just mean that if I send a double spend that neither of the payments will be 
made? So the thief just got an even bigger incentive to double-spent!
 

>   - that based on his measured time offset from the first spend he 
> received, at most a tiny fraction of the network will delay his block
>
>   - that not too many nodes saw an earlier spend that he didn't see, 
> which could increase that fraction
> 
>   - that most other nodes saw his tx.  Any who didn't will only learn 
> about it by receiving his block, and they will assign it the time when 
> they receive the block.  That's likely to be more than T (30 seconds) 
> after an earlier spend, so they would delay the block.

This doesn't addresses the point that Matt brought up.
Your proposal essentially has some side effects that would be disastrous to 
miners. As detailed by the other two replies on this thread.

Re: [Bitcoin-development] DS Deprecation Window

[Tom Harding]

On 10/27/2014 7:36 PM, Gregory Maxwell wrote:
> Consider a malicious miner can concurrently flood all other miners
> with orthogonal double spends (which he doesn't mine himself). These
> other miners will all be spending some amount of their time mining on
> these transactions before realizing others consider them
> double-spends.

If I understand correctly, the simplest example of this attack is three 
transactions spending the same coin, distributed to two miners like this:

             Miner A    Miner B
Mempool       tx1a       tx1b
Relayed       tx2        tx2

Since relay has to be limited, Miner B doesn't know about tx1a until it 
is included in Miner A's block, so he delays that block (unless it 
appears very quickly).

To create this situation, attacker has to transmit all three 
transactions very quickly, or mempools will be too synchronized. 
Attacker tries to make it so that everyone else has a tx1a conflict that 
Miner A does not have.  Ditto for each individual victim, with different 
transactions (this seems very difficult).

Proposal shows that there is always a tiny risk to including tx1 when a 
double-spend is known, and I agree that this attack can add something to 
that risk.  Miner A can neutralize his risk by excluding any tx1 known 
to be double-spent, but as Thomas Zander wrote, that is an undesirable 
outcome.

However, Miner A has additional information - he knows how soon he 
received tx2 after receiving tx1a.

The attack has little chance of working if any of the malicious 
transactions are sent even, say, 10 seconds apart from each other. 
Dropping the labels for transmit-order numbering, if the 1->2 transmit 
gap is large, mempools will agree on 1.  If 1->2 gap is small, but the 
gap to 3 is large, mempools will agree on the 1-2 pair, but possibly 
have the order reversed.  Either way, mempools won't disagree on the 
existence of 1 unless the 1->3 gap is small.

So, I think it will be possible to quantify and target the risk of 
including tx1a to an arbitrarily low level, based on the local 
measurement of the time gap to tx2, and an effective threshold won't be 
very high.  It does highlight yet again, the shorter the time frame, the 
greater the risk.

Re: [Bitcoin-development] DS Deprecation Window

[Tom Harding]

Added a section "Confidence to include tx1" and subsection "Deliberate 
delay attack"
https://github.com/dgenr8/out-there/blob/master/ds-dep-win.md

I found that under concerted attack, if miner excludes any transaction 
first seen less than 30 seconds ago, or double-spent less than 30 
seconds after first seen, he should expect 5 of 10000 nodes to delay his 
block.

Hal Finney remarked that this idea would need "careful analysis." More 
help is very welcome.
https://bitcointalk.org/index.php?topic=3441.msg48789#msg48789

Cheers!

On 10/28/2014 10:38 AM, Tom Harding wrote:
> So, I think it will be possible to quantify and target the risk of 
> including tx1...
>