The scheme of selecting a Proposer and Validators based on PoS can be considered as random sampling from a group with a discrete probability distribution.

• S: the total amount of issued stake
• s_i: the stake amount held by a candidate i (Σ s_i = S)

Random Sampling based on Categorical Distribution

For simplicity, here is an example in which only a Proposer is selected from candidates with winning probability of p_i = s_i / S.

First, create a pseudo-random number generator using vrf_hash as a seed, and determine the threshold threshold for the Proposer. This random number algorithm should be deterministic and portable to other programming languages, but need not be cryptographic.

val rand = new Random(vrf_hash)
val threshold:Long = (rand.nextDouble() * S).toLong

Second, to make the result deterministic, we retrieve the candidates sorted in descending stake order.

val candidates:List[Candidate] = query("SELECT * FROM candidates WHERE stake > 0 ORDER BY stake DESC, public_key");

Finally, find the candidate hit by the arrow threshold of Proposer.

var proposer = candidates.last
var cumulativeStakeAmount:Long = 0
for(c <- candidates){
  if(cumulativeStakes <= threshold && threshold < cumulativeStakes + c.stake){
    proposer = c
    break
  }
  cumulativeStakes += c.stake
}

This is a common way of random sampling according to a categorical distribution by using a uniform random number. Similar to throwing an arrow on a spinning darts whose width is proportional to the probability of each item.

Selecting of a Consensus Group

By applying the above, we can select a consensus group consisting of one Proposer and V Validators. This is equivalent to performing V+1 categorical trials, which is the same as a random sampling model with a multinomial distribution. It's possible to illustrate this notion using a multinomial distribution demo I created in the past. This is equivalent to a model that selects a Proposer and Validators when K is the number of candidates and n=V+1.

As an example of intuitive code, I expand categorical sampling to multinomial.

val thresholds = new Array[Long](V + 1)
for(i <- 0 until thresholds.length){
  thresholds(i) = (rand.nextDouble() * S).toLong
}

var cumulativeStakes:Long = 0
val winner = new Array(thresholds.length)
for(c <- candidates){
  for((t, i) <- thresholds.zipWithIndex){
    if(cumulativeStakes <= t && t < cumulativeStakes + c.stake){
     winner(i) = c
    }
  }
  cumulativeStakes += c.stake
}
val proposer = winner(0)
val validator1 = winner(1)
...

In the above steps, a single candidate may assume multiple roles. If you want to exclude such a case, you can remove the winning candidate from the candidates. In this case, the thresholds must be recalculated because the total S of the population changes.

Computational Complexity

1. typical sort algorithm: O(N log N), where N is the number of all candidates.
2. generating random numbers: O(V + 1).
3. winner extraction: O(N × (V+1)), is the worst case. In many cases, loops can be interrupted.

The computational complexity is mainly affected by the number of candidates N. There is room for improvement by remembering the list of candidates that have been sorted by the stake.