[tor-dev] Proposal draft: Better hidden service stats from Tor relays

[A. Johnson]

> This indeed seems plausible under the powerful assumption that the
> underlying stat is constant.

Actually it applies to any known relative pattern, for example, that the number increases by 1 each time.

> where the additive noise is applied to the center of the first bin?

Yes, you can look at it like that.

> I can see how this is better, since the underlying value gets
> immediately smoothed by binning. However, it does give me a weird
> hacky feeling...
> 
> Is this construction something that has been used before?

Well, the output here is a bin, not a number, and the “exponential mechanism” is the generalization of the Laplace mechanism to handle arbitrary output spaces (kunaltalwar.org/papers/expmech.pdf). In this case, I believe that adding Laplace noise to a bin center and then re-binning is a way to select according to the distribution that the exponential mechanism would prescribe.

Aaron