TL;DR: Improvement of the above scheme using a variant of the TRIBES low-influence function. Leads to better results on the single validator influence, but the trade off with coalitions can clearly be seen.
One problem with my voting scheme above is the binomial distribution of the number of votes, making it very impractical. I thought the TRIBES function might be a better paradigm, and I think I at least got a practical result in terms of reducing single vote.
TRIBES: The TRIBES function for n voters divided into tribes of w consists of dividing the voters into n/w tribes of w voters each. Each tribe computes the AND of all the votes in the tribe, then the votes of all tribes are ORed. The resulting bit is the result of the TRIBES function.
In the case of the block end scheme above, the what we care about is whether a voter who has a positive vote can change the result from 1 to 0 by not submitting their vote. Not submitting a negative vote has no influence. TRIBES actually performs quite poorly in this, as is intuitively clear when you consider that a typical positive vote only has one tribe voting positively and then any of its voter can turn it into a negative one by not submitting their vote.
So instead, I consider the function ITRIBES: In this function each tribe of w members computes the OR of its votes, and then the AND of the votes from all tribes is computed. (This is in fact \neg TRIBES(\neg X).)
New voting construction: Using this, we consider this new voting scheme based on ITRIBES with parameters p_C, n, w
Each RANDAO block uniquely determines n voters as well as a split of these voters into n/w tribes of size w. All the n voters then publish their votes if positive (predetermined by the second hash onion above) and any voter who sees a positive vote coalition according to the ITRIBES function can publish an EPOCH END block.
The probability of a positive vote is then
\displaystyle p_\text{EPOCH END} = (1 - (1 - p_C)^w)^\frac{n}{w}
(assuming all nodes are honest and online)
Single voter influence: If a single voter has a positive vote, and the overall vote is positive, then the probability that holding back his vote will make the vote fail is
\displaystyle p_\text{Influence} = (1 - p) ^ {w - 1}
which is the probability that all other voters in the same tribe have a negative vote.
[The traditional single voter influence on the vote is: \text{Inf}_1 = (1 - p) ^ {w - 1} (1 - (1 - p_C)^w)^{\frac{n}{w} -1}, but I think p_\text{Influence} is the more important measure]
Coalition influence: Now, we can also compute the probability that a coalition of f validators can prevent a positive vote from happening by holding back their votes. Let’s consider tribe one only. Then, assuming that the vote of this tribe is positive, we can compute the probability that the coalition controls all the positive votes as
\displaystyle \theta = \frac{(1 - (1 - f)p)^w - (1 - p)^w}{1 - (1 - p)^w}
Then, if the overall vote is positive, the probability that the coalition controls at least one tribes positive vote is the probability that the total vote is controlled by the coalition:
\displaystyle p_\text{Coalition influence} = 1 - (1 - \theta)^\frac{n}{w}
Choosing the parameters: For a given p_\text{EPOCH END} and a number of voters n, we can choose the parameters p_C and w in many different ways. Of particular interest are two sets of parameters:
- We can optimize for minimal single voter influence p_\text{Influence}. This leads to values for p_C close to 1/2. I call these the “Influence optimised” values.
- We can optimize for coalition influence. In this case, we want fewer tribes and therefore a smaller p_C, to reduce the chance of the coalition controlling any single tribe. In the extreme this leads to w=n and p_C = p_\text{EPOCH END} / n, which is trivial, but minimises the chance of coalition influence (the probability of controlling a single voter is simply equal to f.
Results: Below are some results for p_\text{EPOCH END} = 0.1. I allowed w to be fractional to be able to perform optimisation on p_C while fixing p_\text{EPOCH END}. The “Average” optimisation simply halves the p_C from the Influence optimisation. p_\text{Coal} is the coalition influence for a coalition of size 0.05 of all validators, and “Coalition” refers to the coalition size required in order to get a 50% influence on the outcome of positive votes.
So far this confirms the suspicion that the trade off for reducing the influence of single validators is a (probably unacceptable) increase in the power of larger coalitions.
Optimization n w p_C p_EPOCH Inf1 p_Inf p_Coal Coalition Influence 20 2.58 0.409 0.100 0.059 0.435 0.221 0.129 Average 20 4.19 0.205 0.100 0.078 0.481 0.153 0.187 Influence 60 3.28 0.479 0.100 0.026 0.227 0.325 0.084 Average 60 5.86 0.239 0.100 0.033 0.265 0.221 0.128 Influence 100 3.63 0.501 0.100 0.017 0.161 0.376 0.071 Average 100 6.73 0.250 0.100 0.022 0.192 0.257 0.109 Influence 140 3.88 0.513 0.100 0.014 0.127 0.409 0.064 Average 140 7.34 0.256 0.100 0.017 0.153 0.281 0.099 Influence 180 4.06 0.520 0.100 0.011 0.106 0.434 0.060 Average 180 7.81 0.260 0.100 0.014 0.129 0.299 0.092 Influence 220 4.21 0.526 0.100 0.010 0.091 0.454 0.057 Average 220 8.19 0.263 0.100 0.012 0.111 0.314 0.087 Influence 260 4.34 0.530 0.100 0.008 0.080 0.470 0.054 Average 260 8.52 0.265 0.100 0.011 0.099 0.327 0.083 Influence 300 4.45 0.533 0.100 0.007 0.072 0.484 0.052 Average 300 8.80 0.267 0.100 0.010 0.089 0.337 0.080 Influence 340 4.55 0.536 0.100 0.007 0.065 0.496 0.051 Average 340 9.05 0.268 0.100 0.009 0.081 0.347 0.078 Influence 380 4.64 0.539 0.100 0.006 0.060 0.506 0.049 Average 380 9.27 0.269 0.100 0.008 0.075 0.355 0.076 Influence 420 4.72 0.541 0.100 0.006 0.056 0.516 0.048 Average 420 9.47 0.270 0.100 0.007 0.069 0.363 0.074 Influence 460 4.79 0.542 0.100 0.005 0.052 0.524 0.047 Average 460 9.65 0.271 0.100 0.007 0.065 0.370 0.072