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>
Subject: Re: [bitcoin-dev] Compact Block Relay BIP
Precedence: list

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