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
|
Return-Path: <peter_r@gmx.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9BE5D411
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 23:37:12 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mout.gmx.net (mout.gmx.net [212.227.15.15])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 99173123
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 23:37:11 +0000 (UTC)
Received: from [192.168.1.59] ([205.250.126.165]) by mail.gmx.com (mrgmx003)
with ESMTPSA (Nemesis) id 0MKqOW-1azujY2zjs-0001Bq;
Tue, 10 May 2016 01:37:05 +0200
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
From: Peter R <peter_r@gmx.com>
In-Reply-To: <CAAS2fgRL1=YSrAZVES0WBySyL1brZcvQsvZdsqUEY2-8UOFFiA@mail.gmail.com>
Date: Mon, 9 May 2016 16:37:00 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
References: <5727D102.1020807@mattcorallo.com> <86058327.pdmfHP132A@kiwi>
<CAAS2fgRiSNNHA5psaUYOM6rHfjJ1aOgWhnsT8Z-pU4FBcR_65w@mail.gmail.com>
<2273040.Bd6rtJjYLF@garp>
<CAAS2fgR01=SfpAdHhFd_DFa9VNiL=e1g4FiguVRywVVSqFe9rA@mail.gmail.com>
<CAAS2fgRL1=YSrAZVES0WBySyL1brZcvQsvZdsqUEY2-8UOFFiA@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>,
Bitcoin Development Discussion <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.2104)
X-Provags-ID: V03:K0:p3Z4JEzEFRvzUhre3y2wYPajiIkZOVHK7m56LM9WF70lafbIR0s
b2Iu9dLVGBPEw4YYsnv2yTobvZOOEAYHohCR1ywMTp+DrVJEdB1plLwkZTsy5sPjB9z7q5n
/3GMVS9sljxQjEin3uJHgINvDtnkATNJFOPUSyLKvGwoyVEhGk938iefT5Dvx2Bc61704gG
C7cLsHF9Q5J9y1Aym6Vnw==
X-UI-Out-Filterresults: notjunk:1;V01:K0:a4z1YH+rVHY=:4gvWrxT9P5PuDloyWlgXme
om+R3Whh6X0+aMy19I45Y66Z6Uz8DTiDsnBkiXqJUbaiiUynZO865Wn17L+aJc+CyDGCPq4zL
N44dU543xOYJoxYf725Wycv5K5AQ+J5sOXsO4p6E+GaHlAfSsgwTfL4xEnbhkmZ3zM+QanFEy
rgJzAV6YxeHg365FzeJU7cOUzXPg/BrFQlW1L3uR23LyPsXNBs7QCmeA3FwqjyDRZw/3eftma
dLGVF+kBwOT10vonsG+wNc0EMtKu8ASJJXtRimP+zwktnxQcB9IStftsgwIkxfpXgv7hU9cRF
L1eQi492o5UxUhsAuMtArAg4kRFr467Vhadq/D9w+Rhw4pWy5v+0QSQGeApbDV8kGRwK0xqUF
CQZDuPxMsLYE0dD7tUQCg8kaolFnofThDlt3mcEfJNfYOtVFESPfrMORIYJ/DsRGkERpWFuP1
R1GhMKj6KIdfGcpB+/Vbtpq4LIqJskdYiPiA9u+OycmRi5gA/YbDq4CbMAgbJ0c8LpndbSuAX
dmAtvvDX7LFBm/BRVNVDEfXvaJ3HFkv78X+Apytv0jDFyl5pT2g3qiw93RRuKxQfauqS+P3IT
tH43h5tTJ0Llxgk0s+AXdhio5WOPYzVRytqLJq1JEriELDFFOBldGMQcH5cT9VxTqVT8Rws0W
uikTeQiCd4KuVu9P6FMSpn3ktKEhJF4AM/iL+BPvROW+LLTGxfInJe0tCXbC9TM6FnPkB9gdb
pw3NH4huBu+dgP/tHA7TBQChQ8OQZ/Xc6Q6I9ehWnF8XzQTn3kPslpecw0j0GfSAlSOPdduF2
fTeTHZZ
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM,
RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 09 May 2016 23:43:19 +0000
Subject: Re: [bitcoin-dev] Compact Block Relay BIP
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 09 May 2016 23:37:12 -0000
Greg Maxwell wrote:
> What are you talking about? You seem profoundly confused here...
>=20
> I obtain some txouts. I write a transaction spending them in malleable
> form (e.g. sighash single and an op_return output).. then grind the
> extra output to produce different hashes. After doing this 2^32 times
> I am likely to find two which share the same initial 8 bytes of txid.
[9 May 16 @ 4:30 PDT]
I=E2=80=99m trying to understand the collision attack that you're =
explaining to Tom Zander. =20
Mathematica is telling me that if I generated 2^32 random transactions, =
that the chances that the initial 64-bits on one of the pairs of =
transactions is about 40%. So I am following you up to this point. =
Indeed, there is a good chance that a pair of transactions from a set of =
2^32 will have a collision in the first 64 bits. =20
But how do you actually find that pair from within your large set? The =
only way I can think of is to check if the first 64-bits is equal for =
every possible pair until I find it. How many possible pairs are there? =
=20
It is a standard result that there are=20
m! / [n! (m-n)!]=20
ways of picking n numbers from a set of m numbers, so there are
(2^32)! / [2! (2^32 - 2)!] ~ 2^63
possible pairs in a set of 2^32 transactions. So wouldn=E2=80=99t you =
have to perform approximately 2^63 comparisons in order to identify =
which pair of transactions are the two that collide?
Perhaps I made an error or there is a faster way to scan your set to =
find the collision. Happy to be corrected=E2=80=A6
Best regards,
Peter
|
