Bitcoin Forum
July 23, 2018, 06:21:21 PM *
News: Latest stable version of Bitcoin Core: 0.16.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Random Number On Blockchain  (Read 474 times)
truedeckTeam
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
January 24, 2018, 05:05:54 PM
Merited by malevolent (1)
 #1

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.
1532370081
Hero Member
*
Offline Offline

Posts: 1532370081

View Profile Personal Message (Offline)

Ignore
1532370081
Reply with quote  #2

1532370081
Report to moderator
fair bitcoin games | pvp - pve - solo pve games | faucet |
Free satoshi code btcoon500
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
spartacusrex
Hero Member
*****
Offline Offline

Activity: 658
Merit: 506



View Profile
January 24, 2018, 05:22:29 PM
Merited by achow101 (2), mprep (1)
 #2

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
Member
**
Offline Offline

Activity: 196
Merit: 31

This text is irrelevant


View Profile
January 26, 2018, 09:07:36 AM
 #3


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
Hero Member
*****
Offline Offline

Activity: 798
Merit: 616


rgbkey.github.io/pgp.txt


View Profile WWW
January 26, 2018, 05:52:55 PM
 #4

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
Member
**
Offline Offline

Activity: 196
Merit: 31

This text is irrelevant


View Profile
January 27, 2018, 06:03:30 PM
 #5

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
Full Member
***
Offline Offline

Activity: 150
Merit: 102


View Profile
January 27, 2018, 06:15:18 PM
Merited by achow101 (1)
 #6

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
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 06, 2018, 12:01:36 PM
 #7

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
Legendary
*
Offline Offline

Activity: 1302
Merit: 1007


Please do not PM me loan requests!


View Profile WWW
February 06, 2018, 12:23:34 PM
 #8

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
Jr. Member
*
Offline Offline

Activity: 42
Merit: 4

<3 BTC


View Profile
February 06, 2018, 08:38:35 PM
 #9

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

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


LCC - LitecoinCash - https://p2p-a.minelcc.net
etherflip
Copper Member
Jr. Member
*
Offline Offline

Activity: 103
Merit: 6


View Profile
February 07, 2018, 05:36:58 AM
 #10

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
Copper Member
Full Member
***
Offline Offline

Activity: 168
Merit: 742


Help! I’ve got the Pleurodelinaemia! @nym.zone


View Profile WWW
February 07, 2018, 05:55:21 AM
Merited by gmaxwell (1)
 #11

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
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 07, 2018, 07:58:33 AM
 #12

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
Copper Member
Full Member
***
Offline Offline

Activity: 168
Merit: 742


Help! I’ve got the Pleurodelinaemia! @nym.zone


View Profile WWW
February 07, 2018, 08:11:59 AM
 #13

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
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 07, 2018, 10:06:26 AM
 #14

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
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 08, 2018, 01:39:46 AM
 #15

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
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 09, 2018, 02:02:46 AM
 #16

I think we need mental poker on blockchain.
nullius
Copper Member
Full Member
***
Offline Offline

Activity: 168
Merit: 742


Help! I’ve got the Pleurodelinaemia! @nym.zone


View Profile WWW
February 09, 2018, 02:11:28 AM
Merited by mprep (1)
 #17

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
Moderator
Legendary
*
qt
Offline Offline

Activity: 2450
Merit: 1353



View Profile
February 09, 2018, 08:57:28 AM
Merited by Foxpup (3), ruletheworld (1), nullius (1)
 #18

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.

Bitcoin will not be compromised
truedeckTeam
Jr. Member
*
Offline Offline

Activity: 35
Merit: 1


View Profile WWW
February 12, 2018, 02:34:49 AM
 #19

Thanks gmaxwell, I am try to archive this , and I think I have found something.
nullius
Copper Member
Full Member
***
Offline Offline

Activity: 168
Merit: 742


Help! I’ve got the Pleurodelinaemia! @nym.zone


View Profile WWW
March 04, 2018, 01:49:07 AM
 #20

@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 2m+n hashes.  I posit that to influence the inner and outer hashes simultaneously (“zeroth iteration”), the cost would again be 2m * 2n = 2m+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 2m+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.)

Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!