# Minimal Variance Allocation of Rights and Applications to Blockchain Consensus

Maxime Reynouard

► To cite this version:

Maxime Reynouard. Minimal Variance Allocation of Rights and Applications to Blockchain Consensus. 2025. hal-05136184

HAL Id: hal-05136184

https://hal.science/hal-05136184v1

Preprint submitted on 30 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Minimal Variance Allocation of Rights and Applications to Blockchain Consensus

Maxime Reynouard

<figure><img src="image_2.png" /></figure>

Paris Dauphine University - PSL, France
Nomadic Labs, France

## Abstract

Randomness plays a critical role in distributed systems and blockchain technology, facilitating tasks such as load balancing, leader election, and fault tolerance, which enhance system scalability and resilience. However, while randomness is fundamental to certain systems, it can also pose liabilities, including unpredictability and security risks. In this paper, we focus on the allocation of rights, a shared random process in many blockchains, particularly in the allocation of block proposal or validation rights. We propose two new allocations protocol to reduce the randomness of this process and discuss the challenges of achieving minimal variance in this allocation. Beyond improving the allocation protocol, they offer an alternative approach to secure random seed generation by reducing its criticality. In fact, this serves as a complementary solution to existing measures that focus on preventing random seed manipulation. In addition, we evaluate the effectiveness of our proposal and analyze potential countermeasures that attackers might employ. Our approach improves the resilience and security of blockchain networks, addressing concerns associated with randomness in consensus protocols.

**2012 ACM Subject Classification** Security and privacy → Distributed systems security; Theory of computation → Pseudorandomness and derandomization

**Keywords and phrases** Blockchain, Consensus, Randomness, Security, Apportionment, Sybil Attacks, Allocation

Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

## 1 Introduction

In distributed systems, randomness facilitates tasks such as load balancing, leader election, and fault tolerance, enhancing the scalability and resilience of the system [31, 19, 24]. Randomness is embedded in Proof-of-Work (PoW) consensus protocols such as Bitcoin [27]. Similarly, in Proof-of-Stake (PoS) consensus algorithms, randomness is used to select validators or block producers [9, 3, 22, 37], ensuring decentralization and dividing control over the consensus among participants. In contrast to PoW, randomness is not intrinsic to PoS consensus protocols and needs to be replicated within the consensus with a Cryptographically Secure Pseudorandom Number Generator (CSPRNG) [5]. Furthermore, its emulation can introduce vulnerabilities [32, 17]. In general, randomness introduces challenges such as probabilistic guarantees, biased outcomes, synchronization complexity, and performance overhead [16].

At the consensus level, several attacks rely on being temporarily lucky in the random processes. Indeed, most consensus protocols ensure security through decentralization: when power is appropriately shared among participants, no single entity can gain control over the consensus. However, when power is randomly shared, it can happen that a participant temporarily gains enough control to perform certain attacks (selfish mining [14, 30, 17], balancing attack [28]). Simultaneously, the selection of a shared random seed used in the rest of the consensus protocol becomes a vector of attacks [35, 32].

Most consensus protocols use random allocations of block proposal rights and incentivize the proposal of blocks. This leads participants to have an income stream which is variable

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
## 23:2 Minimal Variance Allocation of Rights for Blockchain Consensus

and therefore less desirable. In fact, in economics and finance, risk aversion [36] refers to the preference for outcomes with lower uncertainty. This effect is considerable and has led institutions to develop methods such as mean-variance analysis (also known as Modern Portfolio Theory - MPT) [25]. Therefore, reducing the randomness of block proposal right allocations could make consensus incentives more attractive to participants. Especially to small ones since they have the lowest mean-to-standard deviation ratio. This could encourage greater participation, thereby enhancing decentralization and security; or this could be compensated by lowering the incentive amounts, in turn decreasing the inflationary and fiscal consequences of the consensus protocol rewards.

In this paper, we look at a general random protocol that is shared by many PoS blockchains, sometimes at several points of their consensus protocol: the allocation of rights [9, 3, 33, 22, 37, 8]. These rights can be used to perform different actions such as block proposal, block building, transaction ordering, block validation, or selecting subcommittees. For example, in the case of Ethereum's consensus, the 32 slots (time frames representing block proposal rights) of each epoch (groups of 32 slots) are allocated among Ethereum's validators. Another example: Tezos consensus protocol (Tenderbake), which is a Byzantine Fault Tolerance (BFT) style protocol, selects a validation subcommittee by allocating 7000 voting rights to the participants. In PoS blockchains, the protocol with which we allocate rights usually aims at emulating the PoW randomness: each right is allocated *independently and with identical distribution* (IID) with a probability proportional to the stake. This protocol aims at providing *fairness* (each user expected number of rights is proportional to its stake), as well as probabilistic security<fnref n="1" />. Note that the *fairness constraint* forcing the expected number of rights to be proportional to the stake also prevents from incentivizing collusion (if the expected number of rights is super-linear) or from incentivizing the split of the stake under several accounts<fnref n="2" /> (if the expected number of rights is sub-linear).

While the allocation protocol has just started being discussed in the context of blockchains [17], a very similar problem is known with different names in other fields. The oldest such problem, *apportionment* has been studied for several hundred years in the mathematics field of social choice, it stems from the problem of allocating seats in the House of Representatives among states based on their population. In this field, the search for fairness has led to the constraint *quota*: Each state should obtain the floor or ceiling of the number of seats it is *entitled* to according to their population share. However, solutions from this field are traditionally deterministic and therefore cannot respect exactly the fairness constraint (the expected number of seats a state gets equals their *entitlement*); moreover, respecting quotas can lead to nondesirable properties such as the Alabama paradox<fnref n="3" />, see [4] for a full account of the field's state of the art and its impossibility theorems. In 2004, Grimmett [18] proposed using randomness to solve the issues of deterministic apportionment with a protocol that would respect quotas, fairness, and other monotonicity properties. Recently, a link was made between this problem and that of *unequal probability sampling* in statistics and that of *dependent randomized rounding* in computer science [12]. In these fields, the problem consists of selecting a fixed amount of elements from a set *without replacement* and with different probabilities. We now know that if we restrain apportionment protocols to those who respect the quota constraint, the problems are equivalent [12]. This enables the application of more

<footnote n="1">¹ The assumption for standard longest chain protocols is that more than half of the blocks are proposed by honest agents, guaranteeing the longest chain over time for honest agents [27]</footnote>

<footnote n="2">² This could be seen as a Sybil attack [13]</footnote>

<footnote n="3">³ In 1880, the size of the House of Representatives was discussed and it was discovered that with a size of 299 seats, Alabama would get 8 seats, whereas with a size of 300 seats Alabama would only get 7 seats.</footnote>
than 50 known protocols [7] to achieve such an allocation; all of which might have different desirable properties [12].

Let us address here the concern for predictability that one should have. A strong argument for randomness relies on the security that unpredictability provides. In fact, the threat of an eclipse attack [20] is credible and this attack is often used in combination with others to facilitate it [29]. Here randomness provides the benefit of unpredictability, since it is hard to know who will get a certain right (at a certain time). As maintaining an eclipse attack over long periods of time is difficult; this unpredictability provides protection. Our approach does not change that one bit. That is because we do not discuss the order in which rights are assigned, only the number of rights assigned to each agent at each allocation. An attacker does not get additional information on which agent receives a specific right before the allocation happens compared to the current IID allocation. In other words, while reducing the randomness, our proposal does not increase the predictability in the sense that is relevant for security. To be sure of that, one could even randomly shuffle the allocation's order after it is completed. The reduced randomness, however, provides control, preventing certain luck-based attacks.

## 1.1 Contributions

In this paper, we propose to reduce the randomness with which the rights are allocated to participants in blockchain PoS protocols in two ways inspired by other fields of study. In the first one, we propose to use an incremental protocol in which participants would be granted the floor of the number of rights they are entitled to, then the remaining rights would be allocated as before in an IID fashion that would guarantee the fairness constraint. This ensures that participants get at least the floor of their entitlements (satisfying the lower quota constraint). However, they may get more than the ceiling of their entitlements (the upper quota constraint is not respected), therefore, this allocation only reduces the randomness but does not minimize it. The second allocation we propose consists of using any of the known protocols from the aforementioned fields to minimize randomness under the fairness constraint.

In addition to proposing the new right allocation protocols, this paper analyses how this enhances security. To do that, we consider two different issues posed by the randomness of the right allocation in blockchain protocols: 1) the opportunity for random seeds manipulations<fnref n="4" />; 2) the need for large subcommittees<fnref n="5" /> when they are sampled.

If attackers did not adapt to our proposals, security improvements would be drastic. However, since we do not entirely eliminate the randomness of the allocation protocol (and for good reasons: the fairness constraint which also prevents other types of manipulation cannot be respected without randomness), we can expect attackers to deploy a Sybil countermeasure to recover part of the lost randomness. Indeed, with a large stake, a participant will have a large entitled number of rights, so its lower quota (which is allocated deterministically) will represent most of it. In contrast, a very small stake will most likely have a fully random allocation (if its entitled number of rights is smaller than 1). We can therefore anticipate

<footnote n="4">⁴ If an attacker can manipulate the seed to have several possible choices, they might do so to increase the number of rights they are allocated. In the case of block proposal rights this can mean increasing their revenues from the consensus, see [35]</footnote>

<footnote n="5">⁵ Subcommittees can be randomly sampled when a task is too to be executed by all agents, but too sensible to be entrusted to a single agent. In this case their exist a compromise between a small committee to avoid overheads and a large one to increase security, see [17]</footnote>
attackers splitting their stake over several accounts so that each of those accounts retains a larger part of randomness. The use of several accounts in order to perform an attack is traditionally called a Sybil attack [13], but since here it represents more a means to lower the effectiveness of our proposal to be able to use other attacks, we call it a Sybil countermeasure. We provide two approaches that allow us to model the effects of such a Sybil countermeasure. We simulated the results of our proposals for the two problems (random seed manipulation and subcommittee sampling) with those two models and compared them with the baseline IID allocation. As expected, without Sybil countermeasures, the improvements are impressive (for example, in the case of subcommittee sampling, with standard parameters, the safe size of a subcommittee can be lowered from 6982 to 40). Sybil countermeasures temper those improvements, and depending on the assumptions made about how the Sybil attack happens, we still have significant improvements (in the same case, we can now lower the number of rights from 6982 to 2203 in the worst case).

In short:

- We bridge the fields of blockchain consensus with that of apportionment (or unequal probability sampling or dependent randomized rounding).

- We optimistically analyze the direct impact of our proposals. Under the assumption that the attacker does not react: our proposal entirely negates certain selfish attacks such as Ethereum's random seed manipulation; and greatly improves subcommittee sampling (for the same parameters we reduce the size of the subcommittee from 6982 to 40).

- We then anticipate how an attacker might mitigate their effects and provide a second analysis, conservative this time. In the case of Ethereum's random seed manipulation, if the attacker can have very large amount of Sybils he can recover most of the potential of the attack (85%). But the subcommittee improvement remains interesting (the most conservative hypothesis allows a size reduction to 2203).

## 1.2 Related work

The problem of the random seed manipulation is well known; see [35] for an excellent account of the case of manipulating Ethereum's random seed generation algorithm (called RANDAO). While we propose to reduce incentives for attacking random seeds, previous work focused on how to completely prevent random seed manipulations [26]. The most common approach is the use of commit-reveal schemes; even though attacks become more complex, this leaves the door open to some manipulations. The two ways to achieve unpredictability guarantees that receive the most attention are: (1) Verifiable Delay Functions (VDFs) [6], which involves a time-delayed computation to ensure unpredictability; (2) Threshold cryptography schemes [10], which involve dividing a secret into shares distributed among multiple parties, which can then be combined to produce random seeds with resilience against individual failures or malicious behavior. Both approaches have their advantages and their drawbacks: (1) they make strong assumptions on the attacker's hardware and the mathematical hardness of the problems they rely on; (2) they introduce complexity and overhead in the system. Those drawbacks are why prominent PoS blockchains (such as Ethereum) still do not use randomness beacons with strong unpredictability guarantees. Although securing the random seed generation remains a definite necessity, we propose an orthogonal approach that reduces the criticality of the random seed, making it less of a liability and reducing the incentives to manipulate it. Similarly for the problem of subcommittee sampling, discussions tend to revolve around how to manage the size of the committee rather than how to reduce it [8].

In the context of blockchains, [17] represents, to our knowledge, the only study addressing the reduction of randomness. However, their analysis is confined to the specific problem of
subcommittee selection. Unaware of related research in other domains that tackle equivalent challenges, they proposed several allocation schemes, including the LowVAlloc scheme, which we also discuss in this paper. In particular, their approach did not achieve the optimality of minimal-variance schemes such as MinVAlloc, even though it was their outspoken aim. Furthermore, their focus was limited to subcommittee sampling, whereas we extend the scope to a more general framework of stake allocation. This broader perspective enables us to evaluate these schemes in the context of an alternative problem: the best-of-k allocations and suggests that they could be employed in other contexts as well. Lastly, their study exclusively considered the *implicit model* of the attacker's behavior, which assumes the worst case of unrestricted stake distribution for the attacker. In contrast, we propose the *σ-model*, offering a more nuanced view of the attacker's capabilities.

## 2 General Model

A committee $\mathcal{N} = \{1, 2, ..., n\}$ of $n$ agents participates in the allocation of rights protocol. A single agent is noted $i \in \mathcal{N}$, each agent $i \in \mathcal{N}$ has a stake $S_i$. The total stake is therefore $S = \sum_{i=1}^{n} S_i$, allowing us to compute the normalized stakes $s_i = S_i/S$ for each agent $i \in \mathcal{N}$. We suppose that $R$ rights will be randomly distributed among the $n$ agents, and note $R_i$ the random integer variable representing the number of rights agent $i \in \mathcal{N}$ will have received. In PoS blockchains, the governing principle is that an agent's agency on the chain should be proportional to their stake, hence we take interest in the entitlement $E_i = Rs_i$ of each agent $i$.

### 2.1 Fairness Constraint

Since each agent's agency should be proportional to their stake, we assume any fair allocation protocol abides the following **fairness constraint**:

$$E_i = \mathbb{E}(R_i), \forall i \in \mathcal{N} \qquad (1)$$

where $\mathbb{E}(V)$ denotes the expected value of the random variable $X$.

In addition to ensuring fairness, this linear constraint also ensures that agents will not be able to increase their expected number of rights by splitting their stakes (sublinear expected gains) nor by entering coalitions (superlinear expected gains). Indeed, let us imagine the case of quadratic gains where there is a scalar $\lambda$ such that $\mathbb{E}(R_i) = \lambda E_i^2 = \lambda R^2 s_i^2$ then two agents with strictly positive stakes ($s_i, s_j > 0$) entering a coalition would get more expected rights than separately. To show this, we use a slight abuse of notation, noting $E_{i+j}$ and $R_{i+j}$ the entitlement and rights received by a coalition of two separate agents $i$ and $j$. This gives:

$$\begin{aligned} \mathbb{E}(R_{i+j}) &= \lambda E_{i+j}^2 \\ &= \lambda R^2 (s_i + s_j)^2 \\ &= \lambda R^2 (s_i^2 + s_j^2 + 2s_i s_j) \\ &> \lambda R^2 s_i^2 + \lambda R^2 s_j^2 \\ &> \mathbb{E}(R_i + R_j) \end{aligned}$$

Similarly, let us imagine that $\mathbb{E}(R_i) = \lambda \sqrt{E_i} = \lambda \sqrt{Rs_i}$, we would then similarly end up with $\mathbb{E}(R_{i+j}) < \mathbb{E}(R_i + R_j)$. In this case, we incentivize an agent to split their stake over
23:6 Minimal Variance Allocation of Rights for Blockchain Consensus

2 accounts $i$ and $j$ (and actually a maximal amount of accounts$^6$). Only a linear relation prevents both those manipulations which makes the fairness constraint a security property.

3 Allocation protocols

Since we are trying to reduce or even minimize the randomness of the right allocation, we will look at the variance of this random variable. Variance gives a good measure of how random the allocation protocol is from the point of view of an agent$^7$. In Section 4, two issues are presented that could be directly mitigated by having a protocol with less variance.

3.1 Current allocation protocol: IID Allocation

In most consensus protocols, the allocation of rights consists in having each right allocated independently to agent $i \in \mathcal{N}$ with probability $s_i$. This means that from the point of view of agent $i$, whether they get a specific right is a Bernoulli random variable with parameter $s_i$. And the total number of rights $i$ is a binomial random variable of parameters $R$ and $s_i$, that is, $R_i = \mathcal{B}(R, s_i)$.

The variance of a binomial law is known; here we have $Var(R_i) = Rs_i(1-s_i) = E_i(1-s_i)$. Note that, as a healthy blockchain is decentralized, so for most agents $1 - s_i \approx 1$, meaning their variance is approximately $Var(R_i) \approx E_i$ and can therefore take values arbitrarily large. The following allocation proposals however, bound the variance to a constant independent of the problem parameters.

3.2 Incremental solution with Lowered Variance: LowVAlloc

Since variance measures dispersion (meaning that it is a measure of how far we can expect to
draw from the expected value), when trying to lower it, it seems only natural to try and draw
rights as close to the expected value as possible. An incremental way to achieve this is by
starting to give to each agent their *guaranteed rights* $G_i = \lfloor E_i \rfloor$ and then proceed similarly
to before:

1. Give their *guaranteed rights* $G_i = \lfloor E_i \rfloor$ to each agent $i$.

2. Compute the *residual claims* $C_i = E_i - G_i$ and the *residual rights* $C = \sum_{i \in \mathcal{N}} C_i$.

3. Then compute the *normalized residual claims* $c_i = C_i/C$.

4. Allocate the *C* residual rights just as before with the IID allocation and normalized residual claim as probabilities: for each right we independently draw (with replacement) an agent *i* with probability *c*ᵢ.

<footnote n="6">⁶ Most PoS blockchains require a minimal stake to enter consensus, leading to a lower bound on the size of an account, and therefore a bound on the number of accounts an agent can take part in the consensus with.</footnote>

<footnote n="7">⁷ Computer scientists are generally used at looking at entropy as a measure of randomness. However, entropy fails to account that agents will usually consider a variable with a 50%/50% chance to be 4 or 6 less random than one with a 50%/50% chance to be 0 or 10; that is because entropy only looks at the distribution of a random variable without considering its support.</footnote>
The pseudocode for this allocation is given in the algorithm 1 in appendix A. One can immediately see that this satisfies the fairness constraint as for $i \in \mathcal{N}$:

$$ 
\begin{aligned}
\mathbb{E}(R_i) &= G_i + \mathbb{E}[\mathcal{B}(C, c_i)] \\
&= G_i + C c_i \\
&= G_i + C \frac{C_i}{C} \\
&= G_i + E_i - G_i \\
&= E_i
\end{aligned}
$$

Furthermore, one can note that in addition to having $C \le R$, we even have $C \le n - 1$ because $C_i = E_i - \lfloor E_i \rfloor < 1$. In terms of variance, this protocol gives us for each agent the variance of the binomial law $\mathcal{B}(C, c_i)$ resulting from the last part of the algorithm (the beginning is deterministic), that is: $\mathrm{Var}(R_i) = C c_i (1 - c_i) = C_i (1 - c_i) \le C_i = E_i - \lfloor E_i \rfloor < 1$. With this quick and easy change, agents already get a constant bound on the variance of the protocol. However, we can go further than that.

## 3.3 Minimal Variance Allocation: MinVAlloc

Once we start to try to reduce the variance, it seems only logical to try to minimize it. Given the fairness constraint from equation (1), intuition dictates that this is achieved by guaranteeing $R_i$ takes values as close to $E_i$ as possible under the constraint that $R_i$ is an integer random variable, and given that $E_i$ is probably not an integer. So we ensure that the support of $R_i$ is $\{\lfloor E_i \rfloor, \lfloor E_i \rfloor + 1\}$ (this is known as the quota constraint in the apportionment literature) and set its probabilities to respect the fairness constraint from equation (1). Here is a simple example to better understand: If an agent $i$ is entitled to $E_i = 4.7$ rights, we would like them to get 4 rights with probability 0.3 and 5 rights with probability 0.7, such a distribution guarantees the constraint fairness with the tightest possible support. Recalling that $C_i = E_i - \lfloor E_i \rfloor$, the theorem and proof from [34] show that the following distribution for the random variable $R_i$ would minimize the variance under the fairness constraint:

$$ \mathbb{P}(R_i = r) = \begin{cases} 1 - C_i, & \text{for } r = \lfloor E_i \rfloor \\ C_i, & \text{for } r = \lfloor E_i \rfloor + 1 \\ 0, & \text{else.} \end{cases} \qquad (2) $$

The minimal variance achieved under the fairness constraint is: $\mathrm{Var}(R_i) = C_i(1 - C_i) \le 1/4$. With this, the bound on the variance has been lowered from 1 to 1/4. However, we still have to provide a protocol to allocate the rights that achieves this property. As explained in the Introduction, this can be achieved in many different ways [7].

### MinVAlloc based on Grimmett's allocation

We chose Grimmett's [18] allocation protocol among others solely for its simplicity in being understood and proven to work. Any of the allocation protocols guaranteeing the quota (agents get the floor or ceiling of their entitlements) and fairness constraints would be suitable replacements of MinVAlloc as we only use those two properties for the rest of the paper. See [12] for a comparison of a few protocols based on other properties that might be desirable. The protocol is straightforward, its pseudo-code can be found in appendix B, and it can be explained in the visual and elegant following way:
<figure><img src="image_5.png" /><figcaption>Figure 1 Grimmett’s protocol illustration</figcaption></figure>

1. Line up the entitlements of the agents on a linear $[0, R]$ axis.

2. Shift that axis leftward by $u$.

3. For each integer in $[1, R]$, attribute a right to the agent whose entitlement is aligned with the integer.

Figure 1 illustrates a small example for three agents $a, b$ and $c$ with respective entitlements $E_a = 3.8, E_b = 0.8, E_c = 2.4$, for $R = 7$, and with a draw of $u = 0.3$. Here, $a$ gets the rights 1 to 4, $b$ gets 0 rights and $c$ gets the rights 5 to 7. And in appendix C, one can find the formal proof that this indeed constitutes an allocation respecting the quota and fairness constraints.

## 4 Results: two problems stemming from right allocation

Here we present the results of switching from an IID rights allocation to LowVAlloc or MinVAlloc in two cases: best-of-$k$ allocation and subcommittee sampling security criterium. The code that served to obtain these results and those of section 6 can be found here [1].

But first: our protocols introduced a new dependency for the number of rights the attacker might receive: the number of residual rights $C$ does not depend only on the attacker's stake, but on the entire stake distribution. To be able to simulate the allocations, we now need the whole vector of normalized stakes $\mathbf{s}$. In the results we present in the rest of the paper, we chose to use Ethereum's stake distribution as it is currently the highest PoS market capitalization. The distribution was obtained from dune [21].

In order to be able to consider an attacker with an arbitrary normalized stake $\mathbf{s}_f$, we also suppose that the attacker's stake diluted the current Ethereum stake distribution, just as if an attacker that had idle ETH (Ethereum's tokens) just staked them, this means that an agent $i$ with a normalized stake of $s_i^*$ in the current distribution will have a normalized stake $s_i = s_i^*(1 - s_f)$ in our attack model.

### 4.1 Best-of-$k$ allocation

We view the allocation of rights as being the generalization of a process happening at in several places for different PoS consensus protocols. A very common and critical instance of allocation of rights is the allocation of block proposal rights. Most protocols [9, 22, 37, 33, 3], use a shared temporary random seed to randomly draw block proposal rights over a fixed horizon. For example, Ethereum's GASPER [9] has epochs of 32 slots, each epoch has its own shared random seed that is used to draw the block proposer for each of the 32 slots. Attacks exist that aim at manipulating the random seed. They can serve to get more block proposal rights for a certain epoch, hence increasing the rewards and fees perceived by the attacker. The random seeds are generated using the RANDAO protocol, and this vulnerability is known as the Last Revealer Attack (LRA) see [35] for a detailed explanation of how such manipulations can be performed and why.

Here we only need to understand that when the attacker controls the proposal right for the last block of an epoch they can choose whether to propose it or not, and in each case compute the possibilities for the resulting random seed used by the next epoch. This gives
<table><caption>**Table 1** Best-of-2 Allocation gains - Protocol comparison</caption><thead><tr><th rowspan="2">k</th><th rowspan="2">R<br>Protocol \ s<sub>f</sub></th><th colspan="4">32</th><th colspan="4">1024</th></tr><tr><th>0.0005</th><th>0.01</th><th>0.1</th><th>0.3</th><th>0.0005</th><th>0.01</th><th>0.1</th><th>0.3</th></tr></thead><tbody><tr><td rowspan="3">2</td><td>IID</td><td>0.80%</td><td>10.51%</td><td>16.40%</td><td>10.51%</td><td>14.11%</td><td>12.98%</td><td>4.81%</td><td>2.53%</td></tr><tr><td>LowVAlloc</td><td>0.67%</td><td>10.23%</td><td>0.46%</td><td>0.88%</td><td>14.06%</td><td>0.21%</td><td>0.05%</td><td>0.01%</td></tr><tr><td>MinVAlloc</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td rowspan="3">4</td><td>IID</td><td>0.78%</td><td>12.42%</td><td>25.39%</td><td>16.91%</td><td>18.04%</td><td>21.92%</td><td>8.54%</td><td>4.53%</td></tr><tr><td>LowVAlloc</td><td>0.74%</td><td>11.99%</td><td>0.51%</td><td>1.12%</td><td>18.01%</td><td>0.24%</td><td>0.06%</td><td>0.01%</td></tr><tr><td>MinVAlloc</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td rowspan="3">8</td><td>IID</td><td>0.78%</td><td>12.69%</td><td>30.27%</td><td>20.88%</td><td>18.97%</td><td>28.26%</td><td>11.54%</td><td>6.15%</td></tr><tr><td>LowVAlloc</td><td>0.78%</td><td>12.22%</td><td>0.51%</td><td>1.17%</td><td>18.90%</td><td>0.24%</td><td>0.06%</td><td>0.01%</td></tr><tr><td>MinVAlloc</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td></tr></tbody></table>

Cost-adjusted relative increase in expected gains $E_f^k/E_f - 1$ for different number of rights $R$, number of allocation to choose from $k$, allocation protocol and attacker stake $s_f$.

them the occasion to compute the results of the next allocation of rights and to choose the best-of-2 outcomes. Since the attacker needs to forgo their current proposal right to choose one of the seeds, one of the allocations needs to be corrected by a loss of earning of one right. But the attack can be generalized, with the control over the $l$ last blocks of an epoch, the attacker can choose between $k = 2^l$ random seeds (each of those last blocks can either be proposed or not leading to independent random seeds). Once again the allocation needs to be adjusted for the cost of attacking, but since the attacker can always choose not to attack (by proposing all the $l$ blocks) they can only gain from having this possibility to maximize the allocated rights. We only look at what the attacker can gain from a single attack without considering an optimal long term strategy as this problem is far from trivial, see [35].

When the attacker has a choice between $k$ random seeds, for $j \in \{1, ..., k\}$, we note $\Lambda(j)$ the loss from the number of blocks proposal rights that needs to be forgone to choose seed $j$ and $R_f^j$ the number of rights allocated to the attacker with this seed. The net resulting number of rights from this seed is $R_f^j - \Lambda(j)$ and we can note $E_f^k = \mathbb{E}[\max(R_f^1 - \Lambda(1), ..., R_f^k - \Lambda(k))]$ the expected value from maximizing the net reward when choosing the best-of-$k$ random seed. Table 1, shows the results of the cost-adjusted relative gains of such attacks $E_f^k/E_f$. We consider different parameter values for $R$, $s_f$ and up to $l = 3$ last block controlled.

We make the following observations:

- The IID allocation gains are not monotonous relative to the attacker's stake, that is because of contradictory forces: 1) for small stakes the gains from the attack are small because the agent rarely gets more than 1 right so the alternative seed with a cost of 1 is rarely worth picking; 2) for larger stakes the mean deviation ($\sqrt{Var(R_i)} = \sqrt{E_i(1 - s_i)}$) increases slower than the entitlement $E_i$, dampening the relative efficiency of the attack.

- LowVAlloc provides very little improvement for low attacker stakes. This is because the random allocation of the residual claims is mostly unchanged from the IID allocation as 1) the attacker gets 0 rights deterministically ($G_f = 0$) therefore $C_i = E_i$ and 2) we still have $c_i \ll 1$ as either $E_i \ll 1$ or $C \gg 1$; this leads to the approximation $Var(R_i) \approx E_i$ to remain valid.

- With a larger $R$, it is easier for LowVAlloc to provide an improvement. Intuitively, this
23:10 Minimal Variance Allocation of Rights for Blockchain Consensus

comes from the fact that as an approximation of the the entitlements $E_i = Rs_i$, the guaranteed rights $G_i = \lfloor E_i \rfloor$ gets mostly<fnref n="8" /> better for higher values.

■ With MinVAlloc, no more gain is possible, the results we have are true 0 values, not rounded values; here we have *lowered the allocation's randomness* sufficiently the attack is just eliminated. That is easily explained as the rights allocated to the attacker can only take two values with a difference of 1, so there is no chance that paying 1 to attack yields a better result when taking that cost into account.

4.2 Random Subcommittee sampling

Subcommittee sampling is a compromise one can come to when a task cannot be entrusted to a single agent but asking every agent to do the task would be too costly overall; in this case a possible solution is to sample a subcommittee from the committee $N$ to tackle the task. A larger subcommittee is more representative, possibly enhancing security and decentralization, but it also increases overheads. Some consensus protocols use quorum based algorithms (à la pBFT [11]), they randomly sample a subcommittee for the validation of each block [3, 33]. Furthermore, subcommittee sampling is also used for some scalability solutions such as sharding for data availability layers [8]. In all of those cases, each right represents a *vote* or a *seat* in the subcommittee and we do not want the attacker to control too large a share of the subcommittee.

For our approach to remain general, we will use a threshold $\tau(R)$ on the number of rights to represent the limit over which an attacker can derail the task of the subcommittee: if the attacker controls less rights than the threshold ($R_f < \tau(R)$) the task is safe. We suppose that the normalized stake $s_f$ controlled by the attacker verifies: $s_f \le \frac{\tau(R)}{R} - \delta$ with $\delta > 0$ a protection margin. Without this, the criterion cannot be achieved as it would be common for the attacker to be able to compromise the subcommittee's task. Typically $\tau(R) = \frac{R}{3}$, especially in the Byzantine generals problem [23], in some variations we have other fractions [2] such as $\tau(R) = \frac{R}{2}$ when the network is considered reliable. Some other use-cases exists where only 1 out of $n$ of the subcommittee agents have to be honest, in this case $\tau(R) = R$. Since we consider a *random* sampling, given a small probability $\epsilon$, we need to use a probabilistic security criterion of the following form:

$$ \mathbb{P}(R_f \ge \tau(R)) < \epsilon \qquad (3) $$

This criterion simply states that the probability for the attacker (whose maximal stake is needed as an additional hypothesis) has less than $\epsilon$ probability to get $\tau(R)$ rights or more. We can see that with a large sample $R$, the security criterion should be achieved: as $s_f \le \frac{\tau(R)}{R} - \delta$ this is ensured by the central limit theorem (CLT) [15]. Without the $\delta$ margin, this criterion cannot be achieved for small $\epsilon$. The question becomes that of the efficiency of the sampling: we want the smallest sample size $R$ guaranteeing the security criterion (3). Indeed a lower $R$ means that the subcommittee tasks need to be trusted to less agents, meaning less network loss from redundancy.

► **Remark 1.** One can also see probabilistic finality criterion from longest chain rules [27, 22] as an instance of subcommittee sampling. Indeed, let us suppose an attacker reveals a hidden fork, and that the length of this fork plus that of the honest one is $R$. The attacker's fork will be selected if its length is longer than $\text{length} \ge \tau(R) = \frac{R}{2} + 1$. Of we want that to be a very

<footnote n="8">⁸ The function $x \in \mathbb{R}^+ \mapsto [x]/x \in [0, 1]$ is not monotonous but tends toward 1 when $x \to +\infty$</footnote>
<table><caption>**Table 2** Subcommittee Sampling - Minimal safe *R*</caption><thead><tr><th>τ(R)/R</th><th>Protocol \ s<sub>f</sub></th><th>0.01</th><th>0.1</th><th>0.2</th><th>0.3</th><th>0.5</th><th>0.9</th><th>0.99</th></tr></thead><tbody><tr><td rowspan="3">100.0%</td><td>IID</td><td>6</td><td>11</td><td>16</td><td>21</td><td>36</td><td>228</td><td>2383</td></tr><tr><td>LowVAlloc</td><td>6</td><td>8</td><td>8</td><td>10</td><td>13</td><td>64</td><td>593</td></tr><tr><td>MinVAlloc</td><td>3</td><td>3</td><td>3</td><td>3</td><td>4</td><td>20</td><td>200</td></tr><tr><td rowspan="3">50.0%</td><td>IID</td><td>15</td><td>39</td><td>87</td><td>217</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>LowVAlloc</td><td>13</td><td>25</td><td>33</td><td>49</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>MinVAlloc</td><td>5</td><td>5</td><td>5</td><td>9</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td rowspan="3">33.3%</td><td>IID</td><td>25</td><td>97</td><td>382</td><td>6982</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>LowVAlloc</td><td>22</td><td>43</td><td>76</td><td>316</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>MinVAlloc</td><td>7</td><td>7</td><td>10</td><td>40</td><td>✗</td><td>✗</td><td>✗</td></tr></tbody></table>

Minimal subcommittee size *R* satisfying the security criterion for $\varepsilon = 1e-9$ for different threshold functions $\tau$, attacker normalized stake $s_f$ and allocation protocols.

improbable event (with probability smaller than $\varepsilon$), we end up with the same probabilistic criterion (3).

In table 2, one can see the different minimal number of rights *R* that satisfies the security criterion from equation 3 for different stakes and $\tau$ and for $\varepsilon = 1e-9$<fnref n="9" />. Because of the condition $s_f \le \frac{\tau(R)}{R} - \delta$ with $\delta > 0$, some security criteria are impossible to obtain and are noted $\times$. The values for minimal *Rs* follow sensible trends and one can note that in Tezos consensus protocol *Tenderbake* [3], similar hypotheses were made for the selection of the size of the block attestation subcommittee. Indeed, they have $\tau(R) = \frac{R}{3}$, $s_f = 0.3$ and $\varepsilon = 3.2e-10$ and they chose a size of $R = 7000$. This seems to be a rounded value that corroborates our results of 6982 for similar parameters (only $\varepsilon$ varies and with the same one, we find 7354). In the same table 2, one can see the improvements that can be reached on *R* with our proposed allocations. Those improvements are better when $\delta$ is small i.e. when $s_f$ is close to $\frac{\tau(R)}{R}$; that is logical as when there is a small margin of error, the control over the deviations from the mean becomes more valuable.

## 5 Sybil countermeasure

Faced with this new allocation of rights protocol and its added security, an attacker might try to circumvent it. A straightforward way to do so, is to resort to a Sybil attack: create multiple accounts and split the stake between them, this will mean that the attacker will lower its guaranteed right and increase the part that they get randomly. This would enable the attacker to recover part of the variance they lost, hence making their attacks more interesting for the "best-of-*k* allocation" and more dangerous for the subcommittee sampling.

The dependency to the whole normalized stake vector *s* introduced in section 4 is also the source of the resilience of our approach to sybil counter measure. Indeed, even though the attacker might split their stake into several accounts, honest agents have no reason to do so. Therefore they will keep a certain amount of guaranteed rights that will still contribute to the allocation protocol being less random. To illustrate this, here is an extreme example. *R* = 5

<footnote n="9">⁹ This corresponds to the order of magnitude of a common hypothesis: for a random draw happening every second, the attack should not be possible more than once every hundred years : $\varepsilon = 3.2e-10$</footnote>
rights are distributed among 5 agents each with equal stakes: $s_1 = s_2 = s_3 = s_4 = s_5 = 0.2$. If one of them becomes an attacker and splits their stakes among any number of Sybils, the four others will still have 1 guaranteed right $G_i = 1$. The last one will be allocated randomly among the attacker's sybils, leading to a probability of 1 for the attacker to get 1 right. In this case the attacker could not get any variance back no matter how much they split their stake.

## 5.1 $\sigma$-models

We need to adopt an attack model, here we suppose that the attacker with stake $s_f$ has $\sigma$ Sybils with identical stakes. This means that the Sybil accounts will each control a normalized stake of $\frac{s_f}{\sigma}$. With both our proposed allocation protocol, each Sybil will deterministically get its guaranteed rights $G_\sigma = \lfloor \frac{E_f}{\sigma} \rfloor$ rights, meaning the attacker gets $G_f = \sigma G_\sigma = \sigma \lfloor \frac{E_f}{\sigma} \rfloor$. Each Sybil is left with a residual claim $C_\sigma = \frac{E_f}{\sigma} - \lfloor \frac{E_f}{\sigma} \rfloor$, normalized to $c_\sigma = \frac{C_\sigma}{C}$. Note that the total number of residual rights $C$ will depend on $\sigma$ as with the attacker lose guaranteed rights, $C$ augments.

Then with LowVAlloc, in the random part of the protocol, the attacker takes part in the $C$ lotteries and wins each with probability $\sigma c_\sigma$. This gives us a binomial law $B(C, \sigma c_\sigma)$. Note that the guaranteed rights $G_f = 0$ and that $C_\sigma = \frac{E_f}{\sigma}$ once $\sigma > E_f$, and therefore neither $C$ nor $\sigma c_\sigma = \frac{E_f}{C}$ change anymore, meaning that higher amounts of Sybils will not influence the random part of the allocation $B(C, \sigma c_\sigma)$.

For MinVAlloc, we could think that each Sybil would yield a Bernoulli law with parameter $C_\sigma$ resulting in total number of rights that will follow a Binomial law with parameters $\sigma$ and $C_\sigma$. However when the number of Sibyls is too high, the accounts cannot be spread out during the allocation anymore; for example, if more than half the accounts are the attacker's sybils, their will be at least two sybil accounts following one another in the allocation. Since the attacker does not control the ordering of the accounts, it can be sensible to consider that the draws won't be independent. Since the estimated total number of participants to the consensus protocol of Ethereum is very high ($n > 160000$), we suppose that when ordering the accounts what will happen locally in the order, is that Sybils will be one after another in a chain of length $l$. With this model, $l$ would closely follow a geometric random variable of parameter $\frac{n}{\sigma+n}$. Therefore $E(l) = 1 + \frac{\sigma}{n}$. We then suppose that only 1 account of this chain of length $l$ can get a right because of the dependency induced by MinVAlloc. From there, the number of draws the attacker takes part in is: $n_{draws}^f = \min(C, \lfloor \frac{\sigma}{l} \rfloor)$, meaning the random variable part of their total draw is $B(n_{draws}^f, \frac{C_f}{n_{draws}^f})$.

This gives us the two models (for LowVAlloc and MinVAlloc) that we need in order to be able to simulate the best-of-$k$ attacks. Results will be presented in section 6.

## 5.2 Implicit model for subcommittee sampling

Here, in addition to the last two $\sigma$-models, we can resort to another model for the Sybil attack. This is because the aim is for the protocol to determine a minimal $R$ that guarantees the security criterion, and while the protocol knows the stake distribution it does not know which accounts are operated by the attacker. Therefore, in this *implicit model*, we will not explicitly look at the number of Sybils the attacker uses but rather the accumulated locked and free rights they control across all the Sybil accounts.

Lets note $c_f$ the sum of the normalized residual claims of the attacker. We can also remark that the rights the attacker gets $R_f$ can be split into the rights they got deterministically $G_f$
<table><caption>**Table 3** Best-of-2 Gains - protocol comparison with Sybil counter-measures</caption><thead><tr><th>Protocol \ σ</th><th>1</th><th>9</th><th>10</th><th>1000</th><th>1000000</th></tr></thead><tbody><tr><td>IID</td><td>10.51%</td><td>10.51%</td><td>10.51%</td><td>10.51%</td><td>10.51%</td></tr><tr><td>LowVAlloc</td><td>0.88%</td><td>0.88%</td><td>9.02%</td><td>9.02%</td><td>9.01%</td></tr><tr><td>MinVAlloc</td><td>0%</td><td>0.85%</td><td>0.47%</td><td>9.01%</td><td>9.01%</td></tr></tbody></table>

Cost-adjusted relative increase in expected gains $E_f^2/E_f - 1$ for $R = 32$ and attacker normalized stake $s_f = 0.3$.

and randomly $H_f$, the latter being a random variable. By changing its number of Sybils, the attacker can influence the value of $G_f$, and the random law of $H_f$. However, here we consider the stake distribution fixed, we just do not know which accounts belong to the attacker (we will still have an hypothesis on the value of its cumulated stake $s_f$), therefore the attacker cannot change $C$

For LowVAlloc, we therefore have $R_f = G_f + H_f = G_f + \mathcal{B}(C, c_f)$. The attacker will try to maximize its variance to increase its chance of being over-represented, so if they can, they will try to ensure that $c_f = 0.5$ (to maximize $var(\mathcal{B}(C, c_f)) = C c_f (1 - c_f)$). So using expected value the precedent equation gives: $\mathbb{E}(R_f) = R s_f = G_f + \frac{C}{2}$ this means that $G_f = R s_f - \frac{C}{2}$. This worst case is what we will assume to compute the best possible $R$. Our criterion then becomes:

$$ \mathbb{P} \left( R s_f - \frac{C(R)}{2} + \mathcal{B}(C(R), 0.5) \geq \tau(R) \right) < \varepsilon \qquad (4) $$

For MinVAlloc, in the worst case the attacker's Sybils are spread out during the allocation. This therefore leads us to the same security criterion as before because the attacker will take part in the draw of each free right.

# 6 Results: Resilience to Sybil countermeasure

## 6.1 Random Seed Incentives

For these results, we focus on the basic (and most relevant) case of $k = 2$ and the situation of a threatening attacker with a stake similar to that of Lido $s_f = 0.3$ on Ethereum $R = 32$. In table 3, for the parameters mentioned, one can compare the effectiveness of the different protocols. Note that, as we mentioned above, without Sybil countermeasures, LowVAlloc and MinVAlloc greatly improve resilience to the attack. However, with the Sybil countermeasure the attacker can recover most of the benefits of the attack. Part of the benefits are not recovered due to the fact that less rights are randomly allocated: honest agents still receive guaranteed rights $G_i$. Note also that as soon as $\sigma > E_f$ (in this case $E_f = R s_f = 32 * 0.3 = 9.6$) the LowVAlloc protocol yields the maximum possible for the attack, while MinVAlloc still retains some resilience and would force the attacker to attack with a larger number of Sybils. Once again, the higher $R$ is, the stronger this retention would be.

## 6.2 Subcommittee sampling

Then in table 4, we compare the different models and protocols under the standard parameters $s_f = 0.3$, $\varepsilon = 1e-9$, and $\tau(R) = \frac{R}{3}$. Note that the implicit model has the same result in
<table><caption>**Table 4** Subcommittee Sampling Minimal safe R - protocol and model comparison with Sybil counter-measures</caption><thead><tr><th>Protocol \ σ</th><th>1</th><th>10</th><th>100</th><th>1000</th><th>1000000</th></tr></thead><tbody><tr><td>IID</td><td>6982</td><td>6982</td><td>6982</td><td>6982</td><td>6982</td></tr><tr><td>LowVAlloc σ-Model</td><td>316</td><td>550</td><td>1045</td><td>2893</td><td>2893</td></tr><tr><td>MinVAlloc σ-Model</td><td>40</td><td>61</td><td>301</td><td>2437</td><td>2893</td></tr><tr><td>Implicit Model</td><td>2203</td><td>2203</td><td>2203</td><td>2203</td><td>2203</td></tr></tbody></table>

Minimal subcommittee size *R* satisfying the security criterion for $\varepsilon = 1e-9$ for $\tau(R) = R/3$, attacker normalized stake $s_f = 0.3$ and attack models.

every column, that is because in this model we do not need to make an assumption on this number; we just consider that there is enough Sybil for an optimal attack, so this line should be interpreted as a single result without a value for the column header $\sigma$. We can see that without Sybil countermeasure, LowVAlloc and MinVAlloc provide identical results, however, once again, MinVAlloc is slightly more resilient to the Sybil countermeasure. Another interesting result is that the $\sigma$-models actually yields worst results for high number of Sybils, than the implicit worst-case model. This is due to the simplifications we made that underestimate the dependency in the allocation of the residual claims in the case of the $\sigma$-models. So depending on the assumptions made for the amount of Sybils the attacker could control, one could choose to follow the $\sigma$-models results and switch to the implicit model if it yields better results when $\sigma$ is allowed to be bigger or for a worst case assumption. Additionally, we can once again see that MinVAlloc has an edge on LowVAlloc as it would force the attacker to have a higher number of siblings to counter the variance reduction measure similarly. However, this edge is lost when we make the worst case assumption of the implicit model.

## 7 Conclusion

We have provided an incremental allocation of rights algorithm LowVAlloc that can be implemented in most blockchains as well as its optimized improvement MinVAlloc. Those two algorithms provide allocations with, respectively, a reduced and minimized variance in the number of rights each agent receives by guaranteeing the lower quota or quota properties. At the same time, they respect the fairness constraint: they maintain the expected number of rights received proportional to entitlements. Reducing and minimizing the variance allows us to have more control on the outcome of the allocations, in turn guaranteeing better security or performance in two vulnerabilities raised by the randomness of the allocation protocol: best-of-*k* allocation and subcommittee sampling probabilistic security. In order to stay one step ahead of potential threats, we also provided how those allocation algorithms might fend against a possible Sybil countermeasure. This showed that in both instances even in the worst cases of Sybils countermeasures, the two allocation algorithms provide better guarantees than the standard IID allocation. And while MinVAlloc is more complex, it achieves sensibly better results than LowVAlloc, as well as being more resilient to a possible Sybil countermeasure.

On the practicality of the implementation: LowVAlloc only represents an incremental change; but we acknowledge that the use of MinVAlloc might have heavier repercussions, especially for block indexers. On the side of space and time complexity: everything is linear in the number of agents *n*, which is identical to the current situation. Additionally, the new
allocations might open the way to new optimizations: As stake distributions usually evolve slowly, guaranteed rights $G_i$ would probably remain the same from an allocation to the next. This could permit to have minimal partial computations solely when the stake distribution evolves. About the efficiency of the proposal, we believe that the most prominent application is that of subcommittee sampling. Under our conservative hypothesis, we can reduce the subcommittee size from 6982 to 2203.

We also hope that this article can inspire others to follow this mindset of reducing the randomness of certain processes to optimize them. May it be in the field of blockchains or another one. Still in the field of blockchains, in the case of allocation of rights: one could take an interest in the order in which rights are allocated. Indeed, a sorted right-allocation array would be easier to store if some agents possess a lot of rights (this is probably interesting for subcommittee sampling). Whereas if the allocation looked more like a round-robin (with uneven number of rights), it would guarantee that an attacker does not get several blocks in a row, making forking attacks and their variants more complicated. It would also have the advantage of improving the variance of the service's availability: it would make it impossible for a participant to be responsible for two block proposals in a row, so in case of a crash of a single participant, no two blocks in a row could be absent.

References

1. Anonymized Repository - Anonymous GitHub, April 2024. [Online: accessed 4. Dec. 2024]. URL: https://anonymous.4open.science/r/Minimal-Variance-Right-Allocation-26A5.

2. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Optimal good-case latency for byzantine broadcast and state machine replication. CoRR, abs/2003.13155, 2020.

3. Lăcrămioara Aştefanoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord, Sara Tucci, and Eugen Zălinescu. Tenderbake – a solution to dynamic repeated consensus for blockchains, 2021. arXiv:2001.11965.

4. Michel L. Balinski and H. Peyton Young. Fair Representation: Meeting the Ideal of One Man, One Vote. Brookings Institution Press, 2001. URL: http://www.jstor.org/stable/10.7864/j.ctvcb59f6.

5. Dan Boneh. Blum-Blum-Shub Pseudorandom Bit Generator, pages 50–51. Springer US, Boston, MA, 2005. doi:10.1007/0-387-23483-7_37.

6. Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 757–788, Cham, 2018. Springer International Publishing.

7. K. R. W. Brewer and Muhammad Hanif. An Introduction to Sampling with Unequal Probabilities, pages 1–19. Springer New York, New York, NY, 1983. doi:10.1007/978-1-4684-9407-5_1.

8. Vitalik Buterin. Proto-danksharding faq. notes.ethereum.org/@vbuterin/proto-danksharding_faq, 2024. Accessed 12. Feb. 2024.

9. Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X Zhang. Combining ghost and casper, 2020. arXiv:2003.03052.

10. Ignacio Cascudo, Bernardo David, Omer Shlomovits, and Denis Varlakov. Mt. random: Multi-tiered randomness beacons. Cryptology ePrint Archive, Paper 2021/1096, 2021. https://eprint.iacr.org/2021/1096. URL: https://eprint.iacr.org/2021/1096, doi:10.1007/978-3-031-33491-7_24.

11. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI ’99, page 173–186, USA, 1999. USENIX Association.
23:16 Minimal Variance Allocation of Rights for Blockchain Consensus

12 José Correa, Paul Gölz, Ulrike Schmidt-Kraepelin, Jamie Tucker-Foltz, and Victor Verdugo. Monotone randomized apportionment, 2024. URL: https://arxiv.org/abs/2405.03687, arXiv:2405.03687.

13 John R. Douceur. The sybil attack. In Peter Druschel, Frans Kaashoek, and Antony Rowstron, editors, *Peer-to-Peer Systems*, pages 251–260, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

14 Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. *Commun. ACM*, 61(7):95–102, 2018.

15 H. Fischer. *A History of the Central Limit Theorem: From Classical to Modern Probability Theory*. Sources and Studies in the History of Mathematics and Physical Sciences. Springer New York, 2010. URL: https://books.google.fr/books?id=v7kTwafIiPsC.

16 Robert W. Floyd. Nondeterministic algorithms. *J. ACM*, 14(4):636–644, oct 1967. doi: 10.1145/321420.321422.

17 Peter Gaži, Aggelos Kiayias, and Alexander Russell. Fait accompli committee selection: Improving the size-security tradeoff of stake-based committees. Cryptology ePrint Archive, Paper 2023/1273, 2023. URL: https://eprint.iacr.org/2023/1273.

18 Geoffrey Grimmett. Stochastic apportionment. *The American Mathematical Monthly*, 111(4):299–307, 2004. URL: http://www.jstor.org/stable/4145239.

19 Indranil Gupta, Robbert van Renesse, and Kenneth P. Birman. A probabilistically correct leader election protocol for large groups. In *Proceedings of the 14th International Conference on Distributed Computing*, DISC '00, page 89–103, Berlin, Heidelberg, 2000. Springer-Verlag.

20 Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. Eclipse attacks on Bitcoin's Peer-to-Peer network. In *24th USENIX Security Symposium (USENIX Security 15)*, pages 129–144, Washington, D.C., August 2015. USENIX Association. URL: https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/heilman.

21 @hildobby. ETH Stakers, February 2024. [Online; accessed 28. Feb. 2024]. URL: https://dune.com/queries/2394100/3927532.

22 Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Jonathan Katz and Hovav Shacham, editors, *Advances in Cryptology – CRYPTO 2017*, pages 357–388, Cham, 2017. Springer International Publishing.

23 Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. *ACM Trans. Program. Lang. Syst.*, 4(3):382–401, 1982.

24 Victor Lomné, Thomas Roche, and Adrian Thillard. On the need of randomness in fault attack countermeasures - application to aes. In *2012 Workshop on Fault Diagnosis and Tolerance in Cryptography*, pages 85–94, 2012. doi:10.1109/FDTC.2012.19.

25 Harry Markowitz. Portfolio selection. *The Journal of Finance*, 7(1):77–91, 1952. URL: http://www.jstor.org/stable/2975974.

26 S. Micali, M. Rabin, and S. Vadhan. Verifiable random functions. In *40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)*, pages 120–130, 1999. doi: 10.1109/SFFCS.1999.814584.

27 Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, Dec 2008. Accessed: 2015-07-01. URL: https://bitcoin.org/bitcoin.pdf.

28 Christopher Natoli and Vincent Gramoli. The balance attack against proof-of-work blockchains: The r3 testbed as an example, 2016. arXiv:1612.09426.

29 Kartik Nayak, Srijan Kumar, Andrew Miller, and Elaine Shi. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack. In *2016 IEEE European Symposium on Security and Privacy (EuroS&P)*, pages 305–320, 2016. doi:10.1109/EuroSP.2016.32.

30 Michael Neuder, Daniel J. Moroz, Rithvik Rao, and David C. Parkes. Selfish behavior in the tezos proof-of-stake protocol. *CoRR*, abs/1912.02954, 2019.
31 Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. *Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox*. Springer Publishing Company, Incorporated, 1st edition, 2019.

32 Do Hai Son, Tran Thi Thuy Quynh, and Le Quang Minh. Randao-based rng: Last revealer attacks in ethereum 2.0 randomness and a potential solution, 2024. URL: https://arxiv.org/abs/2403.09541, arXiv:2403.09541.

33 Harmony Team. Harmony: Technical whitepaper. URL https://harmony. one/whitepaper. pdf, 2018.

34 A. Voytishek and S. Rogasinskii. Minimum variance of a random integer value. *Numerical Analysis and Applications*, 2:216–219, 07 2009. doi:10.1134/S1995423909030021.

35 Toni Wahrstätter. Selfish mixing and randao manipulation - consensus - ethereum research. ethresear.ch/t/selfish-mixing-and-randao-manipulation/16081, 7 2023. (Accessed on 10/13/2023).

36 Jan Werner. *Risk Aversion*, pages 1–6. Palgrave Macmillan UK, London, 2016. doi: 10.1057/978-1-349-95121-5_2741-1.

37 Anatoly Yakovenko. Solana: A new architecture for a high performance blockchain. solana.com/solana-whitepaper.pdf. Accessed: 2-2-2024.

A LowVAlloc pseudocode

Algorithm 1 LowVAlloc pseudocode

1: **procedure** LOWVALLOC(s, R)
2:     **R** := Array(n)
3:     **C** := Array(n)
4:     r := 1
5:     **for** i ∈ N **do**
6:         **R**[r : r + ⌊(Rsᵢ)⌋] := i
7:         r := r + ⌊Rsᵢ⌋
8:         **C**[i] := Rsᵢ - ⌊Rsᵢ⌋
9:     **end for**
10:     **c** := C/sum(C)
11:     **for** r* ∈ [r, R] **do**
12:         **R**[r*] := random.index(c)
13:     **end for**
14:     **return** R
15: end procedure

▷ input: stake array, R
▷ initialize allocation array
▷ initialize residual claim array
▷ initialze right array index
▷ i gets ⌊Rsᵢ⌋ rights
▷ Normalized residual claims
▷ loop through residual claims
▷ IID draw from c
▷ Filled allocation array
## B MinVAlloc pseudocode

**Algorithm 2** MinVAlloc pseudocode

1: **procedure** MINVALLOC(s, R) ▷ input: stake array, R
2:     **R** := Array(n) ▷ initialize allocation array
3:     Shuffle(N, s) ▷ randomize the indexes
4:     **E** := R * s ▷ entitlements array
5:     **cE** := cumulative_sum(E) ▷ cE[i] = Σᵢⱼ=₁ E[j] with the convention cE[0] = 0
6:     u := random(0, 1) ▷ draw u, uniformly on (0,1)
7:     **for** i ∈ N **do**
8:         **R**[i] := [u + cE[i]] - [u + cE[i - 1]] ▷ rights are allocated in batches
9:         **end for**
10:        **end procedure**

## C Proof of Grimmett's allocation properties

**Proof.** First one could need to convince themselves that we allocate exactly R rights:

$$ 
\begin{aligned}
\sum_{i=1}^{n} \left[ \lfloor u + \sum_{k=1}^{i} E_k \rfloor - \lfloor u + \sum_{k=1}^{i-1} E_k \rfloor \right] &= \lfloor u + \sum_{k=1}^{n} E_k \rfloor - \lfloor u \rfloor \\
&= \lfloor u + R \rfloor \\
&= R
\end{aligned}
$$

The sum of all the allocated rights folds itself then we use the fact that the entitlements sum to the total number of rights $\sum_{k=1}^{n} E_k = R \sum_{k=1}^{n} s_k = R$, finally we use the facts that $u \in [0, 1)$ and R is an integer. Then we want to be sure that $R_i$ is an integer. As there is a difference between two floor values: it comes immediately. With these two points, we showed that we have an actual allocation of R rights.

We also want the quota constraint $\lfloor E_i \rfloor \le R_i \le \lfloor E_i \rfloor + 1$ and for that we use the fact that for all $a, b \in \mathbb{R}$:

$$ \lfloor a - b \rfloor \le \lfloor a \rfloor - \lfloor b \rfloor \le \lfloor a - b \rfloor + 1 $$

With this we have:

$$ 
\begin{aligned}
& \lfloor u + \sum_{k=1}^{i} E_k \rfloor - \lfloor u + \sum_{k=1}^{i-1} E_k \rfloor \le R_i \\
& \lfloor u + \sum_{k=1}^{i} E_k - u - \sum_{k=1}^{i-1} E_k \rfloor \le R_i \\
& \lfloor E_i \rfloor \le R_i
\end{aligned}
$$
and:

$$R_i \leq \lfloor u + \sum_{k=1}^{i} E_k \rfloor - \lfloor u + \sum_{k=1}^{i-1} E_k \rfloor$$

$$R_i \leq \lfloor u + \sum_{k=1}^{i} E_k - u - \sum_{k=1}^{i-1} E_k \rfloor$$

$$R_i \leq \lfloor E_i \rfloor + 1$$

Finally we need to make sure the fairness constraint holds, since the support of $R_i$ is of size two, we only need to check one probability:

$$\begin{aligned}
\mathbb{P}[R_i = \lfloor E_i \rfloor + 1] &= \mathbb{P}\left[\lfloor u + \sum_{k=1}^{i} E_k \rfloor - \lfloor u + \sum_{k=1}^{i-1} E_k \rfloor \lfloor E_i \rfloor + 1 \right] \\
&= \mathbb{P}[\lfloor u + E_i \rfloor - \lfloor u \rfloor = \lfloor E_i \rfloor + 1] \\
&= \mathbb{P}[\lfloor u + E_i \rfloor = \lfloor E_i \rfloor + 1] \\
&= \mathbb{P}[u \geq \lfloor E_i \rfloor + 1 - E_i] \\
&= \mathbb{P}[u \geq 1 - C_i] \\
&= C_i
\end{aligned}$$

Here we use the fact that since $u$ is drawn uniformly over $[0, 1)$, we can shift the constant of both floor values by $\sum_{k=1}^{i-1} E_k$. Then for the same reason $\lfloor u \rfloor = 0$. Then we rewrite the condition for $u$ to allow $\lfloor u + E_i \rfloor \lfloor E_i \rfloor$. The rest is a substitution and the use of $u$'s distribution. □

<figure><img src="image_6.png" /></figure>