Opened 7 years ago

Last modified 3 years ago

#9954 new defect

Replace broadcast voting protocol with something more robust

Reported by: nickm Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-dirauth robustness voting needs-proposal research-program
Cc: iang Actual Points:
Parent ID: Points:
Reviewer: Sponsor:


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.

Child Tickets

Change History (4)

comment:2 Changed 7 years ago by iang

Cc: iang added

comment:3 Changed 3 years ago by dgoulet

Keywords: tor-dirauth added; tor-auth removed

Turns out that tor-auth is for directory authority so make it clearer with tor-dirauth

comment:4 Changed 3 years ago by nickm

Keywords: robustness voting needs-proposal research-program added
Severity: Normal
Note: See TracTickets for help on using tickets.