[tor-bugs] #15469 [Tor]: Remove data structure containing unique IP address sets

[Tor Bug Tracker & Wiki]

#15469: Remove data structure containing unique IP address sets
-----------------------------+----------------------------------------
     Reporter:  karsten      |      Owner:
         Type:  enhancement  |     Status:  new
     Priority:  major        |  Milestone:  Tor: 0.2.7.x-final
    Component:  Tor          |    Version:
   Resolution:               |   Keywords:  tor-relay privacy SponsorR
Actual Points:               |  Parent ID:  #7532
       Points:               |
-----------------------------+----------------------------------------
Changes (by nickm):

 * keywords:   => tor-relay privacy SponsorR
 * priority:  normal => major
 * parent:   => #7532
 * milestone:   => Tor: 0.2.7.x-final


Comment:

 We can do much better here, in fact.  We can retain an estimate of unique
 IPs without keeping a map of client IPs.

 (I am guessing that SponsorR might be interested here since they are
 interested in safe stats for hidden services, and a general safe stats
 infrastructure could be quite useful.)

 Oluwakemi Hambolu and Richard Brooks (both of Clemson) have drawn my
 attention to a couple of estimation techniques that could help a lot here.
 Have a look at these papers:
      http://www.mathcs.emory.edu/~cheung/papers/StreamDB/Probab/1985
 -Flajolet-Probabilistic-counting.pdf
      http://arxiv.org/pdf/math/0608176.pdf
      http://agl.cs.unm.edu/~forrest/publications/final-2007.pdf
 and this MS thesis:
 http://tigerprints.clemson.edu/cgi/viewcontent.cgi?article=2987&context=all_theses

 And also see "Attack Tolerant Privacy Preserving Statistics using
 Probabilistic Counting" (forthcoming; I have permission to share a copy).

 See also ticket #7532

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/15469#comment:1>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online