How to generate weighted random number using Chainlink VRF

[yashm001]

Hey everyone!

I am working on a smart contract which involves selecting a random address from an array. I am using Chainlink VRF for generating random number and select the address at that particular index.

But the twist here is that, there is a selection probability associated with every address.

I read the chainlink VRF docs but couldn't find a work around. Can anybody please help me out here?

[PatrickAlphaC]

Hello! This would be a better stack exchange ETH question since it doesn't apply to this course. Could you make this question there?

[Ju-Rien]

Although @PatrickAlphaC asked that you send this question on stack exchange ETH, I still have an answer for you. @yashm001, could you provide the link to your renewed question on stack exchange so that I can answer there too?

What you are asking for is weighted uniform sampling. Let's look at a small example in order to understand our problem, starting with symbolic math and then ending with some code.

We have 4 addresses, $x_1$, $x_2$, $x_3$ and $x_4$, respectively weighted with probabilities
$$p_1 = 0.10, \quad p_2 = 0.25, \quad p_3 = 0.40 \quad \text{ and } \quad p_4 = 0.25.$$ If we can generate a pseudo-random number $t$ between 0 and 1, the sampling procedure is quite straightforward. It ends up being a simple switch case.

• If $t \in [0, 0.1]$, then sampled address is $x_1$.
• If $t \in (0.1, 0.35]$, then sampled address is $x_2$. The $0.35$ is the sum of $p_1 + p_2$.
• If $t \in (0.35, 0.75]$, then sampled address is $x_3$, and, you guessed it,
• if $t \in (0.75, 1]$, then sampled address is $x_4$.

Now, in Solidity, we try not to work with floating point numbers, to avoid rounding numbers inadvertently.
To the best of my knowledge, Chainlink VRF returns "words" which are verifiable pseudo-random uint256 between 0 and $2^{256}-1$.

There are two ways to approach this. Either you bring your probabilities $p_1$, $p_2$, etc. to a scale of uint256, i.e. $p_i * 2^{256}$, or you bring both the word and probabilities to number of decimals that fits your needs. I will only illustrate the first case, as it is the most precise one in terms of rounding errors.

In the first case, you could do the following (not gas optimal and hard coded, but for the sake of clarity):

function wSampling(uint256 randomWord) internal view returns (address) {
    address x1 = 0x//someaddress;
   // ...
    address x4 = 0x//someOtheraddress;

// Our 2 ** 256 - 1.
    uint256 MAX_INT = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff; // "f"*64 ;)

// Here, we have to understand that by dividing by 4 or 10, we are losing some precision, 
// since it's a uint division and 2 ** 256 - 1 is not divisible by 2.
    uint256 p1 = MAX_INT/10; // 0.10
    uint256 p2 = MAX_INT/4; // 0.25
    uint256 p3 = (MAX_INT/10)*4; // 0.40
    uint256 p4 = MAX_INT/4; // 0.25

    if( randomWord <= p1) { return x1; }
    if( randomWord <= p1 + p2) { return x2; }
    if( randomWord <= p1 + p2 + p3) { return x2; }
    else { return x4;}
}

It's important to note here that since $2^{256} - 1$ is not divisible by $2$ (which is a factor of $10$ and $4$), we lose some precision in the integer division, since it is always rounded down. This leads to $x_4$ having very slightly more chance to be picked that it should be, but on the level of $\approx 10^{-77}$. In this case, I think we can say that it is negligible.

[PatrickAlphaC]

dope :)