Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1TRQje-0003Ub-9E for bitcoin-development@lists.sourceforge.net; Thu, 25 Oct 2012 16:56:46 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.216.47 as permitted sender) client-ip=209.85.216.47; envelope-from=gmaxwell@gmail.com; helo=mail-qa0-f47.google.com; Received: from mail-qa0-f47.google.com ([209.85.216.47]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1TRQjd-0000eu-A9 for bitcoin-development@lists.sourceforge.net; Thu, 25 Oct 2012 16:56:46 +0000 Received: by mail-qa0-f47.google.com with SMTP id i29so4225681qaf.13 for ; Thu, 25 Oct 2012 09:56:40 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.214.130 with SMTP id ha2mr9008302qab.50.1351184199741; Thu, 25 Oct 2012 09:56:39 -0700 (PDT) Received: by 10.49.107.103 with HTTP; Thu, 25 Oct 2012 09:56:39 -0700 (PDT) In-Reply-To: References: Date: Thu, 25 Oct 2012 12:56:39 -0400 Message-ID: From: Gregory Maxwell To: Mike Hearn Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.3 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (gmaxwell[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature 0.3 AWL AWL: From: address is in the auto white-list X-Headers-End: 1TRQjd-0000eu-A9 Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Draft BIP for Bloom filtering X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Oct 2012 16:56:46 -0000 On Wed, Oct 24, 2012 at 11:56 AM, Mike Hearn wrote: > I've written a draft BIP describing the bloom filtering protocol > extension developed by myself and Matt. > > https://en.bitcoin.it/wiki/BIP_0037 Thanks for taking the time to write this up. I still don't understand what purpose the apparently gratuitous inefficiency of constantly resending common tree fragments. There are many points of complexity in this protocol=E2=80=94 handling premature disconnections without missing blocks, the actual implementation of the hash functions for the filter, validation of the hash tree, etc. Presumably these components will just get implemented a few times in some carefully constructed library code, so I don't see an implementation complexity argument here=E2=80=94 except the fact that it is= n't what Matt has implemented so far. The current design can cause massive overhead compared to pulling an unfiltered block should a filter be somewhat overboard and also makes this filtering useless for applications which would select a small but not tiny subset of the transactions (e.g. 10%). Also, it's not mentioned in the page=E2=80=94 but the hash function used is not cryptographically strong, so what prevents a complexity (well, bandwidth in this case) attack? someone could start using txids and txouts that collide with the maximum number of other existing txouts in order to waste bandwidth for people. Is this avenue of attack not a concern?