Re: [Asrg] SICS

[Seth Breidbart <sethb at panix.com>]

Laird Breyer <laird at lbreyer.com> wrote:

> While your 40 million user database has constant activity, I presume
> the vast majority of usernames have a long lifetime, a few days at
> least.  So if you build username snapshots at fixed intervals, then
> users would have to wait a little for their new address to become
> "live" etc.

If you're willing to suffer a _few_ false positives on the filtering,
and do a little more arithmetic, you can do better.  Construct some
number of hash functions whose output is an address that holds 1 bit.
Hash each email address with each function, and turn the pointed-at
bit on.  When email comes in, apply all the hash functions and check
the pointed-at bits.  If they're all on, pass the message through.

A new user gets turned on immediately, by turning on the necessary
bits in the table.  A deleted user doesn't go away until the next full
rebuild.  There's a small chance (depends on hash table size, number
of hash functions, number of valid email addresses) of a random
address being accepted due to collisions, but this can be made
acceptably small.  (Using a parameterized set of hash functions allows
them to be changed every rebuild, to avoid the chance that a commonly
attacked bad address passes.)

Seth

_______________________________________________
Asrg mailing list
Asrg at ietf.org
https://www1.ietf.org/mailman/listinfo/asrg