[tor-bugs] #29006 [Core Tor/Tor]: PrivCount proof of concept: add noise to counters

[Tor Bug Tracker & Wiki]

#29006: PrivCount proof of concept: add noise to counters
------------------------------+--------------------------------
     Reporter:  teor          |      Owner:  teor
         Type:  defect        |     Status:  assigned
     Priority:  Medium        |  Milestone:  Tor: 0.4.0.x-final
    Component:  Core Tor/Tor  |    Version:
     Severity:  Normal        |   Keywords:  privcount
Actual Points:                |  Parent ID:  #27908
       Points:                |   Reviewer:
      Sponsor:                |
------------------------------+--------------------------------
 We need to add noise to PrivCount counters to protect user activity. We
 split this noise between the Data Collectors (DCs), so that the final
 aggregate count includes enough noise to protect at least one user's
 activity.

 For consumed bandwidth, we can calculate an average user's activity by
 dividing the total consumed bandwidth by the total number of users. Then,
 we split this noise across all the DCs (the relays that support version 1
 of the PrivCount protocol), using each relay's consensus weight fraction.

 DCs need to add noise when we start, and when each consensus arrives,
 based on our own consensus weight fraction in that consensus. (How do we
 deal with the off-by-one error here? Weight by the time between the last
 consensus, the round end/start, and the time we'll try to fetch the next
 consensus?)

 We'll need to add excess noise to compensate for relay failures, and
 malicious relays.

 We should just use the easiest Gaussian sampling method available. Adding
 any noise is an improvement for almost all of our statistics - we can deal
 with floating point issues later.

 We should keep track of:
 * ConsensusCount - the number of consensuses we've seen
 * PrivCountConsensusWeightFraction - the consensus weight of this relay,
 divided by the consensus weight of all relays supporting PrivCount

 For each counter, we should keep track of:
 * NoiseVarianceAmount - the total variance (standard deviation squared) of
 all noise added to this counter. We use variance because it's additive.
 (And standard deviation is not.)

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