Re: [Bitcoin-development] Draft BIP for Bloom filtering

[Pieter Wuille <pieter.wuille@gmail.com>]

On Wed, Oct 24, 2012 at 06:35:08PM +0200, Mike Hearn wrote:
> > * what does "each hash and key in the output script" mean exactly? what
> about the output script in its entirety?
> 
> It's an informal way to say data elements. If you insert a key then it
> matches both single and multi sig outputs regardless of location.

So all data push operations? Including or excluding 1-byte constants?

What about the entire output script? (if I want to match just one particular multisig output script)

> 
> > * is sharing parts of the merkle branches not worth it?
> 
> We think probably not.

I'm not sure. As soon as you have 129 transactions in a block (including coinbase), you need 8 path
entries for each included transaction, which requires more bytes than the transaction itself.

When you're including M out of N transactions of a block, you never need more than N-M path entries
in total to reconstruct the merkle root. With the proposed format, it requires M*ceil(log2(N)).

For a 1000-transaction block, when matching ~everything, you need >300 KiB of overhead, while almost
nothing is required.

-- 
Pieter