* [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk
@ 2014-05-04 0:29 Tom Harding
2014-05-04 2:54 ` Christophe Biocca
0 siblings, 1 reply; 5+ messages in thread
From: Tom Harding @ 2014-05-04 0:29 UTC (permalink / raw)
To: bitcoin-development
This idea was suggested by "Joe" on 2011-02-14
https://bitcointalk.org/index.php?topic=3441.msg48484#msg48484 . It
deserves another look.
Nodes today make a judgment regarding which of several conflicting
spends to accept, and which is a double-spend. But there is no
incorporation of these collective judgments into the blockchain. So
today, it's the wild west, right up until the next block. To address this:
- Using its own clock, node associates a timestamp with every
transaction upon first seeing its tx hash (at inv, in a block, or when
created)
- Node relays respend attempts (subject to anti-DOS rules, see github
PR #3883)
- Eventually, node adds a consensus rule:
Do not accept blocks containing a transaction tx2 where
- tx2 respends an output spent by another locally accepted
transaction tx1, and
- timestamp(tx2) - timestamp(tx1) > T
What is T?
According to http://bitcoinstats.com/network/propagation/ recent tx
propagation has a median of 1.3 seconds. If double-spender introduces
both transactions from the same node, assuming propagation times
distributed exponentially with median 1.3 seconds, the above consensus
rule with reject threshold T = 7.4 seconds would result in
mis-identification of the second-spend by less than 1% of nodes.*
If tx1 and tx2 are introduced in mutually time-distant parts of the
network, a population of nodes in between would be able to accept either
transaction, as they can today. But the attacker still has to introduce
them at close to the same time, or the majority of the network will
confirm the one introduced earlier.
Merchant is watching also, and these dynamics mean he will not have to
watch for very long to gain confidence if he was going to get
double-spent, he would have learned it by now. The consensus rule also
makes mining a never-broadcast double-spend quite difficult, because the
network assigns it very late timestamps. Miner has to get lucky and
find the block very quickly. In other words, it converges to a Finney
attack.
This would be the first consensus rule that anticipated less than 100%
agreement. But the parameters could be chosen so that it was still
extremely conservative. Joe also suggested a fail-safe condition: drop
this rule if block has 6 confirmations, to prevent a fork in unusual
network circumstances.
We can't move toward this, or any, solution without more data. Today,
the network is not transparent to double-spend attempts, so we mostly
have to guess what the quantitative effects would be. The first step is
to share the data broadly by relaying first double-spend attempts as in
github PR #3883.
*Calcs:
For Exp(lambda), median ln(2)/lambda = 1.3 ==> lambda = .533
Laplace(0,1/lambda) < .01 ==> T = 7.34 seconds
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk
2014-05-04 0:29 [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk Tom Harding
@ 2014-05-04 2:54 ` Christophe Biocca
2014-05-06 17:49 ` Tom Harding
2014-05-12 4:41 ` Tom Harding
0 siblings, 2 replies; 5+ messages in thread
From: Christophe Biocca @ 2014-05-04 2:54 UTC (permalink / raw)
To: bitcoin-development
Unfortunately this could fork the network permanently, which is much
worse than a double spend. There's no magic way to have a consensus,
so it becomes trivial with a few tries to split the network into two
halves: (tx1 before tx2, tx2 before tx1). Some nodes in the middle
will accept either block, but you've still forked off some non-zero
number of nodes.
At a minimum, you'd need a way to reconcile the split (Accept the
offending block once it's 2+ deep). The problem is that since the rule
isn't enforceable, no miner will wait before mining on the longest
chain (which is the rational move), and you're back to where we are
now.
On Sat, May 3, 2014 at 8:29 PM, Tom Harding <tomh@thinlink•com> wrote:
> This idea was suggested by "Joe" on 2011-02-14
> https://bitcointalk.org/index.php?topic=3441.msg48484#msg48484 . It
> deserves another look.
>
> Nodes today make a judgment regarding which of several conflicting
> spends to accept, and which is a double-spend. But there is no
> incorporation of these collective judgments into the blockchain. So
> today, it's the wild west, right up until the next block. To address this:
>
> - Using its own clock, node associates a timestamp with every
> transaction upon first seeing its tx hash (at inv, in a block, or when
> created)
> - Node relays respend attempts (subject to anti-DOS rules, see github
> PR #3883)
> - Eventually, node adds a consensus rule:
> Do not accept blocks containing a transaction tx2 where
> - tx2 respends an output spent by another locally accepted
> transaction tx1, and
> - timestamp(tx2) - timestamp(tx1) > T
>
> What is T?
>
> According to http://bitcoinstats.com/network/propagation/ recent tx
> propagation has a median of 1.3 seconds. If double-spender introduces
> both transactions from the same node, assuming propagation times
> distributed exponentially with median 1.3 seconds, the above consensus
> rule with reject threshold T = 7.4 seconds would result in
> mis-identification of the second-spend by less than 1% of nodes.*
>
> If tx1 and tx2 are introduced in mutually time-distant parts of the
> network, a population of nodes in between would be able to accept either
> transaction, as they can today. But the attacker still has to introduce
> them at close to the same time, or the majority of the network will
> confirm the one introduced earlier.
>
> Merchant is watching also, and these dynamics mean he will not have to
> watch for very long to gain confidence if he was going to get
> double-spent, he would have learned it by now. The consensus rule also
> makes mining a never-broadcast double-spend quite difficult, because the
> network assigns it very late timestamps. Miner has to get lucky and
> find the block very quickly. In other words, it converges to a Finney
> attack.
>
> This would be the first consensus rule that anticipated less than 100%
> agreement. But the parameters could be chosen so that it was still
> extremely conservative. Joe also suggested a fail-safe condition: drop
> this rule if block has 6 confirmations, to prevent a fork in unusual
> network circumstances.
>
> We can't move toward this, or any, solution without more data. Today,
> the network is not transparent to double-spend attempts, so we mostly
> have to guess what the quantitative effects would be. The first step is
> to share the data broadly by relaying first double-spend attempts as in
> github PR #3883.
>
>
> *Calcs:
> For Exp(lambda), median ln(2)/lambda = 1.3 ==> lambda = .533
> Laplace(0,1/lambda) < .01 ==> T = 7.34 seconds
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos. Get
> unparalleled scalability from the best Selenium testing platform available.
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk
2014-05-04 2:54 ` Christophe Biocca
@ 2014-05-06 17:49 ` Tom Harding
2014-05-12 4:41 ` Tom Harding
1 sibling, 0 replies; 5+ messages in thread
From: Tom Harding @ 2014-05-06 17:49 UTC (permalink / raw)
To: Christophe Biocca; +Cc: bitcoin-development
Christophe Biocca wrote:
> it becomes trivial with a few tries to split the network into two
> halves: (tx1 before tx2, tx2 before tx1).
"before" implies T=0. That is a much too optimistic choice for T; 50%
of nodes would misidentify the respend.
> Tom Harding <tomh@thinlink•com> wrote:
>> - Eventually, node adds a consensus rule:
>> Do not accept blocks containing a transaction tx2 where
>> - tx2 respends an output spent by another locally accepted
>> transaction tx1, and
>> - timestamp(tx2) - timestamp(tx1) > T
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk
2014-05-04 2:54 ` Christophe Biocca
2014-05-06 17:49 ` Tom Harding
@ 2014-05-12 4:41 ` Tom Harding
2014-05-12 13:04 ` Tom Harding
1 sibling, 1 reply; 5+ messages in thread
From: Tom Harding @ 2014-05-12 4:41 UTC (permalink / raw)
To: bitcoin-development
Christophe Biocca wrote:
> The problem is that since the rule
> isn't enforceable, no miner will wait before mining on the longest
> chain (which is the rational move), and you're back to where we are
> now.
Back up to the miner who decided to include a "seasoned" double-spend in
his block. Let's say he saw it 21 seconds after he saw an earlier
spend, and included it, despite the rule.
The expected cost of including the respend is any revenue loss from
doing so: (total miner revenue of block)*(fraction of hashpower
following the rule). So today, if only 1% of hashpower follows the rule
(ie a near total failure of consensus implementation), he still loses at
least .25 BTC.
.25 BTC is about 1000x the typical "double-spend premium" I'm seeing
right now. Wouldn't the greedy-rational miner just decide to include
the earlier spend instead?
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk
2014-05-12 4:41 ` Tom Harding
@ 2014-05-12 13:04 ` Tom Harding
0 siblings, 0 replies; 5+ messages in thread
From: Tom Harding @ 2014-05-12 13:04 UTC (permalink / raw)
To: bitcoin-development
Sorry to run on, a correction is needed. A much better approximation
requires that the rule-following minority finds the next TWO blocks, so
the cost is
(total miner revenue of block)*(fraction of hashpower following the rule)^2
So the lower bound cost in this very pessimistic scenario is .0025 BTC,
still quite high for one transaction. I guess miner could try to make a
business out of mining double-spends, to defray that cost.
On 5/11/2014 9:41 PM, Tom Harding wrote:
> Back up to the miner who decided to include a "seasoned" double-spend
> in his block. Let's say he saw it 21 seconds after he saw an earlier
> spend, and included it, despite the rule.
>
> The expected cost of including the respend is any revenue loss from
> doing so: (total miner revenue of block)*(fraction of hashpower
> following the rule). So today, if only 1% of hashpower follows the
> rule (ie a near total failure of consensus implementation), he still
> loses at least .25 BTC.
>
> .25 BTC is about 1000x the typical "double-spend premium" I'm seeing
> right now. Wouldn't the greedy-rational miner just decide to include
> the earlier spend instead
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2014-05-12 13:04 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-04 0:29 [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk Tom Harding
2014-05-04 2:54 ` Christophe Biocca
2014-05-06 17:49 ` Tom Harding
2014-05-12 4:41 ` Tom Harding
2014-05-12 13:04 ` Tom Harding
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox