summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2012-10-24 19:11:05 +0200
committerbitcoindev <bitcoindev@gnusha.org>2012-10-24 17:11:15 +0000
commita2b193d5a02442acf42df048108b0999a0a10acc (patch)
treeff76667144b2ea3091c3a6dd343b0401f78b95c6
parent3ae66bfaaedf0668b082d9292322dad99833dc85 (diff)
downloadpi-bitcoindev-a2b193d5a02442acf42df048108b0999a0a10acc.tar.gz
pi-bitcoindev-a2b193d5a02442acf42df048108b0999a0a10acc.zip
Re: [Bitcoin-development] Draft BIP for Bloom filtering
-rw-r--r--24/5b512795dcdd9319909274f3b856ec1ccf355881
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
+
+