diff options
author | Pieter Wuille <pieter.wuille@gmail.com> | 2012-10-24 19:11:05 +0200 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2012-10-24 17:11:15 +0000 |
commit | a2b193d5a02442acf42df048108b0999a0a10acc (patch) | |
tree | ff76667144b2ea3091c3a6dd343b0401f78b95c6 | |
parent | 3ae66bfaaedf0668b082d9292322dad99833dc85 (diff) | |
download | pi-bitcoindev-a2b193d5a02442acf42df048108b0999a0a10acc.tar.gz pi-bitcoindev-a2b193d5a02442acf42df048108b0999a0a10acc.zip |
Re: [Bitcoin-development] Draft BIP for Bloom filtering
-rw-r--r-- | 24/5b512795dcdd9319909274f3b856ec1ccf3558 | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/24/5b512795dcdd9319909274f3b856ec1ccf3558 b/24/5b512795dcdd9319909274f3b856ec1ccf3558 new file mode 100644 index 000000000..d4d0fa0a0 --- /dev/null +++ b/24/5b512795dcdd9319909274f3b856ec1ccf3558 @@ -0,0 +1,81 @@ +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 <pw@vps7135.xlshosting.net>) 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 <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> +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 <bitcoin-development@lists.sourceforge.net> +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: <bitcoin-development.lists.sourceforge.net> +List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe> +List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development> +List-Post: <mailto:bitcoin-development@lists.sourceforge.net> +List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help> +List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>, + <mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 + + |