134-robust-voting.txt 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
  1. Filename: 134-robust-voting.txt
  2. Title: More robust consensus voting with diverse authority sets
  3. Author: Peter Palfrader
  4. Created: 2008-04-01
  5. Status: Accepted
  6. Target: 0.2.1.x
  7. Overview:
  8. A means to arrive at a valid directory consensus even when voters
  9. disagree on who is an authority.
  10. Motivation:
  11. Right now there are about five authoritative directory servers in the
  12. Tor network, tho this number is expected to rise to about 15 eventually.
  13. Adding a new authority requires synchronized action from all operators of
  14. directory authorities so that at any time during the update at least half of
  15. all authorities are running and agree on who is an authority. The latter
  16. requirement is there so that the authorities can arrive at a common
  17. consensus: Each authority builds the consensus based on the votes from
  18. all authorities it recognizes, and so a different set of recognized
  19. authorities will lead to a different consensus document.
  20. Objective:
  21. The modified voting procedure outlined in this proposal obsoletes the
  22. requirement for most authorities to exactly agree on the list of
  23. authorities.
  24. Proposal:
  25. The vote document each authority generates contains a list of
  26. authorities recognized by the generating authority. This will be
  27. a list of authority identity fingerprints.
  28. Authorities will accept votes from and serve/mirror votes also for
  29. authorities they do not recognize. (Votes contain the signing,
  30. authority key, and the certificate linking them so they can be
  31. verified even without knowing the authority beforehand.)
  32. Before building the consensus we will check which votes to use for
  33. building:
  34. 1) We build a directed graph of which authority/vote recognizes
  35. whom.
  36. 2) (Parts of the graph that aren't reachable, directly or
  37. indirectly, from any authorities we recognize can be discarded
  38. immediately.)
  39. 3) We find the largest fully connected subgraph.
  40. (Should there be more than one subgraph of the same size there
  41. needs to be some arbitrary ordering so we always pick the same.
  42. E.g. pick the one who has the smaller (XOR of all votes' digests)
  43. or something.)
  44. 4) If we are part of that subgraph, great. This is the list of
  45. votes we build our consensus with.
  46. 5) If we are not part of that subgraph, remove all the nodes that
  47. are part of it and go to 3.
  48. Using this procedure authorities that are updated to recognize a
  49. new authority will continue voting with the old group until a
  50. sufficient number has been updated to arrive at a consensus with
  51. the recently added authority.
  52. In fact, the old set of authorities will probably be voting among
  53. themselves until all but one has been updated to recognize the
  54. new authority. Then which set of votes is used for consensus
  55. building depends on which of the two equally large sets gets
  56. ordered before the other in step (3) above.
  57. It is necessary to continue with the process in (5) even if we
  58. are not in the largest subgraph. Otherwise one rogue authority
  59. could create a number of extra votes (by new authorities) so that
  60. everybody stops at 5 and no consensus is built, even tho it would
  61. be trusted by all clients.
  62. Anonymity Implications:
  63. The author does not believe this proposal to have anonymity
  64. implications.
  65. Possible Attacks/Open Issues/Some thinking required:
  66. Q: Can a number (less or exactly half) of the authorities cause an honest
  67. authority to vote for "their" consensus rather than the one that would
  68. result were all authorities taken into account?
  69. Q: Can a set of votes from external authorities, i.e of whom we trust either
  70. none or at least not all, cause us to change the set of consensus makers we
  71. pick?
  72. A: Yes, if other authorities decide they rather build a consensus with them
  73. then they'll be thrown out in step 3. But that's ok since those other
  74. authorities will never vote with us anyway.
  75. If we trust none of them then we throw them out even sooner, so no harm done.
  76. Q: Can this ever force us to build a consensus with authorities we do not
  77. recognize?
  78. A: No, we can never build a fully connected set with them in step 3.