Handle extreme values better in add_laplace_noise()

[teor]

We think it's impossible to get values this large, but we should still check for them and handle them appropriately.

[teor]

Please see my branch bug23523.

[nickm]

review-group-24 is now open.

[nickm]

The comment on get_max_safe_noise seems to be unfinished; get_min_safe_noise needs documentation.

Otherwise, looks okay to me, but you know the math here better than I do. Is there a math reviewer you'd recommend for the math changes, or shall we just merge it in once those comments are ready?

[teor]

Please see the fixups in my bug23523 branch, they:

• re-format a comment for style and line length, and remove a unicode character
• expand the comments on the new functions, use the correct integer type, and handle unusually large mantissa lengths
• add a missing semicolon

I would recommend catalyst as a reviewer, they are good with fiddly math. Or maybe isis?
(I am looking forward to a future where we can write code like this in a language that does its own integer checks, and has built-in saturating arithmetic functions.)

[teor]

(I also added a changes file to the branch)

[nickm]

setting owner

[catalyst]

I'm still looking over this. One thing that sticks out is that the comment in get_min_safe_noise() is inaccurate and caused me to misinterpret what it's actually doing on platforms with DBL_MANT_DIG less than 64. It might be more correct to say "This is always safe, because floating point numbers are sign-magnitude and the negation of an exact number is also exact."

[teor]

Replying to catalyst:

I'm still looking over this. One thing that sticks out is that the comment in get_min_safe_noise() is inaccurate and caused me to misinterpret what it's actually doing on platforms with DBL_MANT_DIG less than 64. It might be more correct to say "This is always safe, because floating point numbers are sign-magnitude and the negation of an exact number is also exact."

All the types here are int64_t.

But I agree the comment is confusing, particularly after I added a case that actually returns +/-INT64_MAX.

Let's change it to:

  tor_assert(get_max_safe_noise() >= 0);
  /* This is safe as long as get_max_safe_noise() is in 0..INT64_MAX, because -INT64_MAX..0 are representable as an int64_t. */
  return -get_max_safe_noise();

[teor]

Also, a close reading of the proof in section 5.2 of the paper [0] shows that it only applies up to 2⁴⁶, not 2⁵³.
So we need to define a constant and use that instead.
And I think we should error out on platforms that don't have mantissas of 2⁵³.

(How do we report numbers greater than 2⁴⁶?
We increase the sensitivity of the signal.
Practically, this means we multiply the final noise by a scaling factor 2^N, clear the N lowest bits of the signal, and add them together.
We have to clear the signal bits, otherwise signals of 0 are biased, because they only occur half as often.
This is what we tried to do by rounding the hidden service counts to the nearest figure, but it's not implemented correctly.)

[0]: ​https://pdfs.semanticscholar.org/2f2b/7a0d5000a31f7f0713a3d20919f9703c9876.pdf

[teor]

We should revise or close these tickets based on Appendix C in the latest privcount-shamir spec:

​https://github.com/teor2345/privcount_shamir/blob/noise-limits/doc/xxx-privcount-with-shamir.txt

The good news is that we probably don't need to care about extreme values or binning, because properly implemented noise has known limits, and doesn't need binning.

[teor]

Moving most of my assigned tickets to 0.3.4

[nickm]

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

[nickm]

These needs_revision, tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if somebody does the necessary revision.

[teor]

We should fix these issues by migrating these statistics to PrivCount in Tor.
See #25263 and its parents for details.