The sortition algorithm is an important part of the Pactus blockchain, responsible for the fair, transparent and random selection of validators to join the committee. It utilizes a Verifiable Random Function, or VRF for short, to generate a verifiable random number.
The generated random number should be in the range of 0 to the total staked coins. If validators can prove that their generated number is less than their stake, they can send the sortition transaction. Once a sortition transaction is included in a block, the validator will join the committee, and the oldest validator in the committee will leave it.
Verifiable Random Function is a pseudo-random function that the owner of key \(s\) at any point of \(x\) can evaluate \(v=f_s(x)\) and also provides \(proof_x\) efficiently proving that \(v\) is correct. We call such a mathematical object a verifiable pseudo-random function, VRF for brevity 1.
Pactus uses the BLS signature scheme as the source of VRF. Since BLS signatures are unique, the hash of a BLS signature can be used to produce a secure and verifiable random number.
The VRF takes three parameters: the sortition seed, secret key of the validator, and the total stake of the blockchain. Once the VRF is executed, it produces an index with a proof. The index is a number between zero and the total staked coins, and the proof allows validators to verify the correctness of the generated index.
The pseudocode below demonstrates the evaluation of the VRF for the sortition algorithm:
\[\begin{align*} & \textbf{function} \ VRF(sk, seed, total\_stake) \\ & \qquad pk \gets P_{BLS}(sk) \\ & \qquad proof \gets S_{BLS}(sk, seed || pk) \\ & \qquad rnd \gets H(proof) \\ & \qquad index \gets \frac{(rnd \times total\_stake)}{2^{256}} \\ & \qquad \\ & \qquad \textbf{return} \ index, proof \\ & \textbf{end function} \end{align*}\]where:
To verify a sortition proof, both the validator’s public key and stake are required:
\[\begin{align*} & \textbf{function} \ verifyVRF(pk, seed, proof, stake, total\_stake) \\ & \qquad \textbf{if} \ V_{BLS}(pk, seed || pk, proof) = True \ \textbf{then} \\ & \qquad \qquad rnd \gets H(proof) \\ & \qquad \qquad index \gets \frac{(rnd \times total\_stake)}{2^{256}} \\ & \qquad \\ & \qquad \qquad \textbf{return} \ index \leqslant stake \\ & \qquad \textbf{else} \\ & \qquad \qquad \textbf{return} \ False \\ & \qquad \textbf{end if} \\ & \textbf{end function} \end{align*}\]where:
There is no need to send \(index\) alongside \(proof\) because the result should be less than the validator’s stake, and the validator’s stake is known at each block.
The sortition algorithm relies on a random and publicly verifiable seed that cannot be manipulated by adversaries. Otherwise, adversaries may select a seed that favors the selection of corrupt users.
To prevent this, the BLS signature scheme is used to generate the sortition seed. Since BLS signatures are unique and deterministic, adversaries cannot generate more than one valid signature per block. In each block, the block proposer generates a new sortition seed based on the previous seed using the following function:
\[\begin{align*} & \textbf{function} \ generateSeed(sk, prev\_seed) \\ & \qquad \textbf{return} \ S_{BLS}(sk, H(prev\_seed)) \\ & \textbf{end function} \end{align*}\]Since the proposer’s public key is known, the seed for the next block can be easily verified. If the seed is invalid, the proposed block will be rejected. The verification function is as follows:
\[\begin{align*} & \textbf{function} \ verifySeed(pk, prev\_seed, seed) \\ & \qquad \textbf{return} \ V_{BLS}(pk, H(prev\_seed), seed) \\ & \textbf{end function} \end{align*}\]The sortition seed for the genesis block set to 0.
The total staked coin in each block is calculated by summing the staked coins of all active validators. An active validator is a validator that has not yet unbonded.