MIME-Version: 1.0
Sender: gmaxwell@gmail.com
In-Reply-To: <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>
	<5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com>
Date: Tue, 10 May 2016 02:12:03 +0000
Message-ID: <CAAS2fgR8j5QJkVb2rEfpi27OvN4gVw2ROaehLRvsojQd7yrpXg@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
To: Peter R <peter_r@gmx.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Development Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Compact Block Relay BIP
Precedence: list

On Mon, May 9, 2016 at 11:37 PM, Peter R <peter_r@gmx.com> wrote:
> It is a standard result that there are
>     m! / [n! (m-n)!]
> 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 ha=
ve to perform approximately 2^63 comparisons in order to identify which pai=
r 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

$ echo -n Perhaps. 00000000f2736d91 |sha256sum
359dfa6d4c2eb2ac81535392d68af4b5e1cb6d9c6321e8f111d3244329b6a4d8
$ echo -n Perhaps. 0000000011ac0388 |sha256sum
359dfa6d4c2eb2ac44d54d0ceeb2212500cb34617b9360695432f6c0fde9b006

Try search term "collision", or there may be an undergrad Data
structures and algorithms coarse online-- you want something covering
"cycle finding".

(Though even ignoring efficient cycle finding, your factorial argument
doesn't hold... you can simply sort the data... Search term
"quicksort" for a relevant algorithm).