Bitcoin Forum

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?

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.

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

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.

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

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?

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.

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.

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

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.

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


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.

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!

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

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

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.

How would it help at all? If there is any block withholding threat, its level will remain unchanged no matter how the outcome is calculated, the miner has always the required advantage for such an attack because of his premium.

As I've mentioned above-thread, unlike what op suggests, a well designed multiplayer hash commitment game is safe against block withholding and if somehow a miner/colluder could evaluate the trade-off between the outcome and the block reward, e.g there is a high stake bet and he is somehow aware of the plain text behind the player's commitment hash, theoretically there exists no provably secure solution to void miner's premium in being aware of  his mined block and his freedom to relay it or not.

Edit
I guess it would be easy to prove the above assertion mathematically.

Could you please explain how Chain-Bet.com is susceptible to miners manipulation? I believe, if it were practically possible, we would have been out of business by now.

you know, many years ago that I was working as a freelance programmer, I had received a job from a guy in Vegas about a gambling web site.. however we always could find pretty good sources of random number generation, but in business world the project owner really needed to show his customers that he was providing the randomness to his job from sources that manipulating them is impossible and they could also check it - so I suggested him to use the hash output of news feed of famous news agencies, so all customers could check it independently. BUT, there always should be a limitation in gambling/bet solutions that work with such trustful sources, because when the amount of gambling goes above the ETHICS that a journalist must abide by, you may receive garbage news in specific period of time, just to win the prize. we still have the same situation in this topic - nothing could changes ever.


this is the key point. the block hash is a value that generates based on MANIPULATION of its related NONCE value, but hash values of block content naturally generate from hash algorithm. we know that a miner still could find his own order of his reserved transactions, but he still has to keep and follow a format in plaintext of raw transaction - not something unruly like nonce. so always work with content of a winner block. obviously this could not prevent the withholding problem, but prevents the manipulation to have a specific winner block.


aim at preventing a miners "roll again" or "withholding" of a block, you still need to have "a good timing" and keep "the confirmation rule". for example (as ETFBitcoin mentioned it too), you need to end your bet session (that comes from calculation rounds) for the next 3rd block when the next 1st block is still unknown (which kills the time for a miner to manipulate an output) and also wait for introducing the bet winner after the next 20th block (prevent roll backing):

round 341: HASH(hash_tx_2,hash_tx_8,hash_tx_6,hash_tx_9,hash_tx_3) of block 238697 [you end bet session for round 343]
round 342: HASH(hash_tx_2,hash_tx_8,hash_tx_6,hash_tx_9,hash_tx_3) of block 238701
round 343: HASH(hash_tx_5,hash_tx_9,hash_tx_7,hash_tx_2,hash_tx_7) of block 238703
round 344: ...


excluding the fact that transactions get pre-mined by different miners for a block in my scheme, you also have 3 different ROOT HASH from the same order of transactions, which means reordering one transaction causes changes in 3 different ROOT HASH values - makes it really hard for a miner proceed for a winner target hash (remember, I always sort transactions in block content - reordering in that scheme is impossible by the protocol). I have a RNOG value as master hash root that comes from HASH(positive_hash_root, Merkle_hash_root,negative_hash_root), and I strongly suggest you include this scheme in calculation of round values above.

NOW, if you like to make it stronger for higher amount of bets (and making withholding trivial), include more upcoming facts to the equation:

round 341: HASH(hash_tx_6,hash_tx_9,RNOG,hash_CNN_344,NIST_RNG_344,us_national_debt_344) of block 238697 [end of bet session - 343]
round 342: HASH(hash_tx_3,hash_tx_4,RNOG,hash_CNN_345,NIST_RNG_345,us_national_debt_345) of block 238701
round 343: HASH(hash_tx_7,hash_tx_2,RNOG,hash_CNN_346,NIST_RNG_346,us_national_debt_346) of block 238703
round 344: ...

references:

http://edition.cnn.com/services/rss/
https://www.nist.gov/programs-projects/nist-randomness-beacon
http://www.usdebtclock.org/world-debt-clock.html
https://www.random.org/
http://www.usdebtclock.org/

so, work with timing - my friend..

Dude! it is really a wall of text,  ;D

And yet, not a single strong argument out there:
And this is the point you are missing:
Miner withholds the block because (hypothetically) he profits more from colluding with the house, he has burned a lot of resources to get there and you are offering him an opportunity to censor/manipulate the raw block for free, before any work, in preparation phase?  Otherwise how does it make a difference at all?
If the hash matters, it matters and nothing else does!
If the miner has a way to evaluate and make a trade-off based on the key/hash/data whatever he has a premium on it, he does!
If he decided to withhold the block it would be very easy for him to build a brand new block from scratch in less than few milliseconds in case he is not satisfied by it for any reason, I mean it, just few milliseconds!

See? No point in arguing about a wrong idea, my advise as always, forget about it and move on  ;)

that is one of the symptoms of buffer over flow in client side  ;D ;D server side is working properly  :o :o


the hash matters, but the hash of rounds that creates based on the principles of bet/gambling provider. in this scenario anything that happen among a miner and the house (colluding, etc), will be useless when your ROUND-HASH should wait till finally identifies by some news feed or economical values in the future.. in this method, hash values of a blockchain are part of input parameters to the ROUND-HASH - not all of them.

Well, not a good practice to overflow readers with dummy data to distract them, it is definitively author's fault.  :D

Now you are abandoning your "other block data" idea and bring forward another flaw, non-blockchain stuff for randomization! But "news feed, economical data, ..." aren't true randomization sources whatsoever and they are subject to manipulation ways more than block hash. If they were reliable, why would we use blockchain after all?

You can't solve a problem or be helpful by mixing a dozen of flawed approaches that are supposed to cover for each other magically.

Dummy Data?! when someone asks for elaborating the subject, you have to provide more info - and that is called responsibility.


if you don't RUSH into reply  ;D ;D and read the info carefully, you could see that step by step based on what attack that a bet/gambling provider need to prevent, he could do something special about it. each data source has its own characteristics and mixing them takes you to a better level of trust/security. for example, when you only have static password and decide to add one time password for a login process, we could say you have 2-factor authentication. and we can't say it (a login) 2-factor authentication, when it has 2 step of one time passwords, because they both work the same and are vulnerable to the same attack model.

therefore, when a blockchain is your only source of randomization, by mixing several blocks (header & content) you only could increase the difficulty, nothing more. if you mix data from two different blockchains, this is also trivial (refer to the 2-factor authentication sample above). now, by having the blockchain info (each of block header & block content has their own characteristics in defending the process) as the main source of randomization project, just aim at preventing any kinds of colluding among house and miners, you just add news/stock/weather/etc values to the process. their duty in the process is different here.

eventually, what we write here is about what-to-do, not how-to-do.. this is the project manager's call to pick (a) proper source(s) of data for randomization.

You jump from a flawed proposal to another flawed one and you consider it as being responsible?  :D

Perhaps accusing readers of not being thoughtful when they do not accept your confused proposals and try to help you in performing better in the forum is another responsible act of yours! Isn't it?  :D

An NO! by stacking up multiple flawed approaches to a problem you do not build anything useful, it would be just a conglomeration of bullshits. Attackers usually are incentivized enough to use every single flaw of every single piece of garbage you've piled up there.

It is cryptography, you need to resist white box security test, you couldn't just wrap multiple obfuscation techniques, adversaries with enough incentives open your layers of obfuscation one by one. Instead of making false and irrelevant analogies (like with  two phase authentication), you need to understand what people mean by a "provably fair game".

My main objection was your weird style in bringing forward another flawed idea as a work-around for your previous flawed ideas and turning the discussion to an endless debate which gets more irrelevant and confused as it continues. I see you don't pay attention and continue talking instead of thinking. It is really an unfortunate, I expected more from you and you know why.  ;)

In this thread you first show-up with a magical solution which is using raw block data instead of its hash as the source of randomization which is the worst idea ever and when I reject it solidly, instead of correcting yourself or at least moving on, you come back with another flawed work-around: getting help from external feeds as some sort of auxiliary source of randomization to make it harder (how much?) to break, and now you are telling us it is all about making things harder!

It is not! We don't give a shit to a hard problem, neither adversaries do. They break anything that is not provably infeasible to break and there exists a gain in breaking it!

Well, since we are talking about a hypothetical blockchain here (and I have mentioned already in the OP that some issues need to be resolved before this becomes practical, I'm only focusing on the incentives for now), you could require miners to stake some coins in a deposit from which those bets get resolved.  I know that this changes the system quite a lot (as you need to buy coins first before joining and initial coins needed to be distributed in a way that is not mining), but mining security would then still be PoW and not PoS.

By having miners stake a deposit, you can make them lose more than the block reward - and that's basically all my proposal is about.  (And analysing in detail that this actually rectifies incentives, which I'm still working on.)

Of course, hash commitments are a very good solution where they work - I'm not disputing that (and have acknowledged it multiple times).  But I believe and tried to explain that there are situations in which they probably won't work, so that alternatives are also interesting to consider.  (That said - if you do see a good way to apply hash commitments to, say, Huntercoin, I'm very interested in hearing about it!)

Ok. I tried not to get here but I deliberately used nothing at stake term in my post to remind you that it has something to do with the PoW/PoS choice and now you are taking the bait.

For miners to be credible for high stake games you would need such a staking mechanism and it complicates everything. Your project, your decisions, but I'm not sure how big is the bite  ;)

Edit:
As of hash commitment approach and its applicability to Huntercoin, I need to do some assessments and will keep you informed about the results if anything new.

Yes sure - I'm aware that my proposal is far from practical at the moment.  For now, I only want to assess whether it could be interesting at all, namely whether at least the game theoretic incentives can be good.  How to implement it in a real blockchain would then be the next step (if the incentives are indeed right).

(My background is from academic mathematics, I only stumbled accidentally into engineering - that may explain why I'm still interested in looking at such ideas even if they may be impractical.)


Definitely!  More precisely, just determining when disasters happen in Huntercoin using a hash-commitment scheme would be very interesting to me (that is then applicable to other situations and games as well).  Roughly speaking, you have a permission-less blockchain where everyone is free to create an "account" and then you need to determine the outcome of events for certain blocks that affect every player at once (not only e.g. two players that bet against each other).

Of course you can do things like everyone is free to submit a hash commitment and reveal it, and then all those that are revealed go into the randomness.  But with a scheme like that, ultimately the miner still knows before everyone else and miners can also censor reveal transactions to nudge the result.  Since you don't know which players are actually online, you can't enforce that everyone or some fixed set of players actually has to reveal to prevent miner censorship.  But if you can solve that, let me know! :)

I've now finished a full analysis.  All details can be found in the paper: http://arxiv.org/abs/1901.06285

But to summarise the results, the conjectures I posted early on in this thread worked out.