From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9B6BD74 for ; Tue, 10 May 2016 02:12:05 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf0-f43.google.com (mail-lf0-f43.google.com [209.85.215.43]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B163719A for ; Tue, 10 May 2016 02:12:04 +0000 (UTC) Received: by mail-lf0-f43.google.com with SMTP id y84so220552386lfc.0 for ; Mon, 09 May 2016 19:12:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-transfer-encoding; bh=27UZgNedO4UUNnjWHbGOUhzDGFcbepNWPAg4Qx2AL9A=; b=UW66znqg6LTjjlZoknDSQV9EkUP+bwGIi2zBVGIoZvNxeMki9n3swgX5lsNFf+k64G 6qBFEJcF0XvsRxMInrdkafEJt4nuC4l5ETZDBEZxgRzN05q4HJ0RBgkkYLqqGkhCP+G2 EthZEdb+wWd22E7Ebm4DZGYiz2grt0jfXpJfPo3V+OdgiKROzG1VQogBnbAqSkFGyH+C AvFRF0muKEzKQiaGMS0clBC3N7SxY4ektV6AyD8tKTETijLZzmn0AWEm5OG78oBC2U4h Vo+tZMmwgOochcMEmGIbLc/rJ8rR6ttiVhYwGi5kSM+gfSW18eBM3QrXeaFOPx6EaFZr hqQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc:content-transfer-encoding; bh=27UZgNedO4UUNnjWHbGOUhzDGFcbepNWPAg4Qx2AL9A=; b=IZKfRjGUqwEpBrhcJSBeNK7V25r+E4LivH9n4+rp2PVhLRBQNSSAhfOrvyy35GAxg2 TJfRYnE1TG/85d3CIwEpoNPFWpoPLUSeUFO+ma63YSmK/txdngsY2dETIm0Buyjg5l4/ QDVkNOkCc5vMD2kd40AzZU6OIqZ4G98XlmaleqPWPqVqBpa7mYBPpjClTouMXpmcAITo eJxdcXwGP4Lk/tT0nM96bQMDZFET8HnXwTAQniuIyMOZUHWDjOOoFJ+TD0oaAVS2fVcW yrfGylzrWhReKaXIPBsyhSXz6GBgce0YikWLz5vkoc7eHp4ALNiURULMA6tjISd3iIz2 qNJg== X-Gm-Message-State: AOPr4FUBVOEywOwadSHQBrgEUX2WHwegCX22bEnMInwZtIV9UV6eTMcMKM4JLXo8lJO5VLvplBXenKUtAbtS0g== MIME-Version: 1.0 X-Received: by 10.25.77.204 with SMTP id a195mr16967617lfb.14.1462846323121; Mon, 09 May 2016 19:12:03 -0700 (PDT) Sender: gmaxwell@gmail.com Received: by 10.112.65.108 with HTTP; Mon, 9 May 2016 19:12:03 -0700 (PDT) In-Reply-To: <5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com> References: <5727D102.1020807@mattcorallo.com> <86058327.pdmfHP132A@kiwi> <2273040.Bd6rtJjYLF@garp> <5C2809F9-286D-49E4-89DB-7109B73F6076@gmx.com> Date: Tue, 10 May 2016 02:12:03 +0000 X-Google-Sender-Auth: QfQGgRhoNcYgSC-1Qs4mTPT8NX8 Message-ID: From: Gregory Maxwell To: Peter R Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Development Discussion Subject: Re: [bitcoin-dev] Compact Block Relay BIP X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 10 May 2016 02:12:05 -0000 On Mon, May 9, 2016 at 11:37 PM, Peter R 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).