We want to find suitable transition rules in the ‘‘colored FPC’’ voting scheme. Here we analyze the case of finitely many colors, however, the protocol can be generalized to infinitely many. Consider a network with N participants and \{c_i\}_{i \in I} colors. Assume further that there is a dRNG and r is the random number (RN) produced for the current round. We can use r to produce a deterministic (the same for all network participants) ‘‘thresholds’’ for a given color. For example, using
\tau_i = Hash(r + c_i).
Thresholds can be required to be an element of any interval, e.g. [1/3; 2/3]. Due to the common RN r any node that sees the same color c_i will apply the same threshold.
Assume that during the query a node obtained n_i votes for color c_i. Then in the next round, the node will vote for the color which maximizes the score
s_i = \frac{n_i}{\tau_i}.
Note that for two colors in the presented system, the transition rule reduces to standard FPC (with the threshold satisfying: \tau = \tau_1 /(\tau_1 +\tau_2)).
We hope that the presented protocol converges fast and inherits berserk resilience of standard FPC. However, to confirm that we require simulation results.
It might be worth noting that for c_2 the majority rule is then based on \tau_2^*=1-\tau, and that if n_1 and n_2 are normalized, the color gets accepted that achives a score above 1, e.g. n_1>\tau\rightarrow s_1>1 .
Generally it might be useful to normalize the thresholds and votes, i.e. \sum_i{\tau_i}=1=\sum_i{n_i}. then in order for any color to be acceptable the score needs to be above 1. However, in this case still multiple colors may have a score above 1.
After the discussion with @mthcl he suggested that option ‘I choose neither’ should be allowed to spontaneously arise from the system which is split for too long. So here is a modification of the protocol.
Assume that the color c_0 is a special color (from our point of view it is a vote for ‘I choose neither’). This color can be chosen from the very beginning (for example if network participant receives two double spends too close in time). However, if none of the other colors is getting a majority for a long time we should allow it to spontaneously pop up (even if none of the nodes at the moment holds this opinion)
so we update the score function of color c_0 to the form
Where function f: \mathbb{N} \rightarrow \mathbb{R}_+ is strictly increasing function and j is the number of around node votes on particular conflict. k is a number of votes obtained in the current and the function \mathbf{1}_{k/2 > max\{n_i\}} is an indicator. This Indicator takes a value of 0 when max\{n_i\} >k/2 i.e.: certain opinion has the 50\% majority. Otherwise it is 1.
This might indeed work for the abstract colored-FPC scheme with a fixed number of colors (assuming that node picks the opinion which maximizes the score). However, in the tangle where the number of colors is not fixed the protocol might be attackable. The malicious actor may influence the voting outcome by spamming the conflicts. When the attacker broadcasts them to different parts of the network users may end up with different \sum_i \tau_i (some network participants see more colors than others).
I think FPC should still work if the scores are approximately the same. If there are many conflicts \sum_i \tau_i should be similar even if some of the nodes are missing some txs.
This seems to be necessary. If \tau_i would not be mapped to a value far enough away from 0, the score s_i can become very large considering similar values of n_i.