[tor-bugs] #9954 [Tor]: Replace broadcast voting protocol with something more robust

[Tor Bug Tracker & Wiki]

#9954: Replace broadcast voting protocol with something more robust
----------------------+----------------------------------
 Reporter:  nickm     |          Owner:
     Type:  defect    |         Status:  new
 Priority:  normal    |      Milestone:  Tor: unspecified
Component:  Tor       |        Version:
 Keywords:  tor-auth  |  Actual Points:
Parent ID:            |         Points:
----------------------+----------------------------------
 While discussing #8244, Aniket Kate had some comments about our voting
 protocol:

 >The only modification I would like to suggest is to replace your
 broadcast protocol in the voting round. It is not secure against what is
 called "dangerous chain of failures" in distributed computing research ;
 i.e., if one authority crash in per sub-phase (1A, 1B, ...), then at least
 one working (or correct) authority might have more votes than others.
 >
 >To explain it, I am attaching Lorenzo Alvisi's (UT-Austin) notes along
 with email. I thought those will be easy to understand than a research
 paper. In these notes,
 > * Dangerous chain is explained on page 7
 > * Two protocols that overcome this (possibly extremely unlikely
 situation) problem are available on page 12
 > * I would encourage you to incorporate the early stopping protocol as,
 in absence of any failure, it completes in the exactly same manner as your
 current protocol. I think it will not add too much to your current
 broadcast code, but at the same time take care of gradual failures of
 directory authorities.
 > * The protocol description does not mention signatures as they are
 defined for non-malicious setting. Nevertheless, it will be easy for me to
 include signatures to the description at appropriate places if you choose
 to use it.

 I replied with:

 >I'll check this out, but I'm not sure whether the change is worth it in
 this case.  If I understand correctly, the failure mode here is no
 consensus is generated if crashes happen at exactly the wrong times, or
 sends votes to others at exactly the wrong times.  But our protocol can
 tolerate up to 24/48 hours worth of non-generated consensuses. (Our usual
 approach when this happens has been "Just debug it".)
 >
 >I'll check out the complexity of the stepping protocol, though.

 Still, more minds should think on this.

 I'm investigating whether I have permission to post Lorenzo Alvisi's
 slies, or whether they're already online.

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