Replace broadcast voting protocol with something more robust
While discussing #8244 (moved), 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.