[bitcoin-dev] Compact Block Relay BIP

Gregory Maxwell greg at xiph.org
Tue May 10 02:12:03 UTC 2016

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
$ echo -n Perhaps. 0000000011ac0388 |sha256sum

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

More information about the bitcoin-dev mailing list