Bitcoin Forum
May 22, 2019, 12:21:59 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Are nonces predictable?  (Read 148 times)
marciks
Newbie
*
Offline Offline

Activity: 108
Merit: 0


View Profile
March 26, 2019, 02:30:18 PM
 #1

In a hipotetic game that uses nonces as seed I mean.. would it be OK to use nonces for this purpose?
NEW GAME FORMAT
JACKPOT UP TO $8000+
Guess The Symbols Of a Real Ethereum Hash
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1558527719
Hero Member
*
Offline Offline

Posts: 1558527719

View Profile Personal Message (Offline)

Ignore
1558527719
Reply with quote  #2

1558527719
Report to moderator
1558527719
Hero Member
*
Offline Offline

Posts: 1558527719

View Profile Personal Message (Offline)

Ignore
1558527719
Reply with quote  #2

1558527719
Report to moderator
HeRetiK
Legendary
*
Offline Offline

Activity: 1106
Merit: 1049


the forkings will continue until morale improves


View Profile
March 26, 2019, 02:40:56 PM
Merited by ETFbitcoin (1)
 #2

While you can't predict which nonce is going to be the correct one (ie. a valid nonce for successfully mining a block) a miner could in theory only search for the correct nonce within a given subset of nonces and not necessarily lessen their chance for finding the correct one (eg. the chance to find a valid nonce within the subset of even numbers is as high as the chance of finding a valid nonce within the subset of odd numbers). So at least in theory a miner can manipulate which nonces hit the blockchain. Not sure how viable such an attack would be in practice though.

marciks
Newbie
*
Offline Offline

Activity: 108
Merit: 0


View Profile
March 26, 2019, 03:09:08 PM
 #3

So making a sum with like 5 block nonces would avoid this possible attack vector I suppose.. I just want to make sure that no one can predict results in a collective game.. Just getting some thoughts
HeRetiK
Legendary
*
Offline Offline

Activity: 1106
Merit: 1049


the forkings will continue until morale improves


View Profile
March 26, 2019, 03:33:51 PM
Merited by bones261 (2)
 #4

I guess given a proper mangling of the input even a single nonce should be sufficient for most purposes (eg. the SHA256 of a predetermined public server seed + nonce should be unpredictable enough for a single random outcome. A much slower cryptographic hash would likely be preferable though). I'm not sure whether including multiple nonces would up the security level that much (ie. since an attacker would know the other nonces, they could adjust their nonce-"space" accordingly). But like I said, I'm not sure whether such an attack would be viable to begin with.

ETFbitcoin
Legendary
*
Offline Offline

Activity: 1638
Merit: 1766

Use SegWit and enjoy lower fees.


View Profile WWW
March 26, 2019, 04:47:31 PM
 #5

Nonce seems to be "random" enough, but few block analysis mention otherwise. Quoting from https://bitcoin.stackexchange.com/q/24650,

Edited: Apr 18

I wrote a small program to collect some statistical data. From recent Dogecoin block #186,299 to #145,000 (the last mandatory update)

total 41,300 blocks

    number of odds = 3,891 (9.42%)
    number of evens = 37,409 (90.58%)
        ratio of odd to even is about 1:10
    Among the evens, the number of multiples of 256 = 35,106
        85% of total
        93.866% of evens

Update: 4/20

I recently also checked the nonces from block 552,780 to 253,898 of Litecoin.

totally 298,883 blocks.

    number of odds = 42,963 (14.374521%)
    number of evens = 255,920 (85.625479%)
    Among the evens, the number of multiples of 256 = 225,746
        75.529890% of total


Depending on your game and whether money is involved, using nonces isn't good idea. Set a number before game started and hash it with salting to keep fairness is better idea IMO.

marciks
Newbie
*
Offline Offline

Activity: 108
Merit: 0


View Profile
March 26, 2019, 05:20:30 PM
 #6

Nonce seems to be "random" enough, but few block analysis mention otherwise. Quoting from https://bitcoin.stackexchange.com/q/24650,

Edited: Apr 18

I wrote a small program to collect some statistical data. From recent Dogecoin block #186,299 to #145,000 (the last mandatory update)

total 41,300 blocks

    number of odds = 3,891 (9.42%)
    number of evens = 37,409 (90.58%)
        ratio of odd to even is about 1:10
    Among the evens, the number of multiples of 256 = 35,106
        85% of total
        93.866% of evens

Update: 4/20

I recently also checked the nonces from block 552,780 to 253,898 of Litecoin.

totally 298,883 blocks.

    number of odds = 42,963 (14.374521%)
    number of evens = 255,920 (85.625479%)
    Among the evens, the number of multiples of 256 = 225,746
        75.529890% of total


Depending on your game and whether money is involved, using nonces isn't good idea. Set a number before game started and hash it with salting to keep fairness is better idea IMO.

Good info..

You guys could point me a better option though.. The idea behind this game is to select a winner (or more) from a list of particpants. The game would announce something like: "we are at block 568903 - result at 569000 (using nonces as seeds from block 568996 to 569000)"
Using multiple blocks would avoid nonces comming from only a miner, right?

This way we would have deterministic results from the algorithm.. The problem is the seed origin.. so I thought that nonces could be usefull..

Any thoughts?

hypothetically I could forge game results.. by using nonces, I couldn't
domob
Legendary
*
Offline Offline

Activity: 1060
Merit: 1091


View Profile WWW
March 26, 2019, 05:41:11 PM
Merited by ETFbitcoin (1)
 #7

You guys could point me a better option though.. The idea behind this game is to select a winner (or more) from a list of particpants. The game would announce something like: "we are at block 568903 - result at 569000 (using nonces as seeds from block 568996 to 569000)"
Using multiple blocks would avoid nonces comming from only a miner, right?

I think there are two commonly used approaches:  The first is to use the block hash instead of the nonce.  This way, it is way harder for a miner to manipulate it - but they still can if the game is worth really a lot of money.  Basically when they have solved a block but do not like the outcome of the game, they can decide to not publish the block and try again.  But that loses them a block reward - so is only worth it if your game is about more money than that.

The second is using a hash commitment - like what @ETFBitcoin proposed above.  You can have all participants of the game create random numbers and publish the hashes.  Then you base your game outcome on some combination of the numbers themselves (which the players have to reveal after everyone published their hash).  This ensures that noone knows the outcome (or can manipulate it) before the hashes are revealed, but also noone can change their number afterwards since that would invalidate the commitment.

Use your Namecoin identity as OpenID: https://nameid.org/
Donations: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
ETFbitcoin
Legendary
*
Offline Offline

Activity: 1638
Merit: 1766

Use SegWit and enjoy lower fees.


View Profile WWW
March 26, 2019, 05:43:27 PM
 #8

Good info..

You guys could point me a better option though.. The idea behind this game is to select a winner (or more) from a list of particpants. The game would announce something like: "we are at block 568903 - result at 569000 (using nonces as seeds from block 568996 to 569000)"
Using multiple blocks would avoid nonces comming from only a miner, right?

This way we would have deterministic results from the algorithm.. The problem is the seed origin.. so I thought that nonces could be usefull..

Any thoughts?

hypothetically I could forge game results.. by using nonces, I couldn't

Seed origin from nonces on multiple blocks is good idea and i doubt multiple pool / miners with big hashrate would work together just to manipulate a game result.

Since the winner is based on participant list, not number/value chosen by participant, there's no need to worry about increasing winrate by choose specific number/value.

Miz4r
Legendary
*
Offline Offline

Activity: 1246
Merit: 1000


View Profile
March 26, 2019, 06:02:08 PM
 #9

Nonce seems to be "random" enough, but few block analysis mention otherwise. Quoting from https://bitcoin.stackexchange.com/q/24650,

Edited: Apr 18

I wrote a small program to collect some statistical data. From recent Dogecoin block #186,299 to #145,000 (the last mandatory update)

total 41,300 blocks

    number of odds = 3,891 (9.42%)
    number of evens = 37,409 (90.58%)
        ratio of odd to even is about 1:10
    Among the evens, the number of multiples of 256 = 35,106
        85% of total
        93.866% of evens

Update: 4/20

I recently also checked the nonces from block 552,780 to 253,898 of Litecoin.

totally 298,883 blocks.

    number of odds = 42,963 (14.374521%)
    number of evens = 255,920 (85.625479%)
    Among the evens, the number of multiples of 256 = 225,746
        75.529890% of total


I wonder if this could be a self-fulfilling prophecy? As in in the early days some large miners may have done some analysis and found that something like 60% of the nonces were even, which could totally be explained by statistical variance of course but still some large miners may have decided to just look for even nonces based on these findings. This obviously skews the statistics more in favor of even nonces, because more hashrate is only looking for those nonces now. After some time you may find that 90% of the nonces turn out to be even as more and more miners stop looking at odd nonces like some kind of perpetually reinforced superstitious bias. I mean statistics don't lie. Wink

Bitcoin = Gold on steroids
HeRetiK
Legendary
*
Offline Offline

Activity: 1106
Merit: 1049


the forkings will continue until morale improves


View Profile
March 26, 2019, 06:20:12 PM
 #10

Nonce seems to be "random" enough, but few block analysis mention otherwise. Quoting from https://bitcoin.stackexchange.com/q/24650,

Edited: Apr 18

I wrote a small program to collect some statistical data. From recent Dogecoin block #186,299 to #145,000 (the last mandatory update)

total 41,300 blocks

    number of odds = 3,891 (9.42%)
    number of evens = 37,409 (90.58%)
        ratio of odd to even is about 1:10
    Among the evens, the number of multiples of 256 = 35,106
        85% of total
        93.866% of evens

Update: 4/20

I recently also checked the nonces from block 552,780 to 253,898 of Litecoin.

totally 298,883 blocks.

    number of odds = 42,963 (14.374521%)
    number of evens = 255,920 (85.625479%)
    Among the evens, the number of multiples of 256 = 225,746
        75.529890% of total


I wonder if this could be a self-fulfilling prophecy? As in in the early days some large miners may have done some analysis and found that something like 60% of the nonces were even, which could totally be explained by statistical variance of course but still some large miners may have decided to just look for even nonces based on these findings. This obviously skews the statistics more in favor of even nonces, because more hashrate is only looking for those nonces now. After some time you may find that 90% of the nonces turn out to be even as more and more miners stop looking at odd nonces like some kind of perpetually reinforced superstitious bias. I mean statistics don't lie. Wink

The most probable answer is already given in the quoted StackOverflow thread, namely that most Scrypt mining back in the day was done using GPUs that are big-endian (ie. the way that the GPUs in question worked favored even numbers over odd numbers) [1]. So in theory one should be able to find a correlation between the shift from GPUs to ASICs and an increased equilibrium of odd and even nonces.

[1] https://bitcoin.stackexchange.com/a/24893

PrimeNumber7
Member
**
Offline Offline

Activity: 98
Merit: 87


View Profile
March 27, 2019, 03:33:53 AM
 #11

You guys could point me a better option though.. The idea behind this game is to select a winner (or more) from a list of particpants. The game would announce something like: "we are at block 568903 - result at 569000 (using nonces as seeds from block 568996 to 569000)"
Using multiple blocks would avoid nonces comming from only a miner, right?

This was answered above
I'm not sure whether including multiple nonces would up the security level that much (ie. since an attacker would know the other nonces, they could adjust their nonce-"space" accordingly).

The miner of block 569000 (in your example) could mine trying to use a nonce that results in an outcome in its favor.

If you published the hash of the block numbers, plus extra "random text" you could avoid this attack vector because only you will know which blocks will be used until you disclose the result. You must include the additional text otherwise someone could brute force the block numbers.

marciks
Newbie
*
Offline Offline

Activity: 108
Merit: 0


View Profile
March 28, 2019, 12:52:01 PM
 #12

Given all answers, I think it will be better to use random.org :/ thanks, everyone
Pages: [1]
  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!