public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Matt Corallo <bitcoin-list@bluematt.me>
To: bitcoin-development <bitcoin-development@lists.sourceforge.net>
Subject: [Bitcoin-development] Bloom Filter Implementation
Date: Wed, 15 Aug 2012 02:26:31 +0200	[thread overview]
Message-ID: <1344990391.4355.21.camel@bmthinkpad.lan.bluematt.me> (raw)

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<tx hash> 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




             reply	other threads:[~2012-08-15  0:26 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-08-15  0:26 Matt Corallo [this message]
2012-08-15 10:07 ` [Bitcoin-development] Bloom Filter Implementation Mike Hearn

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1344990391.4355.21.camel@bmthinkpad.lan.bluematt.me \
    --to=bitcoin-list@bluematt.me \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox