Combining bloom filters?
3 messages, 17 Aug 2013. Started by Jeff Garzik.
Jeff Garzik, Matt Corallo, Pieter Wuille
Consider wallet A builds bloom filter A' and wallet B builds bloom filter B'. Can A' and B' be or'd together to form a single bloom filter C' ?
Under some conditions, yes. The filters must have the same parameters (tweak, size, hash count). Bitcoinj implements this in its BloomFilter class.
Matt
Jeff Garzik <jgarzik@bitpay•com> wrote:
Quoted text (19 lines)
>Consider wallet A builds bloom filter A' and wallet B builds bloom >filter B'. Can A' and B' be or'd together to form a single bloom >filter C' ? > >-- >Jeff Garzik >Senior Software Engineer and open source evangelist >BitPay, Inc. https://bitpay.com/ > >------------------------------------------------------------------------------ >Get 100% visibility into Java/.NET code with AppDynamics Lite! >It's a free troubleshooting tool designed for production. >Get down to code-level detail for bottlenecks, with <2% overhead. >Download for free and get started troubleshooting in minutes. >http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk >_______________________________________________ >Bitcoin-development mailing list >Bitcoin-development@lists•sourceforge•net >https://lists.sourceforge.net/lists/listinfo/bitcoin-development
If both constructed bloom filters use the same seed and the same number of hash functions, yes. Assuming the input filters were optimal for a given FP rate, the resulting filter will be worse.