Topic: Random numbers in a blockchain - page 2. (Read 881 times)

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.

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.

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).

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.

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.

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?

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.


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://bitcointalksearch.org/topic/shahin-go-round-proof-of-consistency-poco-and-the-ringchain-5066624

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.

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.

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

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.

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...

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?