summaryrefslogtreecommitdiff
path: root/b2/7bd46249a44e9fa41e5c437cb21f070ccd0895
blob: 1c95a93168fbcc2545b43d92c73a4ef0bab69885 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <tomh@thinlink.com>) id 1WgkPR-0005Bn-98
	for bitcoin-development@lists.sourceforge.net;
	Sun, 04 May 2014 00:36:01 +0000
X-ACL-Warn: 
Received: from mail-pd0-f182.google.com ([209.85.192.182])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1WgkPQ-0003to-7n
	for bitcoin-development@lists.sourceforge.net;
	Sun, 04 May 2014 00:36:01 +0000
Received: by mail-pd0-f182.google.com with SMTP id fp1so1057000pdb.13
	for <bitcoin-development@lists.sourceforge.net>;
	Sat, 03 May 2014 17:35:54 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to
	:subject:content-type:content-transfer-encoding;
	bh=1dQ9/mhIbOGxLu6VO+qaqpE5VVz3IhlsbMZWZ2B0Ua0=;
	b=f8qBWWUVc7dImXwXx1BwgVB8Ce75qjRrHmvovsGsCU6LMHiZ4RVMorU5gpKWaNkZXF
	ezsCdCjCw2+S7YynSkrNTpJQAH4LItMDkEIJQY0k9mYEqvq+I41R0O0nOBu2Eyz5YVxt
	iFtmcilbB4s98hCHPH5mPZoEl/i8RXV28uKIYGGxk2m1bNQVqNNTd1UnL0vRns+ylms0
	vy85sjKYtHjcEQL2TszNOosvoNOrvGDMLET3pSTNlt+bqSTU0Tr2ep+4ZVMfinxPd3nu
	C2/J+FRjByT0N+R+bAMbBAJDHjZe5BQIs3VAN8bMcuJ/gR/fL3nNvOSYRq2IxyCUoPTQ
	QcpA==
X-Gm-Message-State: ALoCoQlN4P9W27DmLgjTJlMSMYlaDXoLvM8SLrcdY0p1xv8X7DDDWhy5jLTltHymbaly3ByYmpfE
X-Received: by 10.66.119.136 with SMTP id ku8mr53822603pab.121.1399163341078; 
	Sat, 03 May 2014 17:29:01 -0700 (PDT)
Received: from [192.168.1.89] (99-6-44-248.lightspeed.sntcca.sbcglobal.net.
	[99.6.44.248]) by mx.google.com with ESMTPSA id
	ry8sm30768596pac.29.2014.05.03.17.28.59
	for <bitcoin-development@lists.sourceforge.net>
	(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
	Sat, 03 May 2014 17:29:00 -0700 (PDT)
Message-ID: <536589CC.8080005@thinlink.com>
Date: Sat, 03 May 2014 17:29:00 -0700
From: Tom Harding <tomh@thinlink.com>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64;
	rv:24.0) Gecko/20100101 Thunderbird/24.5.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
	See http://spamassassin.org/tag/ for more details.
	-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
	no trust [209.85.192.182 listed in list.dnswl.org]
X-Headers-End: 1WgkPQ-0003to-7n
Subject: [Bitcoin-development] A statistical consensus rule for reducing
	0-conf double-spend risk
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sun, 04 May 2014 00:36:01 -0000

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