Skip to main content
MathOverflow

Return to Answer

added 72 characters in body
Source Link
Faré
Faré
  • 99
  • 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, becausesince blockchain computations are literally billions of time more expansiveexpensive 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 one—hescore—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 he can prove is no worse than his score yet that no one else canwill be able to match with their own approximations. NoThanks 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$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.

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, because blockchain computations are literally billions of time more expansive than local computations. Happily, the winner only has to show 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 one—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 he can prove is no worse than his score yet that no one else can match. 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 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.

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.

Source Link
Faré
Faré
  • 99
  • 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, because blockchain computations are literally billions of time more expansive than local computations. Happily, the winner only has to show 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 one—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 he can prove is no worse than his score yet that no one else can match. 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 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.