18

Each one of bitcoin and its derived crypto-currencies has a nonce value in the block, no matter what the algorithm is. Every miner tries to search for a luck nonce which can make the hash value smaller than the target under the required difficulty.

However, recently I search scrypt based cryptocurrencies, like the dogecoin and vertcoin block chain for few blocks. I found most of the nonce are even numbers, except for (only manually browsed in block explorer)

Block #184161 - nonce = 8dce5c01

Block #184143 - nonce = 2a674001

Block #184139 - nonce = 930aa899

many other blocks from the latest block (Block #184174) and blocks in between of them are even numbers. Moreover, many nonce value are in hex number of form XXXXXX00 (in an integer hex number form, it is stored as 00XXXXXX in block), or multiples of 256.

The same outcome I observed in Vertcoin blocks. I manually traversed for few blocks and also found nonces of them are also even numbers.

I'd like to ask a question. If I configure the scrypt or n-scrypt to search only even numbers, is it possible to have higher chance to find the nonce which can solve the current quickly?

BTW, I won't expect the mining revenue of each miner in the pool (PPS or PPLNS) is going to be greater than that of normal nonce searching algorithm because the pool count for "shares" you found. When you skip odd numbers, you also lose the chance to get a share (solved by the odd nonce) which can meet the diff the pool gives to you. However, when a pool found a nonce that can solve the block, then the pool wins and gets the rewards.


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

Update: 4/21

I use a small Perl script and call litecoind/dogecoind wallet to print out each block's nonce. It is very slow but quite simple. It would be very fast when you are using binary block database parser.

#!/usr/bin/perl -w

my $odd = 0;
my $even = 0;
my $m256 = 0;
my $total = 0;
for ($i = 186299; $i >= 145000; $i = $i-1) {
    $nonce = `dogecoind getblock \`dogecoind getblockhash $i\` | grep nonce`;
    chomp $nonce;
    $nonce =~ s/[^0-9]*//g;
    printf "%d %d\n", $i, $nonce;

    if (($nonce %2)== 1) {
            $odd++;
    }
    else {
            $even = $even + 1;
            $m256++ if (($nonce % 256) == 0);
    }
    $total ++;
}
printf "odds=%d (%f%%) evens=%d (%f%%) 256s=%d (%f%%)\n",
     $odd, (100.0*$odd/$total),
     $even, (100.0*$even/$total),
     $m256, 100.0*$m256/$total;
  • 2
    Every nonce has the same chance of solving a block or share. Using only even nonces will not change your odds at all. It could be that some mining software prefers to try even nonce values; perhaps it's more efficient on certain hardware or something. – Nate Eldredge Apr 16 '14 at 19:19
  • 2
    I agree with @NateEldredge here. Also looking at an other scrypt based altcoin, Litcoin, I saw no significant difference between the occurrences of even and odd nonces. It seems to be related to Dodgecoin, not to the hashing algorithm in use. However, it would be interesting to know why the nonce values take this shape in Dodgecoin. Dodgecoin. – Jori Apr 17 '14 at 14:56
  • 2
    I get similar statistical data among LTC and DOGE, (even Vertcoin). Don't known the reason but looks very interesting. – jclin Apr 21 '14 at 6:24
  • 1
    @NateEldredge, please see my latest update. Just a small perl to retrieve block nonces. – jclin Apr 22 '14 at 1:56
  • 1
    At this point, I believe your seemingly innocent question deserves an full-blown investigation, publishing its partial results in a blog, or even (should you polish them) in a journal. If the disparity holds true for other scrypt-based coins, you might have spotted a vulnerability or a nice way to increase profitability of miners! As Nate suggested, might be worth testing in an isolated, small network. Have you checked for SHA-256 based coins? Where can I tip you for your efforts? – Joe Pineda Apr 23 '14 at 3:31
8

I think that Tim S. may have the answer with his comment about endian-ness.

Your observations about the nonce having its lowest byte zero (being a multiple of 256), are with respect to the little-endian byte order of the block itself. From the perspective of a big-endian machine, these are statements about the high byte of the nonce.

So consider a miner which is big-endian. The natural algorithm is "start with nonce=0, compute scrypt, increment nonce, repeat", so your "even" nonces will be tried first. However, when a new transaction (or a new block from another miner) arrives, a new block header has to be constructed, and it would be natural to restart the nonce at zero when this happens. In order to get a nonce that is "not a multiple of 256", it has to complete 2^24 hashes before being restarted.

Of course, x86 is the most common desktop CPU, and it is little-endian, but most scrypt mining is done on GPUs. I hypothesize that a majority of these GPUs are big-endian, or at least that some common mining software causes them to increment their nonce in a big-endian manner. Does anyone know if this is the case?

From this chart, it looks like modern GPUs can run scrypt at roughly 1 Mhash/sec. So 2^24 hashes would take 16 seconds. Litecoin is currently averaging roughly 10K transactions per day, which is an average of one every 8 seconds or so. So it would not be surprising that a miner would usually not get into their high byte (which for you is the low byte) before restarting.

This hypothesis would also explain why we do not see such a pattern with Bitcoin. Current SHA-256 ASIC miners run at many Ghash/sec, and so are very likely to go through all 2^32 possible nonces before being restarted by new transaction data. (We might see patterns in the extraNonce, though.)

  • 1
    Not quietly, only AMD GPU is big endian. The hash still has to be calculated in little endian order. Even hardware can compute the hash without caring endian-ness to obtain a hash value, however, the nonce will be re-check with cgminer scrypt (in CPU) again before send to the pool. If GPU uses big endian to compute the hash and gets a valid result, then cgminer will reject that. So the nonce value must be consistent read by either big or little endian platform. You can use AMD's extension with printf to print the nonce in GPU and the cgminer's nonce to see they are the same value. – jclin Apr 25 '14 at 1:08
  • The remain 2^8 is zero is also not possible for so many cases. For 2^24 it only needs 16 seconds to compute in 1MH/s GPU, so it will advance to the next byte of 2^8. When any bit of highest 8 bits of big endian is not zero, it could not be multiples of 256 in little endian. Considering the block time of LTC is 2.5 minutes, and Dogecoin is target for 1 minutes, it is long enough for GPU to use the remain 2^8 bits. When it exhaustively searched 2^32 and found nothing, the miner increases the timestamp 1 second and starts over and over again. – jclin Apr 25 '14 at 1:16
  • You can check the source code of GPU OpenCL scrypt in popular cgminer/sgminer. The OpenCL miner counts the nonce from 0 to an upper value by using thread id as the nonce. So basically it is a incremental value, for example, 4096 threads are issued to compute nonce from 0~4095 (because threads numbered from 0 to 4095), and then 4096~8191 in the second run, and so on. You can add extra printf or applog to cgminer/sgminer to see what the nonce can solve the diff and accepted by the pool. Basically the nonce printed for every accepted diff is also a increment value from small to larger number. – jclin Apr 25 '14 at 1:48
  • @jclin: Thanks for the comments. I realized the mistake about the low bit shortly after posting but did not get to correct it until now. I appreciate the details about cgminer and its interaction with the GPU; I will read them more carefully when I have more time. – Nate Eldredge Apr 25 '14 at 2:01
  • I also need to correct my comments. "2^8 bits" is the high byte (or 8 bits and has 2^8 values) – jclin Apr 25 '14 at 3:18
1

I conducted the following tests using C# (using the block header from the Litecoin wiki; Dogecoin is the same deal). Here's a test using scrypt: (I didn't preset the limit at 14857; it just took so long I stopped it there)

var dict = new Dictionary<uint, int> { { 0, 0 }, { 1, 0 } };
byte[] blockHeader = new byte[] { 0x01, 0x00, 0x00, 0x00, 0xae, 0x17, 0x89, 0x34, 0x85, 0x1b, 0xfa, 0x0e, 0x83, 0xcc, 0xb6, 0xa3, 0xfc, 0x4b, 0xfd, 0xdf, 0xf3, 0x64, 0x1e, 0x10, 0x4b, 0x6c, 0x46, 0x80, 0xc3, 0x15, 0x09, 0x07, 0x4e, 0x69, 0x9b, 0xe2, 0xbd, 0x67, 0x2d, 0x8d, 0x21, 0x99, 0xef, 0x37, 0xa5, 0x96, 0x78, 0xf9, 0x24, 0x43, 0x08, 0x3e, 0x3b, 0x85, 0xed, 0xef, 0x8b, 0x45, 0xc7, 0x17, 0x59, 0x37, 0x1f, 0x82, 0x3b, 0xab, 0x59, 0xa9, 0x71, 0x26, 0x61, 0x4f, 0x44, 0xd5, 0x00, 0x1d, 0x45, 0x92, 0x01, 0x80, };
for (uint nonce = 0; nonce < 14857; nonce++)
{
    var nonceBytes = BitConverter.GetBytes(nonce);
    Array.Copy(nonceBytes, 0, blockHeader, blockHeader.Length - 4, 4);
    var hash = SCrypt.ComputeDerivedKey(blockHeader, blockHeader, 1024, 1, 1, null, 32);
    if (hash[31] == 0)
        dict[nonce % 2] += 1;
}

Results:

0 32
1 29

And with SHA256 (using the block header from the Bitcoin wiki)

var sha = SHA256.Create();
var dict = new Dictionary<uint, int> { { 0, 0 }, { 1, 0 } };
byte[] blockHeader = new byte[] {0x01,0x00,0x00,0x00,
    0x81,0xcd,0x02,0xab,0x7e,0x56,0x9e,0x8b,0xcd,0x93,0x17,0xe2,0xfe,0x99,0xf2,0xde,0x44,0xd4,0x9a,0xb2,0xb8,0x85,0x1b,0xa4,0xa3,0x08,0x00,0x00,0x00,0x00,0x00,0x00,
    0xe3,0x20,0xb6,0xc2,0xff,0xfc,0x8d,0x75,0x04,0x23,0xdb,0x8b,0x1e,0xb9,0x42,0xae,0x71,0x0e,0x95,0x1e,0xd7,0x97,0xf7,0xaf,0xfc,0x88,0x92,0xb0,0xf1,0xfc,0x12,0x2b,
    0xc7,0xf5,0xd7,0x4d,
    0xf2,0xb9,0x44,0x1a,
    0x42,0xa1,0x46,0x95,};
for (uint nonce = 0; nonce < 1000000; nonce++)
{
    var nonceBytes = BitConverter.GetBytes(nonce);
    Array.Copy(nonceBytes, 0, blockHeader, blockHeader.Length - 4, 4);
    var hash = sha.ComputeHash(sha.ComputeHash(blockHeader));
    if (hash[0] == 1)
        dict[nonce % 2] += 1;
}

The results:

0 1908 
1 1951 

This shows that, regardless of whether the nonce is even, coin algorithms produces roughly the same number of high-difficulty results. (I believe this is a good test of both SHA256 coins like Bitcoin and scrypt coins like Litecoin and Dogecoin; yes, I'm pretending the difficulty is much lower by only paying attention to one byte, but the point remains)

So why are multiples of 256 and even numbers so common in the real world? My guess is that mining software most commonly chooses these nonces, though there's no benefit to it. For example, what you call a nonce divisible by 256 could be considered a number under 2^24 (with reversed endianness). Nonces don't need to be chosen with high entropy, so it's acceptable for them to be somewhat predictable - just as long as you're not wasting your time by using the same nonce twice on the same block header.

  • Please note that I got the results from scrypt based crypto-currencies. I also did not see the same pattern mentioned in my question found in SHA256 based algorithm. Moreover, running the algorithm only is not accurate, because there is a target value, which can be derived from the difficulty, and the sha256 or scrypt result has to be less than the target. If you are also running scrypt algorithm only, I guess you the same results that odds and evens have no great difference on their occurrences. – jclin Apr 24 '14 at 20:28
  • I'll see if I can do a proper test with scrypt. – Tim S. Apr 24 '14 at 20:33
  • @jclin I've updated my answer to include scrypt. As I expected, even nonces are no better than odd ones. (I'd be highly surprised if they were - it would mean these crypto hashes could actually be easily manipulated) You've found an interesting triviality, nothing significant. – Tim S. Apr 24 '14 at 20:55
  • I understand that data (even nonce is the LSB=0) computed with sha256 or scrypt won't produce any significant results of favoring even nonces. When LTC in low difficulty, for example block 0~10, your can see most of then are odd numbers. The nonce found in the block might not be the only solution, but just the first one found to be less than the required target value. So for example, LTC block #5 nonce is 6103, and there should be a even number greater than 6103 can solve the block under the difficulty. Your program just prove that many nonces can match your requirement of hash[0]=1. – jclin Apr 24 '14 at 21:46
  • 2
    @jclin: If scrypt really is secure, skipping nonces or not is irrelevant in either solo or pooled mining. Every nonce is equally likely to produce a valid block, and likewise, every nonce is equally likely to produce a valid share (which is just a lower difficulty target). You could run through all numbers in order, or the even numbers, or the primes - it makes no difference. – Nate Eldredge Apr 25 '14 at 0:27
0

The endianness might be not an issue because either in big or little endian, it allows a way to increase the possibility to find the nonce quickly compare to others who just sequentially iterate over 2^32 times.

In big endian, the result means > 80% nonces are found under the space from 0 to 2^24, so don't waste time to continue to try 2^24 to 2^32, just advance to next second or alter some data to start finding the nonce from 0 again.

In little endian, the result means > 80% nonces are multiples of 256, so you might also have 80% ~ 90% possibilities to find the nonce that can solve the block.

Because the nonce is not predicable, either counting the nonce from 0 up in big endian or little endian should not be a issue. They always could find a possible solution to the block.

  • 2
    No, I think you have got a misconception. This approach will not find a winning nonce more quickly - it will be exactly the same. Every nonce has an equal chance of winning. The value of the winning nonce, if there even is one for a given block, is completely random; it is just as likely to be between 0 and 2^24 as in any other equal sized range. For some blocks (indeed, the vast majority), there is no 32-bit nonce that wins. For others there might be many. – Nate Eldredge Apr 25 '14 at 14:46
  • So it doesn't matter at all which nonce values you try, or whether you try all nonces for a given block, or whether you give up before trying them all and change the block header in some other way. At the end of the day, the average number of winning blocks you have found is related only to the number of different valid block headers you have tried to hash - exactly how they differ is totally irrelevant. – Nate Eldredge Apr 25 '14 at 14:48
  • And according to my hypothesis, the reason more people are finding nonces between 0 and 2^24 is because more people are looking there - because it happens to be computationally convenient to do so. If we all switched to a miner that preferred to try nonces between 145235236 and 162012452, we'd expect to find lots of winning nonces in that range, but the total number found would be exactly the same, on average. – Nate Eldredge Apr 25 '14 at 14:51
  • I believe every nonce has an equal chance of winning. Considering the searching game is sequential, what nonce you first have or quickly get is the key to get the block solved. Like a dice game, if you know number six shows up frequently, so you could buy six to win more than others. Rolling a dice multiple times and shows 6,6,6,6 does not mean the dice is unfair. It could be followed by 5,5,5,5,4,4,4,4,...,1,1,1,1 and the possibility of every number of the dice is 1/6, and we could be at the 2nd or 3rd appearance of 6. – jclin Apr 25 '14 at 15:08
  • I'm not sure it is computationally convenient or not to compute only 24 bits of an integer. As I know, except for ASIC miner implementation, the popular cgminer and sgminer scans nonce till 0xFFFFFFFF or time's up or abort due to new block. – jclin Apr 25 '14 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.