Topic: Random numbers in a blockchain (Read 881 times)

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.

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!

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.

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

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

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?  

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!

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

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

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.

that is one of the symptoms of buffer over flow in client side  server side is working properly 


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.

Dude! it is really a wall of text, 

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 

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

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.

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.

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.

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

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?

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?

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

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!

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.

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.