Lottery in O(1) per participant

Question

Goal: implement in $O(1)$ per participant a lottery where each participant has some large number of tickets, and the best (e.g. least) one wins, without actually burning electricity in proportion to the number of tickets. Thus, enable blockchains to burn less electricity.

A. Given a random distribution $X$ of numbers between $0$ and $1$, compute the distribution $Y_n = \min(X_0..X_{n-1})$ of the minimum of $n$ independent variables each with the same distribution as $X$.

Up to a smooth change of variable, let's assume $X$ uniformly distributed for now, with $P(X \le x) = x$. Let $Q_n(x) = P( Y_n \le x )$. Then $Q_0(x) = 0$ (because $\min$ of the empty set is the top value), and $Q_{n+1}(x) = P(X_n \le x \wedge Y_n \le x)$. Since the events are independent, $Q_{n+1}(x) = x + Q_n(x) - x Q_n(x) = x + (1-x) Q_n(x)$. This is iterating an affine function, thus $Q_n(x)=x (1-(1-x)^n)/(1-(1-x))$. Conclusion: $Q_n(x) = 1-(1-x)^n$.

B. Supposing that useful values of $n$ (number of tickets) will be in a given range that is big enough (say less than $M \approx 10^m$ for $3 \le m \le 30$), find an initial distribution $X$ such that it is easy to algorithmically generate in $O(1)$ operations a PRNG approximating $X_n$ given $n < M$, and such that $X_n$ is as uniform as possible for a given parameter $n \approx N$, and/or such that not too many digits are necessary to pick a winner between about $M/N$ participants.

Is there an efficient way to pick a number at random according to this distribution for a very large $N$ within a few order of magnitudes of $M$, and/or a change of variable that will make it possible to approximate the drawing of winning tickets according to this method?

Answer 1

Let's assume the blockchain has some kind of working VRF mechanism (Verifiable Random Function), whereby a pseudo-random number can verifiably be agreed upon in a way that not any participant can control. This VRF is used to pick a seed. Then, every participant is assigned a 256-bit number based on the hash of this seed and their address, which is pseudo-random enough with a uniform distribution.

Assuming the participant possesses $N$ tokens, his random number is normalized to a real being 0 and 1, yields a number $x$ that is uniform in the distribution of the user, such that $1-(1-x)^{1/n}$ is his score in everyone's distribution. The median score for that user is $\log 2/n$. Now, since the blockchain data is public, everyone can compute everyone else's score, too, and determine who's scoring second.

Everyone then knows the winner, but we have to prove it to the blockchain in a way that can be verified with as few computations as possible, since blockchain computations are literally billions of time more expensive than local computations. Happily, the winner only has to show a computable approximation his score to the blockchain, making a claim, and depositing some collateral as he does. The claimant then challenges anyone else to show a better score—he knows they won't be able to, and he knows how far in the Taylor expansion of his own score to go to show a number no one else will be able to match with their own approximations. Thanks to the collateral, no one is interested in lying—that would be expensive for no reward. Also, with very high probability, the best score will be far enough from $1$ and close enough to $0$ that this best Taylor expansion will converge in very few steps.

As a caveat, multiple precision arithmetics is necessary, even if using e.g. 256-bit numbers like Ethereum, to compute the terms of the Taylor expansion. Indeed, we need enough spare bits to avoid with very high probability collisions between the best and second best numbers.