Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 gmaxw...@gmail.com wrote: On Wed, Feb 6, 2013 at 8:33 AM, Mike Hearn m...@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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_d2d_feb___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 m...@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.apkcan=2q= 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 m...@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-l...@bluematt.mewrote: 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 -- Free Next-Gen Firewall Hardware Offer Buy your Sophos next-gen firewall before the end March 2013 and get the hardware for free! Learn more. http://p.sf.net/sfu/sophos-d2d-feb___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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.apkcan=2q= 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 m...@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-l...@bluematt.mewrote: 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 -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_d2d_jan___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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-l...@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 -- Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS, MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current with LearnDevNow - 3,200 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_122912 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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-l...@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 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 Java SE, Java EE, Eclipse, Spring, Hibernate, JavaScript, jQuery and much more. Keep your Java skills current with LearnJavaNow - 200+ hours of step-by-step video tutorials by Java experts. SALE $49.99 this month only -- learn more at: http://p.sf.net/sfu/learnmore_122612 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 Java SE, Java EE, Eclipse, Spring, Hibernate, JavaScript, jQuery and much more. Keep your Java skills current with LearnJavaNow - 200+ hours of step-by-step video tutorials by Java experts. SALE $49.99 this month only -- learn more at: http://p.sf.net/sfu/learnmore_122612 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 m...@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 jgar...@exmulti.com wrote: On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo bitcoin-l...@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. jgar...@exmulti.com -- 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 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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. -- Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS, MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft MVPs and experts. ON SALE this month only -- learn more at: http://p.sf.net/sfu/learnmore_122712 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 -- 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 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
On Thu, Jan 10, 2013 at 10:59 PM, Matt Corallo bitcoin-l...@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. jgar...@exmulti.com -- 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 ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 0x/(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 -- Keep yourself connected to Go Parallel: DESIGN Expert tips on starting your parallel project right. http://goparallel.sourceforge.net ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 0x/(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 -- Monitor your physical, virtual and cloud infrastructure from a single web console. Get in-depth insight into apps, servers, databases, vmware, SAP, cloud infrastructure, etc. Download 30-day Free Trial. Pricing starts from $795 for 25 servers or applications! http://p.sf.net/sfu/zoho_dev2dev_nov ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 -- LogMeIn Central: Instant, anywhere, Remote PC access and management. Stay in control, update software, and manage PCs from one command center Diagnose problems and improve visibility into emerging IT issues Automate, monitor and manage. Do more in less time with Central http://p.sf.net/sfu/logmein12331_d2d ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
On Fri, Oct 26, 2012 at 10:01 AM, Mike Hearn m...@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) -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
On Fri, Oct 26, 2012 at 10:21 AM, Mike Hearn m...@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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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 -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
On Wed, Oct 24, 2012 at 3:10 PM, Mike Hearn m...@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 -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Draft BIP for Bloom filtering
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. -- Everyone hates slow websites. So do we. Make your web apps faster with AppDynamics Download AppDynamics Lite for free today: http://p.sf.net/sfu/appdyn_sfd2d_oct ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
