Making the RANDAO less influenceable using a random 1 bit clock

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:

  1. 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.
  2. 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

Possible follow-ups:

  1. We can probably explore if the “voters” above can be the same as the attesters (Attestation committee based full PoS chains, version 2).
  2. There should be an easy way of generating this vote based on a vdf, such that the influence of single votes can only be known when the vdf output is known. That could potentially greatly reduce the influence of knowing the vdf early.