Random Number On Blockchain

[truedeckTeam]

How Can one generate a random number on blockchain , and all remain decentralised , everyone has same result but no one know the number until the number disclose to public.

[1714898801]

1714898801

[1714898801]

1714898801

[1714898801]

1714898801

[1714898801]

1714898801

[1714898801]

1714898801

[1714898801]

1714898801

[spartacusrex]

Take the first bit of Hash(blockhash) of the last 64 blocks.

Make a 64 bit number. Hash That.

It's random.

Everyone can calculate it independently.

[Colorblind]

Yeah this is pretty much comes from irreversibility (unpredictability) of hash function.
All you need to do is to take some immutable properties, that being added to blockchain unpredictable (as spartacusrex mentioned above) and use hash to further normalize distribution and you got it. Just write a rule that works similar every time next block is appended.

It is important to understand that this still won't be "true" randomness (if such thing even exists), but will be nearly impossible to predict and likely give uniform distribution of output values.

[RGBKey]

I've struggled with a problem like this before. I was trying to find a way to use the Bitcoin blockchain to generate random numbers similar to how provably fair gambling sites generate them now. Unfortunately, I couldn't find a way that didn't involve either waiting time for the next Bitcoin block (which was undesirable for me) or placing trust in another party.

[Colorblind]

I've struggled with a problem like this before. I was trying to find a way to use the Bitcoin blockchain to generate random numbers similar to how provably fair gambling sites generate them now. Unfortunately, I couldn't find a way that didn't involve either waiting time for the next Bitcoin block (which was undesirable for me) or placing trust in another party.

You can’t generate another random number before another piece of information added to what you use as a seed, therefore you can’t really generate numbers more often than new block appears. You may however generate arbitrary amounts of random numbers per block or use faster blockchain to Do so.

[CounterEntropy]

How Can one generate a random number on blockchain , and all remain decentralised , everyone has same result but no one know the number until the number disclose to public.

Read: How random the last digit of a block hash really is?

[truedeckTeam]

Thanks but if I use block hashes, then it will be pre predictable. I need something that is unpredictable until it gets in public.

[Taras]

Thanks but if I use block hashes, then it will be pre predictable. I need something that is unpredictable until it gets in public.

The last digit of a block hash is really not pre-predictable because no miner in their right mind would forfeit their block in order to manipulate the last digit. The benefit of doing so would have to be greater than the 12.5 BTC loss of throwing away their solution. It may still be possible to manipulate if there are two block candidates (an unresolved chain split) but the usual waiting for 6 confirmations solves that.

[DrSha]

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

This might be a good reference point for you to check out.

[etherflip]

Take the first bit of Hash(blockhash) of the last 64 blocks.

Make a 64 bit number. Hash That.

It's random.

Everyone can calculate it independently.

This is not truly random. There is a reason random.org relies on lightning strikes to generate random numbers.

If you are using Ethereum, Oraclize provides RNG via ledger and access to sites like random.org - we are using Oraclize.

[nullius]

Take the first bit of Hash(blockhash) of the last 64 blocks.

Make a 64 bit number. Hash That.

It's random.

Everyone can calculate it independently.

This is not truly random. There is a reason random.org relies on lightning strikes to generate random numbers.

If you are using Ethereum, Oraclize provides RNG via ledger and access to sites like random.org - we are using Oraclize.

You are confusing subtle variation in meanings of the word “random”.  Part of the problem here is that OP did not so rigorously specify the properties of the needed numbers.  From what was said (and from OP’s username), I presume what is needed is network shared, uniformly distributed pseudorandom values which can be neither predicted nor influenced in advance by anyone.  According to that specification, I don’t immediately see any reason why spartacusrex’s suggestion would not suffice.  Care to explain?

For one example of protocols respectively producing and consuming such values, see the Tor Shared Random Subsystem Specification (plus references therein), and the Tor Rendezvous Specification - Version 3 (the “next-gen” .onion services which were recently released).

(I will here leave aside analysis of your suggestions; but I hope nobody is using “random.org” for secret key material of any kind whatsoever.)

[truedeckTeam]

Thanks but if I use block hashes, then it will be pre predictable. I need something that is unpredictable until it gets in public.

The last digit of a block hash is really not pre-predictable because no miner in their right mind would forfeit their block in order to manipulate the last digit. The benefit of doing so would have to be greater than the 12.5 BTC loss of throwing away their solution. It may still be possible to manipulate if there are two block candidates (an unresolved chain split) but the usual waiting for 6 confirmations solves that.

By this way again the problem is same it is predictable and seen by all , everyone can see last 6 blocks and can go to number.

What my idea is to use a pow algorithm to some random difficulty, and that difficulty is taken by people, because nature is what is true random. Let’s say that we will ask people to move pointers at a particular time and use that randomness together and make a difficulty number and use pow.

[nullius]

truedeckTeam, why not a commit-and-reveal scheme where each participant commits a hash of a random value, then reveals the value, and all values are hashed together?  In my prior post, I provided links to one such system.  I don’t know if that meets your criterion for “decentralized”; you did not specify your requirements quite clearly.

[truedeckTeam]

truedeckTeam, why not a commit-and-reveal scheme where each participant commits a hash of a random value, then reveals the value, and all values are hashed together?  In my prior post, I provided links to one such system.  I don’t know if that meets your criterion for “decentralized”; you did not specify your requirements quite clearly.

It may have some problems, suppose
We played a game on decentralised platform like blockchain. Now if we take inputs from each users and ask them to send hash , then one who will collect those hashes gains the power to predict what will be the number. So game will be somewhat centralised . And I think we can use this number as difficulty and use POW

[truedeckTeam]

truedeckTeam, why not a commit-and-reveal scheme where each participant commits a hash of a random value, then reveals the value, and all values are hashed together?  In my prior post, I provided links to one such system.  I don’t know if that meets your criterion for “decentralized”; you did not specify your requirements quite clearly.

The requirements are something like gambling game on blockchain

[truedeckTeam]

I think we need mental poker on blockchain.

[nullius]

truedeckTeam, why not a commit-and-reveal scheme where each participant commits a hash of a random value, then reveals the value, and all values are hashed together?  In my prior post, I provided links to one such system.  I don’t know if that meets your criterion for “decentralized”; you did not specify your requirements quite clearly.

It may have some problems, suppose
We played a game on decentralised platform like blockchain. Now if we take inputs from each users and ask them to send hash , then one who will collect those hashes gains the power to predict what will be the number. So game will be somewhat centralised .

No, the one who collects the hashes would not be able to predict the outcome.  That is one of the purposes of committing hashes.

0. Collect commitments H(A), H(B), H(C).  Observe that A, B, and C remain secrets; each is known only to the person who generated it.  Thus, the outcome of #3 below cannot be predicted by anybody.  Every participant should have a copy of all hash commitments before proceeding to the next step.  After these commitments are all made, the outcome cannot be changed—yet it is still unknown to anybody!

1. Collect the revealed A, B, C.  Observe that the people who generate these cannot now change them to influence the outcome, because:

2. Verify the revealed A, B, C respectively hash to the committed H(A), H(B), H(C).  All participants can verify this independently.

3. Calculate H("my protocol" || A || B || C).  This is the outcome.  All participants can calculate this independently.

That’s a simplified version of protocols actually in use.  Did you read the Tor specifications as to which I linked?

(I may potentially have further thoughts; but let’s start there.)

[gmaxwell]

The standard protocol is a commit and reveal protocol as mentioned above with hashes.  The problem commit and reveal protocols have is that the last party to reveal can jam the process if he doesn't like the result.   In some contexts thats harmless, in others its fatal.

The hash the last block's ID approach can be biased by miners.  Without knowing what the the result would be used for you can't argue that they wouldn't do it... if they could make themselves win a 100 BTC lottery for sure, ... it would be totally reasonable to orphan and throw out blocks to pull it off.    The earlier proposal to use "the last 64 blocks" doesn't help, the last block is sufficient-- it already commits to all prior blocks anyways.

You can attempt to reduce the holdup issue in a commit and reveal protocol by using verifiable secret sharing.  For example: Alice, Bob, and Charley  generate secret values a, b, c and using ECC compute and publish points  aG, bG, cG   -- these are their commitments.   Then each party generates a new random value r and sends one of the other two parties r and the other party their secret-r, and those parties publish rG and (s-r)G.  So for example, Alice sends r to bob, and (a-r) to Charley.  Bob and Charley publish rG and (a-r)G, and each of them can add the values and check that they equal Alice's commitment because aG = rG + (a-r)G; but the players all still know nothing about each other's secrets. Once the sharing is done, people can start revealing their secrets.  Alice reveals a, Bob reveals b... Charley decides he doesn't like the result and falls offline, but now Alice and bob can reveal the shares of Charley's secret...  Whoever remains can compute H(a||b||c).  Of course, if Bob and Charley are co-conspirators they can abort as soon as they get Alice's shares if they don't like the result. This approach generalizes to any threshold of participants.

These sorts of ideas can be combined.

But which combinations are interesting depends on the application. For example,  one case I've thought a lot about is making random values that people in the future can be pretty confident weren't rigged.

Alice and Bob can agree on their terms and generates the a private key as a hash of the agreement terms and a random value sends a bitcoin to their own keys A and B in block 1000.   Then after block 1000 they sweep their coins and reveal their keys and your random number becomes  H(blockhash || a_private || b_private).   This would make it difficult for the miner to bias without knowing A and B's keys, letting them steal the coins. A and B couldn't easily restate their random values because they're commuted in the chain, etc.

Another idea which I've not seen implemented is to use a slow sequential function on the block hash. So e.g. your randomness involves H(blockhash)  but you make H in that case some function that takes 20 minutes to compute.   You can argue that a miner might throw out a block solution to bias a result-- but if he can't even tell the result for 20 minutes after finding the block that is much harder.  I understand that Ben Fisch  has been working on finding functions for H() in this example which are cheap to verify, so others can check the results of that 20 minutes of computation without doing 20 minutes of computation themselves.

[truedeckTeam]

Thanks gmaxwell, I am try to archive this , and I think I have found something.

[nullius]

@gmaxwell, thanks for the explanation of the holdup issue and how to work around it with secret sharing.  I also appreciate the idea of hashing private keys, thus exploiting participants’ self-interested need to keep them absolutely secret early in the protocol.

In the interim between my above posts (2018-02-08), I was pondering another idea.  I frankly don’t know whether it’s a sound idea, or half-baked; so I kept it up my sleeve whilst mulling whether it’s even worth a mention.  Due to a sudden interest I have in provably fair gambling, I will now give it a shot.  Who knows—perhaps I may want to found my own gambling site, and make of myself Bitcoin thousandaire.

The hash the last block's ID approach can be biased by miners.

I’m usually a critic of Satoshi’s use of double-hashes.  But here, I think it can really come in handy:  Use the inner hash as the source of a public pseudorandom number which is infeasible to influence or predict in advance.

Zeroth iteration of the idea:  Breakage requires a partial preimage attack on the input to another partial preimage attack.  My gut tells me that this is one of those ideas which is either ingenious, or trivially stupid.

(Aside, is double-SHA256 fully baked into silicon in available current-generation mining hardware?  Or can it be programmed to return both the inner and outer hashes?  If the former, then add the cost of making your own ASICs in calculating the real-world cost of attack.)

If that does not suffice, next iteration:  Hash (or HMAC) the inner hash together with a different predefined nonce such as a counter.  E.g., for the hash at block height h, use:  HMAC_SHA256("I always win!" || (uint32_t)h, block_inner_hash).

Or hash the inner hash together with pseudorandom material from a different source, such as a popular altcoin blockchain with a different PoW.  E.g., hash this intermediate state from a Bitcoin double-hash together with some intermediate state from an Equihash.

Aside:  Of course, the inner hash can be kept secret by the generating miner whilst its commitment (the outer hash) is baked ever-deeper into the blockchain.  This can probably be useful for some other purpose.

I always approach such ideas by placing myself in the role of an attacker.  For simple use of the block hash as suggested by others, I understand that if the attacker wanted to influence m bits of the hash in addition to the n bits of needed zeroes, the cost of the attack is 2^m+n hashes.  I posit that to influence the inner and outer hashes simultaneously (“zeroth iteration”), the cost would again be 2^m * 2ⁿ = 2^m+n hashes.  That is why I am trying to tie the inner hash to something else, and/or use the inner hash as an input for another hash which also depends on other independent inputs.  I seek some way to substantially raise the cost above 2^m+n hashes.  There may be some means to exploit the irreversibility of the outer hash, which I have not yet thought of.

The goal seems obvious, but I must state it clearly for the sake of clear argument:  How could it be made infeasible for the miner to influence the result whilst also managing to create any Bitcoin blocks at all?  (Much less without impractically high risk of orphans?)  I know I did plenty of handwaving above.  Ultimately, I’d seek to pin it down to something with a rigorously characterized 128-bit security level (or higher).

N.b., I’d be as fascinated to see this idea attacked and shot down as I would be to find out that it’s a brilliant insight.

Thanks.


(Notice:  I independently conceived this idea on 2018-02-08; and I am first publicly disclosing it today, as of the timestamp on this post.  I will promptly archive-snapshot this post, so as to provide at least a modicum of prior art evidence in case it’s a good idea and some idiot runs to file for a patent on it.)