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

[Karsten Loesing]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/12/14 20:20, A. Johnson wrote:
>> 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.

Still a very powerful assumption given the stats we're gathering.

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

I see the value in switching algorithms and doing the binning step
before adding noise.

But I don't see the value of binning the result once more.  In a
sense, we're already binning signal + noise by cutting off the float
part.  I don't see what we gain by reducing resolution even more.  It
seems just unnecessary.

Example:

 - We observe 123 things.
 - We round up to the next multiple of 8, so to 128.
 - We add Laplace noise -12.3456, obtain 110.6544, round down to 110.
 - Why would we round up to the next multiple of 8 again, to 112?

It should be equally hard to infer the 128 value from 110 with bin
size 1 or 112 with bin size 8.  Unless I'm wrong.  Please prove me
wrong? :)

For now, I'm going to switch algorithm order in the code and not add a
second binning step.

All the best,
Karsten
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: GPGTools - http://gpgtools.org

iQEcBAEBAgAGBQJUiBUMAAoJEJd5OEYhk8hIw3MH/RIQWeN+MQalG/NWovKqiFiA
/+FsEI/tGjzptnjPtYebHzrmor4xr1ZA3sdZA06MH887wypZY3+Gp47kTZYwIybD
ytfqjHJa/nItgPORvjp4ILsvJ+7KIq563ovMxLz0ZsrLmlUARluO2Ri53HrIulEA
attFlg98UzLht+UrYhOL/EdZXGVhOd3yuZg+PcFz1zxuYZZszH/6zjYu0oordVwG
VnujgzSp9/7ggQahn/3grhpEbiNI6pDNi+pcGOu3VsbccCLn1gFJHglhK+HM70tx
zhMwRzFRay+KFm7bgtXNPQkt7hvdckl9I3aSUQyx+Xwx5ylSCIgs4XK/QJ8xdNM=
=NE+w
-----END PGP SIGNATURE-----