Draft BIP for Bloom filtering
34 messages, 24 Oct 2012 to 20 Feb 2013. Started by Mike Hearn.
Mike Hearn (15), Pieter Wuille (5), Greg Maxwell (5), Matt Corallo (4), Gavin Andresen (2), Jeff Garzik (2), Andreas Schildbach
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.
On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
Quoted text (7 lines)
> 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?
Quoted text (7 lines)
> 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.
Quoted text (2 lines)
> Some questions: > * why limit the number of matching transactions to 255?
Copy/paste error in the does :(
Quoted text (1 line)
> * 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.
Quoted text (1 line)
> * is sharing parts of the merkle branches not worth it?
We think probably not.
On Wed, Oct 24, 2012 at 06:35:08PM +0200, Mike Hearn wrote:
Quoted text (5 lines)
> > * 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)
Quoted text (4 lines)
> > > * 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.
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.
On Wed, 2012-10-24 at 14:54 -0400, Gavin Andresen wrote:
Quoted text (5 lines)
> 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?
Quoted text (15 lines)
> > 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
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:
Quoted text (24 lines)
> 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 >
On Wed, Oct 24, 2012 at 3:10 PM, Mike Hearn <mike@plan99•net> wrote:
Quoted text (2 lines)
> 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...).
Quoted text (4 lines)
> 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.
On Wed, Oct 24, 2012 at 4:29 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:
Quoted text (3 lines)
> 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.
On Wed, Oct 24, 2012 at 11:56 AM, Mike Hearn <mike@plan99•net> wrote:
Quoted text (4 lines)
> 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?
On Thu, Oct 25, 2012 at 12:56 PM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (2 lines)
> 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.
Quoted text (4 lines)
> 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?
Quoted text (6 lines)
> 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.
On Fri, Oct 26, 2012 at 10:01 AM, Mike Hearn <mike@plan99•net> wrote:
Quoted text (5 lines)
> 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)
Quoted text (2 lines)
> 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.
On Fri, Oct 26, 2012 at 10:21 AM, Mike Hearn <mike@plan99•net> wrote:
Quoted text (3 lines)
> 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.
Quoted text (1 line)
> 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.
On Fri, Oct 26, 2012 at 04:01:58PM +0200, Mike Hearn wrote:
Quoted text (6 lines)
> 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.
On Wed, Oct 24, 2012 at 05:56:07PM +0200, Mike Hearn wrote:
Quoted text (4 lines)
> 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).
On Wed, 2012-11-21 at 16:15 +0100, Pieter Wuille wrote:
Quoted text (12 lines)
> 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).
Quoted text (6 lines)
> * 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).
Quoted text (4 lines)
> 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
On Wed, Nov 21, 2012 at 01:38:37PM -0500, Matt Corallo wrote:
Quoted text (17 lines)
> 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.
Quoted text (13 lines)
> > 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).
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.
On Thu, 2013-01-10 at 16:21 +0100, Mike Hearn wrote:
Quoted text (10 lines)
> 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.
Quoted text (4 lines)
> > - 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.
Quoted text (11 lines)
> > - 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).
Quoted text (9 lines)
> > 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
On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote:
Quoted text (1 line)
> Ive been missing lately, when is 0.8 targeted for freeze?
0.8rc1 will probably happen when the core ultraprune/leveldb stuff is stable.
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:
Quoted text (9 lines)
> 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
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:
Quoted text (49 lines)
> 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
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
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:
Quoted text (15 lines)
> 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
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:
Quoted text (24 lines)
> 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 > >
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:
Quoted text (59 lines)
> 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 >
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:
Quoted text (25 lines)
> 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 > > >
Sorry, to clarify, these are test builds available here:
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:
Quoted text (46 lines)
> 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 >> >> >> >
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:
Quoted text (59 lines)
> 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 >>> >>> >>> >> >
On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn <mike@plan99•net> wrote:
Quoted text (2 lines)
> 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.
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:
Quoted text (7 lines)
> 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. >