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: <5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
Date: Mon, 9 May 2016 18:42:45 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <6BF6388E-2D1F-4A3D-BA57-B1AA94E40F7A@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>
	<5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Compact Block Relay BIP
Precedence: list

[9 May 16 @ 6:40 PDT]

For those interested in the hash collision attack discussion, it turns =
out there is a faster way to scan your set to find the collision:  =
you=E2=80=99d keep a sorted list of the hashes for each TX you generate =
and then use binary search to check that list for a collision for each =
new TX you randomly generate. Performing these operations can probably =
be reduced to N lg N complexity, which is doable for N ~2^32.   In other =
words, I now agree that the attack is feasible. =20

Cheers,
Peter

hat tip to egs

> On May 9, 2016, at 4:37 PM, Peter R via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> Greg Maxwell wrote:
>=20
>> 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.
>=20
> [9 May 16 @ 4:30 PDT]
>=20
> I=E2=80=99m trying to understand the collision attack that you're =
explaining to Tom Zander. =20
>=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
>=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
>=20
> It is a standard result that there are=20
>=20
>    m! / [n! (m-n)!]=20
>=20
> ways of picking n numbers from a set of m numbers, so there are
>=20
>    (2^32)! / [2! (2^32 - 2)!] ~ 2^63
>=20
> 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?
>=20
> 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
>=20
> Best regards,
> Peter
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev