The Bloom Tree

arxiv.org

11 points·irwt··3 comments

Maybe I'm wrong, but the second point in the conclusion seems a bit overstated:

When we want to prove the presence, or absence of single elements to another party in a secure and bandwidth efficient way, instead of sending whole bloom filters

As stated in the paper several times, bloom filters do not prove presence of an element in a set, only absence. Which is fine when used in a caching setting or where false positives are acceptable, but it seems like if you are relying on this exchange for "proving presence or absence...in a secure way..." false positives are a deal breaker especially seeing as how they are doing "the block chains"

But there are supposedly more papers in the pipeline that might explain this. Either way, it was good advertisement, I went to their site, and looked for the project on github (did not find them though) maybe they could link it from their site?

Here is the Github repository: https://github.com/labbloom/bloom-tree

The “github” word in the paper is clickable and redirects to the github repo. It appears to become highlighted only when it is in PDF format, thanks for indirectly pointing that out. The presence proofs are as you said probabilistic, whereas the absence proofs are non-probabilistic. In our specific use case (which we’ll explain in a future paper) the false positive nature of the bloom tree becomes actually handy to the problem we try to solve. But you are correct, we should probably rephrase the sentence to make it clear that the presence proofs are probabilistic and can be false positives, thank you for your feedback. We wrongfully assumed that this would be clear after explaining the probabilistic nature of bloom filters.

Reply on news.ycombinator.com