Re: [9fans] opposite of bloom filter

[Russ Cox <rsc@swtch.com>]

> I'm currently looking for the opposite of an bloom filter, which
> may have false negatives but no false positives.
>
> The purpose is allowing an spooling (store+forward) mail relay
> to learn which addresses are not accepted by the actual maildrop
> (which is connected by an uucp-link, so no direct smtp chat),
> to get rid of the thousands silly error bounces from brute force
> attacks on email addresses.
>
> An trivial idea would be simply using an hashtable as blacklist,
> but obviously that would become very big. I need a more compact
> form, perhaps a subset of regex'es, a colored (b)tree, etc ?
>
> Any ideas ?

Use a Bloom filter.

You are looking for the opposite of a Bloom filter in order
to ask the question "is this an invalid email address?".
Instead, use a Bloom filter to ask the question
"is this a valid email address?".

This requires the remote uucp site to give you a Bloom
filter with all the valid addresses inserted, but that seems
unavoidable.  I don't know how the opposite-of-Bloom-filter
approach would work anyway.

Russ