Bloom filters debunked: Dispelling 30 Years of bad math with Coq
gopiandcode.uk
gopiandcode.uk
[1] https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d...
[2] https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d...
Now, others later recognized this faulty assumption and produced a new formula and a faulty proof for its correctness. A machine certified proof would help here if an actual proof step is wrong, except note the footnote: "To be fair, the error in Bose et al.'s paper was primarily due to incorrect definitions, rather than an incorrect logical step. As an interesting anecdote, the first version of our work was based off the incorrect definitions by Bose et al. and ended up being rejected by reviewers who then rediscovered this error." So again it was human checking that (re-)discovered an issue. One that appears to have been fixed by humans before this work. And one that the machine wasn't able to find.
So now that all known incorrect assumptions are shaken out (there might be unkown ones, Coq can't tell) this work is a machine checked proof of something that had been proved before. It's an achievement, and it's good to have certainty. Almost anything that gets us closer to more formal math and computer science is good. But this particular result is hardly spectacular.
As for the clickbait aspect, I'm also annoyed by it. The title is clearly factually incorrect. No property of Bloom filters has been debunked. A widely cited formula was replaced by an asymptotically equivalent one 12 years ago, and we now have a machine checked argument that this replacement was correct. This isn't a debunking of anything. No math has been disspelled.
Clear and honest science communication is important. Authors overselling their work in such (obvious) ways just highlights that they themselves don't think the work is sensational (which it doesn't have to be!), and it makes readers wonder in what other ways they are intellectually dishonest.
Apologies if my wording did not make this clear: the original proof by Bloom is logically incorrect
Bloom derives his expression by performing a transformation that would only be possible if the bits are independent, but nowhere in his proof does he state that he is making this assumption. It just so happens that even if he had explicitly included this assumption, it would not have been justified. So in that sense, the debunking part is correct - we disprove Bloom's original bound by proving the true bound under the same assumptions that he explicitly makes.
Really cool otherwise, I should really look into Coq more for my own work.
In that sense, this work is really more theoretical than practical, but still, I think, a nice result.
I see, thanks for this clarification. I read your post as saying that the assumption was explicit. I agree that reasoning from an implicit assumption is a logical error. Still, the real problem was not the assumption being implicit/explicit but rather that one doesn't want to rely on it at all. Which again is an extra-logical issue.
> So in that sense, the debunking part is correct - we disprove Bloom's original bound by proving the true bound under the same assumptions that he explicitly makes.
OK. I don't think that recapitulating something that has been known with more or less certainty for 12 years counts as "debunking". For me "debunking" has a connotation of being original, maybe for you it doesn't.
But I especially think that "the formula was only asymptotically correct" is too weak a statement to count as a "debunking". For me "debunking" an algorithm or a data structure would have to be something much bigger, like "Quicksort doesn't always sort" or "binary search trees can lose data" or "Bloom filters can sometimes have false negatives". Not "the behavior we have been seeing for the last 50 years matches the original formula well, but strictly speaking it matches the new formula a bit better". Your mileage obviously varies.
EDIT: Let me stress again that I'm not pooping on your work. The work appears sound and important, since this was so tricky to get right in the past. But I am pooping on the title.
Given the history of the proofs of the Bloomfilter, I'd argue that the bound was not really "known with more or less certainty" - if so many corrections had to be made, why should we believe that this latest paper was truly correct? it does not seem to be unreasonable to believe that there might be other errors that had been been similarly overlooked. Our research tackles this problem - it provides a guarantee that there are no further hidden errors.
> "the formula was only asymptotically correct"
I have no issues with the behaviors of a data structure being characterized in an asymptotic sense, but I do think that giving a bound that you claim to hold exactly, but then having it turn out to only hold asymptotically is incorrect and worthy of debunking. Furthermore, most citations of Bloom's bound do not claim it is an asymptotic bound, but use it as an exact one, which is clearly incorrect.
At the end of the day, this is primarily a formal result with few direct implications on practical usage. As I mentioned in another post, I tried to make it more relatable to an engineering audience, but it's possible that I may have buried the lede somewhat. However, I still stand by the statement that the title is not incorrect, at least if only from a mathematical perspective.
Does it? At a glance you seem to have evaluated Bloom's false positive rate against Knuth's version of the filter. I say this because your starting point is Bose, whose result is for Knuth's version.
The popular "Bloom filter" is not, in fact, Bloom's filter. Their different constructions lead to different exact false positive rates, so I suspect you've failed to prove anything about Bloom's original paper.
Of course Bloom was wrong in any case. Grandi's "On the Analysis of Bloom Filters" (2017) is the paper to read there. It was the first to offer an exact account of the false positive rate for Bloom's construction.
In Bloom's original paper "Space/Time Trade-offs in Hash Coding with Allowable Errors", Bloom proposes multiple variants of these filter structures, and it is true that these variants do have different behaviours.
However, the expression cited as Bloom's bound (equations 16/17 in the paper) are specifically about a data structure (he refers to it as method 2) that works exactly like the standard definition of a Bloom filter (Knuth's version). In this sense, our result holds for Bloom's bound.
For reference, Bloom's description of method 2 is as follows:
> Method 2 competely gets away from the conventional concept of organizing the hash area into cells. The hash area is considered as N individual addressable bits, with addresses 0 through N - 1. It is assumed that all bits in the hash area are first set to 0. Next, each message in the set to be stored is hash coded into a number of distinct bit addresses, say al, a2, ..., ad. Finally, all d bits addressed by al through ad are set to 1.
> To test a new message a sequence of d bit addresses, say al, a2, .. , ad, is generated in the same manner as for storing a message. If all d bits are 1, the new message is accepted. If any of these bits is zero, the message is rejected.
Clearly this method describes the conventional version of the Bloom filter.
> each message in the set to be stored is hash coded into a number of distinct bit addresses
In Knuth's filter, the addresses aren't distinct. Bloom's construction requires that they are, thus the probability of a bit being set to 0 from (16) in Bloom's paper is 1−(1−k/m)^n, different from the 1−(1−1/m)^(kn) in your paper.
Cuckoo hashing is commonly simplified in a similar way, indexing into a single table and allowing the hashes to overlap, unlike Pagh's original.
Anyway, from your paper:
> Bloom then claimed that the probability of a false positive was simply the probability of a single bit being set, raised to the power of k, reasoning that a false positive for an element y ∈ bf only occurs when all the k bits corresponding to the hash outputs are set.
> Unfortunately, as was later pointed out by Bose et al.[8], as the bits specified by f_1(x),...,f_k−1(x) may overlap, we cannot guarantee the independence that is required for any simple relation between the probabilities.
You're still right that Bloom is off, but it's not due to overlap in f_1(x),...,f_k−1(x), which his construction doesn't allow.
My broader point though was about your "guarantee that there are no further hidden errors", because a theorem prover is just a tool, tools are used by people, and people make mistakes.
> each message in the set to be stored is hash coded into a number of distinct bit addresses
Good point, You are right that our correction does not address errors in Bloom's original definition, but rather in the definition of the Bloom filter that is typically used - I'll add a note to address this.
> My broader point though was about your "guarantee that there are no further hidden errors", because a theorem prover is just a tool, tools are used by people, and people make mistakes.
Yes, you are right, that's probably too strong a claim, my aim was to emphasize that there is more certainty in the proof, making it unlikely that there are no further hidden errors, but that was not clear.
In a strict sense, yes, the problem with Bloom's proof was due to an implicit unjustified assumption. However, the reason that this assumption was implicitly introduced, was because Bloom accidentally overlooked certain dependencies between the bits - the "real problem" in this sense is the fact that when reasoning about random algorithms, it is hard to keep track of all the various dependencies involved and this can lead to incorrect proofs. This problem of tracking dependencies is a logical issue and one that is solved by proving the bound in a proof assistant.
Am I misunderstanding what you and/or the article means by "independent"? The fact that indexes derived from (non-overlapping) parts of a hash function output are uniformly ((preferably crypographically-secure-)psuedo-)random (and thus uncorrelated with each other and with indexes from other hash invocations) is what the phrase "hash function" means ("avalanche effect" if I remember my terminology correctly).
The article very clearly points out an error in the original proof.
The HN community can be so toxic sometimes. Inevitably whenever someone produces a new machine-checked proof, all these commenters come out of the woodwork explaining how assumptions/definitions are not verified and therefore the whole endeavor is somehow worthless.
A researcher being excited about their research is nothing to be ashamed about. I especially appreciate the fact that one of the authors took the time to make an accessible blog post to introduce us to their work.
We're using slightly different notions of "proof": I am talking about (1) the proof steps involved in proving a given, fixed statement. You are talking about (2) a wider notion that includes the formulation of the statement to be proved. Both of these are valid meanings for the word "proof". Coq can only check the details of sense 1, not the additional details of sense 2. The error in the original proof (sense 2) is in these additional parts, not in the proof according to sense 1.
> assumptions/definitions are not verified and therefore the whole endeavor is somehow worthless.
This is not at all what I have done.
> A researcher being excited about their research is nothing to be ashamed about.
Right. And the actual work done here is reason enough for excitement.
> I especially appreciate the fact that one of the authors took the time to make an accessible blog post to introduce us to their work.
So do I. But the fact that the target audience keeps discussing the title shows that the title was not appropriate for the target audience.
No, I am not. The original proof used an implicit assumption, which is a problem with the proof proper, not the formulation of the statement to be proved. Using a proof assistant guarantees that there are no implicit assumptions, which is one reason why this work is notable. It rules out an entire class of errors which were present in previous work.
>>> The article very clearly points out an error in the original proof.
You didn't say what error you meant here, but later you wrote this:
> The original proof used an implicit assumption, which is a problem with the proof proper
This is true, but this is not pointed out in the article at all, let alone "very clearly".
As established elsethread, the article's problem with the assumption is not it being implict or explicit, the authors simply didn't want to have to use the assumption at all.
No it isn't.
"Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth
The highest degree of scrutiny that a proof can undergo is to run the code and observe that it works.
It's just ('just'), that that's usually computationally intractable, because you're trying to prove things about the entire set of possible inputs, and that set is infinite or at least extremely large. So you have to settle for lower degrees of scrutiny, that can be more easily verified.
A year or two ago when bloom filters became a recurring popular topic on HN I read a long illustrated medium post on them found via HN out of curiosity to add the concept and tool to my back pocket, and it all seemed complicated and the explanation didn't stick. Your explanation however was quick and made complete sense and I cannot forget it. Appreciate it! Thank you!
I wonder if the key is in quickly grounding the core abstractions with concrete meaning early on, that way your mind quickly has a model of "things" to operate on before attempting to build up the behaviour with more abstract description.
Many descriptions stay in the abstract too long without anything to attach it to for the uninitiated... in which case you either persevere and eventually it clicks and all the relationships fall into place - or you give up out of disinterest.
I've noticed this when explaining things to others, especially non-technical people, when explaining seemingly very simple things, attempting to describe them in multiple ways and failing, and then realizing they need clarification of the "what", after which explanation is easy - sometimes you are blind to it when you already know "what" and already have the mental model so you jump straight into how and why.
Of course, that assumes familiarity with chaining hash tables, but I feel like every CS program goes over hash table implementations, but bloom filters weren't something I learned about until I left college.
- If the bloom filter said "True", then you go ahead and fetch the data from the original structure - If the bloom filter said "False" but that might be a false negative then you'd have to anyway query the original structure to be sure
With 0% false negatives but a relatively small rate of false positives instead, you don't have to query the original source if the filter gave a "False".
Btw. Bloom filters were one of the first probabilistic data structures with real practical uses and still to this day are widely used. They are still not out-classed in every way by newer algorithms like Cuckoo filters.
If "Foo" and "Bar" hash to "XX" and you've shown "Foo" to the filter, it will think it saw "Bar" because what you are really asking is if it saw something that hashes to "XX".
That's the false positive.
On the flip side if "Baz" hashes to "XY" then the filter would tell you with certainty that it never saw "Baz" because it never saw anything hashing to "XY" and so "Baz" could not have been seen either.
First, the definition of Bloom filters is a probabilistic data structure to test the presence of an element in a set no matter the program logic around it.
But secondly, given your example of safe browsing, you can flip positive and negative meanings around freely by how you define the question. Is it "is this a bad domain?" or "is this a good domain?" which you both can convert to "is this domain in the set?" and "is this domain NOT in the set?".
And that's a general problem with "positives" and "negatives", they depend purely on the question and the question can have a boolean negator in it. But that's a logical layer above the data structure. As you said, the data structure does not care, it is just bits and therefore the question is "is the element in the set?".
Same as one could ask "Is it day?" or "Is it night?" which both query the same underlying data about the time and location but would have opposite meanings for positive and negative results.
And so, to give the two terms a better meaning we have a definition of the data structure and the operations on it which defines the meanings of negatives and positives.
I think some part of the reason for confusion with false negatives and positives results from the conotations of "positive" (good) and "negative" (bad).
[0] https://arxiv.org/abs/1912.08258 ("Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters")
Would love to see a table with computed numbers comparing the rates. It’s hard for me to understand the behavior of that second result
[1] https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=90377...
An (asymptotic, for p <=~ 10%) back of the envelope formula is that such a hash table/set of fingerprints takes up a factor of about (1+log_{1/p}(N)) more space than a Bloom filter. It is not hard to derive this. Unlike the incredibly precise Coq formula proof theme, this is all approximate, but more engineering-relevant.
If you were targeting p=0.001 to have a small mistake rate, 1 + log_1000(N) is pretty small (say <~ 1+3=4 for for N <~ 1e9 elements). While it does use 25% space, this Bloom filter would require many more (-log_2(p) =~ 10) probes while the LP hash table would only hit the DIMMs once. Many, but not all, might view a 10x latency reduction as worth 4x the space in the game of space-speed trade-offs.
Analysis of speed these days (where a single main memory hit is thousands of superscalar dynamic instructions) is tilted differently than it was in 1969. Still, even back then Bloom's own original paper had a footnote qualifying his superiority conclusion as dependent upon memory system assumptions. Beats me how this gets lost. Call it "The Bloom filter mystique".
If you're interested at looking at the sources, I think the following commit was around the place where I was working on this: https://github.com/certichain/ceramist/commit/70927c5b50e21a...
What you can do, sometimes, is succeed in proving the negation of the incorrect result.
If you look at the related work section of the paper, we actually present a multitude of papers in the literature (even some recent as 2019) that actually still incorrectly refer to Bloom's expression as an exact bound, so I thought at the time that the "debunking" title was not inaccurate.
I'll keep your advice in mind the next time I write an article about research work.
So none of this matters for malicious site filters, or anything like that. And the reason why it took 30 years to notice the original problem is that, if you just test the false positive rate for typical Bloom filters empirically, you'd come within error margins of the "wrong" result anyway. It's not like people trusted critically bad math for 30 years. The bad math was formally speaking wrong, but close enough to the right result for nobody to notice nor care.
I know mathematicians have to sell their research, but sorry, with this one you didn't advance the state of the art of practical Bloom filter usage, just the state of the art of formal proofs :-)
But what you're saying sounds a lot like many proponents of various flavors of NoSQL, Eventual Consistency, etc. I.e., it sounds like you are saying that lots of people have been using it for a long time, and it's just good enough. The actual correctness isn't really that big a deal.
I might be crossing domain boundaries here and thinking up stuff that really doesn't matter. I mean, bloom filters have a known challenge. No one was ever supposed to use them except for statistical purposes anyway, and with a known error rate, it's fine to add into your models.
But there's also something that feels a little weird about your point. It sounds like you're saying it's good enough for X, Y, and Z use cases; therefore it doesn't really matter how technically wrong it is.
But again, I could be really off.
If you had very specific tolerances here you wouldn't work in terms of the expected false positive rate anyway; you'd build your filter and validate on the real thing.
For example, if you size a bloom filter a certain way, the "bad" math might tell you your false positive rate is 0.001%, while the "good" math might tell you your false positive rate is 0.001002%. It makes no difference. The error is orders of magnitude smaller than the number you get anyway. (I made those numbers up, but I've used Bloom filters and they should be in the ballpark for the sizes I've worked with). The bad math might be strictly speaking incorrect, but it's a good enough approximation for all practical purposes.
This is different from Eventual Consistency stuff, which has real practical implications from not having certain guarantees. Those limitations are real, and they have real consequences, not just a rounding error in a number.
I expect that you would get a lower false-positive rate, though, if some inputs could not randomly query fewer than k bits of the filter!
It does indeed reduce the false positive rate, but comes at the cost of increased space usage. As always, utility of this modification would depend on where you wanted to balance space-vs-accuracy constraints.
For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed.
Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan.
I think it might be interesting to look into though.
Relatedly, mapping real hash functions to bits is also nontrivial to get 100% mathematically correct. As far as I know, the only sound way for hash functions with a fixed number of output bits and a non-power-of-two bloom filter is to truncate to the next power of two, then throw away any results that overflow the filter size and keep trying with new hashes (or repeated hashing). This is thus easy to integrate with avoiding duplicate bits, since you're retrying anyway.
In practice, none of this matters, you can just take a hash output with enough extra bits modulo the Bloom filter size and call it a day. It'll be close enough to uniformly random and non-colliding anyway, for practical filters.
This is an O(n^2) algorithm, which you can improve to O(nlgn) using fenwick trees.
In practice however, it is much quicker to generate random hashes and repeat until they're distinct.
function get_bits(input, hashes, n)
local bits = {}
for i=1,#hashes do
local bit = hashes[i](input) % (n-i+1)
for j=1,i-1 do
if bits[j] <= bit then
bit = bit + 1
end
end
bits[i] = bit
while i > 1 and bits[i] < bits[i-1] do
bits[i], bits[i-1] = bits[i-1], bits[i]
i = i - 1
end
end
return bits
endYou need to truncate to an even number of bits and retry until the output is < n, at which point you're retrying anyway, so you can just retry on collision instead of having all that complicated logic to skip bits.
Nice try though, but if you want formally perfect results like the OP you have to try harder :-) (except real hash functions are only assumed to have perfectly distributed functions anyway, that is not proven and probably not provable, so basically you're screwed either way and none of this matters :-) ).
As others have pointed out you can also just make the k^th hash pick any of the n-k remaining options.
Additionally, Bloom's original bound is given (and typically quoted) as an exact expression for the false positive rate, so while it may be correct as an approximation, I'd say its fair to say that the original bound is wrong.
In the extreme case, imagine that your k hash functions are nearly identical: hash function `H_i` differs from `H_1` only in that the outputs for the `1`st and `i`th elements in the input space are swapped. Of the `N` elements in the input space, all but `k` will completely collide.
If you could assume a perfect hash function, you could treat 64 or 80 bits as secure in a wide swath of inappropriate contexts.
You're confusing statistically uniform with cryptanalytically secure. By that logic you can 'debunk' plain old hash tables because someone might feed you keys that all hash to the same slot.
To calculate the probability, we will work out the number of ways to assign kl hashes to m bits (I.e. functions from a set of size kl to a set of size m), and for each of those ways we will work out how many ways we could assign k hashes to the bits which are set (I.e. ways to get a false positive). We then count the number of possible ways to assign our kl hashes of existing elements and k hashes of the tested element to m bits and divide the former by the latter. For the argument to be valid, each assignment of hashes to bits must have equal probability, which is true if the hashes are independent.
The simple way to count the number of assignments of kl hashes to m bits is easy: for each hash there are m possible bits so we get:
m^(kl)
m^(k(l + 1))
(m choose i) i! {kl; i}
m^(kl) = Sum_(i = 0)^m (m choose i) i! {kl; i}
Sum_i i^k (m choose i) i! {kl; i}
The flaw is that they do not specify that the size of the bit array should be a prime number. This omission alone is astounding. To be fair, they state that they assume the bits from the hash functions are randomly distributed over the bit vector, so with this assumption they skate past this issue even though they have apparently missed that crucial detail of part of how it is accomplished. One wonders if they were unaware.
The fallacy imho, but this is where I depart from the community, thus imho, so take me with a grain of salt if you wish, is that you don’t need multiple independent hash functions. You just need multiple inputs. For example instead of hashing the word “salad” three times, just hash the tokens salad1, salad2, and salad3. If your hash function is worth its salt (npi) then you will be just fine.
Can you use less storage by having distinct bit vectors of each hash? This seems like a natural question once we know the false positive rates are different.
Maybe Bloom was misinterpreted and right all along?
"We instantiated this interface with each of the previously defined AMQ structures, obtaining the Blocked Bloom filters, Counting Blocked Bloom filters and Blocked Quotient filter along with proofs of similar properties for them, for free."
So it sounds like the new AMQ algorithms you allude to are blocked (more cache friendly) variants of existing AMQ algorithms. Are the bounds you proved all good in some sense? Do you know yet if they're actually faster in practice on real hardware, or do optimized implementations still need to be written?
For practical purposes, you would have to take the effect of caches into account, and the performance may vary depending on the particular choice of hardware. Our work stuck mainly to the theoretical side, so we didn't do any empirical testing of these new data structures. I guess the jury is still out on whether these variants are actually better in practice than the existing ones.
There were a couple of typos - might be worth getting someone to proof read it... (I am out atm so don't have a good way of laying out suggestions for corrections)
It was mostly just a quick transcription of the corresponding presentation for the paper, so some typos may have crept in. I'll do a second pass and try and fix that later today.
The diagrams are great too!
I think that was actually a mistake in my writeup, I just copied the latex from the paper without adjusting it to the notations used in the article. I'll make sure to fix it.
It's claimed that the URLs which browsers send up (having been diagnosed positive by the test) will ”have a high likelihood of actually being malicious", but that by no means follows from the test's low false positive rate. You need to consider the background rate.
Just like in the classic example of a positive diagnosis from a low false positive test for a rare desease.
You can reason roughly as follows:
P[ pos | mal ] = 1 (no false negatives)
= P[ pos /\ mal ] = P[ mal ] (Bayes)
P[ pos | ¬ mal ] ~= 0 (low false positive rate)
P[ pos /\ ¬ mal ] / P[ ¬ mal ] ~= 0
(P[ pos ] - P[ pos /\ mal])/(1 - P[mal]) ~= 0
(P[ pos ] - P[ mal ])/(1 - P[ mal ]) ~= 0
P[ pos ] - P[ mal ] ~= 0
P[ mal | pos ]
= P[ mal /\ pos ] / P[pos]
= P[ mal ] / P[ pos ]
~= 1.0Say we have a million urls, and a thousand of them are malicious. Our filter returns a positive result for all the malicious 1000 (no false negatives) and for the safe 999000 urls only 1% will return positive (low false positive), but that's still 9900 false positives. So a positive result only has a (1000 / (1000 + 9900)), i.e. 9%, chance of actually being malicious.
Even with a false positive result of only 0.1%, the probability of a positive result actually being malicious only rises to 50%, so still not in "high likelihood" territory.
I think what I probably should have said instead was that the low false positive rate means that only a small proportion of the honest URLs will be sent up.
You didn't prove this. You can't swap subtraction for multiplication. It's not equivalent to
> [ pos ] - P[ mal ] ~= 0
1e-100 - 1e-200 ~= 0, but
1e-200 / 1e-100 = 1e-100
That's the point of the base rate fallacy. https://en.m.wikipedia.org/wiki/Base_rate_fallacy
False negative rate doesn't matter. A low false positive rate can be much larger than the true positive rate.
Imagine an extremely rare toxin that always turns your skin blue. Only 100 people in the world have it. But 1000 people are wearing blue face paint at any given time. A diagnostic test "are you blue?" Would have no false negatives and very low false positives for the toxin, just like a Bloom filter. But a positive test would not mean highly likely to have the toxin; it would mean highly likely to be wearing face paint.
Yes, I guess the low false positive rate doesn't actually justify believing that the the URL has a high likelihood of actually being malicious.
The correct wording should probably be that the low false positive rate means that non-malicious urls are unlikely to be sent out. I'll fix this.
As in, just like DNS.
It's an ironic demonstration that we shouldn't trust prose. The author's implied thesis is that papers are worthless and only code matters, which applied to the author's paper too!
To reiterate a point I made in an earlier response: In the paper, we actually present a large number of other papers in the literature (even some recent as 2019) that actually still incorrectly refer to Bloom's expression as an exact bound, so I do think that this is important and somewhat justifies the debunked narrative.
From "Google Chrome Privacy Whitepaper":
Chrome checks the URL of each site you visit or file you download against this local list. If you navigate to a URL that appears on the list, Chrome sends a partial URL fingerprint (the first 32 bits of a SHA-256 hash of the URL) to Google for verification that the URL is indeed dangerous. Chrome also sends a partial URL fingerprint when a site requests a potentially dangerous permission, so that Google can protect you if the site is malicious. Google cannot determine the actual URL from this information.
https://www.google.com/chrome/privacy/whitepaper.html#malwar...
(I work for Google but not on anything like this.)
----------------
Q: It is proposed to make the local DNS resolver handle IPv4 by using 64 Bloom filters, BO1, BZ1, BO2, BZ2, ... BO64, BZ64.
Filter BOn answers the question "is bit n of the IP address a 1?", and BZn answers the question "is bit n of the IP address a 0?".
Your resolver checks all these Bloom filters. If BOn return "no", then it knows bit n of the address is 0. If BZn returns "no", then it is knows bit n of the address is a 1. Only if BOn and BZn both return "maybe" for some n must the resolver actually do a DNS query over the internet.
Explain why this proposed resolver would not be useful.
https://github.com/certichain/ceramist/blob/fd5e522f2c381f7d...