Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  assigned
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.4.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 029-backport, 026-backport-  |
  maybe  |
Parent ID:  #25263   | Points:  0.5
 Reviewer:   |Sponsor:
 |  SponsorQ-can
-+-
Changes (by teor):

 * parent:  #23061 => #25263


--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  assigned
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.3.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
 |  SponsorQ-can
-+-
Changes (by nickm):

 * sponsor:   => SponsorQ-can


--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  assigned
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.3.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * milestone:  Tor: 0.3.2.x-final => Tor: 0.3.3.x-final


Comment:

 This can wait until 0.3.3

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (by yawning):

 Produces random values in the range `(-1.0, 1.0)`, with similar semantics
 to my other routine.  Timing characteristics depend on how `copysign()` is
 implemented, though I expect most libms to use bit twiddling of some sort.

 {{{
 double
 uint64_to_dbl_neg1_1(uint64_t x) {
 #if DBL_MANT_DIG > 63
 #error System double mantissa is unexpectedly large.
 #endif
   return copysign(uint64_to_dbl_0_1(x), 0.0 - (x >> 63));
 }
 }}}

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (by teor):

 That works, too: it costs us another random double function, but saves us
 an argument, and some complexity in the callers. Want to write the patch,
 or should I?

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (by catalyst):

 I meant that the new function would exclude -1.0 and +1.0, so `1 -
 fabs(x)` would still be nonzero.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  needs_review => needs_revision


Comment:

 Replying to [comment:3 catalyst]:
 > Wouldn't it be better to have a function that outputs a random double in
 (-1.0, +1.0)?  If you're only using 53 bits of entropy from a RNG call
 that generates 64, there are spare bits to use for generating the sign.

 sample_laplace_distribution() takes the log of a strictly positive
 floating point number, and then applies a random sign.

 We could use sgn() and abs() to decompose `[-1.0, 1.0]` into `{+, -}` and
 `[0.0, 1.0]`, but we'd still have to reject `0.0` before doing the log,
 and then apply the sign. So it seems more complex than the alternative.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_review
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (by catalyst):

 Wouldn't it be better to have a function that outputs a random double in
 (-1.0, +1.0)?  If you're only using 53 bits of entropy from a RNG call
 that generates 64, there are spare bits to use for generating the sign.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_review
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (by nickm):

 Should this be in needs_review? I see a suggestion for writing a patch,
 but I don't see the actual patch itself.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:
 |  needs_review
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.8.1-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  new => needs_review


Old description:

> Currently, sample_laplace_distribution() takes a random double as input,
> and then extracts the following random values:
> * a random sign
> * a random value in (0.0, 1.0]
>
> This reduces the precision of the result. For details, see:
> https://trac.torproject.org/projects/tor/ticket/23061#comment:32
>
> Instead, the function could take a random boolean sign and p, and the
> transform becomes:
> {{
> result = mu - b * (sign ? 1.0 : -1.0)
> * tor_mathlog(1.0 - p);
> }}
>
> This would increase the precision by one bit, plus whatever precision is
> lost in `2.0 * fabs(p - 0.5)`.
>
> This may have been introduced in dad5eb7.

New description:

 Currently, sample_laplace_distribution() takes a random double as input,
 and then extracts the following random values:
 * a random sign
 * a random value in (0.0, 1.0]

 This reduces the precision of the result. For details, see:
 https://trac.torproject.org/projects/tor/ticket/23061#comment:32

 Instead, the function could take a random boolean sign and p, and the
 transform becomes:
 {{{
 result = mu - b * (sign ? 1.0 : -1.0)
 * tor_mathlog(1.0 - p);
 }}}

 This would increase the precision by one bit, plus whatever precision is
 lost in `2.0 * fabs(p - 0.5)`.

 This may have been introduced in dad5eb7.

--

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

[tor-bugs] #23415 [Core Tor/Tor]: sample_laplace_distribution() should take multiple random inputs

[Tor Bug Tracker & Wiki]

#23415: sample_laplace_distribution() should take multiple random inputs
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor: 0.3.2.x-final
Component:  Core |Version:  Tor: 0.2.8.1-alpha
  Tor/Tor|   Keywords:  tor-relay, security-low, privcount,
 Severity:  Normal   |  031-backport, 030-backport, 029-backport, 028
 |  -backport-maybe, 026-backport-maybe
Actual Points:   |  Parent ID:  #23061
   Points:  0.5  |   Reviewer:
  Sponsor:   |
-+-
 Currently, sample_laplace_distribution() takes a random double as input,
 and then extracts the following random values:
 * a random sign
 * a random value in (0.0, 1.0]

 This reduces the precision of the result. For details, see:
 https://trac.torproject.org/projects/tor/ticket/23061#comment:32

 Instead, the function could take a random boolean sign and p, and the
 transform becomes:
 {{
 result = mu - b * (sign ? 1.0 : -1.0)
 * tor_mathlog(1.0 - p);
 }}

 This would increase the precision by one bit, plus whatever precision is
 lost in `2.0 * fabs(p - 0.5)`.

 This may have been introduced in dad5eb7.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs