* [Bitcoin-development] Draft BIP for Bloom filtering
@ 2012-10-24 15:56 Mike Hearn
2012-10-24 16:22 ` Pieter Wuille
` (2 more replies)
0 siblings, 3 replies; 34+ messages in thread
From: Mike Hearn @ 2012-10-24 15:56 UTC (permalink / raw)
To: Bitcoin Dev
I've written a draft BIP describing the bloom filtering protocol
extension developed by myself and Matt.
https://en.bitcoin.it/wiki/BIP_0037
(yes I know there's some kind of process around getting allocated a
number - it seems overkill for this).
Please read it and let me know if there are any missing details or
things which sound wrong.
Design-wise, it occurred to me as I wrote the BIP that the method of
delaying reception of invs is a bit ad-hoc. It may be better to have a
bloom filter be sent in the version message itself. On the other hand,
having a flag to delay invs means that the filter can be calculated in
parallel to bringing up the network connections. Whilst actually
making a Bloom filter is fast, with deterministic wallets you may need
to do a lot of calculations to find the keys to scan for.
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 15:56 [Bitcoin-development] Draft BIP for Bloom filtering Mike Hearn @ 2012-10-24 16:22 ` Pieter Wuille 2012-10-24 16:35 ` Mike Hearn 2012-10-25 16:56 ` Gregory Maxwell 2012-11-21 15:15 ` Pieter Wuille 2 siblings, 1 reply; 34+ messages in thread From: Pieter Wuille @ 2012-10-24 16:22 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote: > I've written a draft BIP describing the bloom filtering protocol > extension developed by myself and Matt. > > https://en.bitcoin.it/wiki/BIP_0037 > > Please read it and let me know if there are any missing details or > things which sound wrong. Some questions: * why limit the number of matching transactions to 255? * what does "each hash and key in the output script" mean exactly? what about the output script in its entirety? * is sharing parts of the merkle branches not worth it? > Design-wise, it occurred to me as I wrote the BIP that the method of > delaying reception of invs is a bit ad-hoc. It may be better to have a > bloom filter be sent in the version message itself. On the other hand, > having a flag to delay invs means that the filter can be calculated in > parallel to bringing up the network connections. Whilst actually > making a Bloom filter is fast, with deterministic wallets you may need > to do a lot of calculations to find the keys to scan for. I'm not in favor of stuffing too much into the version message, it already seems overloaded. A byte with some bit-flags is fine by me - higher bits can later be added for other boolean flags. -- Pieter ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 16:22 ` Pieter Wuille @ 2012-10-24 16:35 ` Mike Hearn 2012-10-24 17:11 ` Pieter Wuille 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2012-10-24 16:35 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 446 bytes --] > Some questions: > * why limit the number of matching transactions to 255? Copy/paste error in the does :( > * 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. > * is sharing parts of the merkle branches not worth it? We think probably not. [-- Attachment #2: Type: text/html, Size: 530 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 16:35 ` Mike Hearn @ 2012-10-24 17:11 ` Pieter Wuille 2012-10-24 18:54 ` Gavin Andresen 0 siblings, 1 reply; 34+ messages in thread From: Pieter Wuille @ 2012-10-24 17:11 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev 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 ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 17:11 ` Pieter Wuille @ 2012-10-24 18:54 ` Gavin Andresen 2012-10-24 19:00 ` Matt Corallo 2012-10-24 19:10 ` Mike Hearn 0 siblings, 2 replies; 34+ messages in thread From: Gavin Andresen @ 2012-10-24 18:54 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Dev RE: sharing parts of the merkle branches when returning a 'merkleblock' : I think I agree that complicating the BIP for what should be a very rare case (more than a handful of transactions in a block match the transactions in your wallet) is the right decision. I want to make sure I'm understanding this bit correctly: "In addition, because a merkleblock message contains only a list of transaction hashes, any transactions that the requesting node hasn't either received or announced with an inv will be automatically sent as well. This avoids a slow roundtrip that would otherwise be required (receive hashes, didn't see some of these transactions yet, ask for them)." Requiring serving/relaying nodes to keep track of which transactions they have or have not sent to their peers makes me nervous. I think requiring an extra 'inv' round-trip would be simpler to implement and less likely to lead to some kind of DoS attack. -- -- Gavin Andresen ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 18:54 ` Gavin Andresen @ 2012-10-24 19:00 ` Matt Corallo 2012-10-24 19:10 ` Mike Hearn 1 sibling, 0 replies; 34+ messages in thread From: Matt Corallo @ 2012-10-24 19:00 UTC (permalink / raw) To: bitcoin-development On Wed, 2012-10-24 at 14:54 -0400, Gavin Andresen wrote: > RE: sharing parts of the merkle branches when returning a 'merkleblock' : > > I think I agree that complicating the BIP for what should be a very > rare case (more than a handful of transactions in a block match the > transactions in your wallet) is the right decision. I believe you meant NOT complicating? > > I want to make sure I'm understanding this bit correctly: > > "In addition, because a merkleblock message contains only a list of > transaction hashes, any transactions that the requesting node hasn't > either received or announced with an inv will be automatically sent as > well. This avoids a slow roundtrip that would otherwise be required > (receive hashes, didn't see some of these transactions yet, ask for > them)." > > Requiring serving/relaying nodes to keep track of which transactions > they have or have not sent to their peers makes me nervous. I think > requiring an extra 'inv' round-trip would be simpler to implement and > less likely to lead to some kind of DoS attack. > Sadly that requires (potentially) more DoS potential because you require nodes to store each transaction that could be requested instead of just going ahead and forwarding them. I agree the BIP should not specify that the sending node is required to keep track of which transactions have been announced/sent to clients, however since the reference client does so currently, that implementation is significantly simpler (note that it is a bounded set in the reference client, so even the reference client doesn't really fully comply with the BIP as stated here). Matt ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 18:54 ` Gavin Andresen 2012-10-24 19:00 ` Matt Corallo @ 2012-10-24 19:10 ` Mike Hearn 2012-10-24 20:29 ` Gavin Andresen 1 sibling, 1 reply; 34+ messages in thread From: Mike Hearn @ 2012-10-24 19:10 UTC (permalink / raw) To: Gavin Andresen; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1326 bytes --] Bitcoin already keeps track of which nodes have seen what to avoid redundant inv announcements. I think if you are approaching most transactions in a block matching the filter then you would just request full blocks and do all the filtering client side On Oct 24, 2012 8:54 PM, "Gavin Andresen" <gavinandresen@gmail•com> wrote: > RE: sharing parts of the merkle branches when returning a 'merkleblock' : > > I think I agree that complicating the BIP for what should be a very > rare case (more than a handful of transactions in a block match the > transactions in your wallet) is the right decision. > > I want to make sure I'm understanding this bit correctly: > > "In addition, because a merkleblock message contains only a list of > transaction hashes, any transactions that the requesting node hasn't > either received or announced with an inv will be automatically sent as > well. This avoids a slow roundtrip that would otherwise be required > (receive hashes, didn't see some of these transactions yet, ask for > them)." > > Requiring serving/relaying nodes to keep track of which transactions > they have or have not sent to their peers makes me nervous. I think > requiring an extra 'inv' round-trip would be simpler to implement and > less likely to lead to some kind of DoS attack. > > -- > -- > Gavin Andresen > [-- Attachment #2: Type: text/html, Size: 1685 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 19:10 ` Mike Hearn @ 2012-10-24 20:29 ` Gavin Andresen 2012-10-24 20:58 ` Mike Hearn 2012-10-24 21:55 ` Jeff Garzik 0 siblings, 2 replies; 34+ messages in thread From: Gavin Andresen @ 2012-10-24 20:29 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Wed, Oct 24, 2012 at 3:10 PM, Mike Hearn <mike@plan99•net> wrote: > Bitcoin already keeps track of which nodes have seen what to avoid redundant > inv announcements. Oops, right. That memory usage is bounded right now by bounds on the memory pool size, though, right? (I'm being lazy and not digging into that code) What is the worst-case for an attacker interested in trying to get you to saturate your upstream bandwidth or use lots of memory? Set a bloom filter that matches everything, and then start requesting old blocks in the chain? It would be nice if the worst-case was no worse than the worst-case we've got now (... requesting full, old blocks...). -- -- Gavin Andresen ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 20:29 ` Gavin Andresen @ 2012-10-24 20:58 ` Mike Hearn 2012-10-24 21:55 ` Jeff Garzik 1 sibling, 0 replies; 34+ messages in thread From: Mike Hearn @ 2012-10-24 20:58 UTC (permalink / raw) To: Gavin Andresen; +Cc: Bitcoin Dev > What is the worst-case for an attacker interested in trying to get you > to saturate your upstream bandwidth or use lots of memory? Set a > bloom filter that matches everything, and then start requesting old > blocks in the chain? It would be slightly worse than shipping a full block but not seriously so. If you just want to saturate bandwidth or disk IOPS you could probably just request random blocks over and over again. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 20:29 ` Gavin Andresen 2012-10-24 20:58 ` Mike Hearn @ 2012-10-24 21:55 ` Jeff Garzik 1 sibling, 0 replies; 34+ messages in thread From: Jeff Garzik @ 2012-10-24 21:55 UTC (permalink / raw) To: Gavin Andresen; +Cc: Bitcoin Dev On Wed, Oct 24, 2012 at 4:29 PM, Gavin Andresen <gavinandresen@gmail•com> wrote: > Oops, right. That memory usage is bounded right now by bounds on the > memory pool size, though, right? (I'm being lazy and not digging into > that code) Correct me if I'm wrong but... I do not think there is any bound on mempool size. My proposal to age-out long-unconfirmed transactions is related, but does not completely solve the unbounded-size issue. -- Jeff Garzik exMULTI, Inc. jgarzik@exmulti•com ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 15:56 [Bitcoin-development] Draft BIP for Bloom filtering Mike Hearn 2012-10-24 16:22 ` Pieter Wuille @ 2012-10-25 16:56 ` Gregory Maxwell 2012-10-25 17:01 ` Gregory Maxwell 2012-10-26 14:01 ` Mike Hearn 2012-11-21 15:15 ` Pieter Wuille 2 siblings, 2 replies; 34+ messages in thread From: Gregory Maxwell @ 2012-10-25 16:56 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Wed, Oct 24, 2012 at 11:56 AM, Mike Hearn <mike@plan99•net> wrote: > I've written a draft BIP describing the bloom filtering protocol > extension developed by myself and Matt. > > https://en.bitcoin.it/wiki/BIP_0037 Thanks for taking the time to write this up. I still don't understand what purpose the apparently gratuitous inefficiency of constantly resending common tree fragments. There are many points of complexity in this protocol— handling premature disconnections without missing blocks, the actual implementation of the hash functions for the filter, validation of the hash tree, etc. Presumably these components will just get implemented a few times in some carefully constructed library code, so I don't see an implementation complexity argument here— except the fact that it isn't what Matt has implemented so far. The current design can cause massive overhead compared to pulling an unfiltered block should a filter be somewhat overboard and also makes this filtering useless for applications which would select a small but not tiny subset of the transactions (e.g. 10%). Also, it's not mentioned in the page— but the hash function used is not cryptographically strong, so what prevents a complexity (well, bandwidth in this case) attack? someone could start using txids and txouts that collide with the maximum number of other existing txouts in order to waste bandwidth for people. Is this avenue of attack not a concern? ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-25 16:56 ` Gregory Maxwell @ 2012-10-25 17:01 ` Gregory Maxwell 2012-10-26 14:01 ` Mike Hearn 1 sibling, 0 replies; 34+ messages in thread From: Gregory Maxwell @ 2012-10-25 17:01 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Thu, Oct 25, 2012 at 12:56 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote: > I still don't understand what purpose the apparently gratuitous > inefficiency of constantly resending common tree fragments. Sorry for the rapid additional comment, but I should also have mentioned that the in efficiency is at odds with the privacy argument for the particular mechanism... if the filter is not set at least somewhat too broadly then it will uniquely identify the user. The inefficiency, however, argues for setting the filter as narrowly as possible because there is much more bandwidth used for a wider filter than would be otherwise. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-25 16:56 ` Gregory Maxwell 2012-10-25 17:01 ` Gregory Maxwell @ 2012-10-26 14:01 ` Mike Hearn 2012-10-26 14:17 ` Gregory Maxwell 2012-11-06 19:14 ` Pieter Wuille 1 sibling, 2 replies; 34+ messages in thread From: Mike Hearn @ 2012-10-26 14:01 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev > Presumably these components will just get implemented a few times in > some carefully constructed library code, so I don't see an > implementation complexity argument here— except the fact that it isn't > what Matt has implemented so far. Well, yes, that is basically the implementation complexity argument :) Engineering time isn't free. I don't feel I understand the effort required to do some kind of partial tree encoding. Having a kind of custom compression whereby branches are represented as varint indexes into a dictionary, I can feel how much work that involves and maybe I can make time over the next few weeks to implement it. Has anyone got example code for representing partial Merkle trees? > Also, it's not mentioned in the page— but the hash function used is > not cryptographically strong, so what prevents a complexity (well, > bandwidth in this case) attack? someone could start using txids and > txouts that collide with the maximum number of other existing txouts > in order to waste bandwidth for people. Is this avenue of attack not > a concern? If you just want to waste bandwidth of nodes you can connect to nodes and repeatedly download blocks, or fill the network with fake nodes that spam random generated transactions to whoever connects. I don't see how to avoid that so it seems odd to worry about a much more complicated attack. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-26 14:01 ` Mike Hearn @ 2012-10-26 14:17 ` Gregory Maxwell 2012-10-26 14:21 ` Mike Hearn 2012-11-06 19:14 ` Pieter Wuille 1 sibling, 1 reply; 34+ messages in thread From: Gregory Maxwell @ 2012-10-26 14:17 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Fri, Oct 26, 2012 at 10:01 AM, Mike Hearn <mike@plan99•net> wrote: > If you just want to waste bandwidth of nodes you can connect to nodes > and repeatedly download blocks, or fill the network with fake nodes > that spam random generated transactions to whoever connects. I don't > see how to avoid that so it seems odd to worry about a much more > complicated attack. Because I can potentially waste bandwidth of all nodes forever (well as long as users are still scanning blocks with my transactions in them) with O(1) work. Though I'm not sure how much of a threat is vs just paying 1e-8 btc to lots of addresses which would only be less bad by some constant factor as worse. I guess I should try to attack it and see how bad the pollution I can construct should be. (offline, of course) ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-26 14:17 ` Gregory Maxwell @ 2012-10-26 14:21 ` Mike Hearn 2012-10-26 14:34 ` Gregory Maxwell 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2012-10-26 14:21 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev > Because I can potentially waste bandwidth of all nodes forever (well as long > as users are still scanning blocks with my transactions in them) with O(1) work. And this gets you what? Users who have active wallets will have their bandwidth wasted for as long as you keep up the attack. Once you stop active wallets won't be rescanning that part of the chain and new users won't be scanning it either, as they skip blocks before their earliest key time using getheaders. So basically you can waste the bandwidth of active users for a while, by spamming transactions. This is not a new attack. Anyway, it's trivial to DoS the entire Bitcoin network today. It hasn't ever happened. Maybe one day it will, but the only rationale people can come up with for such an attack beyond random griefing is governments, and complexity attacks are really not their style. Much easier to just pass a law. I'm not saying DoS should be ignored, but I do feel there are limits to how far down that rabbithole it's worth going. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-26 14:21 ` Mike Hearn @ 2012-10-26 14:34 ` Gregory Maxwell 0 siblings, 0 replies; 34+ messages in thread From: Gregory Maxwell @ 2012-10-26 14:34 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Fri, Oct 26, 2012 at 10:21 AM, Mike Hearn <mike@plan99•net> wrote: > Anyway, it's trivial to DoS the entire Bitcoin network today. It > hasn't ever happened. Maybe one day it will, but the only rationale > people can come up with for such an attack beyond random griefing is Which happens and is a concern. Altcoins have been attacked on things we fixed. For example, litecoin nodes were being run out of disk space through addr.dat flooding. I think we've been generally fortunate that the level of griefing is low (though not non-existent). But part of the reason its been low is that it's probably harder to DOS attack bitcoin than you believe. In the reference client a lot of work has gone in to removing attacks with sublinear cost for the attackers. That people aren't attacking much now is not an argument to accept a new vulnerability much less a _normative_ vulnerability in the protocol. That it's no big deal even attacked would be a fine argument to me, so I'll go try to convince myself of that. > governments, Please don't put that kind of black helicopter junk in my mouth. I agree with you the point that these aren't a source of concern for me. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-26 14:01 ` Mike Hearn 2012-10-26 14:17 ` Gregory Maxwell @ 2012-11-06 19:14 ` Pieter Wuille 1 sibling, 0 replies; 34+ messages in thread From: Pieter Wuille @ 2012-11-06 19:14 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Fri, Oct 26, 2012 at 04:01:58PM +0200, Mike Hearn wrote: > I don't feel I understand the effort required to do some kind of > partial tree encoding. Having a kind of custom compression whereby > branches are represented as varint indexes into a dictionary, I can > feel how much work that involves and maybe I can make time over the > next few weeks to implement it. Has anyone got example code for > representing partial Merkle trees? I've implemented code for efficient representation of partial merkle trees: see https://github.com/sipa/bitcoin/commits/partialmerkle The encoding/decoding algorithm uses a depth-first traversal of the tree, at each node outputting whether anything relevant is beneath, and if not, storing its hash and not descending into the children. Furthermore, thanks to some properties of the tree, some hard upper bounds on the size of the serialized structures are guaranteed. See the comments in the code for details. Unit tests are included to verify that 1) encoding and decoding a subset of transactions is an identity 2) the calculated merkle root matches the merkle root calculated by the existing merkle algorithm in the source code 3) the calculated merkle root actually depends on all hashes in the data structure. 4) serialization/deserialization is an identity 5) bounds on the size of the serialization are respected Hope it is clear enough to port to other languages. -- Pieter ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-10-24 15:56 [Bitcoin-development] Draft BIP for Bloom filtering Mike Hearn 2012-10-24 16:22 ` Pieter Wuille 2012-10-25 16:56 ` Gregory Maxwell @ 2012-11-21 15:15 ` Pieter Wuille 2012-11-21 18:38 ` Matt Corallo 2 siblings, 1 reply; 34+ messages in thread From: Pieter Wuille @ 2012-11-21 15:15 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote: > I've written a draft BIP describing the bloom filtering protocol > extension developed by myself and Matt. > > https://en.bitcoin.it/wiki/BIP_0037 Two comments I made on the pullreq page, which are probably better discussed here: * The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit differences between the different hash function's seeds. Together with the tweak, however, the first and the last now get seeds tweak and tweak-1. I think something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large odd 32-bit integers). * I feel uneasy about the arbitrary filter parameters used for the implicitly created filter when sending filteradd without filterload. The server cannot be expected to make a reasonable guess how the client is going to use the filter, and the client still has to track how large the server-side filter grows anyway. I'd prefer to make this simply illegal (DoS 100): filteradd always requires an active filter. Maybe the actual filter data in filterload can be made optional: if it is omitted, it's assumed to be all zeroes (though that would mean the size has to be specified). -- Pieter ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-11-21 15:15 ` Pieter Wuille @ 2012-11-21 18:38 ` Matt Corallo 2012-11-27 21:10 ` Pieter Wuille 0 siblings, 1 reply; 34+ messages in thread From: Matt Corallo @ 2012-11-21 18:38 UTC (permalink / raw) To: bitcoin-development On Wed, 2012-11-21 at 16:15 +0100, Pieter Wuille wrote: > On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote: > > I've written a draft BIP describing the bloom filtering protocol > > extension developed by myself and Matt. > > > > https://en.bitcoin.it/wiki/BIP_0037 > > Two comments I made on the pullreq page, which are probably better discussed here: > * The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit > differences between the different hash function's seeds. Together with the tweak, > however, the first and the last now get seeds tweak and tweak-1. I think > something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large > odd 32-bit integers). Meh, sure, whatever...I dont really think the seed values matter significantly (Murmur3 isnt that bad of a hash function...) (and the original algorithm wont result in a significant bit difference between the seeds in many cases). > * I feel uneasy about the arbitrary filter parameters used for the implicitly > created filter when sending filteradd without filterload. The server cannot be > expected to make a reasonable guess how the client is going to use the filter, > and the client still has to track how large the server-side filter grows anyway. > I'd prefer to make this simply illegal (DoS 100): filteradd always requires an > active filter. I think there is some consensus here, and I have no problem doing it this way (in large part, filteradd should not be used at all). > Maybe the actual filter data in filterload can be made optional: > if it is omitted, it's assumed to be all zeroes (though that would mean the size > has to be specified). > I'm not sure here, if you are sending a filter just to use filteradd to add things to it manually, you are doing something very, very, very wrong... Though we could certainly do some kind of compressed bloom filter encoding to allow for small filter loads (loading the few things you need to filteradd right away) where you anticipate adding significantly more filter elements down the road (can anyone even come up with a case where you anticipate doing this?), the filter is small enough (max 36kB) that I see little benefit for the large increase in complexity (or is this another repeat of the merkle branch discussion?) Matt ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-11-21 18:38 ` Matt Corallo @ 2012-11-27 21:10 ` Pieter Wuille 2013-01-10 15:21 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Pieter Wuille @ 2012-11-27 21:10 UTC (permalink / raw) To: Matt Corallo; +Cc: bitcoin-development On Wed, Nov 21, 2012 at 01:38:37PM -0500, Matt Corallo wrote: > On Wed, 2012-11-21 at 16:15 +0100, Pieter Wuille wrote: > > On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote: > > > I've written a draft BIP describing the bloom filtering protocol > > > extension developed by myself and Matt. > > > > > > https://en.bitcoin.it/wiki/BIP_0037 > > > > Two comments I made on the pullreq page, which are probably better discussed here: > > * The 0xFFFFFFFF/(n-1)*i seed value seems intended to result in large bit > > differences between the different hash function's seeds. Together with the tweak, > > however, the first and the last now get seeds tweak and tweak-1. I think > > something simpler like k1*i+k2*n+tweak is better (with k1 and k2 arbitrary large > > odd 32-bit integers). > Meh, sure, whatever...I dont really think the seed values matter > significantly (Murmur3 isnt that bad of a hash function...) (and the > original algorithm wont result in a significant bit difference between > the seeds in many cases). Sure, it's nothing important, but it seems like it fails to do what it was intended for. How about just this: tweak + i*0xFBA4C795 (number optimized to give large seed differences for every tweak). If you want variation when changing the number of hash functions, just choose a different seed. > > Maybe the actual filter data in filterload can be made optional: > > if it is omitted, it's assumed to be all zeroes (though that would mean the size > > has to be specified). > > > I'm not sure here, if you are sending a filter just to use filteradd to > add things to it manually, you are doing something very, very, very > wrong... Though we could certainly do some kind of compressed bloom > filter encoding to allow for small filter loads (loading the few things > you need to filteradd right away) where you anticipate adding > significantly more filter elements down the road (can anyone even come > up with a case where you anticipate doing this?), the filter is small > enough (max 36kB) that I see little benefit for the large increase in > complexity (or is this another repeat of the merkle branch discussion?) It's probably not worth it for something that is max 36 kilobytes. If ever necessary, we can define a new message type that just lists a number of bits to be set in the server-side filter. For now, I agree that you should just send the filter as intended, and not expect to do many filteradds (though you should take the implicitly-added txids into accounted when computing the filter size). -- Pieter ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2012-11-27 21:10 ` Pieter Wuille @ 2013-01-10 15:21 ` Mike Hearn 2013-01-11 3:59 ` Matt Corallo 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-10 15:21 UTC (permalink / raw) To: Pieter Wuille; +Cc: Bitcoin Dev Here's a quick update on where we're up to. Thanks to Matts excellent work, I was able to test his bitcoinj and bitcoin-qt work together today. There are a few minor tweaks needed, but I feel like we're maybe a week away from having all the code in a mergeable state. Here is the remaining work: - There are a couple of bugfixes needed on the bitcoinj side: the fallback to downloading full blocks is problematic and needs to be deleted, there's an API change we want - Adjust the default FP rate requested by BCJ to be 0.0001, this is appropriate for the latest blocks in the chain and yields 0-5 false positives per block - Introduce a new part to the filter protocol that allows clients to control auto-expansion. This turned out to be very volatile, we saw jumps from 0-3 FPs per block to 500 in the space of 1 block, perhaps if a SatoshiDice transaction got into the filter. A simple yes/no flag can suffice for now, but a better solution would be for the client to submit templates for output scripts that would trigger auto-adding the matched outpoint - autoexpansion is only needed in the case where the input script doesn't contain any predictable data. For pay-to-address and P2SH it does, so expansion doesn't help. Matt said he'd hopefully try to look at this soon. With auto-expansion disabled, the FP rate adjusted and a bugfix on the bcj side I was able to sync a wallet using a bloom filtered chain. Although it's tight, I think this work should go into 0.8 - it'll be much more compelling to advertise it this way, we can say "Upgrade to 0.8 and help network performance for everyone". And in the case that we discover a showstopper problem, we just don't deploy the code that uses the new messages into clients. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-10 15:21 ` Mike Hearn @ 2013-01-11 3:59 ` Matt Corallo 2013-01-11 5:02 ` Jeff Garzik 0 siblings, 1 reply; 34+ messages in thread From: Matt Corallo @ 2013-01-11 3:59 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Thu, 2013-01-10 at 16:21 +0100, Mike Hearn wrote: > Here's a quick update on where we're up to. > > Thanks to Matts excellent work, I was able to test his bitcoinj and > bitcoin-qt work together today. There are a few minor tweaks needed, > but I feel like we're maybe a week away from having all the code in a > mergeable state. Here is the remaining work: > > - There are a couple of bugfixes needed on the bitcoinj side: the > fallback to downloading full blocks is problematic and needs to be > deleted, there's an API change we want First of the two is done. > > - Adjust the default FP rate requested by BCJ to be 0.0001, this is > appropriate for the latest blocks in the chain and yields 0-5 false > positives per block Is a part of the larger API changes mentioned above. > > - Introduce a new part to the filter protocol that allows clients to > control auto-expansion. This turned out to be very volatile, we saw > jumps from 0-3 FPs per block to 500 in the space of 1 block, perhaps > if a SatoshiDice transaction got into the filter. A simple yes/no flag > can suffice for now, but a better solution would be for the client to > submit templates for output scripts that would trigger auto-adding the > matched outpoint - autoexpansion is only needed in the case where the > input script doesn't contain any predictable data. For pay-to-address > and P2SH it does, so expansion doesn't help. Matt said he'd hopefully > try to look at this soon. The flags mentioned have been implemented, both to disable autoexpansion, enable it for all outputs, enable for only pay to pubkey outputs (the most likely use-case), or use a set of templates. The matched templates part isn't properly tested and I would like comments on that part (see the last few commits at https://github.com/bitcoin/bitcoin/pull/1795). > > With auto-expansion disabled, the FP rate adjusted and a bugfix on the > bcj side I was able to sync a wallet using a bloom filtered chain. > > Although it's tight, I think this work should go into 0.8 - it'll be > much more compelling to advertise it this way, we can say "Upgrade to > 0.8 and help network performance for everyone". And in the case that > we discover a showstopper problem, we just don't deploy the code that > uses the new messages into clients. Ive been missing lately, when is 0.8 targeted for freeze? Matt ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-11 3:59 ` Matt Corallo @ 2013-01-11 5:02 ` Jeff Garzik 2013-01-11 14:11 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Jeff Garzik @ 2013-01-11 5:02 UTC (permalink / raw) To: Matt Corallo; +Cc: Bitcoin Dev On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote: > Ive been missing lately, when is 0.8 targeted for freeze? 0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable. -- Jeff Garzik exMULTI, Inc. jgarzik@exmulti•com ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-11 5:02 ` Jeff Garzik @ 2013-01-11 14:11 ` Mike Hearn 2013-01-11 14:13 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-11 14:11 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev I did some very rough initial performance tests. Syncing from a local peer gives me about 50 blocks per second in the later parts of the chain (post SD), which is about a 10-20x speedup over what I could do before. This is on a MacBook Pro. But at those points it's clearly bottlenecked by bitcoind which has saturated its CPU core. This makes sense - the filtering is much more server than client intensive because every transaction in every block has to be loaded and checked. I think filtering can be fairly well parallelized on the server side. So the current 10-20x speedup could potentially be larger if the server becomes more efficient at scanning and filtering blocks. It's still a very nice win for now, especially bandwidth wise. And if Matt makes the mempool command filtered it solves a common usability problem as well. Once we get this code in, merged and rolled out I think what we need for bloom v2 is clear: - Multi-thread the filtering process in bitcoind so transactions can be checked in parallel. A 4-core server would then get 4x faster at filtering blocks and assuming it's not too busy doing other stuff we could maybe sync at more like 200 blocks per second, which is cool ... more than a days worth of history for each second of syncing. - Make the client smarter so the FP rate is adapted during the sync process. An FP rate that makes sense post-SD results in no false positives pre-SD, more or less. - Make the client shard its wallet keys over multiple peers, for better privacy. - Make the client suck down filtered blocks in parallel from multiple peers, for better speed. As it seems the bottleneck for chain sync is now CPU time, the latter point may be the most important from a practical perspective. On Fri, Jan 11, 2013 at 6:02 AM, Jeff Garzik <jgarzik@exmulti•com> wrote: > On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote: >> Ive been missing lately, when is 0.8 targeted for freeze? > > 0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable. > > -- > Jeff Garzik > exMULTI, Inc. > jgarzik@exmulti•com ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-11 14:11 ` Mike Hearn @ 2013-01-11 14:13 ` Mike Hearn 2013-01-16 10:43 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-11 14:13 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev Oh, one last stat - syncing the entire chain with a wallet containing two keys and a 0.0001 FP rate (one or two FPs every 5 blocks or so) resulted in a download of about 46mb of data. On Fri, Jan 11, 2013 at 3:11 PM, Mike Hearn <mike@plan99•net> wrote: > I did some very rough initial performance tests. > > Syncing from a local peer gives me about 50 blocks per second in the > later parts of the chain (post SD), which is about a 10-20x speedup > over what I could do before. This is on a MacBook Pro. But at those > points it's clearly bottlenecked by bitcoind which has saturated its > CPU core. This makes sense - the filtering is much more server than > client intensive because every transaction in every block has to be > loaded and checked. > > I think filtering can be fairly well parallelized on the server side. > So the current 10-20x speedup could potentially be larger if the > server becomes more efficient at scanning and filtering blocks. It's > still a very nice win for now, especially bandwidth wise. And if Matt > makes the mempool command filtered it solves a common usability > problem as well. > > Once we get this code in, merged and rolled out I think what we need > for bloom v2 is clear: > > - Multi-thread the filtering process in bitcoind so transactions can > be checked in parallel. A 4-core server would then get 4x faster at > filtering blocks and assuming it's not too busy doing other stuff we > could maybe sync at more like 200 blocks per second, which is cool ... > more than a days worth of history for each second of syncing. > > - Make the client smarter so the FP rate is adapted during the sync > process. An FP rate that makes sense post-SD results in no false > positives pre-SD, more or less. > > - Make the client shard its wallet keys over multiple peers, for > better privacy. > > - Make the client suck down filtered blocks in parallel from multiple > peers, for better speed. > > As it seems the bottleneck for chain sync is now CPU time, the latter > point may be the most important from a practical perspective. > > On Fri, Jan 11, 2013 at 6:02 AM, Jeff Garzik <jgarzik@exmulti•com> wrote: >> On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote: >>> Ive been missing lately, when is 0.8 targeted for freeze? >> >> 0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable. >> >> -- >> Jeff Garzik >> exMULTI, Inc. >> jgarzik@exmulti•com ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-11 14:13 ` Mike Hearn @ 2013-01-16 10:43 ` Mike Hearn 2013-01-16 15:00 ` Matt Corallo 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-16 10:43 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev Matts latest code has been tested by Andreas and seems to work correctly. He had to extend the client a bit to refresh the filter every 25k blocks because even with the extra flag, eventually the filter degrades into uselessness, but it did still improve the situation quite a bit. Because it's unit tested, been reviewed by me several times, has an interoperable implementation that has also been tested by Andreas in a build of his smartphone app, I'm going to ACK the current code and request that it be merged in to 0.8. What do you say Gavin? The next step after that would be profiling. It's a big performance improvement for SPV clients already, but not as much as I anticipated. I suspect there's a simple bottleneck or missed optimization somewhere. But that can obviously come post-0.8 ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-16 10:43 ` Mike Hearn @ 2013-01-16 15:00 ` Matt Corallo 2013-01-18 16:38 ` Mike Hearn 2013-01-30 11:09 ` Mike Hearn 0 siblings, 2 replies; 34+ messages in thread From: Matt Corallo @ 2013-01-16 15:00 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev Actually, there is one more minor algorithmic change I would like to make to the way the hash function is computed really quick before it gets merged, I'll have that finished up by the end of today. Matt On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: > Matts latest code has been tested by Andreas and seems to work > correctly. He had to extend the client a bit to refresh the filter > every 25k blocks because even with the extra flag, eventually the > filter degrades into uselessness, but it did still improve the > situation quite a bit. > > Because it's unit tested, been reviewed by me several times, has an > interoperable implementation that has also been tested by Andreas in a > build of his smartphone app, I'm going to ACK the current code and > request that it be merged in to 0.8. What do you say Gavin? > > The next step after that would be profiling. It's a big performance > improvement for SPV clients already, but not as much as I anticipated. > I suspect there's a simple bottleneck or missed optimization > somewhere. But that can obviously come post-0.8 ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-16 15:00 ` Matt Corallo @ 2013-01-18 16:38 ` Mike Hearn 2013-01-19 9:51 ` Andreas Schildbach 2013-01-30 11:09 ` Mike Hearn 1 sibling, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-18 16:38 UTC (permalink / raw) To: Matt Corallo; +Cc: Bitcoin Dev I'm thinking we should actually make the change we talked about before and have the filtered block sent before the transaction data. For one, it's not intuitive (API wise) that you'd get a callback saying "new pending tx" immediately before another callback saying "tx was confirmed", but that's what the current setup makes most natural. To fix it we'd have to notice that a tx message wasn't requested by us, buffer it, and wait for the corresponding filteredblock message. It seems cleaner to receive a filteredblock and then for any tx that matches it, attach it to the FilteredBlock object and wait until it is full up, then pass it to the wallet code all at once. Another issue is that to risk analyze unconfirmed transactions you really have to download all dependencies. That has to be triggered by seeing an unconfirmed transaction. It's dumb to start this process for a tx that is actually in the chain, so you need to have some notion of whether it came from a filtered block anyway. I only realized this today. I think when we discussed this before, the justification for having it work the current way was that it was simpler to integrate with the SPV client code if it was done this way around. But I don't think it's really simpler. There are enough odd side effects of doing it this way, that I feel it'd be better to tweak the protocol now whilst we have the chance. On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote: > Actually, there is one more minor algorithmic change I would like to > make to the way the hash function is computed really quick before it > gets merged, I'll have that finished up by the end of today. > > Matt > > On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: >> Matts latest code has been tested by Andreas and seems to work >> correctly. He had to extend the client a bit to refresh the filter >> every 25k blocks because even with the extra flag, eventually the >> filter degrades into uselessness, but it did still improve the >> situation quite a bit. >> >> Because it's unit tested, been reviewed by me several times, has an >> interoperable implementation that has also been tested by Andreas in a >> build of his smartphone app, I'm going to ACK the current code and >> request that it be merged in to 0.8. What do you say Gavin? >> >> The next step after that would be profiling. It's a big performance >> improvement for SPV clients already, but not as much as I anticipated. >> I suspect there's a simple bottleneck or missed optimization >> somewhere. But that can obviously come post-0.8 > > ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-18 16:38 ` Mike Hearn @ 2013-01-19 9:51 ` Andreas Schildbach 0 siblings, 0 replies; 34+ messages in thread From: Andreas Schildbach @ 2013-01-19 9:51 UTC (permalink / raw) To: bitcoin-development Matt, I saw your commit and immediately started using it for testing. Now I think the bitcoinj side needs some love because not one transaction is being confirmed (all just pending) when replaying the blockchain. On 01/18/2013 05:38 PM, Mike Hearn wrote: > I'm thinking we should actually make the change we talked about before > and have the filtered block sent before the transaction data. > > For one, it's not intuitive (API wise) that you'd get a callback > saying "new pending tx" immediately before another callback saying "tx > was confirmed", but that's what the current setup makes most natural. > To fix it we'd have to notice that a tx message wasn't requested by > us, buffer it, and wait for the corresponding filteredblock message. > It seems cleaner to receive a filteredblock and then for any tx that > matches it, attach it to the FilteredBlock object and wait until it is > full up, then pass it to the wallet code all at once. > > Another issue is that to risk analyze unconfirmed transactions you > really have to download all dependencies. That has to be triggered by > seeing an unconfirmed transaction. It's dumb to start this process for > a tx that is actually in the chain, so you need to have some notion of > whether it came from a filtered block anyway. I only realized this > today. > > I think when we discussed this before, the justification for having it > work the current way was that it was simpler to integrate with the SPV > client code if it was done this way around. But I don't think it's > really simpler. There are enough odd side effects of doing it this > way, that I feel it'd be better to tweak the protocol now whilst we > have the chance. > > On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote: >> Actually, there is one more minor algorithmic change I would like to >> make to the way the hash function is computed really quick before it >> gets merged, I'll have that finished up by the end of today. >> >> Matt >> >> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: >>> Matts latest code has been tested by Andreas and seems to work >>> correctly. He had to extend the client a bit to refresh the filter >>> every 25k blocks because even with the extra flag, eventually the >>> filter degrades into uselessness, but it did still improve the >>> situation quite a bit. >>> >>> Because it's unit tested, been reviewed by me several times, has an >>> interoperable implementation that has also been tested by Andreas in a >>> build of his smartphone app, I'm going to ACK the current code and >>> request that it be merged in to 0.8. What do you say Gavin? >>> >>> The next step after that would be profiling. It's a big performance >>> improvement for SPV clients already, but not as much as I anticipated. >>> I suspect there's a simple bottleneck or missed optimization >>> somewhere. But that can obviously come post-0.8 >> >> > > ------------------------------------------------------------------------------ > Master HTML5, CSS3, ASP.NET, MVC, AJAX, Knockout.js, Web API and > much more. Get web development skills now with LearnDevNow - > 350+ hours of step-by-step video tutorials by Microsoft MVPs and experts. > SALE $99.99 this month only -- learn more at: > http://p.sf.net/sfu/learnmore_122812 > ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-16 15:00 ` Matt Corallo 2013-01-18 16:38 ` Mike Hearn @ 2013-01-30 11:09 ` Mike Hearn 2013-01-30 11:13 ` Mike Hearn 1 sibling, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-30 11:09 UTC (permalink / raw) To: Matt Corallo; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2034 bytes --] Andreas has uploaded Android builds that use the new bloom filtering and peer selection code (also, dependency analysis of transactions). The performance gain is very cool. The app feels dramatically faster to start up and sync. Because the app syncs on charge when I opened it around lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up 6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That was on wifi. The next lowest hanging perf fruit is almost certainly to optimize disk accesses. Flash on Android devices seems to be much slower than laptop flash storage, and current bitcoinj is very inefficient in how it writes (one write per block header!). This matters a lot when doing fast catchup for first time users. The BIP is now a little bit stale, but only slightly. On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt•me>wrote: > Actually, there is one more minor algorithmic change I would like to > make to the way the hash function is computed really quick before it > gets merged, I'll have that finished up by the end of today. > > Matt > > On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: > > Matts latest code has been tested by Andreas and seems to work > > correctly. He had to extend the client a bit to refresh the filter > > every 25k blocks because even with the extra flag, eventually the > > filter degrades into uselessness, but it did still improve the > > situation quite a bit. > > > > Because it's unit tested, been reviewed by me several times, has an > > interoperable implementation that has also been tested by Andreas in a > > build of his smartphone app, I'm going to ACK the current code and > > request that it be merged in to 0.8. What do you say Gavin? > > > > The next step after that would be profiling. It's a big performance > > improvement for SPV clients already, but not as much as I anticipated. > > I suspect there's a simple bottleneck or missed optimization > > somewhere. But that can obviously come post-0.8 > > > [-- Attachment #2: Type: text/html, Size: 2693 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-30 11:09 ` Mike Hearn @ 2013-01-30 11:13 ` Mike Hearn 2013-02-06 16:33 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-01-30 11:13 UTC (permalink / raw) To: Matt Corallo; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2533 bytes --] Sorry, to clarify, these are test builds available here: https://code.google.com/p/bitcoin-wallet/downloads/detail?name=bitcoin-wallet-2.39_bitcoinj0.7.apk&can=2&q= It's not on the Play store yet. It probably makes sense to release after some more testing and after Bitcoin 0.8 comes out, as otherwise there's a risk that 0.7 snapshot nodes will get overloaded. On Wed, Jan 30, 2013 at 12:09 PM, Mike Hearn <mike@plan99•net> wrote: > Andreas has uploaded Android builds that use the new bloom filtering and > peer selection code (also, dependency analysis of transactions). > > The performance gain is very cool. The app feels dramatically faster to > start up and sync. Because the app syncs on charge when I opened it around > lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up > 6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That > was on wifi. > > The next lowest hanging perf fruit is almost certainly to optimize disk > accesses. Flash on Android devices seems to be much slower than laptop > flash storage, and current bitcoinj is very inefficient in how it writes > (one write per block header!). This matters a lot when doing fast catchup > for first time users. > > The BIP is now a little bit stale, but only slightly. > > > On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt•me>wrote: > >> Actually, there is one more minor algorithmic change I would like to >> make to the way the hash function is computed really quick before it >> gets merged, I'll have that finished up by the end of today. >> >> Matt >> >> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: >> > Matts latest code has been tested by Andreas and seems to work >> > correctly. He had to extend the client a bit to refresh the filter >> > every 25k blocks because even with the extra flag, eventually the >> > filter degrades into uselessness, but it did still improve the >> > situation quite a bit. >> > >> > Because it's unit tested, been reviewed by me several times, has an >> > interoperable implementation that has also been tested by Andreas in a >> > build of his smartphone app, I'm going to ACK the current code and >> > request that it be merged in to 0.8. What do you say Gavin? >> > >> > The next step after that would be profiling. It's a big performance >> > improvement for SPV clients already, but not as much as I anticipated. >> > I suspect there's a simple bottleneck or missed optimization >> > somewhere. But that can obviously come post-0.8 >> >> >> > [-- Attachment #2: Type: text/html, Size: 3620 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-01-30 11:13 ` Mike Hearn @ 2013-02-06 16:33 ` Mike Hearn 2013-02-06 16:45 ` Gregory Maxwell 0 siblings, 1 reply; 34+ messages in thread From: Mike Hearn @ 2013-02-06 16:33 UTC (permalink / raw) To: Matt Corallo; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 2765 bytes --] Can somebody please unlock the BIP wiki page? I don't know why it was locked but it's stale. On Wed, Jan 30, 2013 at 12:13 PM, Mike Hearn <mike@plan99•net> wrote: > Sorry, to clarify, these are test builds available here: > > > https://code.google.com/p/bitcoin-wallet/downloads/detail?name=bitcoin-wallet-2.39_bitcoinj0.7.apk&can=2&q= > > It's not on the Play store yet. It probably makes sense to release after > some more testing and after Bitcoin 0.8 comes out, as otherwise there's a > risk that 0.7 snapshot nodes will get overloaded. > > > On Wed, Jan 30, 2013 at 12:09 PM, Mike Hearn <mike@plan99•net> wrote: > >> Andreas has uploaded Android builds that use the new bloom filtering and >> peer selection code (also, dependency analysis of transactions). >> >> The performance gain is very cool. The app feels dramatically faster to >> start up and sync. Because the app syncs on charge when I opened it around >> lunchtime it had only 7 hours of data to sync (42 blocks) and it brought up >> 6 peer connections, found a 0.7.99 node and synced all in <2 seconds. That >> was on wifi. >> >> The next lowest hanging perf fruit is almost certainly to optimize disk >> accesses. Flash on Android devices seems to be much slower than laptop >> flash storage, and current bitcoinj is very inefficient in how it writes >> (one write per block header!). This matters a lot when doing fast catchup >> for first time users. >> >> The BIP is now a little bit stale, but only slightly. >> >> >> On Wed, Jan 16, 2013 at 4:00 PM, Matt Corallo <bitcoin-list@bluematt•me>wrote: >> >>> Actually, there is one more minor algorithmic change I would like to >>> make to the way the hash function is computed really quick before it >>> gets merged, I'll have that finished up by the end of today. >>> >>> Matt >>> >>> On Wed, 2013-01-16 at 11:43 +0100, Mike Hearn wrote: >>> > Matts latest code has been tested by Andreas and seems to work >>> > correctly. He had to extend the client a bit to refresh the filter >>> > every 25k blocks because even with the extra flag, eventually the >>> > filter degrades into uselessness, but it did still improve the >>> > situation quite a bit. >>> > >>> > Because it's unit tested, been reviewed by me several times, has an >>> > interoperable implementation that has also been tested by Andreas in a >>> > build of his smartphone app, I'm going to ACK the current code and >>> > request that it be merged in to 0.8. What do you say Gavin? >>> > >>> > The next step after that would be profiling. It's a big performance >>> > improvement for SPV clients already, but not as much as I anticipated. >>> > I suspect there's a simple bottleneck or missed optimization >>> > somewhere. But that can obviously come post-0.8 >>> >>> >>> >> > [-- Attachment #2: Type: text/html, Size: 4133 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-02-06 16:33 ` Mike Hearn @ 2013-02-06 16:45 ` Gregory Maxwell 2013-02-20 12:44 ` Mike Hearn 0 siblings, 1 reply; 34+ messages in thread From: Gregory Maxwell @ 2013-02-06 16:45 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn <mike@plan99•net> wrote: > Can somebody please unlock the BIP wiki page? I don't know why it was locked > but it's stale. I asked for permissions to unlock it but haven't heard back— will prod. ^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [Bitcoin-development] Draft BIP for Bloom filtering 2013-02-06 16:45 ` Gregory Maxwell @ 2013-02-20 12:44 ` Mike Hearn 0 siblings, 0 replies; 34+ messages in thread From: Mike Hearn @ 2013-02-20 12:44 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 564 bytes --] I paid the new anti-spam deposit and updated the BIP 37 page to the latest version of the protocol, then marked it as accepted. High fives all round, but especially to Matt for doing the heavy lifting on this feature. On Wed, Feb 6, 2013 at 5:45 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote: > On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn <mike@plan99•net> wrote: > > Can somebody please unlock the BIP wiki page? I don't know why it was > locked > > but it's stale. > > I asked for permissions to unlock it but haven't heard back— will prod. > [-- Attachment #2: Type: text/html, Size: 947 bytes --] ^ permalink raw reply [flat|nested] 34+ messages in thread
end of thread, other threads:[~2013-02-20 12:45 UTC | newest] Thread overview: 34+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-10-24 15:56 [Bitcoin-development] Draft BIP for Bloom filtering Mike Hearn 2012-10-24 16:22 ` Pieter Wuille 2012-10-24 16:35 ` Mike Hearn 2012-10-24 17:11 ` Pieter Wuille 2012-10-24 18:54 ` Gavin Andresen 2012-10-24 19:00 ` Matt Corallo 2012-10-24 19:10 ` Mike Hearn 2012-10-24 20:29 ` Gavin Andresen 2012-10-24 20:58 ` Mike Hearn 2012-10-24 21:55 ` Jeff Garzik 2012-10-25 16:56 ` Gregory Maxwell 2012-10-25 17:01 ` Gregory Maxwell 2012-10-26 14:01 ` Mike Hearn 2012-10-26 14:17 ` Gregory Maxwell 2012-10-26 14:21 ` Mike Hearn 2012-10-26 14:34 ` Gregory Maxwell 2012-11-06 19:14 ` Pieter Wuille 2012-11-21 15:15 ` Pieter Wuille 2012-11-21 18:38 ` Matt Corallo 2012-11-27 21:10 ` Pieter Wuille 2013-01-10 15:21 ` Mike Hearn 2013-01-11 3:59 ` Matt Corallo 2013-01-11 5:02 ` Jeff Garzik 2013-01-11 14:11 ` Mike Hearn 2013-01-11 14:13 ` Mike Hearn 2013-01-16 10:43 ` Mike Hearn 2013-01-16 15:00 ` Matt Corallo 2013-01-18 16:38 ` Mike Hearn 2013-01-19 9:51 ` Andreas Schildbach 2013-01-30 11:09 ` Mike Hearn 2013-01-30 11:13 ` Mike Hearn 2013-02-06 16:33 ` Mike Hearn 2013-02-06 16:45 ` Gregory Maxwell 2013-02-20 12:44 ` Mike Hearn
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox