Opened 6 weeks ago

Last modified 3 weeks ago

#29006 assigned enhancement

PrivCount proof of concept: add noise to counters

Reported by: teor Owned by: teor
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: privcount, 040-unreached-20190109, 041-accepted-20190115
Cc: Actual Points:
Parent ID: #27908 Points: 2
Reviewer: Sponsor: SponsorV


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.)

Child Tickets

Change History (6)

comment:1 Changed 6 weeks ago by teor

Type: defectenhancement

These should all be enhancements

comment:2 Changed 6 weeks ago by teor

Points: 2

If we hard-code a lot of things, this should not take more than a few days.

comment:3 Changed 6 weeks ago by teor

Keywords: 040-unreached-20190109 041-proposed added
Milestone: Tor: 0.4.0.x-finalTor: unspecified

These tasks are on the 0.4.1 roadmap for PrivCount and Sponsor V.

comment:4 Changed 6 weeks ago by teor

Keywords: 041-proposed-on-roadmap added; 041-proposed removed
Milestone: Tor: unspecifiedTor: 0.4.1.x-final

Let's review these tickets at the next meeting using our 041-proposed process.

They're on the roadmap, so the review should focus on ticket size and team capacity (and sponsor expectations).

comment:5 Changed 5 weeks ago by teor

Keywords: 041-accepted-20190115 added; 041-proposed-on-roadmap removed

These PrivCount tickets are on the 041 roadmap, we accepted their points estimates in 041 without discussion.

comment:6 Changed 3 weeks ago by nickm

Sponsor: SponsorV
Note: See TracTickets for help on using tickets.