[bitcoin-dev] Compact Block Relay BIP

[Gregory Maxwell]

On Mon, May 9, 2016 at 11:37 PM, Peter R <peter_r at 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’t 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…

$ 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).