From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1T1RRZ-0001Xh-45 for bitcoin-development@lists.sourceforge.net; Wed, 15 Aug 2012 00:26:41 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of bluematt.me designates 173.246.101.161 as permitted sender) client-ip=173.246.101.161; envelope-from=bitcoin-list@bluematt.me; helo=mail.bluematt.me; Received: from vps.bluematt.me ([173.246.101.161] helo=mail.bluematt.me) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1T1RRY-0007F0-1U for bitcoin-development@lists.sourceforge.net; Wed, 15 Aug 2012 00:26:41 +0000 Received: from [IPv6:2001:470:9ff2:1:221:ccff:fe5d:b72] (unknown [IPv6:2001:470:9ff2:1:221:ccff:fe5d:b72]) by mail.bluematt.me (Postfix) with ESMTPSA id A90223A2E for ; Wed, 15 Aug 2012 00:26:33 +0000 (UTC) Message-ID: <1344990391.4355.21.camel@bmthinkpad.lan.bluematt.me> From: Matt Corallo To: bitcoin-development Date: Wed, 15 Aug 2012 02:26:31 +0200 Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.4.3-1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-Spam-Score: -1.5 (-) 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 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1T1RRY-0007F0-1U Subject: [Bitcoin-development] Bloom Filter Implementation 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: Wed, 15 Aug 2012 00:26:41 -0000 I spend some time implementing some of the changes discussed in the previous thread "New P2P commands for diagnostics, SPV clients", and wanted to field comments before I write up a BIP. I have implemented a simple bloom filter that works on transactions as well as a new block relay type which relays blocks as header+coinbase tx +vector which allows for faster relay for clients which already have transactions in memory pool. In order to request that all future MSG_TX inv messages and blocks (only those relayed in the new format) are filtered, SPV clients will send a filterload message with a serialized bloom filter. Nodes can also send filteradd messages which add particular data blocks to the filter (not recommended for anonymity) and call filterclear which disables filtering on a node's connection until re-enabled. The filter will match any tx which: 1. Has a script data element in either a scriptPubKey or scriptSig which matches the filter. 2. Spends an input who's COutPoint is in the filter. 3. Has a hash in the filter (see #4 for why this matters). 4. Has a script data element in a prevout's scriptPubKey. This allows for matching pay-to-pubkey transactions without sending a new filter after each transaction which matched (which would cause some nasty timing issues where you may miss transactions if you get transactions back-to-back before you can send a new filter). Matching of prevouts only occurs on free txes, not those in blocks. Thus, before requesting a block, SPV clients should update the remote node's filter, if required, to be sure it includes the hash of any transaction which would not otherwise match the filter so that the node knows when its transactions are included in blocks. I can't say I'm a big fan of requiring SPV nodes constantly update the filter when they learn about new transactions (could get nasty during IDB, if the node has a lot of transactions, as you could end up re-requesting blocks many times), but I really don't think its worth loading all prevouts when a node is in IBD to fix it. The branch can be found at https://github.com/TheBlueMatt/bitcoin/compare/master...bloom Matt