Topic: Random Number On Blockchain (Read 785 times)

True..

Hash( next block hash ) better..

Please read the scheme described by @nullius ,and gmaxwell , it has something important

Right, but everyone will know what's the next number, of block 65. You add 0 or 1 to the previous 63 bits and get 2 possible results, which can't be called random, correct?

It maybe, but if we supply something called nonce , then it is just close to random, however it is still not random

You are right , that’s what we are trying to do, a true random number on blockchain, and some good ideas from nullius and gmaxwell

Ye it's all run through a hashing algorithm that makes think appear random when in fact they are not random. If you type in the same input the out output will always be the same making the key generated not actually random

@nullius , sir you agreed?

Thanks nullius,
My thinking was that like bitshares has a community that produces blocks , we can ask users to generate a random number using their device’s cpu usage and noise, and then submit the hash of that number, .... Now the user who is going to produce block will submit his random number hash and produce a block , now each one who submitted their random number hash asked to submit their random numbers, then these all random number get mixed and a new final random number get generated, now each user can verify it using algorithm(that generate the final number using all numbers) and also if user submit their random number was correct or not , because they already submitted the hash in previous block.

Please do not try to cook up such an ad hoc scheme for gathering randomness.  The scheme you describe is on its face both inadequate for gathering entropy, and easily influenced by local (physical) or perhaps even network attackers.  (A network attacker who can persuade you to visit his website can use Javascript to trivially influence your CPU usage, and thus CPU temperature.)

Worst of all, the scheme you describe requires trust not only in a central party (“he then choose the right number and announce”), but in all parties (how do you remotely verify CPU usage and soundcard input?).  I see no means whatsoever that “people will see and verify” the result here.  What is this thread about?  Why not just have your site pick bits off your server’s /dev/random, which nobody else can verify to be fairly obtained?  The scheme you describe would provide strictly less practical security than that, insofar as it is not even a good local entropy gathering scheme.

If you want a secure network randomness protocol for use on what I presume to be a provably fair gambling site, then implement a commit-and-reveal protocol as I described upthread, with enhancement of the ideas outlined by gmaxwell for preventing holdup by dishonest participants.  This protocol will be cryptographically secure.

Off-topic:  If you be interested in gathering entropy from physical sources, I suggest that you read the paper for Turbid, a high-entropy symbol generator which uses thermodynamic (not acoustic) noise from the analogue circuits in an ordinary computer soundcard.  Proper design of such a thing requires extensive knowledge of both maths and physics.  The Turbid author (Dr. John Denker) has both.

All your ideas are good, but I think only nature is true random , so if we build something that will use device temperature cpu usage at that instant, and some noise from microphone, then hash them all , then this will be a random number. And again we can choose a system that will announce some perimeters to accept a random number, and all people submit their numbers to him, he then choose the right number and announce, then people will see and verify that if he chosen right number or not.

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


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

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

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.

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

I think we need mental poker on blockchain.

The requirements are something like gambling game on blockchain

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

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.

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