Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1TR4U7-0003TN-Od for bitcoin-development@lists.sourceforge.net; Wed, 24 Oct 2012 17:11:15 +0000 X-ACL-Warn: Received: from vps7135.xlshosting.net ([178.18.90.41]) by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1TR4U3-0006xD-Ez for bitcoin-development@lists.sourceforge.net; Wed, 24 Oct 2012 17:11:15 +0000 Received: by vps7135.xlshosting.net (Postfix, from userid 1000) id C47EA494008; Wed, 24 Oct 2012 19:11:05 +0200 (CEST) Date: Wed, 24 Oct 2012 19:11:05 +0200 From: Pieter Wuille To: Mike Hearn Message-ID: <20121024171104.GA31766@vps7135.xlshosting.net> References: <20121024162255.GA30290@vps7135.xlshosting.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-PGP-Key: http://sipa.ulyssis.org/pubkey.asc User-Agent: Mutt/1.5.21 (2010-09-15) X-Spam-Score: 0.5 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (pieter.wuille[at]gmail.com) 0.0 DKIM_ADSP_CUSTOM_MED No valid author signature, adsp_override is CUSTOM_MED -0.7 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain 1.2 NML_ADSP_CUSTOM_MED ADSP custom_med hit, and not from a mailing list X-Headers-End: 1TR4U3-0006xD-Ez Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] Draft BIP for Bloom filtering X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Oct 2012 17:11:15 -0000 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