* [Bitcoin-development] Bloom Filter Implementation
@ 2012-08-15 0:26 Matt Corallo
2012-08-15 10:07 ` Mike Hearn
0 siblings, 1 reply; 2+ messages in thread
From: Matt Corallo @ 2012-08-15 0:26 UTC (permalink / raw)
To: bitcoin-development
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
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [Bitcoin-development] Bloom Filter Implementation
2012-08-15 0:26 [Bitcoin-development] Bloom Filter Implementation Matt Corallo
@ 2012-08-15 10:07 ` Mike Hearn
0 siblings, 0 replies; 2+ messages in thread
From: Mike Hearn @ 2012-08-15 10:07 UTC (permalink / raw)
To: Matt Corallo; +Cc: bitcoin-development
This is great, thanks!
A few remarks:
If you have to update the filter after every block, IBD will require a
round-trip after every single block download instead of doing bulk
requests with getblocks. That sounds like it'd kill any performance
gains won by the feature. There needs to be a way to do bulk getblocks
on hundreds/thousands of blocks at a time and then have the data
stream in. Perhaps the server node can update the filter for you, as
the rules are deterministic?
As you know the remote end will request the transactions given their
hashes anyway, why not save the bandwidth for the hashes and the
network round-trip by just providing the transactions immediately in
the block? I was imagining something like:
// A CMerkleTx without the redundant block hash
class CLiteMerkleTx : public CTransaction {
std::vector<uint256> vBranch;
int nIndex;
}
class CMerkleBlock {
int nVersion;
uint256 hashPrevBlock;
uint256 hashMerkleRoot;
unsigned int nTime;
unsigned int nBits;
unsigned int nNonce;
std::vector<CLiteMerkleTx> vMatchedTxns;
}
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2012-08-15 10:07 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-08-15 0:26 [Bitcoin-development] Bloom Filter Implementation Matt Corallo
2012-08-15 10:07 ` Mike Hearn
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox