PrivCount Research Retrospective

Transcript of an IRC chat on #tor-dev in the 3/4 July patch party. Posted with permission, edited to remove other users.

<+komlo> i don't have patches to discuss, but i would like to hear opinions about good research ideas that didn't make it into tor, and why
...
<+komlo> ah ok, just that the idea lacked complete analysis and further analysis revealed flaws
<+komlo> ok, understood.
<+komlo> are there common trends in the analysis that isn't done?
...
<+komlo> ah right. making assumptions explicit is important
<+komlo> and sufficient information to reproduce the results
<+catalyst> it seems that often reviewers of papers lack the context to know if the assumptions were flawed
...
<teor4> komlo: I can tell you the privcount story if you want
<+komlo> teor4: that would be great!
<+komlo> just thinking these over and what concrete "do these things" recommendations would be helpful
<teor4> Ok, so researchers looked at Tor's statistics, and said: "wow, that's a lot of detailed information that adversaries are getting for free"
...
<+teor> And they thought that tor could do better, by adopting a secure stats aggregation scheme, with noise
<+teor> (secure stats aggregation reveals the network total, rather than each relay total)
<+komlo> teor: yep, following
<+teor> (noise hides a client's usage on the network)
<+teor> So they wrote a system called PrivEx, that had a single statistics counter, and their paper was done
<+komlo> teor: what do you mean by single statistics counter? 
<+teor> each Tor relay's public statistics are a simple total of what that relay has seen, sometimes categorised into countries. The non-public logs show about the same level of detail.
<+teor> komlo: just looking up the paper
<+komlo> teor: no worries, i can look at the paper later. 
<+komlo> teor: i'm curious what the delta was between that paper and privcount :) 
<+teor> komlo: ha! we're not even at PrivCount yet
<+teor> So the single counter was the number of hits on a large list of censored exit domains
<+teor> And then that paper was done, and it was called PrivEx: http://discovery.ucl.ac.uk/1463996/1/Elahi%20et%20al.%20PrivEx%20.pdf
<+teor> (And those researchers did great work, because they actually deployed on the live tor network, rather than providing a theoretical scheme)
<+komlo> ah yes that seems useful 
<+teor> And then another group of researchers came along, and they said: "wait, Tor has many statistics, and we want to protect users even when an adversary knows them all"
<+teor> So they generalised PrivEx to multiple counters, with a combined noise budget that protected all of a user's actions on the network, rather than a particular action from a particular user
<+komlo> teor: that seems like a good next step to build on 
<+teor> And they made some improvements to the code, and deployed on the live network, and called it PrivCount, and their paper was done
<+teor> http://www.robgjansen.com/publications/privcount-ccs2016.pdf
<+komlo> i'm waiting for the catch :) 
<+teor> deployed a short-term experimental collection on the live network
<+teor> And then several groups of researchers though that PrivCount was great, and so they modified this experimental PrivCount to collect more statistics, and wrote papers
<+teor> Some of them used machine learning: http://www.robgjansen.com/publications/insidejob-ndss2018.pdf
<+komlo> "We deployed PrivCount on the live Tor network with 1 tally server, 6 share keepers, and 7 data collectors monitoring one Tor relay each."
<+komlo> ^ from the paper 
<+teor> Others used traffic flow analysis (and their paper is in draft)
<+teor> And others focused on collecting a large number of statistics (me et al), and their paper is in draft
<+teor> We also expanded the deployment to 16-17 relays, and 3 operators
<+teor> And did some early work on unique counts (PrivEx/PrivCount only support additive counts)
<+teor> And then the grant was done, and the papers were done-ish
<+teor> And at the same time, those researchers wanted to get their experimental PrivCount implementation deployed on the Tor network
<+komlo> and PrivCount was ready to be dropped directly into tor? :) 
<+teor> Oh, I wish!
<+teor> Just skimming prop#280 to refresh my memory
<+teor> But the design wasn't robust enough to scale to 1000s of relays, and their Tor patch required the control port to be open, which is a security issue, and it was slow
<+teor> (And none of us asked these questions in 2016, so we were a bit surprised in 2017 to get that feedback)
<+teor> And so nickm and I redesigned PrivCount for Tor, and wrote prop#280
<+teor> But prop#280 didn't solve all our open issues, because it didn't specify noise, and if any Tally Reporter (aggregation node) went down, there were no stats that day
<+teor> So we wrote prop#288
<+teor> where we specify secret sharing for redundancy, and how to generate noise, because it's easy to generate insecure noise
<+teor> And here's what we thought we had left to do:
<+teor> https://gitweb.torproject.org/torspec.git/tree/proposals/288-privcount-with-shamir.txt#n537
<+komlo> right, i wondered how often scalability is a major issue when evaluating research papers for potential implementation 
<+teor> So prop#288 defines the low-level API
<+teor> But we still need to specify how to allocate noise between counters, between relay partitions (to avoid outliers), between relays, and between consensuses
<+teor> And we need to work out how to determine the amount of client usage we want to protect for each statistic, in a repeatable way
<+teor> And we need to work out how to add and remove statistics, once some are already deployed
<+teor> And how we communicate the configuration parameters to all the relays
<+teor> So there's still a lot of work left
<+teor> If everyone is ok, I'll take a copy of the last few minutes, tidy it up, and put it on trac wiki
<+komlo> teor: ok by me, thanks for asking 
<+teor> So there's still a lot of work left to get PrivCount in Tor, and it's not necessarily work that interests researchers
<+catalyst> teor: ok with me, though i didn't say much once you started :)
<+komlo> teor: sure- would you say this is something that should have been discussed in the research paper or addressed in the implementation? 
<+teor> PrivCount specifies how to allocate noise between counters, and between relays using an operator model. But that might not be the best compromise model for Tor.
<+teor> (Maybe consensus weight or number of relays is better.)
<+teor> PrivCount also tries to justify the amount of client usage that's being protected, but it's not repeatable. We should probably measure actual client usage. (Which is circular!)
<+teor> The PrivCount configuration model isn't robust enough for a large number of relays
<+komlo> ^ that is a good takeaway 
<+teor> And researchers tend to shut down and redeploy new versions, rather than investing in mixed version deployment compatibility
<+teor> ^ another good takeaway
<+komlo> agreed, mixed versioning is always tricky :) 
<+komlo> ok this is all really helpful, quite a lot to think over 
<+teor> With PrivCount it's also tricky because the total noise across all statistics on all reporting relays determines user privacy
<+teor> And there's probably a few other things I've forgotten
<+komlo> right, trying to think about what a takeaway would be for how the deployment across the network matters for a single relay 
<+teor> Oh, with N relay partitions, we can resist N malicious or broken relays, but we probably need better resistance than that
<+komlo> i guess there wouldn't be a good incremental deployment option there? 
<+teor> I think the best option is to say that the noise budget is X, and each relay adds X*1/R to the noise, where R is the number of relays that support PrivCount in Tor
<+teor> (Technically it's X*sqrt(1/R), because noise standard deviation isn't additive.)
<+teor> With some minimum number of relays you need to get a report.
<+komlo> incremental deployment adds risk (which makes deploying it hard)? (to generalize)
<+teor> Yes, it means you have to think about minimum thresholds, and scaling
<+komlo> yeah that is tricky 
<+komlo> ok, this has been extremely helpful :) i'm going to go write notes and think about how to synthesize this, i'll send out notes after
<+teor> Oh, also, experimental PrivCount fails if any node fails. But PrivCount in Tor needs to work even if a significant fraction of the relays fail.
<+komlo> ^ omg
<+komlo> yes definitely! failure cases are very important!
<+teor> Researchers can usually repeat an experiment that fails. We can't really do that on the live tor network.
<+komlo> not exactly :)
<+teor> People expect Tor stats most days
<+komlo> signing off for the evening now- thanks for the great ideas/feedback, feel free to add more here, i'll read scrollback in the morning 
<+teor> No worries, I'll put notes on the wiki
<+teor> Also, part of scaling will be running a simulation of splitting the noise from 6000 relays, and working out if the integer truncation makes our noise too low
<+teor> Or we could just use ceil() to be safe.
<+teor> Anyway, lots of work to do!