[tor-bugs] #13339 [Core Tor/Tor]: Prop140: Complete Consensus diffs / Merge GSoC project

[Tor Bug Tracker & Wiki]

#13339: Prop140: Complete Consensus diffs / Merge GSoC project
-------------------------------------------------+-------------------------
 Reporter:  mvdan                                |          Owner:  nickm
     Type:  enhancement                          |         Status:
                                                 |  assigned
 Priority:  High                                 |      Milestone:  Tor:
                                                 |  0.3.1.x-final
Component:  Core Tor/Tor                         |        Version:  Tor:
                                                 |  0.2.7
 Severity:  Normal                               |     Resolution:
 Keywords:  gsoc, merge, tor-client, prop140,    |  Actual Points:
  027-triaged-1-in, 028-triaged, pre028-patch,   |
  tor-dos, low-bandwidth, nickm-                 |
  deferred-20160905, tor-03-unspecified-201612,  |
  sponsor4, TorCoreTeam201703                    |
Parent ID:                                       |         Points:  parent
 Reviewer:                                       |        Sponsor:
                                                 |  Sponsor4
-------------------------------------------------+-------------------------

Comment (by mvdan):

 Hi Sebastian,

 I had to re-read my own docs because I completely forgot what
 calc_changes() even was :)

 > According to the documentation of calc_changes() I would think that the
 proper result would be unchanged, changed, unchanged, changed.

 Admitting that I don't fully remember how this thing worked, I think
 you're assuming too much.

 For example, having [a a a a] and [a b a b], and the bits [0 1 1 0] and [0
 1 0 1], what we will do is:

 * change the second and third elements [a a] with [b]: [a b a]
 * add a fourth element [b]: [a b a b]

 The ed diff, if I recall correctly, should be something like (doing this
 in my head, so could be wrong):

     1,2cb
     .
     3ab
     .

 I understand you were expecting the bits to be [0 1 0 1] and [0 1 0 1].
 Then, the diff would be something like:

     2cb
     .
     4cb
     .

 Note that the two are valid. Yours is a bit smaller as far as bytes used,
 but it's still the same number of operations.

 If I remember correctly, calc_changes optimizes for number of lines
 added/deleted in the diff, not for the size of the ed diff. This is
 because it doesn't do an ed diff at all - it is done at a higher level, in
 a func that calls it. It ended up with this result just like it could have
 ended with yours - both mean four lines changed (deleted+added) in total.
 In other words, the number of bits set to "1" across both bit vectors is
 4.

 Perhaps a way to get slightly smaller ed diffs would be to get
 calc_changes to prefer the operator 'c' over 'a' and 'd'. But remember
 that this operation should only be used in very small pieces of the
 consensus, so I don't expect you'd be saving much at the cost of
 complexity.

 So TL;DR: the expected values are correct. Not the smallest ed diff nor
 the one that a human would do, but one that is almost as small.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/13339#comment:56>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online