Date: Wed, 24 Oct 2012 19:11:05 +0200
From: Pieter Wuille <pieter.wuille@gmail.com>
To: Mike Hearn <mike@plan99.net>
Message-ID: <20121024171104.GA31766@vps7135.xlshosting.net>
References: <CANEZrP0XALwBFJyZTzYd5xBp4MRrjv0s_y2tOXbO7UgjWF2HzA@mail.gmail.com>
	<20121024162255.GA30290@vps7135.xlshosting.net>
	<CANEZrP1sxtOb+czMtBTkmzngEwMYRqD667WyKQkAOKLi+mGBGQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CANEZrP1sxtOb+czMtBTkmzngEwMYRqD667WyKQkAOKLi+mGBGQ@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Draft BIP for Bloom filtering
Precedence: list

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