Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: jeezy on September 07, 2013, 10:34:16 AM



Title: RNG using Block informations
Post by: jeezy on September 07, 2013, 10:34:16 AM
Hey guys,

okay, first of all I'm new to this crypto stuff and I know the issue of "Provably Fair" has been discussed over and over again. Yet I haven't quiet found any definite answer to my approach. What I want to do is make the RNG more transparent by taking the information of the next/current block found (txconf=1).

My approach so far looks like this:

Code:
hmac_sha512($blockhash, $nonce)

Since I think the nonce is fairly random and could never be guessed, using it as the secret would give me quiet a strong random variable which is also transparent at the same time. Now I read a lot of stuff about blockhashes tending towards lower numbers, so I should add something to the hash to make it even more random.

Would you think adding the blocktime would make it even more random or isnt necessary:

Code:
hmac_sha512($blockhash, $nonce+$blocktime)

Cheers


Title: Re: RNG using Block informations
Post by: fpgaminer on September 07, 2013, 11:08:36 AM
Could you describe a specific use case?  i'm having a hard time imaging what the hmac_sha512 of a blockhash could be used for.


Quote
Since I think the nonce is fairly random
Are you referring to the nonce in the block header?  If so, it's not necessarily random (it's possible to mine with nonce set to a constant, for example), and it's certainly quite biased.


Title: Re: RNG using Block informations
Post by: Dabs on September 07, 2013, 11:15:47 AM
HMAC is usually used where the first argument is secret, and the "message" is the second argument.

You can use the blockhash, or the merkle root hash, both are random and practically unpredictable. The nonce for most gaming sites are usually incrementing, unless you are talking about the blockchain nonce used for that particular block.

The block time would be optional and not needed.

What is your intended purpose? Some game? You mention "Provably Fair". I personally like this kind of topic.

If you use public information for your RNG, then the results are predictable after the fact. This is good for games where the results are needed later, such as raffles or lottos. Not so much for games where you want the results now, such as dice games.


Title: Re: RNG using Block informations
Post by: jeezy on September 07, 2013, 11:21:25 AM
Could you describe a specific use case?  i'm having a hard time imaging what the hmac_sha512 of a blockhash could be used for.

You could for instance take the first decimal via pregmatch and use it as a 0-9 RNG. My test script that I ran hundred of times (1 billion iterations each) verifies that it's evenly distributed 0-9 and no number is in favor.

Quote
Since I think the nonce is fairly random
Are you referring to the nonce in the block header?  If so, it's not necessarily random (it's possible to mine with nonce set to a constant, for example), and it's certainly quite biased.

Okay, how about taking the exact blocksize as the second secret then? That should be unguessable before the block gets found/generated?


Title: Re: RNG using Block informations
Post by: jeezy on September 07, 2013, 11:27:04 AM
HMAC is usually used where the first argument is secret, and the "message" is the second argument.

You can use the blockhash, or the merkle root hash, both are random and practically unpredictable. The nonce for most gaming sites are usually incrementing, unless you are talking about the blockchain nonce used for that particular block.

The block time would be optional and not needed.

What is your intended purpose? Some game? You mention "Provably Fair". I personally like this kind of topic.

If you use public information for your RNG, then the results are predictable after the fact. This is good for games where the results are needed later, such as raffles or lottos. Not so much for games where you want the results now, such as dice games.

Yeah, in PHP it's the other way around  ;) http://www.php.net/manual/en/function.hash-hmac.php

So I could just hmac the blochhash and merkleroot and would get a non-predictable hash. That's good to know! I will run a couple of tests with merkleroots then.


Title: Re: RNG using Block informations
Post by: Remember remember the 5th of November on September 07, 2013, 12:32:19 PM
Could you describe a specific use case?  i'm having a hard time imaging what the hmac_sha512 of a blockhash could be used for.

You could for instance take the first decimal via pregmatch and use it as a 0-9 RNG. My test script that I ran hundred of times (1 billion iterations each) verifies that it's evenly distributed 0-9 and no number is in favor.

Quote
Since I think the nonce is fairly random
Are you referring to the nonce in the block header?  If so, it's not necessarily random (it's possible to mine with nonce set to a constant, for example), and it's certainly quite biased.

Okay, how about taking the exact blocksize as the second secret then? That should be unguessable before the block gets found/generated?

Then how would you know it beforehand to use it yourself?


Title: Re: RNG using Block informations
Post by: markm on September 07, 2013, 01:57:44 PM
Are you familiar with the usual techniques existing sites use to accomplish "provably fair" ?

If so what is it about their method(s) that make them unsuitable for your use-case (and thus requires you to re-invent their apparently not so elegant after-all wheel)?

-MarkM-


Title: Re: RNG using Block informations
Post by: jeezy on September 07, 2013, 03:26:58 PM
Could you describe a specific use case?  i'm having a hard time imaging what the hmac_sha512 of a blockhash could be used for.

You could for instance take the first decimal via pregmatch and use it as a 0-9 RNG. My test script that I ran hundred of times (1 billion iterations each) verifies that it's evenly distributed 0-9 and no number is in favor.

Quote
Since I think the nonce is fairly random
Are you referring to the nonce in the block header?  If so, it's not necessarily random (it's possible to mine with nonce set to a constant, for example), and it's certainly quite biased.

Okay, how about taking the exact blocksize as the second secret then? That should be unguessable before the block gets found/generated?

Then how would you know it beforehand to use it yourself?

Not beforehand, the second a new block is found the information is there and I can use it for 1 conf txs.

Are you familiar with the usual techniques existing sites use to accomplish "provably fair" ?

If so what is it about their method(s) that make them unsuitable for your use-case (and thus requires you to re-invent their apparently not so elegant after-all wheel)?

I just want it to be a full transparent RNG layer on top of the block chain.


Title: Re: RNG using Block informations
Post by: markm on September 07, 2013, 03:34:11 PM
I just want it to be a full transparent RNG layer on top of the block chain.

And the usual method does not qualify?

(I had hoped for a yes or no, with more info following in the case of yes.)

So maybe even more clarity is missing... where does $nonce come from? Your pre-imaged scheduled list of nonces-to-be-used-soon or do you mean the nonce a miner put into the blockchain?

(Not sure if pre-imaged is correct term; i mean the file of nonces / seeds / random values concealed onoff your site whose hash is shown all users before they bet, then revealed once it has been consumed so later everyone can see that the seeds to be used were in deed already determined in advance.)

-MarkM-


Title: Re: RNG using Block informations
Post by: jeezy on September 07, 2013, 03:41:52 PM
I just want it to be a full transparent RNG layer on top of the block chain.

And the usual method does not qualify?

(I had hoped for a yes or no, with more info following in the case of yes.)

In my oppinion the second the site operator knows more about the possible outcome than the user, they got the advantage. If that advantage is relevant for the RNG or even gets actively exploited doesn't matter, because the principle is the same. I just want my approach to be as transparent, seamless & integrated as possible, using the given bitcoin protocol.


Title: Re: RNG using Block informations
Post by: markm on September 07, 2013, 03:51:07 PM
So basically all players and the platform know the state of the RNG in advance and then it is up to miners whether or not the next block produces a win or not?

If that is the case, you could just plug in the hash of the block as both inputs to the RNG (both is in the document to digest and the nonce to anti-rainbow the result) couldn't you?

Its no longer a random number generator though if you do that, rather, it is a war among miners to see whether any of them can come up with a winning block, isn't it?

In the usual/customary means of accomplishing "provably fair" miners have no say as they only provide one input, the other is already pre-determined in advance (provable after the fact that is was in fact pre-determined) and not known to miners.

It sounds like you are calling for a hashpower war, like the ancient times "God's Acre"* concept that God will see to it that the right answer will be revealed on the battlefield.

God does not play dice ;) aka God's Acre is not a cryptologically random process.

So to get "provably random", first a true prophet of the true God records a prophetic file containing a list of all the nonces that will be used over the next however many rolls of the dice, then the miners do their thing without any knowledge of the nonces, or something like that. I gotta sleep again I think as this is starting to get mind-boggling again. (How do they prove they didn't reveal to the miner(s) in advance what the prophet put in that file? Hmm.) Hope someone else can help I just ran out of steam. Its the fact the prophet was right as to what the nonce would be that proves it all, somehow, I do recall that much I think.

Prophet: "the hash of today's nonces-file is weg04ee-0y"

At end of day the file of nonces is published, lo and behold, the prophet was right as to what that file's hash is!

Bah, I now see, I think, why you prefer that all miners, not only site-insiders, know the nonce in advance. (The usual method doesn't seem elegant at all to me right now. The holy file of nonces-to-be-used seems merely a cheatsheet the site insiders can crib from.)

-MarkM-

* Wikipedia doesn't mention God's Acre being a term for a battlefield, it has it as a graveyard. Try googling for God's acre game, as I got the term in my youth from a tabletop miniatures battles rule book, which is where I also got the idea it was a term used in olden times. As I use it here, I mean a battlefield as in God will determine the outcome when the crusaders and infidels meet to "hash it out".


Title: Re: RNG using Block informations
Post by: jeezy on September 07, 2013, 05:26:17 PM
words

Not sure if this is a troll or not but I will say this much: All I wanted to know is if the blockhash is totally random and can't possibly be known in advance, so I can use it as a transparent RNG seed, one guy said it sure is, so this issue is settled then.


Title: Re: RNG using Block informations
Post by: gmaxwell on September 08, 2013, 03:05:43 AM
Not sure if this is a troll or not but I will say this much: All I wanted to know is if the blockhash is totally random and can't possibly be known in advance, so I can use it as a transparent RNG seed, one guy said it sure is, so this issue is settled then.
Too bad, because markm gave you a nice answer.

Miners can potentially select the block hash to meet some characteristic. They'd do so at great cost, but that being a viable attack depends on what exactly you're using this for, what information is available to miners, etc.



Title: Re: RNG using Block informations
Post by: Dabs on September 08, 2013, 04:28:44 AM
How much time do you need? A block is about 10 minutes. If you can wait a day, you could use other site secrets as well. You can even use random.org.

My lotto uses 7 secrets. 1 only I know, 5 belonging to other sites, and 1 from atmospheric noise which no one knows. I concatenate them all together then use that to hash my tickets. It can't get any more provably fair than that.

I say, use 1 secret of your own + the block hash or the merkle root hash of the next block and not even the miners would be able to reasonably manipulate it. This is exactly what PeerBet does, and almost the same method of blockchain based games like SatoshiDice.


Title: Re: RNG using Block informations
Post by: gmaxwell on September 08, 2013, 04:30:36 AM
merkle root hash of the next block
You use the merkle root of the next block??? Where is this site of yours?  Daddy needs a new pair of shoes!


Title: Re: RNG using Block informations
Post by: Dabs on September 08, 2013, 05:29:30 AM
I don't have one yet, but I think using the merkle root is better than the block hash, don't you think?

Quote
Every transaction has a hash associated with it. In a block, all of the transaction hashes in the block are themselves hashed (sometimes several times -- the exact process is complex), and the result is the Merkle root. In other words, the Merkle root is the hash of all the hashes of all the transactions in the block. The Merkle root is included in the block header.

Clarification, I suggest using the merkle root of the next block as a means to determine the winner of your game or as source of unpredictable random numbers which can be verified later. Players have to wait until the next block. I'm thinking you misunderstood what I said and I am predicting the merkle root of a future block, which is impossible.


Title: Re: RNG using Block informations
Post by: gmaxwell on September 08, 2013, 06:51:52 AM
I don't have one yet, but I think using the merkle root is better than the block hash, don't you think?
I hope you're building this service with your own money... because you're going to be broke if you think this is okay.

Miners can iterate over their merkle root for practically free. Your security would come entirely from how difficult it would be for an attacker to convince miners to run special block template creation software that picks merkle roots to their liking.. The attacker doesn't even need pool cooperation, and they could setup a parallel secondary pool where people submit shares with suitable roots and pay them for it. (e.g. users install a patched cgminer on their miners and start getting paid for producing work that attempts to rig your game).


 


Title: Re: RNG using Block informations
Post by: markm on September 08, 2013, 07:51:19 AM
Right.

So if you must use God's Acre, that is, a block...

You might as well use the whole block (aka the whole acre). :)

Any bit of it they change is still an iteration with a bit changed, just like if they'd changed a bit of the nonce or extranonce.

But why do you need to use blocks at all?

Depending on quite what you are trying to do, might it work just as well to tell the player "I have made up a seed whose hash is X, please enter a seed you want to use, then I will reveal my seed, you can hash it and see it does indeed hash as I claimed, so you know I didn't change my seed after seeing yours" ?

-MarkM-

EDIT: I went back up-thread (https://bitcointalk.org/index.php?topic=289558.msg3101714#msg3101714) to clarify my use of the term God's Acre (https://www.google.com/search?q=God%27s+Acre+game&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a) as wikipedia doesn't mention it meaning battlefield they say graveyard.


Title: Re: RNG using Block informations
Post by: jeezy on September 08, 2013, 09:53:16 AM
Miners can potentially select the block hash to meet some characteristic. They'd do so at great cost, but that being a viable attack depends on what exactly you're using this for, what information is available to miners, etc.

As soon as the current txs are confirmed (1), I need a provably fair 0-9 RNG. So my idea was to hmac the blockhash + something else (it can't be anything I control or know) and take the first digit the hmac produces and thats our winning number. Maybe I should just take the current blockhash (conf=1) + something of the last block (size/nonce/merkle/whatever) (conf=2). That would mean that miners need to manipulate 2 blocks in a row to rig the game.


Title: Re: RNG using Block informations
Post by: gmaxwell on September 08, 2013, 10:28:14 AM
That would mean that miners need to manipulate 2 blocks in a row to rig the game.
No they wouldn't. Not unless there is state they don't know.


Title: Re: RNG using Block informations
Post by: markm on September 08, 2013, 11:13:56 AM
As soon as the current txs are confirmed (1), I need a provably fair 0-9 RNG.

Okay so tell the user the hash of the seed that you do know, ask them for a random seed they provide themselves (for example, the transaction number of the transaction in which they sent you some bitcoins), wait for the block to confirm, then whether they win or not tell them the actual seed you used, the one you previously told them the hash of.

Notice that even if they lose, they still need to know what seed you had chosen, the one you had told them the hash of, if they want proof of fairness.

If you don't want to publish the proof (the seed you chose) on a diceroll by diceroll basis you can use aggregates such as having each day's seeds-to-use already in files ready to use (more than enough for each day, way more in case you get unexpected amount of traffic) and after the day is over move that day's file to a place where the public can see it, and publish there too the bet by bet / diceroll by diceroll log of all the dicerolls so the public can match up first roll of the day to first seed you had scheduled for use that day, second roll to second seed etc.

Log to public could maybe publish live realtime what the hash of your seed is, what seed a user provided, and, when the block is confirmed, what the dice actually came up as. Then once the day is over, publish the actual file of seeds and enhance the day's log by appending each seed that was actually used to the log entry of the play it was used by.

If you want to spam losing bets to the blockchain you could encode the seed you used into the "you lost" spam as well as coding it into the "you won" payments so the player can see it is fair as soon as they know whether they won or lost.

-MarkM-


Title: Re: RNG using Block informations
Post by: Dabs on September 08, 2013, 12:55:15 PM
@gmaxwell, so the merkle root hash is a bad idea? Well, the block hash doesn't seem so bad anymore then. But if you have a server seed as well, that makes 3 seeds in total which can be used in the hash or HMAC function.

1. Server Secret Seed
2. Block Hash or Merkle Root
3. Player or Client Seed


Title: Re: RNG using Block informations
Post by: TierNolan on September 08, 2013, 09:17:48 PM
1. Server Secret Seed
2. Block Hash or Merkle Root
3. Player or Client Seed

Why not just use this system:

Player picks random number X
Server picks random number Y

Server sends hash(Y) to the player
Player sends hash(X) to the server

Player sends X to the server
Server sends Y to the player

Both compute (X XOR Y) and take the lowest digit.

Note: X and Y would be large numbers

That gets you a completely random number, as long as at least one of the server and the player wants it to be random.


Title: Re: RNG using Block informations
Post by: markm on September 09, 2013, 01:18:30 AM
That gets you a completely random number, as long as at least one of the server and the player wants it to be random.

A protocol that allows non random results if both parties want it to would be awesome for money-laundering and bribes!

You could head off to the casino to collect your pre-determined paycheque, and by sheer luck, you win, that exact amount, and no one can prove it wasn't sheer luck!

Your protocol that I don't think quite provides that though. I wonder what protocol would...

Or wait, maybe yours does provide that! I figure its more useful/interesting to raise the question than to bother thinking whether yours does until after I post, so others can experience the joy of thinking too...

Though maybe the real answer is so obvious it doesn't really require any thought.

(Oh yeah? Then how come a few setences ago, back when "I don't think", I didn't necessarily type the right answer? Hmm. Maybe "I do think" would be a more useful general approach to problem-solving.)

I can guess now that legislators will prefer the "seeds to use file made in advance" to "invent a new seed on a per play/player basis on the spot" if only to make launderers have to keep very tight appointments to be sure they were in fact hitting the site precisely at the right point in the sequence of seed-use to get their payseed honoured.

-MarkM-


Title: Re: RNG using Block informations
Post by: Dabs on September 09, 2013, 02:10:59 AM
It depends on how soon you need to create the new random numbers. Dice sites will not lose on purpose unless the owner does not want to pay his investors, which is a problem with all dice sites.

If you need the numbers instantly, you need to use a server secret to prevent players from choosing the results. If you need to be certain that either party can manipulate the results, you need to get the seed or secret from a disinterested third party and wait for those numbers.

You can use other site secrets, the next block hash, real life lotto numbers... They all have time schedules. Other sites usually take a day. Some have one every hour. Real life lottos you can be assured will not be manipulated, otherwise someone will use that to buy the winning ticket.


Title: Re: RNG using Block informations
Post by: jeezy on September 09, 2013, 07:43:33 AM
Again guys, I don't want to use any server secret, client/server seed technique and no external rng. This topic is specificly for using the information we got on the blockchain to generate solid & transparent random numbers. I think I got quiet a good idea for my project now, thanks.


Title: Re: RNG using Block informations
Post by: deepceleron on September 09, 2013, 12:13:18 PM
I previously published a method using the block hash as a pseudo-random number generator for raffle ticket picking. The block hash is quite random: the only way of manipulating future block hashes is to be a significant miner and discard winning block hashes if they don't meet a criteria, which gives you even less chance of influence than your hashrate would indicate in addition to discarding 50 25 BTCs:

http://we.lovebitco.in/raffle.html

Hey guys,

okay, first of all I'm new to this crypto stuff and I know the issue of "Provably Fair" has been discussed over and over again. Yet I haven't quiet found any definite answer to my approach. What I want to do is make the RNG more transparent by taking the information of the next/current block found (txconf=1).

My approach so far looks like this:

Code:
hmac_sha512($blockhash, $nonce)

Using a 512 bit hash gives the illusion that there is more entropy than there is.

The block hash can be considered as a random number generator, with an even distribution of results between 0 and the current difficulty target, currently 0000000000000031679C00000000000000000000000000000000000000000000. That's currently less than 198 bits of entropy. It would be more appropriate to re-hash the block hash with a secure 160 bit algorithm such as RIPEMD-160 just to be clear in algorithms that that is the depth of the randomness.

A block hash not the best secret for a gambling site, as it not a secret, and your salting method may be discoverable. It is good when a future random number pick will determine a winner and the picking method needs to be verifiable by all.


Title: Re: RNG using Block informations
Post by: jeezy on September 09, 2013, 12:29:46 PM
I previously published a method using the block hash as a pseudo-random number generator for raffle ticket picking. The block hash is quite random: the only way of manipulating future block hashes is to be a significant miner and discard winning block hashes if they don't meet a criteria, which gives you even less chance of influence than your hashrate would indicate in addition to discarding 50 BTCs:

http://we.lovebitco.in/raffle.html

Hey guys,

okay, first of all I'm new to this crypto stuff and I know the issue of "Provably Fair" has been discussed over and over again. Yet I haven't quiet found any definite answer to my approach. What I want to do is make the RNG more transparent by taking the information of the next/current block found (txconf=1).

My approach so far looks like this:

Code:
hmac_sha512($blockhash, $nonce)

Using a 512 bit hash gives the illusion that there is more entropy than there is.

The block hash can be considered as a random number generator, with an even distribution of results between 0 and the current difficulty target, currently 0000000000000031679C00000000000000000000000000000000000000000000. That's currently less than 198 bits of entropy. It would be more appropriate to re-hash the block hash with a secure 160 bit algorithm such as RIPEMD-160 just to be clear in algorithms that that is the depth of the randomness.

A block hash not the best secret for a gambling site, as it not a secret, and your salting method may be discoverable. It is good when a future random number pick will determine a winner and the picking method needs to be verifiable by all.

Yeah, I've seen your approach last week and find it very interesting for the idea I got. It's basically exactly what I need. Also I might rainbow the result with the txs that went into the raffle. This is both transparent for everyone and adds even more entropy.