00/ Abstract

We formulate a stake-based consensus problem in terms of a two-player game and propose a protagonist consensus policy to optimize a Nash equilibrium via a weight reduction algorithm with a guarantee of minority stake deterioration. We generalize this to a two-team game and propose a smooth density evolution algorithm that outperforms coarser estimates. We perform a full-scale Monte Carlo analysis and confirm the accuracy of our theoretical results, and show the possibility of a 40% stake + 25% utility attack. The result is a variable-expense consensus algorithm that can be fit to blockchain compute constraints to reach accurate consensus in adversarial settings.

01/ Stake-based weight consensus

1.1 Problem definition

We consider a two-player game between (protagonist) honest stake$\ 0.5< s_{H} \le 1 \:$ and (adversarial) cabal stake ($\ 1 - s_{H} \:$) competing for total fixed reward $\ e_H + e_C = 1 \:$with honest emission $\ e_{H}$ and cabal emission $\ e_{C}$, respectively, followed by stake updates $\ s^{\prime}_{H}= \frac{{s_{H} + e_{H}}}{2} \:$ and $\ s^{\prime}_{C}= \frac{{1 - s_{H}+e_{C}}}{2} \:$. The honest objective $\ s_{H} \le e_{H} \:$ at least retains scoring power $\ s_{H}$ over all action transitions in the game, otherwise when $\ e_{H} \le s_{H} \:$ honest emission will erode to 0 over time, despite a starting condition of $\ 0.5 < s_{H}$.

We assume honest stake sets objectively correct weights $\ w_{H} \:$ on itself, and $\ 1 - w_{H} \:$ on the cabal, where honest weight$\ w_{H} \:$represents an ongoing expense of the honest player, sustained throughout the game. However, cabal stake has an action policy that freely sets weight $\ w_{C} \:$ on itself, and $\ 1 - w_{C} \:$ on the honest player, at no cost to the cabal player, with the objective to maximize the required honest self-weight expense $\ w_{H} \:$ via$\ w_{C}^{*}=\arg \max_{w_{C}}E[w_H| \;s_{H}=e_{H}(s_{H},w_{H},w_{C})] \:$.

We then assume the honest majority $\ s_{H}>0.5 \:$ can counter with a consensus policy $\ \pi \:$allowed to modify all weights modulo player labels, so it is purely based on the anonymous weight distribution itself, optimizing the Nash equilibrium $\ min_{\pi}\max_{w_{C}}E[w_{H}\;|\;s_{H}=e_{H}(s_{H},\pi(\mathbf{w}))]\:$.

The majority stake enforces an independent and anonymous consensus policy $\ \pi \:$(e.g. through a blockchain solution) that modifies the weights to minimize the expense $\ w_{H} \:$, which has been maximized by the cabal applying an objectively incorrect gratis self-weight $\ w_{C} \:$. Consensus aims to produce $\ \pi( \mathbf{w}) \rightarrow (w^{ \prime}_{H}, w^{\prime}_{C}) \:$ so that $\ w^{\prime}_{C}=1-w^{\prime}_{H} \:$, by correcting the error $\ \epsilon=w^{\prime}_C+w^{\prime}_H-1>0$. Note that the input cost $\ w_{H} \:$ remains fully expensed, and that $\ w^{\prime}_{H} \:$ merely modifies the reward distribution that follows, but not knowing which players are honest or cabal (anonymous property).

Figure 1 / Selfish weighting problem: Minority cabal sets $\ w_{C}=1 \:$ self-weight to maximally grow its relative stake, e.g. at (`1) honest majority stake of $\ s_{H}=0.6 \:$ and honest utility of $\ w_{H}=0.75 \:$ would require cabal to report self-weight $\ w_{C}<0.62 \:$ for honest stake to be retained. (b) Consensus solution: Stake-based consensus $\ \eta=3 \:$ corrects excessive self-weight of minority stake, e.g. at (`2) $\ s_{H}=0.6 \:$ , $\ w_{H}=0.75 \:$ no selfish cabal weight can prevent honest stake retention, even $\ w_{C}=1 \:$ results in honest stake ratio gain. Zero-weight problem: Minority cabal is virtually the only scoring incentive recipient of the cabal utility reward when its actual utility is near-zero, e.g. at (`3) where honest stake deteriorates. (c) Weight trust solution: Require the majority stake to agree that a weight is non-zero, otherwise smoothly nullify the associated reward to the degree of mistrust, which then removes the honest stake deterioration region when $\ w_{H}>0.95 \:$. Consensus guarantee: Honest majority stake is retained when $\ s_{H}\ge 0.6 \:$ and $\ w_{H}\ge 0.75 \:$, despite strategic cabal weight setting.

Figure 2 / Retention line interpretation: (a) Honest incentive share contour plot for $\ s_{H}=0.6 \:$only, highlighting where the emission is $\ e_{H}=0.6 \:$, e.g. at (`1). However, at (`2) the contour recedes again due to the zero-weight problem. (b) Similarly, the specific emission contour plot for $\ s_{H}=0.7 \:$, highlighting the contour where the emission is $\ e_{H}=0.7 \:$, which means with inflation the honest share ratio of $\ s_{H}=0.7 \:$ can be retained if honest utility is at least $\ w_{H}>0.75 \:$ like at (`3). (c) Retention lines: A compound plot combines all the highlighted $\ s_{H}=e_{H} \:$contours from individual contour plots (e.g. $\ s_{H}=0.6 \ and \ s_{H}=0.7$), to show the overall retention profile. Generally, the higher the honest stake, the higher the honest utility requirement to retain stake proportion under adversarial weight setting.

Figure 3 / Scoring incentive: A percentage share of the utility rewards equal to stake in a score, as incentive to encourage honest scoring. (a) No scoring incentive leads to extreme selfish weight setting, since the cabal does not share in the honest rewards. (b)-(f) Higher scoring incentive reduces selfishness evidenced by receding honest self-weight requirement for stake retention. However, the zero-weight problem at (`1) increases as well, since only the cabal can claim reward share from both honest and cabal subsets while honest sets zero weight on the cabal. The weight trust solution with smooth edge coverage $\ w_{H}>0.95) \:$ can only be extended so far before legitimate low-utility is also nullified, which practically limits scoring incentive around 50%.

1.2 Reward emission

In the two-player characterization of the game, there are two bimodal weight distributions of $\ (w_{H},\; 1-w_{C}) \:$ and $\ (1-w_{H}, w_{C}) \:$ on the honest and cabal players, respectively. The stake proportions behind the bimodal distributions are $\ (b_{HH}, \ b_{CH})=(w_Hs_H, \ (1-w_{C})(1-s_{H})) \:$ and$\ (b_{HC}, \ b_{CC})=((1-w_{H})s_{H}, \ w_{C}(1-s_{H})) \:$ , respectively.

Primary incentive $i$ is the normalized sum of stake proportions, where honest rank $\ r_{H}=w_{H} s_{H}+(1-w_{C})(1-s_{H}) \:$ and cabal rank $\ r_{C}=(1-w_{H})s_{H}+w_{C}(1-s_{H}) \:$ are normalized to give $\ i_{H}=\frac{r_{H}}{r_{H}+r_{C}} \:$ and $\ i_{C}= \frac{r_{C}}{r_{H}+r_{C}} \:$ . An additional reward $d$ is the scoring share of incentive, i.e. $\ d_{H}=\frac{w_{H} s_{H}}{r_{H}}i_{H}+\frac{(1-w_{H})s_{H}}{r_{C}}i_{C} \:$ and$\ d_{C}=\frac{(1-w_{C})s_{C}}{r_{H}}i_{H}+\frac{w_{C}s_{C}}{r_{C}}i_{C} \:$. Finally, the complete reward emissions are$\ e_{H}=\frac{i_{H}+d_{H}}{2}$ and $\ e_{C}=\frac{i_{C}+d_{C}}{2} \:$, such that $\ e_{H}+e_{C}=1 \:$ .

Figure 4 / Larger minority excess: The excess weight above consensus is larger for minority-stake when $\ w_{H}<w_{C} \:$. (a) Positive contours when $\ w_{H}<w_{C} \:$ at (`1) indicate regions of cabal error-correction potential. (b) Cabal error-correction region grows as majority stake increases $\ s_{H}=0.55\rightarrow 0.95 \:$. (c) However at (`2), larger majority excess appears on the right-side when $\ w_{C}<w_{H} \:$(to be avoided), which negatively impacts the majority weight more than the minority.

1.3 Consensus deviation

The weight consensus is the stake-proportion weight average$\ \overline{w_{j}} = \sum_i(s_{i} w_{ij})w_{ij} / \sum_k(s_{k} w_{kj})\:$, and accordingly the consensus weights for the honest and cabal players are
$\ \overline{w_{H}}=\frac{s_{H} w_{H}^2 + (1-s_{H})(1-w_{C})^2}{s_{H} w_{H} + (1-s_{H})(1-w_{C})} \:$ and ,
$\ \overline{w_{C}}=\frac{s_{H} (1-w_{H})^2 + (1-s_{H})w_{C}^2}{s_{H} (1-w_{H}) + (1-s_{H})w_{C}} \:$ respectively

Under typical adversarial play with $\ 1-w_{H}<w_{C} \:$ , the upper modes $\ w_{H}> \overline{w_{H}} \:$ and $\ w_{C}> \overline{w_{C}} \:$ of the honest and cabal weight distributions, respectively, will exceed the consensus. Honest excess $\ \overline{w_{H}}<w_{H} \:$ is present when $\ 1-w_{C}<w_{H}: \:$

Similarly, $\ 1-w_{H}<w_{C} \:$ produces cabal excess $\ \overline{w_{C}}<w_{C} \:$ :

Lemma 1 (Larger Minority Excess). Minority-stake excess weight is larger than majority-stake excess weight, i.e.$\ w_{C} - \overline{w_{C}} > w_{H} - \overline{w_{H}}, \ when \ w_{H} < w_{C} \:$

We use a symbolic solver (Wolfram) to show that the cabal excess is larger when $\ w_{H} < w_{C}, \:$ i.e.
$\ \frac{dw_{C}}{dw_{H}}=\frac{w_{C}-\overline{w_{C}}}{w_{H}-\overline{w_{H}}} > 1 \:$
The cabal excess is larger with majority honest stake when

Otherwise, for the following conditions

Otherwise, for the following conditions

1.4 Excess weight reduction

Stake-proportional consensus advantages the honest player with $\ s_{H}>0.5 \:$ , since it biases the consensus weight toward the honest vote and exposes the cabal excess self-weight$\ w_{C} > \overline{w_{C}} \:$ where $\ dw_{C}>dw_{H} \:$ . Consequently, a consensus policy $\ \pi(\mathbf{w})=\min(\overline{\mathbf{w}}, \mathbf{w}) \:$ can reduce excess weight above the consensus$\ \overline{\mathbf{w}} \:$ , where cabal weight should decrease more than honest weight. The weight reductions normally only happen in the upper modes $\ w_{H} \:$ and $\ w_{C} \:$ of the honest and cabal weights, respectively.

Figure 5 / Larger minority excess: The excess weight above consensus is larger for minority-stake when $\ w_{H}<w_{C} \:$. (a) Positive contours when $\ w_{H}<w_{C} \:$ at (`1) indicate regions of cabal error-correction potential. (b) Cabal error-correction region grows as majority stake increases $\ s_{H}=0.55\rightarrow 0.95 \:$. (c) However at (`2), larger majority excess appears on the right-side when $\ w_{C}<w_{H} \:$(to be avoided), which negatively impacts the majority weight more than the minority.

The consensus policy $\ \pi(\mathbf{w})\rightarrow (w^{\prime}_{H}, w^{\prime}_{C}) \:$ attempts to correct the error $\ \epsilon=w_{H}+w_{C}-1 \:$ so that

The approximate number of weight reduction steps is $\ \eta \:$, and the consensus policy is thus converted to an iterated function $\ \pi=f^{\eta} \:$ , where the function is repeated $\ \eta \:$ times $\ f^3(\mathbf{w})=f(f(f(\mathbf{w}))) \:$ . Note that$\ f(\mathbf{w})=\min(\overline{\mathbf{w}}, \mathbf{w}) \:$ recomputes the consensus weight $\ \overline{\mathbf{w}} \:$ each time.

Figure 6 / Emission slashing: Iterative weight correction reduces effective scoring weight and incentive share. (a) Initial scoring weight is always 1, but weight correction reduces this whenever $\ \sum w\neq 1 \:$, with the largest reduction seen at (`1). (b) Emission is the average of scoring incentive and utility reward and cabal emission is slashed, i.e. $\ e^{(\eta=3)} < e^{(\eta=0)} \:$ particularly in the $\ w_{H}<w_{C} \:$ and $\ 0.5<s_{H} \:$ region around (`2). (c) Consequently, honest emission is boosted in region (`2), but the zero weight vulnerability at (`3) slashes honest emission, although comparatively little.

Figure 7 / Cabal slash (two-team). (a) Statistical analysis simplifies the two-player result. (b) The two-team generalization fully enacts the weight distribution, and a Monte Carlo analysis reveals the worst-case cabal slash closely following the two-player result. (c) Cabal incentive is boosted at the zero weight vulnerability of (`1), but weight trust solution ensures active cabal slash at (`2).

We compute $\ \eta = \frac{w_{H} + w_{C} - 1}{d w_{H} + d w_{C}} \:$ and compare with the correction factor$\ dw_{C}/dw_{H} \:$ to identify the optimal $\ \eta \:$ avoiding over-correction in the detrimental$\ w_{C}<w_{H} \:$ region where $\ dw_{C}/dw_{H}<1 \:$

We observe that higher $\ \eta>3 \:$ values extend the correction further into the detrimental$\ w_{C}<w_{H} \:$ region where $\ dw_{C} - dw_{H} < 0 \:$ , hence an optimal $\ \eta\approx 3 \:$ is identified, which is large enough to provide sufficient correction when $\ w_{H}<w_{C} \:$ .

Application of the consensus policy $\ \pi(\mathbf{w})=f^{\eta\approx 3}(\mathbf{w}) \:$ can partially correct the error $\ \epsilon=w^{\prime}_{C}+w^{\prime}_{H}-1>0 \:$ , in particular the previous expense $\ w_{H}=1 \:$ is reduced to $\ w_{H}<0.75 \:$ for $\ s_{H}=0.6 \:$ , even at Nash equilibrium with $\ w_C^{*}=0.8 \:$ . Importantly, the consensus policy $\ \pi(\mathbf{w}) \:$ operates on anonymized weights and do not assume the player identities, thus behaves impartially in terms of a stake-based consensus.

1.5 Smoothed weight reduction

The correction function $\ f(\mathbf{w})=\min(\overline{\mathbf{w}}, \mathbf{w}) \:$ should be smoothed to ensure$\ \lim_{dw\rightarrow 0}f^{\eta}(w+dw) - f^{\eta}(w)<\varepsilon \:$ where adjacent weights are corrected to a similar degree. The correction factor should also depend on the magnitude of deviation from consensus, in terms of a standard deviation $\sigma$. We opt for a stake-weighted mean absolute deviation, since it does not make the normal assumption as strongly as mean square deviation, as follows

The standard correction $\ 0 \le \alpha<1 \:$ fully applies when$\ w - \overline{\mathbf{w}}=\sigma(\mathbf{w}) \:$, and amplifies when$\ w - \overline{\mathbf{w}}>\sigma(\mathbf{w}) \:$ to a maximum correction at$\ \overline{\mathbf{w}} \:$ with a proposed smoothed function iterate

Figure 8 / Weight trust: Majority stake should set non-zero weight to a player, otherwise its reward is nullified. (a) Two-team honest emission with just the consensus policy, with zero weight vulnerability at (`1). (b) Applying weight trust protects the $\ 0.95<w_{H} \:$ region and removes the exploit. (c) Honest retention is now monotonically possible at increasing honest self-weight.

The smoothed function iterate now requires more steps, where a larger $\ \alpha\approx 1-\delta \:$results in a larger $\ \eta \:$ , such that $\ \eta\delta\approx 3 \:$ , according to

We compare the previous retention graph $\ (\eta=3, \alpha=0) \:$against $\ (\eta=3/(1-0.95), \alpha=0.95) \:$ and observe a reduced cost $\ w_{H}=0.7<0.75 \:$with the smoothed iterate with $\ \alpha>0 \:$.

We ensure monotonicity of the consensus policy by choosing the minimum $\ \varepsilon>0 \:$added to the deviation $\ \sigma(\mathbf{w}) \:$.

1.6 Weight trust

Weight trust $\ T=(W>0)S \:$ is the sum of stake assigning a non-zero weight to a player, and a consensus$\ C=(1 + \exp(-\rho(T-\kappa)))^{-1} \:$ provides a smooth threshold at $\kappa$ where exceeding$\kappa$ ratio of stake quickly allows for high trust. A modified rank$\ r^{\prime}=rc \:$ multiplies rank with the weight trust consensus, which influences the emission so that zero cabal weight $\ w^{\prime}_{C}=1-w_{H}\approx 0 \:$ receives low consensus thereby penalizing cabal emissions.

The vulnerable region of $\ w_{H}=1 \:$ and $\ 0.8<w_{C}<0.95 \:$allows for cabal stake gain when $\ s_{H}=0.6 \:$, but the weight trust consensus smoothly pads the region around$\ w_{H}=1 \:$ and removes the vulnerability. The cabal can thus not claim reward when the honest majority deems cabal utility to be zero, despite the non-zero self-weight reported by the minority cabal.

Figure 9 / Evolution smoothness: Evolving through more smaller steps with$\ \eta=59 \:$ reduces the zero weight exploit at black (`3), compared to $\ \eta=3 \:$ at (`1), since fine-grained correction steps more accurately track changes in consensus. The two-team honest emissions (Monte Carlo worst-case analysis) tend to further reduce the zero weight exploits at (`2), (`4) compared to the two-player case at (`1), (`3).

02/ Density generalization

2.1 Overview

We generalize the two-player game to a two-team game with $\ |H| \:$ honest and $\ |C| \:$ cabal players, that have $\ \sum_{i\in H}s_{i}=s_{H} \:$ honest stake and $\ \sum_{i\in C}s_{i}=1-s_{H} \:$ cabal stake. Honest players $\ i\in H \:$ set $\ \sum_{j\in H}w_{ij}=w_{H} \:$ self-weight and $\ \sum_{j\in C}w_{ij}=1-w_{H} \:$ weight on cabal players, while cabal players $\ i\in C \:$ set $\ \sum_{j\in C}w_{ij}=w_{C} \:$ self-weight and $\ \sum_{j\in H}w_{ij}=1-w_{C} \:$weight on honest players. The rank components result in the same aggregates in the two-player game.

In particular, the weight consensus of an individual honest player is shown to be $\ \overline{w_{h}}=\frac{\overline{w_{H}}}{|H|} \:$ as follows (and similarly for cabal players $\ \overline{w_{c}}=\frac{\overline{w_{C}}}{|C|} \:$)

Under the minimal assumption that the average self-weights set on honest and cabal players are$\ \frac{w_{H}}{|H|} \:$ and $\ \frac{w_{C}}{|C|} \:$ we can construct weight densities$\ p_h(w) = p_{hh}(w) + p_{ch}(w) \:$ and $\ p_{c}(w) = p_{hc}(w) + p_{cc}(w) \:$, here according to the normal assumption (other densities with a similar first moment could possibly also be valid)

The consensus and mean absolute deviations of a weight density function $\ p(w) \:$ are

We overload the iterated function $\ f \:$ as a density evolution function $\ f(p(w)) \:$ that contracts a density$\ p(w) \:$ above consensus$\ \overline{p} \:$ by a nominal degree of $\ \alpha \:$ at a single deviation $\ \frac{w-\overline{p}}{\sigma(p)} \:$, in order to correct the error $\ \epsilon=w_{H}+w_{C}-1 \:$. The density is contracted via $\ g(w)=f^{-1}(w) \:$involving the original iterated function $\ f \:$.

The final rank after applying the consensus policy $\ \pi=f^{\eta} \:$ is $\ r_{i} = \int f^{\eta}(p_{i}(w))dw \:$, where a single function iteration contracts the consensus by $\ \overline{p^{\prime}}-\overline{p} \:$, which is equal to

Figure 10 / Density evolution: Weight correction through density evolution reduces cabal weight consensus more than honest reduction $\ (s_{H}=0.6, w_{H}=0.7, w_{C}=0.8) \:$ . The honest weights and cabal weights have an equal starting consensus at (`1), but through density evolution the cabal reduces more to (`3), versus a higher end honest consensus at (`2). Density evolution thus succeeds in penalizing the minority cabal and allows for honest stake retention. The theoretical probability densities in (a), (c) closely match the stochastically sampled results in (b), (d). The crosshair markers indicate the consensus flanked by a standard deviation above and below.

Simulating the consensus policy $\ (\eta=3/(1-0.95), \alpha=0.95) \:$ on weight densities set on honest and cabal players where $\ s_{H}=0.6, w_{H}=0.7, w_{C}=0.8 \:$, we see an equal starting consensus weight reduce further for the cabal players $\ (6.76\rightarrow 3.8) \:$ vs honest players $\ (6.76\rightarrow 4.41) \:$. The consensus policy acts as an upper-mode resiliency test where cabal self-weight with minority stake fails comparatively to honest self-weight with majority stake.

2.2 Stochastic sampling

We move from theoretical density analysis to a stochastic sampling analysis, where the original$\ \pi(\mathbf{w})=f^{\eta}(\mathbf{w}) \:$ can be applied directly to a weight sample $\ \mathbf{w} \:$ for a player, gradually contracting excess weight toward the consensus until an optimal contraction volume is reached. We observe very similar density evolution results as with the theoretical density analysis.

2.3 Two-team game

We perform a worst-case Monte Carlo analysis of a full-scale two-team game by sampling from normal densities, primarily to confirm the accuracy of the preceding aggregate analysis. We run a number of Monte Carlo iterations and record the worse-case results. A blockchain-based consensus algorithm has space and compute limitations, which would favor a smaller $\ \eta \:$ number of density evolution operations, each of which requires$\ O(n^{2}) \:$ operations. A small $\ \eta=3 \:$ with $\ \alpha=0 \:$ produce a full-scale result very close to the aggregate result.

Increasing the number of density evolution steps to $\ \eta=59 \:$ with$\ \alpha=0.95 \:$ manages to remove the zero-utility exploit at $\ w_{H}>0.98 \:$ seen at $\ \eta=3 \:$. However, the aggregate result in the theoretical honest retention deviates slightly, likely due to deviation of the upper mode density below consensus not accounted for in the aggregate.