Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: giantdragon on November 26, 2012, 09:08:49 PM



Title: Predictability of the block generation time
Post by: giantdragon on November 26, 2012, 09:08:49 PM
Is it possible to predict which timestamp will have next Bitcoin block?
I would like to use this value as seed to generate random numbers for the verifiable game.


Title: Re: Predictability of the block generation time
Post by: Revalin on November 26, 2012, 09:16:30 PM
This would allow miners to cheat by choosing a timestamp.


Title: Re: Predictability of the block generation time
Post by: giantdragon on November 26, 2012, 09:24:22 PM
What about using 5 least significant (right) symbols from the block's hash? Is it possible for miners to cheat?


Title: Re: Predictability of the block generation time
Post by: jgarzik on November 26, 2012, 09:26:25 PM
This would allow miners to cheat by choosing a timestamp.

Fact check:  miners can and do choose the timestamp.

Miners are free to change to timestamp within a certain time window.  That helps stir the block hash, when 32-bit nonce is not sufficient.


Title: Re: Predictability of the block generation time
Post by: Revalin on November 26, 2012, 09:29:22 PM
Yes, miners can control every field in the block.  Your game would be especially vulnerable to a Finney type attack.


Title: Re: Predictability of the block generation time
Post by: DeathAndTaxes on November 26, 2012, 09:45:15 PM
What about using 5 least significant (right) symbols from the block's hash? Is it possible for miners to cheat?

In theory yes depending on how you will use it.   The right x digits of the blockhash are random and the only way to produce a block with a different hash would be by brute force (throwing away non-matching ones).  Given each thrown away block is worth 50 BTC that is a large barrier for most prizes.  If the prize was 1,000,000 BTC you might need to reconsider.

The one area where a miner could cheat without it "costing" anything would be to generate entries until they find one which matches a block they already solved and them submit the block.   You can avoid this by requiring the entry to be in the "winning block" or prior block (i.e. unconfirmed entries can't win).


Title: Re: Predictability of the block generation time
Post by: Revalin on November 26, 2012, 09:53:10 PM
What about using 5 least significant (right) symbols from the block's hash? Is it possible for miners to cheat?

In theory yes depending on how you will use it.   The right x digits of the blockhash are random and the only way to produce a block with a different hash would be by brute force (throwing away non-matching ones).  Given each thrown away block is worth 50 BTC that is a large barrier for most prizes.  If the prize was 1,000,000 BTC you might need to reconsider.

The one area where a miner could cheat without it "costing" anything would be to generate entries until they find one which matches a block they already solved and them submit the block.   You can avoid this by requiring the entry to be in the "winning block" or prior block (i.e. unconfirmed entries can't win).

They can cheat by generating a secret block, playing a move in the game, then broadcasting the block.


Title: Re: Predictability of the block generation time
Post by: giantdragon on November 26, 2012, 11:07:51 PM
What do you think about this:

Generate some random string (nonce) on the server for each game, publish it's hash to the players. When all bets will be received, wait until next Bitcoin block appear. Concatinate plaintext of the nonce and block's hash, calculate new SHA-256 hash and use its least significant chars to determine the winner. Then publish plaintext of the nonce to the players.

Described method must ensure that game operator didn't knew game outcome before all bets accepted and cannot change it. Also it must prevent miners from cheating.


Title: Re: Predictability of the block generation time
Post by: DeathAndTaxes on November 26, 2012, 11:10:34 PM
What about using 5 least significant (right) symbols from the block's hash? Is it possible for miners to cheat?

In theory yes depending on how you will use it.   The right x digits of the blockhash are random and the only way to produce a block with a different hash would be by brute force (throwing away non-matching ones).  Given each thrown away block is worth 50 BTC that is a large barrier for most prizes.  If the prize was 1,000,000 BTC you might need to reconsider.

The one area where a miner could cheat without it "costing" anything would be to generate entries until they find one which matches a block they already solved and them submit the block.   You can avoid this by requiring the entry to be in the "winning block" or prior block (i.e. unconfirmed entries can't win).

They can cheat by generating a secret block, playing a move in the game, then broadcasting the block.

Which is why I said you can overcome that by requiring the "entry" = move to be in the winning block or a prior block (unconfirmed entries can't win").  Not sure if you missed that.   If the entries has to be in the current or prior block then the winning block can't be computed before making an entry.


Title: Re: Predictability of the block generation time
Post by: Revalin on November 26, 2012, 11:18:35 PM
Perhaps I misunderstand.  If the game is based on guessing random elements of a block then it can't be based on already confirmed blocks.

In my scenario the block would be confirmed eventually.


Title: Re: Predictability of the block generation time
Post by: jgarzik on November 26, 2012, 11:59:11 PM
Yes, miners can control every field in the block.  Your game would be especially vulnerable to a Finney type attack.

Not quite.  The value of nonce and some other fields (extranonce in scriptSig) are totally up to the miner.  The value of nTime is somewhat up to the miner.  Other fields are simply non variant:  hashPrevBlock and hashMerkleRoot are simply valid, or not.  The miner has no choice in their value.



Title: Re: Predictability of the block generation time
Post by: gmaxwell on November 27, 2012, 05:43:17 AM
and hashMerkleRoot are simply valid, or not.  The miner has no choice in their value.

uh No. The miner can search for hashMerkleRoot values to get particular ones.


Title: Re: Predictability of the block generation time
Post by: jgarzik on November 27, 2012, 09:32:50 AM
and hashMerkleRoot are simply valid, or not.  The miner has no choice in their value.

uh No. The miner can search for hashMerkleRoot values to get particular ones.

You're micro-parsing.  What is meant is that the value of hashPrevBlock and hashMerkleRoot are very specifically defined by algorithm and validation.

The miner also "controls" the value of hashPrevBlock, in the same micro-parsing sense you've provided, by electing to not mine a particular block, thereby skipping a hashPrevBlock.

The basic point is that the miner cannot select any random garbage for those fields.



Title: Re: Predictability of the block generation time
Post by: Stephen Gornick on November 27, 2012, 10:31:08 AM
I would like to use this value as seed to generate random numbers for the verifiable game.

BlockchainRoulette does this:
 - http://blockchainroulette.com


Yes, miners can control every field in the block.  Your game would be especially vulnerable to a Finney type attack.

Yup, and that was brought up for BlockchainRoulette as well:

But for the house, the secret is known and thus if the house were to not play fairly it could use the influence that mining provides to affect the outcome of each round.

With BlockchainRoulette, this currently isn't a fatal flaw though because the site max bets are so low that if the site were to do this to save a 10 BTC payout (maximum risk of loss to the house) they have to throw away a 50 BTC block  (well, even when it is 25 it will still be a greater loss than paying out the winner.)