Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk

2014-05-12 Thread Tom Harding
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 



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


Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk

2014-05-06 Thread Tom Harding
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 t...@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


--
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
#149; 3 signs your SCM is hindering your productivity
#149; Requirements for releasing software faster
#149; Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] A statistical consensus rule for reducing 0-conf double-spend risk

2014-05-03 Thread Christophe Biocca
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 t...@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

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