Opened 21 months ago

Last modified 5 months ago

#25153 assigned task

Specify how PrivCount in Tor statistics are configured and interpreted

Reported by: teor Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: needs-proposal, privcount, 034-triage-20180328, 034-removed-20180328, 035-removed-20180711, teor-unreached-2019-03-08
Cc: Actual Points:
Parent ID: #22898 Points: 5
Reviewer: Sponsor:

Description (last modified by teor)

In prop#280 prop#288, we specified the counters, noise, and secure aggregation for PrivCount in Tor.

Now we need to specify:

  • how long each collection round goes for
  • how we determine which counters are collected
  • how we configure the amount of noise for each counter
  • how Metrics can interpret the final results

We should also try to answer the unanswered questions in prop280.

Child Tickets

TicketStatusOwnerSummaryComponent
#27906assignedPrivCount noise specificationCore Tor/Tor
#27907newPrivCount config and version specCore Tor/Tor

Change History (13)

comment:1 Changed 20 months ago by teor

Parent ID: #22898

comment:2 Changed 20 months ago by teor

Description: modified (diff)

comment:3 Changed 20 months ago by teor

Sponsor: SponsorQ

comment:4 Changed 19 months ago by nickm

Keywords: 034-triage-20180328 added

comment:5 Changed 19 months ago by nickm

Keywords: 034-removed-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

comment:6 Changed 19 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if time permits.

comment:7 Changed 18 months ago by teor

I think I have worked out how we can do PrivCount in Tor version upgrades.

We can safely add counters to an existing PrivCount in Tor deployment if we increase the noise added by older versions (or turn them off if they are too old). If we specify a noise ratio for each stats version in the consensus, then we can increase the noise in older versions each time we release a new version. If we removed counters, we would just accept the excess noise (which is safe), or not increase the noise as much when we add the next counter.

Two further thoughts on PrivCount in Tor:

  1. Each counter we add will add more noise. To get the same relative noise, we can add more collecting relays. I wonder if we can calculate how much consensus weight we need to add per counter.
  1. We can discover relays that submit out of range data without specialised oblivious computation:

a) the tally reporters do an aggregation round where each relay is in its own partition
b) to protect relays which actually reported statistics, each tally reporter adds enough noise to hide the largest valid relay
c) if a relay's total is large enough (4 or 5 sigmas away from the mean, positive or negative), it is probably bad. 4 sigmas is 1 in 16,000, or a 38% probability of a false positive for 6000 relays. So we might need 5 sigma if we ever deploy to the whole network. See https://en.m.wikipedia.org/wiki/Normal_distribution#Standard_deviation_and_coverage

If we ran out of bounds detection before every aggregation, we could use it to detect grossly inadequate noise. Which would make it safe to collect protocol warnings even if we get the action bounds (expected activity for a single client) wrong.

But per-relay partitions enable an attack where you push a client's activity on a guard over the threshold, so the guard is excluded from the stats. We could set the exclusion threshold so high that it's physically impossible to have that many events.

comment:8 Changed 18 months ago by teor

Milestone: Tor: unspecifiedTor: 0.3.5.x-final

This is on our 0.3.5 roadmap.

comment:9 Changed 16 months ago by nickm

Keywords: 035-removed-20180711 added
Milestone: Tor: 0.3.5.x-finalTor: unspecified

These tickets are being triaged out of 0.3.5. The ones marked "035-roadmap-proposed" may return.

comment:10 Changed 15 months ago by nickm

Sponsor: SponsorQSponsorV-can

comment:11 Changed 8 months ago by teor

Keywords: teor-unreached-2019-03-08 added
Owner: teor deleted

Unassign the tasks that are in tor: unspecified

comment:12 Changed 5 months ago by gaba

Removing sponsor V as we do not have more time to include this tickets in the sponsor.

comment:13 Changed 5 months ago by gaba

Sponsor: SponsorV-can

Removing sponsor from tickets that we do not have time to fit in the remain of this sponsorship.

Note: See TracTickets for help on using tickets.