Opened 8 months ago

Last modified 3 months ago

#29006 assigned enhancement

PrivCount proof of concept: add noise to counters

Reported by: teor Owned by:
Priority: Low Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: privcount, 040-unreached-20190109, 041-accepted-20190115, teor-unreached-2019-03-08
Cc: Actual Points:
Parent ID: #27908 Points: 2
Reviewer: Sponsor:

Description

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 (8)

comment:1 Changed 8 months ago by teor

Type: defectenhancement

These should all be enhancements

comment:2 Changed 8 months 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 8 months 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 8 months 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 7 months 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 7 months ago by nickm

Sponsor: SponsorV

comment:7 Changed 6 months ago by teor

Keywords: teor-unreached-2019-03-08 added
Milestone: Tor: 0.4.1.x-finalTor: unspecified
Owner: teor deleted
Priority: MediumLow
Sponsor: SponsorVSponsorV-can

The PrivCount proof of concept must have bandwidth. Everything else is optional.

comment:8 Changed 3 months ago by gaba

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