Random numbers in a blockchain

[domob]

For certain potential blockchain applications (like online casinos or games), it is important to generate fair and unpredictable random numbers.  One way to do that is to base random numbers off the block hash; but in that situation, miners can manipulate the numbers by withholding blocks they don't like.  That costs them the block reward, but if they have sufficiently high stakes in a game, it may be worth it.  The incentive structure for this has even been analysed previously in detail, see http://www.ledgerjournal.org/ojs/index.php/ledger/article/view/29.

One way to overcome this issue for something like a two-player game (think a casino) is to use hash commitments.  For instance, in a roulette game, the player can submit H(nonce | bet) in a transaction that also pays the betting amount.  H is some secure hash function, nonce is a random number chosen by the player and bet is the bet (e.g. "red" or "black").  Then the actual result of the draw is computed from the block hash the transaction is confirmed in, but at this point, the miner does not know the actual bet and thus cannot withhold "bad" blocks.  Afterwards, the player has some time (e.g. 100 blocks) to submit the preimage nonce and bet to claim a win.  If they don't submit or submit a losing bet, then the casino gets the money instead.

This system is unfortunately not suited (at least not without major difficulties) to things like multiplayer game worlds, e.g. random numbers for a game like Huntercoin.  Here, I want to sketch an idea for preventing block withholding for such games in a different way.

The basic idea is to allow anyone (players and other users of the blockchain) to bet directly on block hashes, against the miners but giving the miners a slight "house edge".  This means that honest miners which produce unpredictable and truly random block hashes are (on average) rewarded, while miners that have a skewed distribution (e.g. because they manipulate random numbers) can be punished under the right circumstances.

For instance, let's consider a very simplified situation, that can be generalised for a real application:  Anyone can submit transactions to the blockchain that contain a hashed bet H(nonce | height | bit), predicting what the least-significant bit of the block hash at a (future) height will be.  They can bet an amount N of their choosing, perhaps within certain limits.  If they later reveal their bet and it is correct, they get N * (1 - eps) from the miner that mined that block and their bet back, where eps > 0 is some small parameter.  If they lost or do not reveal, then the miner of the block gets their bet of N.

This means that honest miners win on average, although the scheme of course increases risk and variance of miners.  Players that actually participate also in a casino game based on the least-significant bit of a block hash can hedge their bet, but if they do, they will just lose for sure.

However, if a player or other user monitoring the blockchain has reasons to believe that miners are manipulating the random numbers, they can make money
and punish miners if they are right.  This should serve to rectify miner incentives.

Of course, there are a lot of open questions and potential issues with this proposal.  A non-exhaustive list of issues that I can think of for now is this:

• As this increases risk for miners and their variance (even if honest miners win on average), it may lead to even more centralisation or just discourage miners in general.
• Miners may try to simply not confirm any bets to avoid any risk (or being caught if they manipulate hashes).  But if there are multiple miners on the blockchain and users can bet on arbitrary block heights (not just the "next" block), there may always be a chance to get a bet confirmed by some miner, in particular when combined with additional rewards for the confirming miner or high transaction fees.
• There needs to be an in-depth analysis of the game theory underpinning such a system to see how much the mining incentives are really "fixed" by that (depending also, of course, on the limits to bets and the constant eps).

Nevertheless, I think this idea might be interesting and promising, so I would like to get early feedback on it before working it out in more detail and with proper maths.  Is there any fundamental flaw that I overlooked, or can such a system be made to work?

[Bitcoin Gambling]

The basic idea is to allow anyone (players and other users of the blockchain) to bet directly on block hashes, against the miners but giving the miners a slight "house edge".  This means that honest miners which produce unpredictable and truly random block hashes are (on average) rewarded, while miners that have a skewed distribution (e.g. because they manipulate random numbers) can be punished under the right circumstances.

For last 2 years, we are running a game @ https://www.chain-bet.com, which is based on a similar concept as described by you. Feel free to check it out and let us know your opinion about it...

[domob]

The basic idea is to allow anyone (players and other users of the blockchain) to bet directly on block hashes, against the miners but giving the miners a slight "house edge".  This means that honest miners which produce unpredictable and truly random block hashes are (on average) rewarded, while miners that have a skewed distribution (e.g. because they manipulate random numbers) can be punished under the right circumstances.

For last 2 years, we are running a game @ https://www.chain-bet.com, which is based on a similar concept as described by you. Feel free to check it out and let us know your opinion about it...

Interesting, thanks for the pointer!  However, the game you run is basically what is the "initial game" (online casino) in my post, right?  I.e. players just bet against you and not the miners (which is the point of my idea).  That means that your system actually is (in theory) susceptible to miners manipulating, unless you use a commit-reveal scheme as described in my post.  So what I describe would help your users get more fair play against miners.

[domob]

I've now done some preliminary game-theoretic analysis and calculations about this idea.  I will write it all up nicely in a paper when I find time and have done more detailed calculations, but it seems to me that these are the qualitative (and promising) results:

For simplicity, we assume that we have just one miner (or alternatively, that all miners behave in the same way, which makes sense from a rational game-theoretic point of view under certain assumptions).  In addition to a block reward of 1, certain block hashes (with some probability p) yield the miner an "extra income" of value w.  This can be thought of, for instance, as some beneficial event in a game that yields extra fees or winnings to a miner who also plays in the game.  (Could be a "disaster" in Huntercoin, for instance, or something like that.)

On the other hand, as stated in the original post, "the general public" has the ability to bet against miners.  This means that they can wager some amount b that this event does occur - because if it occurs "too often", then the miner may be manipulating the block hashes.  Taking into account a small but positive house edge eps, this means that this user wins (1-eps)*b from the miner with probability p (when the miner wins the extra w), and loses b to the miner in the other cases.

The miner has now the choice of whether or not they want to withhold blocks.  If they choose to be fully honest, they will produce "winning" blocks with probability p and "losing" blocks with (1-p).  If they are "fully manipulative" and always withhold blocks until they win, they will only produce winning blocks.  They can also choose to be "partially honest", with some probability (1-h) of withholding losing blocks.  This gives a mixed strategy for the miner.

The expected payout of the user is simply proportional to b.  It is positive for h=0 and negative for h=1.  Neither of these cases can be equilibria of the game, since in the first case, as long as b is large enough, the user wins money from the miner and thus the miner has an inventive to switch to h=1.  For the latter, the user always loses money (on average) due to the "house edge", and thus has to choose b=0.  But in that case, the miner has nothing to lose by manipulating blocks, and thus h=1 is not optimal.

Thus, the game must have an equilibrium in mixed strategies with h strictly between 0 and 1, such that the expected payout of the betting user is exactly zero.  The exact value of h (and thus the "honesty of the miner") depends on the parameters like w, eps and b.  This means that the betting scheme described in the original post leads to a game-theoretic equilibrium where the miner still withholds blocks from time to time, but is overall much more honest than without the scheme.  The betting users come out exactly at zero, since the miner's house edge is balanced by the (slight) manipulation of the miner.  Both honest and manipulating miners make a small extra profit, the former due to the house edge and the latter due to their manipulation in games, both of the same value.  In total, this sounds like an interesting scheme.  (But I will do more detailed calculations and a proper write up of the math later.)

EDIT: The full analysis is now finished, and can be found in the paper: http://arxiv.org/abs/1901.06285

[Piggy]

Even if this approach is theoretical, i think would be interesting to pick a blockchain and check how often a block is mined by the same entity, perhaps in both ethereum and bitcoin.
This would help to understand the potential of some miner to pull something like this.

Just to be clear, when you are talking about the miner withholding blocks, this imply the miner having always to place a bet before start mining a block, without any guarantee he will be able to mine it (and manipulate the result), correct?

Intuitively, I think a very simple solution to dissuade the miners from withholding blocks, may be stopping accepting bets for any possible outcome when the hypothetical winning amount is less or equal the block reward.

[mixoftix]

For certain potential blockchain applications (like online casinos or games), it is important to generate fair and unpredictable random numbers.  One way to do that is to base random numbers off the block hash; but in that situation, miners can manipulate the numbers by withholding blocks they don't like.

while your source of randomization in each block finally maintains by 1 miner - the winner of the block - you can not trust the generated values after block creation. one miner with proper processing power always could manipulated the result.

Nevertheless, I think this idea might be interesting and promising, so I would like to get early feedback on it before working it out in more detail and with proper maths.  Is there any fundamental flaw that I overlooked, or can such a system be made to work?

you may find this (under development) document useful about a new PROOF model that I am working on it, the proof-of-consistency which uses the Dither Effect as a controlled noise to the entire process of transaction and reward fee calculation. in PoC miners work separately in block content (transaction level), rather than block header - so none of them could do anything to generate a target value in hashes:

https://bitcointalk.org/index.php?topic=5066624.0

this may help you better analysis the current situation of your idea with classic blockchains.

UPDATE:
take a look at the new data structure of block content.

[aliashraf]

OP!
Suppose, we are running a casino and regularly accept bets from any number of players. In each round:
1-We choose a secret and publish its hash in our site.
2-We define a multi-option betting schema for players to bet on.
3-Players make bets by putting in their wagers but instead of disclosing the option they have chosen, they give us the hash of a formatted message that contains the option number, a time stamp and an arbitrary nonce.
4- After each n blocks we disclose our secret and trim it with m last block hashes to generate a new hash which decides about each option deterministically.
5- To claim their prize, players have to disclose the original messages containing their choices, consistent by hashes they have provided in the third phase, otherwise they lose their wagers.

As you may notice, this scenario is safe against block withholding as  nobody is aware of what a prefered hash looks like.

Are you discussing radically different use cases?

[Piggy]

As you may notice, this scenario is safe against block withholding as  nobody is aware of what a prefered hash looks like.

There would just be the case where the miner and the house are the same entity, in that case it could pretty much decide the winning result.

[mixoftix]

5- To claim their prize, players have to disclose the original messages containing their choices, consistent by hashes they have provided in the third phase, otherwise they lose their wagers.

in the case of dictionary attack, players also need to strength their submitted hash values with SALT - at least.
encryption + padding could be a better option for step 5.

[aliashraf]

As you may notice, this scenario is safe against block withholding as  nobody is aware of what a prefered hash looks like.

There would just be the case where the miner and the house are the same entity, in that case it could pretty much decide the winning result.

Nop. The house is not aware of the bets, only their hashes. When the block hash comes out, the house discloses its secret, now it is up to players to prove their bets which they have committed to before the disclosure.

That said, this schema works only for games that satisfy two following conditions:
1- The betting options cover all the probability space.
2- There is zero or neglectable chance for the house to guess the distribution of bets (like which options are more or less favorable for players to put their bets on).

[Piggy]

Also the probability of each winning outcome should be the same as well, otherwise if the house would be able to "control" the extractions with help of the miner, it could obtain an unfair advantage, even if it's not aware of how the players are betting.

[aliashraf]

Also the probability of each winning outcome should be the same as well, otherwise if the house would be able to "control" the extractions with help of the miner, it could obtain an unfair advantage, even if it's not aware of how the players are betting.

Not exactly necessary:
When the probabilities are not the same for two outcomes, players expect rewards to be proportionally allocated, so we rather need to have the betting conditions verifiably fair. i.e. less probable options more prize and vice versa.

[domob]

For certain potential blockchain applications (like online casinos or games), it is important to generate fair and unpredictable random numbers.  One way to do that is to base random numbers off the block hash; but in that situation, miners can manipulate the numbers by withholding blocks they don't like.

while your source of randomization in each block finally maintains by 1 miner - the winner of the block - you can not trust the generated values after block creation. one miner with proper processing power always could manipulated the result.

Yes, exactly - that's the problem that my proposal tackles.

Suppose, we are running a casino and regularly accept bets from any number of players. In each round:
1-We choose a secret and publish its hash in our site.
2-We define a multi-option betting schema for players to bet on.
3-Players make bets by putting in their wagers but instead of disclosing the option they have chosen, they give us the hash of a formatted message that contains the option number, a time stamp and an arbitrary nonce.
4- After each n blocks we disclose our secret and trim it with m last block hashes to generate a new hash which decides about each option deterministically.
5- To claim their prize, players have to disclose the original messages containing their choices, consistent by hashes they have provided in the third phase, otherwise they lose their wagers.

Are you discussing radically different use cases?

That's what I mentioned as "hash commitment" schemes in the OP.  This certainly works for the classical casino usecase, and has in fact been used since Satoshi Dice as far as I know (and perhaps before that).

But for some usecases, this approach doesn't work (or not easily) - for instance, if you have a decentralised game world where you need random numbers to decide on certain events, but the set of players (who are currently online) is not well-known.  In that case, you do not know for sure from whom to expect hash commitments and/or cannot make sure that everyone of them reveals afterwards.  (And that, in turn, opens another can of worms where miners can just censor certain revealing transactions to control the random numbers again.)  Take a look at disasters in Huntercoin for an example of such a situation.

[aliashraf]

For certain potential blockchain applications (like online casinos or games), it is important to generate fair and unpredictable random numbers.  One way to do that is to base random numbers off the block hash; but in that situation, miners can manipulate the numbers by withholding blocks they don't like.

while your source of randomization in each block finally maintains by 1 miner - the winner of the block - you can not trust the generated values after block creation. one miner with proper processing power always could manipulated the result.

Yes, exactly - that's the problem that my proposal tackles.

Suppose, we are running a casino and regularly accept bets from any number of players. In each round:
1-We choose a secret and publish its hash in our site.
2-We define a multi-option betting schema for players to bet on.
3-Players make bets by putting in their wagers but instead of disclosing the option they have chosen, they give us the hash of a formatted message that contains the option number, a time stamp and an arbitrary nonce.
4- After each n blocks we disclose our secret and trim it with m last block hashes to generate a new hash which decides about each option deterministically.
5- To claim their prize, players have to disclose the original messages containing their choices, consistent by hashes they have provided in the third phase, otherwise they lose their wagers.

Are you discussing radically different use cases?

That's what I mentioned as "hash commitment" schemes in the OP.  This certainly works for the classical casino usecase, and has in fact been used since Satoshi Dice as far as I know (and perhaps before that).

But for some usecases, this approach doesn't work (or not easily) - for instance, if you have a decentralised game world where you need random numbers to decide on certain events, but the set of players (who are currently online) is not well-known.  In that case, you do not know for sure from whom to expect hash commitments and/or cannot make sure that everyone of them reveals afterwards.  (And that, in turn, opens another can of worms where miners can just censor certain revealing transactions to control the random numbers again.)  Take a look at disasters in Huntercoin for an example of such a situation.

I think there is no need for miners to be somehow forced to gamble part of their rewards. I thought you are worried about multiplayer games but it looks like you are proposing kinda houseless games, or to be more correct, all-miners-are-house games.

For ordinary games in which the house is voluntarily proposing a betting schema and players put their bets and play, my scenario is provably secure against blockwithholidng, given they satisfy two conditions:
1- The probability space is covered by the betting schema (there is an option for every outcome)
2- Options are relatively fair, i.e. players are not tempted to be inclined toward or against specific option(s).

EDIT:
In my proposal, players put their wagers in and it is their responsibility to prove their bet, not the house. I have set free miners from being involved in the game by the house secret being padded to the block hash to determine the outcome, they wouldn't be able to collude because they are not aware of the bets, no incentive for withholding the block. Players won't collude with miners as they are not aware of the secret and hence the outcome.

[domob]

I think there is no need for miners to be somehow forced to gamble part of their rewards. I thought you are worried about multiplayer games but it looks like you are proposing kinda houseless games, or to be more correct, all-miners-are-house games.

For ordinary games in which the house is voluntarily proposing a betting schema and players put their bets and play, my scenario is provably secure against blockwithholidng, given they satisfy two conditions:
1- The probability space is covered by the betting schema (there is an option for every outcome)
2- Options are relatively fair, i.e. players are not tempted to be inclined toward or against specific option(s).

EDIT:
In my proposal, players put their wagers in and it is their responsibility to prove their bet, not the house. I have set free miners from being involved in the game by the house secret being padded to the block hash to determine the outcome, they wouldn't be able to collude because they are not aware of the bets, no incentive for withholding the block. Players won't collude with miners as they are not aware of the secret and hence the outcome.

Well, I think you mixed up my proposed solution with the problem.  I am indeed interested in multiplayer games, where the simple commit-reveal scheme (as proposed by you and also already used by e.g. Satoshi Dice) does not work.  The game where miners "are the house" is just my proposed solution for how secure random numbers for multiplayer games can be implemented.  As you say, it is not ideal to add extra risk to miners - but it is so far the best solution I've come up with.

If you have a better idea for how to generate secure random numbers in a multiplayer setting, I'm very happy to hear about it!

[mixoftix]

while your source of randomization in each block finally maintains by 1 miner - the winner of the block - you can not trust the generated values after block creation. one miner with proper processing power always could manipulated the result.

Yes, exactly - that's the problem that my proposal tackles.

in the case of missing something, I need to mention it once again: "instead of using hash values of block header, use hash values of block content - along merkle-tree for example". in fact setting up that amount of data (in block content) to export an exact amount in output is really a power / time consuming process. I think this is not applicable for a miner at all and could provide a good randomness level..

UPDATE 1:
with this approach, you are not going to pick only one hash value of the block in its header. for example, in each round of game, you can express the next combination of transactions:

round 45: HASH(hash_tx_2,hash_tx_8,hash_tx_6,hash_tx_9,hash_tx_3) of block 238712
round 46: HASH(hash_tx_5,hash_tx_9,hash_tx_7,hash_tx_2,hash_tx_7) of block 238713
round 47: ...

now, your game also involves in the process and a miner entity can't set up anything alone. to gain the maximum protection, add some rules into the process above, for example for round 47, add 2 columns above and subtract them from 10, if the output is bigger than 9:

col-1: (2+5) = (7) = 7
col-2: (8+9)-10 = (17)-10 = 7
col-3: (7+6)-10 = (13)-10 = 3
col-4: (9+2)-10 = (11)-10 = 1
col-3: (3+7)-10 = (11)-10 = 1

round 47: HASH(hash_tx_7,hash_tx_7,hash_tx_3,hash_tx_1,hash_tx_1) of block 238714

UPDATE 2:
also mix the HASH of previous round in the process of current round (identifying the position of columns).. this makes them fully unpredictable..

[domob]

in the case of missing something, I need to mention it once again: "instead of using hash values of block header, use hash values of block content - along merkle-tree for example". in fact setting up that amount of data (in block content) to export an exact amount in output is really a power / time consuming process. I think this is not applicable for a miner at all and could provide a good randomness level..

I may be missing something, but how is that solving the problem?  As long as you base random numbers on something derived from the block (using whatever exact function), the miner is always in the position to know the outcome ahead of anyone else, and to withhold a block they don't like.  It is also easy for them to "roll again" after reordering the transactions, introducing transactions of their own or something like that - as far as I can tell, that will also work with your scheme.

So how do you think your proposal protects against miners withholding blocks?

[BitCoinDream]

in the case of missing something, I need to mention it once again: "instead of using hash values of block header, use hash values of block content - along merkle-tree for example". in fact setting up that amount of data (in block content) to export an exact amount in output is really a power / time consuming process. I think this is not applicable for a miner at all and could provide a good randomness level..

I may be missing something, but how is that solving the problem?  As long as you base random numbers on something derived from the block (using whatever exact function), the miner is always in the position to know the outcome ahead of anyone else, and to withhold a block they don't like.  It is also easy for them to "roll again" after reordering the transactions, introducing transactions of their own or something like that - as far as I can tell, that will also work with your scheme.

So how do you think your proposal protects against miners withholding blocks?

There is an economic incentive for the miners NOT to withhold a block. That's how the'll lose the block reward. Have you considered this?

[domob]

in the case of missing something, I need to mention it once again: "instead of using hash values of block header, use hash values of block content - along merkle-tree for example". in fact setting up that amount of data (in block content) to export an exact amount in output is really a power / time consuming process. I think this is not applicable for a miner at all and could provide a good randomness level..

I may be missing something, but how is that solving the problem?  As long as you base random numbers on something derived from the block (using whatever exact function), the miner is always in the position to know the outcome ahead of anyone else, and to withhold a block they don't like.  It is also easy for them to "roll again" after reordering the transactions, introducing transactions of their own or something like that - as far as I can tell, that will also work with your scheme.

So how do you think your proposal protects against miners withholding blocks?

There is an economic incentive for the miners NOT to withhold a block. That's how the'll lose the block reward. Have you considered this?

Yes sure, that's trivial - but there may be cases where the potential gain for withholding the block and thus manipulating a game (e.g. high-stake gambling based on the block hash) is higher than the block reward.  This has been analysed in detail in the Ledger paper I've linked to in the OP (not by me).

[aliashraf]

There is an economic incentive for the miners NOT to withhold a block. That's how the'll lose the block reward. Have you considered this?

Yes sure, that's trivial - but there may be cases where the potential gain for withholding the block and thus manipulating a game (e.g. high-stake gambling based on the block hash) is higher than the block reward.  This has been analysed in detail in the Ledger paper I've linked to in the OP (not by me).

It looks to me somewhat paradoxical:

Your proposal is about a hypothetical blockchain in which miners are discouraged from block withholding because of a punishment mechanism but what this mechanism could ever be? Obviously there is nothing at stake for a miner other than the block reward. But if block reward is enough incentive, how is it possible for a block withholding attack with higher stakes involved to be mitigated at all, without hash commitment (bets not being disclosed by players)?
And with hash commitment for high stake games, how does it help to use your schema instead of what I've proposed earlier?

Please note: Miners in a PoW blockchain are pseudonymous and have no obligation to re-use their wallet addresses in coinbase.