New litecoin-0.8.x is pretty much done, so what is Bloom Filtering?
-
I assume we will be taking advantage of any Litecoin progress.
What are “Bloom filtering” and do Feathercoin already implement “coin-age based priority?”
https://forum.litecoin.net/index.php/topic,877.0.html
see Dev-Warren at footer : 10 July 2013.
>> Now that litecoin-0.8.x is pretty much done, the Litecoin Dev Team is next looking at SPV wallets and vendor integration tools.
>>> Be warned that any alternative implementation of a Litecoin wallet MUST implement coin-age based priority calculation to determine the exact minimum requires fees when sending.
-
best guess … [url=http://en.wikipedia.org/wiki/Bloom_filter]http://en.wikipedia.org/wiki/Bloom_filter[/url]
-
Bloom Filtering is a technique for scanning data and looking for potential matches of a bunch of aggregate queries without actually checking to see if the data matches, thus greatly increasing speed. It works by creating a bit-field of the aggregate queries and ORing all them together, and doing a logical AND against the data to search: If the result > 0, it’s possible the data is present, but if result == 0 it’s definitely not present.
It’s that second case that we’re interested in: If the result == 0, we can skip checking the data altogether and move on to the next piece of data. That means we just saved outselves a bunch of operations we don’t need to do. If the result > 0 we need to see if it’s actually present by comparing the two pieces of data byte-by-byte. Bloom Filters will sometimes return a false positive, but it will NEVER return a false negative, so we can rely on the negative case to always be right, and skip the expensive operations.
So, why does this matter in Bitcoin clients?
Well, when you have a bunch of addresses, you can use a bloom filter to aggregate all your addresses, and scan the blockchain for transactions that might be of interest to you because they contain a key you own. You can therefore SKIP the large majority of actually processing the blockchain, and only focus your processing power on scanning blocks that may contain a transaction with your key in it. When a new block comes in, just run your bloom filter on all it’s input and output addresses, and if the result == 0, don’t bother doing anything else except store it to disk, but if the result > 0, look for incoming/outgoing money and update the balance accordingly. The same is true when importing private keys: You’ll need to scan the entire chain to date to find any transactions to compute your balance.
It’s strictly an optimization that eliminates work under best case scenarios, making certain operations faster. You are, of course, trading memory for CPU cycles, so it’s not without price, but the bloom filter can be calculated once for a set of addresses, and modified to include new ones, but has to be thrown out and recomputed to remove addresses, so it provides the best case optimization for the most common tasks. As a result, you get a speedier, more responsive client.
-
Great explanation, thanks. Will we be implementing this into our FTC client?
-
Bloom filtering - Sounds a pretty good feature, particularly as the blockchain expands.
-
[quote name=“T4rQu1N” post=“23182” timestamp=“1374832340”]
Great explanation, thanks. Will we be implementing this into our FTC client?
[/quote]I hope so. A well trained monkey can OR all the wallet pub addresses together and AND them against the addresses of inputs/outputs in the blockchain with about 20 lines of code. It’s a trivially simple optimization that you can add in some places without touching others making it great for incremental releases leading up to a “full Bloom-Filtering support” release.
It’s also an optimization, and one that doesn’t do anything for the 51% attack. For that, you need PoS or PoB, unless you are willing to accept centralization (ala checkpointing), which defeats the purpose of having a decentralized currency to start with.
-
Better invest your energy in SUPPORTING your investment than dumping around … banana ?
-
We will be following Litecoin to 0.8.x with all the bells and whistles.
Once we have protection in place from Advanced Checkpointing we can then begin the move to a newer code base.
-
Thanks for the info, sounds great, well done.
