Bitcoin Forum

I keep seeing these "invalid or stale" a couple of times a day.

30/01/2011 15:26, bea41297, accepted
30/01/2011 15:26, bea41297, invalid or stale
30/01/2011 15:27, b9c26c57, accepted
30/01/2011 15:27, fb27e19a, invalid or stale

Notice the two lines at the top in bold.  
Could there possibly be more than one answer per getwork?
As you can see, I got the answer previously, then got the same answer again.
Then on the last line, it just came back invalid...probably cause someone else got the answer to the getwork before I did.

Is every getwork unique?  If so, how did I get the same answer twice?

UPDATE:  Got two more
30/01/2011 15:30, e67d85ec, invalid or stale
30/01/2011 15:36, f1f124d9, invalid or stale

Hi FairUser,

'invalid or stale' for unique nonces can be explained by pool update. Pool now doesn't accept shares when new bitcoin block come (see pool thread for more). Now it works in the same way as standalone mining.

About same getworks - it looks like network troubles, which are more and more common. I hope that it will be solved by protocol change, which significantly reduce network communication. Will be introduced this week.

This is not a network communications problem.
I record my getwork request and answers.
The two getwork were ENTIRELY different getwork request, with different data and midstates, yet produced the same answers.

I am also interested to learn what is the difference between these two. I am guessing it would be more efficient to do pool mining resource wise, but it's just a guess since I don't know much about the mining strategy algorithm in each case.

Say I have several 5970s, if I let them mine solo, there's no coordination among these miners, I'd think there would be a some kind of wasted work because of duplicate/overlapped attempts on the same hashes, while the pool mining work can be distributed in a way to avoid or minimize this waste. True or false?

False. there are zillions of possible blocks/hashes to find and no one ever duplicates any searches.

the advantage of pools is you get smaller rewards more frequently. the total rewards are on the average almost identical.

Ever?
Duplicates will never-ever-ever be found in the getwork searches?
Each getwork is unique, and no result from getwork A could possibly match getwork B?

Just trying to make sure I understand that is what you're saying.

If there are no duplicate getwork responses, then the probability of re-doing work is so low that it will almost certainly never happen to anyone as long as Bitcoin exists.

Duplicate getwork responses would cause you to do work that has already been done. However, slush's pool relies on Bitcoin to handle this, so there shouldn't be any difference between mining on your own and mining in a pool. If anything, the pool is more likely to produce duplicates, since Bitcoin was not designed to produce unique work for so many miners.

Assuming it is working as designed. Bugs throw out all bets.

Hashes are 256 bits. The odds of finding two random hashes the same would be much less than the odds of getting struck by lightning on the same day you buy a single ticket and win the lottery. I call that never.

Assuming it is working as designed........that is indeed the question I'm raising.

So why is it when I process the ENTIRE getwork request (vs just finding the first answer and then moving on to the next getwork), I'm seeing a much different result, and quite frequently at that.

Notice that this getwork got 5 answers, and reported all of them to slush's server and were accepted.
29/01/2011 01:41:42, Getting new work.. [GW:29]
29/01/2011 01:41:57, 9d5069e9, accepted at 40.625% of getwork()
29/01/2011 01:41:58, 09fc7161, accepted at 43.75% of getwork()
29/01/2011 01:41:59, 27af8f3c, accepted at 46.875% of getwork()
29/01/2011 01:42:02, ad105798, accepted at 56.25% of getwork()
29/01/2011 01:42:12, 0e920ae8, accepted at 75.0% of getwork()

This sample shows that 3 answers were accepted, 1 invalid, then 1 more accepted.  Notice the Invalid answer is the same as the 1st accepted answer.
31/01/2011 06:46:34, Getting new work.. [GW:291]
31/01/2011 06:46:38, 41b15022, accepted at 6.25% of getwork()
31/01/2011 06:46:53, c597d2b5, accepted at 31.25% of getwork()
31/01/2011 06:46:59, 9babdadf, accepted at 50.0% of getwork()
31/01/2011 06:47:07, 41b15022, invalid or stale at 75.0% of getwork()
31/01/2011 06:47:11, 1ba08127, accepted at 87.5% of getwork()

This sample shows 4 getworks, all without a single answer, then just a single answer for 1 getwork.
31/01/2011 06:04:21, Getting new work.. [GW:212]
31/01/2011 06:04:54, Getting new work.. [GW:213]
31/01/2011 06:05:26, Getting new work.. [GW:214]
31/01/2011 06:05:59, Getting new work.. [GW:215]
31/01/2011 06:06:32, Getting new work.. [GW:216]
31/01/2011 06:06:43, d08c8f3d, accepted at 31.25% of getwork()
31/01/2011 06:07:04, Getting new work.. [GW:217]

These outputs are from a modified version of m0mchill's miner.

Changes include:
- Does not stop when first answer/hash/nonce is found.  It continues searching until all possible hashes have been searched.
- Removes the hard coded limit of 10 seconds for the askrate.  (My card does a single getwork in 30 seconds, so I just set the askrate to 3600 and forget it)

The advantages of these modifications are:
- The entire getwork request is processed, finding all possible answers to a getwork.
- Raises efficiency of getwork/answers to 100%.  Right now it's between 20-30%.
- Lowers the amount of requests and bandwidth used by pool servers.

Right now, I believe, huge portions of hashes in the getwork requests are not being processed because when just 1 answer is found, it moves on to the next getwork, or if the askrate has been reached, it then moves on to the next getwork.  Also, in comparing the results over time of the original miner and this modified version, they find the same amount of answers in the same amount of time (on average).  The original miner seems to generate about 260% more traffic for the pooled mining server and discards well over 60% of the getwork when a single answer is found, or when the askrate is reached.

SO....

If the chances are 1 in a zillion in finding the same answer for different getwork request, then how is this miner finding multiple answers for a SINGLE getwork, some are valid, some a DUPLICATES, how is this happening?

If all getwork request are unique, and possible answers are overlooked when the first answer is found, how does the pool/bitcoin handle searching the rest of that discarded hashes?  Does it?

Is this a problem with the miner, or the getwork patched version of bitcoin?

Have YOU searched the entire 2^32 possible hashes of a getwork before, or do you just trust the miner knows best when it stops short of checking all 2^32 possibilities?

If I'm correct in my findings, how many more blocks could the pool be finding by searching all of the 2^32 hashes per getwork?? 
How many blocks have we missed because we didn't search the entire getwork??

That's your food for thought.  Please think about this and provide good answers.
I'm expecting to release the modified client in the next week or so after I get the pre-compiled versions and sources wrapped up.

Looking forward to feedback on this one.. ;)

I've been asking m0mchill the same things in PM lately. It seems to me that multiple answers could be found for each 2^32 keyspace, and the likelihood that the first answer is the actual answer for the block is only '1 : The average number of answers found in a getwork() that results in answers', with some getwork() not resulting in answers at all.

This brings up the question; If some getwork() simply do not have answers, is this due to a 2^32 keyspace not being an actual equal portion of the block, or is this due to overlapping 2^32 getworks? ...and if it's overlapping, is that the cause of the invalid or stale?

i.e.:
I send a getwork() request and receive my 2^32 keyspace to work on.
XYZMiner belonging to another person gets another 2^32 keyspace in getwork
Do we share an overlap of 2^16 (arbitrary figure for the sake of example) in our respective keyspaces?

Meaning, am I getting invalid or stale because there are multiple people working on the same exact portions of keyspace? If so, isn't that an issue with the getwork patch?

I've also asked m0mchill about the askrate, and it seems his answer to why the client fixes the askrate is basically a "fuck it if it doesn't find it quick enough". Although, he speaks more eloquently than that.

He has also stated that, yes, we are ignoring large portions of the keyspace because we submit the first hash and ignore anything else in the keyspace, whether it's found in the first 10% of the keyspace, or the last 10% of the keyspace. He believes that this is trivial though, since you are moving on to another keyspace quick enough.

Here is a quote from my PM with him (m0mchill):

So, we're not searching the entire keyspace in a provided getwork. What if one of those possible answers you're ignoring is the answer to the block? You just fucked the pool out of a block.

I understand the premise that some getwork may not result in answers, but to the same extent, you could also get multiple valid answers (2, 5, 8, whatever) for a SINGLE getwork.

I see no problem here.


I don't know why miner uploaded same nonce twice, but it is fine that second attempt wasn't counted. Btw I'm expecting that nonce is rising from zero, so looks weird for me that nonces are mixed.


That's fine, isn't it?


I thought that miner is already doing this. At least Diablo's isn't stopping when 'block' is found. Don't forget that this is tweak only for pool, because with crunching real-difficulty hashes, second nonce cannot be valid bitcoin block in any case...


You should put it back. Otherwise you are crunching invalid work for long time (~ 30/600 seconds, so 5% of time is wasted). Plus pool now reject shares which cannot be valid bitcoin blocks, for more info read pool thread. So this isn't improvement in any case.


how did you calculated 20-30%? It isn't correct.

Yes, less often getwork update saves some resources, but will make mining much less effective.

Personally I don't understand why are you posting this, because I already answered all those questions in PMs...


Nothing or not any significant amount. Learn basics of statistics and visit pool stats page...

There is no reason why there should be valid share in every getwork.


No overlapping, every getwork is unique. Read more how getwork() works. Especially the extranonce part.


No. It may be because another bitcoin block was introduced in meantime between getwork() and submit. Then share from old block cannot be candidate for new bitcoin block. Read my last posts in pool thread. By the way, this is not pool/m0mchil miner related, it is how bitcoin works.


And he was true. Longer ask rate, more hashing overhead.


By skipping some nonce space, you don't cut your probability to find valid share/block. There is the same probability of finding share/block by crunching any nonce.


Definitely not. It is only nice optimization for pool to continue hashing of current job, it save some network roundtrips, but it basically does not affect pool success rate.

I think he's basing the efficiency off of the number of submitted results to the number of getworks requested.

If 4 getworks are requested without having valid answers to submit back, and then on the 5th, it finds one answer and submits it back, then moves on without checking the remaining keyspace for more answers, you have a 20% efficiency.

However, if you request 4 getworks that don't result in answers, and then the 5th results in 5 answers, you have 100% efficiency.

So, over time (I'm sure it was looked at for more than just a few minutes) the averages from m0mchill's code would be ~20-30% where FairUser's fork would be closer to a 1:1 ratio, or 100% efficiency.

FairUser, feel free to correct me if my assumption is wrong here, but that seems the most logical way for me to break down what you're trying to say.

Maybe I'm wrong, but you are not paid for higher getwork/submit efficiency, but for finding valid blocks. So you are optimizing wrong thing ;). Maybe you can get 100% getwork/submit ratio, but you are crunching old jobs. But it is your choice and your hashing power.

If this is the case, and the assumption is also true that we are "statistically unlikely" to find the same hash twice inside of the same getwork, can you explain to me what FairUser is seeing here:


Off of a SINGLE getwork, he received 3 valid answers, and then an invalid, followed by another valid. If this only happens when a new block is introduced between getwork and submission, why was the 5th hash accepted? Wouldn't it have been for the previous block? Shouldn't it have been rejected since the block hash on the answer didn't match the current block? Or is it possible that it's merely collision with SHA finding two identical (or similarly identical, taking difficulty into consideration) answers for the same getwork?

Likewise, can you explain to me exactly how ignoring a potentially large amount of hashes that could be the answer to the block doesn't effect the pool solving the block?

Your statistical analysis of the block data is accurate if you're taking into consideration that each getwork can only have one answer, and that the one answer being submitted is the only one that could be the correct answer for block. I think FairUser has shown quite plainly that multiple valid answers can be found within the same getwork.

I'll be happy to have it explained to me why I'm wrong to assume this though.

Did you noticed that it is the same nonce? It is absolutely fine that second attempt was rejected. As I wrote before, I don't know the reason *why* there was second attempt. Afaik, nonces should be sorted from 0 to ffffffff, but maybe there is some simple answer behind mixing of nonces (more solving thread or whatever). Maybe it was only reupload after lost connection, whatever. Maybe m0mchil will response this, I don't know miner internals.


because - as I already wrote - share can be rejected for more reasons. The reason for this rejection is that miner uploaded same nonce twice. It is not relevant to any bug in getwork, skipping some nonce ranges or any other weird stuff you are arguing here.


Because with skipping some nonce range, shit happen. In fact, you are skipping zillions of existing nonces. How can you live with that? :-)


And I said it is nice, but not necessary optimization of miner. This only optimize network latencies, because miner is asking less often, but it does not improve probability that share will be found.

OK.


That's what I thought.  Just wanted to make sure.


Not true.  Look again.
31/01/2011 06:46:34, Getting new work.. [GW:291]
31/01/2011 06:46:38, 41b15022, accepted at 6.25% of getwork()
31/01/2011 06:46:53, c597d2b5, accepted at 31.25% of getwork()
31/01/2011 06:46:59, 9babdadf, accepted at 50.0% of getwork()
31/01/2011 06:47:07, 41b15022, invalid or stale at 75.0% of getwork()
31/01/2011 06:47:11, 1ba08127, accepted at 87.5% of getwork()

3 were accepted, then the 4th was invalid.  So if this was invalid because the block count went up by one (and work from old blocks are now discarded as invalid), how was the 5th answer from this now *old* work, why was it accepted?  Your logic doesn't work here BECAUSE the 5th answer was accepted!  And, the miner doesn't know that the block has increased until it makes the next getwork request. ;)



I wouldn't call it "more" hashing overhead, since it's the same number of kHash/s regardless of *what getwork* it's on.  My kHash/s doesn't change just because I'm on a different getwork.



I agree that the probability of finding the share/block is the same for every getwork....IF YOU LOOK AT THE ENTIRE GETWORK.  Skipping over half the possibilities when just the first hash is found screws with your idea for a perfect 1:1 ratio for getwork/found hashes.  You can't ever expect to see (or find) the entire puzzle (the block) when you are choosing to ignore any part (the skipped hashes in a getwork) of that puzzle.


That is true! 
I'm seeing the same amount of accepted hashes in a given hour with both miners.  The only thing this does is increase efficiency by:
1) Not ignoring nonces of the getwork when a hash is found
2) Not stopping part way through the getwork because the askrate was triggered.

It's not crunching old jobs, it's crunching the same job all the way instead of moving on without potentially finding other valid answers.

It's more effective to crunch through the entire keyspace in (2^32)/MyHashRate seconds than it is to grab new getworks every 5 seconds and potentially not find an answer at all because I'm only checking a very small portion of the keyspace before moving on to the next getwork.

Say I get 50 million hashes a second on my GPU.
2^32 / 50,000,000 = 86 seconds to process an entire keyspace.
If my askrate is set to 5 seconds, I'm only checking 5.82% of each keyspace before moving on and assuming the getwork holds no answers.

You're potentially ignoring 94.18% of answers. Numbers obviously vary based on the speed of the GPU, but for a 5 second askrate to be effective, you would need 859 Million Hashes/s to process a keyspace of a single getwork, and even then the way m0mchills code is written, once it finds the first answer, it moves on to the next getwork anyway. This is flawed.

You can call it whatever, but with long getwork period, you are hashing shits for many % of time :-).


Well, getwork is not a puzzle. It is random walk, when you hit valid share time to time. Nonces are just numbers. It's irrelevant if you are trying to hash 0xaaaa or 0xffff. The probability that you hit valid share is still the same.


Well, this is the only point which make sense. Diablo already implemented this and if it isn't in m0mchil's, it would be nice to implement it, too. But it's definitely on m0mchil decision, not on us.

Also sorry for some impatient responses, but I'm responding those questions to pool users almost every day and it become little boring ;). It isn't anything personal. To be honest, it isn't long time ago when I had very similar questions as you have right now. But thanks to m0mchil, Diablo and few other people on IRC, now I know how much wrong I was ;).

Yes, I will be crunching old jobs for about 30 seconds.  Already working on a mod to check my local bitcoind between "work" (32 of them) in the python code for the current block.  You and I both know what our bitcoind's can do. ;)  This way we can stop within 1 second on a block update and get a new getwork.  So quit thinking in terms of OLD JOBS.  Whether it's old or new, I'm talking about the ability to search the 2^32 hashes.

Your server just happens to be the only server that is running a public pool, hence, it might feel like I'm picking on it...but I'm not.  All these changes helping increase the probability of the pool as a whole to finding the block in the getwork instead of ignoring most of the getwork when just a single answer is found.  Maybe Diablo is doing it different (i hate java personally so I haven't even looked at the code), m0mchill's is ignoring part of the 2^32 POSSIBLE answers after finding just 1.

More blocks == more pay for everyone

OK Slush, do this. 

In your server stats, I want you to list:
1) The number of get requests for the CURRENT round
2) The number of submitted hashes (both ACCEPTED and INVALID/STALE listed separately) for the CURRENT round.

If you wanted to increase the accuracy of this, separate the INVALID/STALE hashes based on the reason they were rejected, ie (WRONG BLOCK) or (INVALID/ALREADY SUBMITTED).

Then take (# of getwork this round)/(# of accepted/invalid(already submitted))*100 and publish that number in real time.
That's how you check the efficiency of the pool's ability to search all hashes for each getwork sent out. 

This will show if you are really get that 1:1 ratio of getwork/solved hashes.

Can you do that?  Publish those numbers on the server stats page? 
Then we all can see what the efficiency of getwork/solved hashes is.

Also, you can't make up for the inefficiency of quiting the search after 1 submitted answer, or askrate tigger, with increasing the speed at which you get work.
That only increases the speed of your inefficiency, it doesn't solve the problem of not looking for more answers.

No, I get the same number of accepted as I do with the normal miner. :)


But if I get to 0xcccc, find an answer and stop looking, I *could be missing* more answers.


That's why I posted in his thread.


Maybe I'm totally wrong in thinking that ignored POSSIBLE answers COULD BE *THE* ANSWER for the block....since I've already found 10 blocks for the pool. ;)
If Diablo Miner does look through the entire 2^32 possible answers, then it is being 100% efficient.  I'd like to see the same with m0mchill's miner, so I made the changes I wanted to see and it bothered when I realized it was ignoring possible answers.

Exactly.  The slower the GPU, and the lower the askrate the worse off your efficiency will be because more possible hashes are being ignored.

Yes, this will work.


Irrelevant in this discussion. You are skipping some nonces, but you are crunching another nonces instead. No block lost.


As pool hashrate is +- constant in one round, you can keep getwork/s * round time to get this.


I don't calculate it now, because I simplified the code with the last update, but I have those number for ~5 millions of shares. Stale blocks were something around 2 %.


I have those numbers, but I'm not interested to make fancy GUI to provide this. I can publish database dump if you're interested.

I'm not interested because pool does not earn bitcoins on getwork/share efficiency. Going to 1:1 ratio is mostly irrelevant, it's only game with numbers. I think you still don't understand this :). What to do with slow CPU miners, which crunch whole space for 2-3 minutes? They should crunch whole nonce just to have fancy 1:1 ratio on pool page?

Of course effectivity of network transfers is nice. You can buy stronger GPU and your getwork/submit efficiency will be higher. But this is not a point. The point is to consistently crunch valid blocks. Thats all.

Btw I think we're slightly offtopic here.

I would love do some stats on a DB dump. PM me the link (or post it). Thank you :)


Only slighty.

SHA-256 returns a random number that is impossible to know before actually doing the work. Since the number returned is random, doing the hashes for one work gives you the exact same chance of solving a block as doing the hashes for another work.

It's like having two boxes full of raffle tickets. Each contains 2 winning tickets. If you find a winning ticket in one box, it doesn't help you (or hurt you) to continue drawing from that box. Nor is it more "efficient" in any way.

I think the question at hand here is, WHY does it not affect the pool's likelihood of finding the answer to the block when ignoring all of these potential answers to hashes?

I understand that the ignored blocks are "compensated" to a degree by processing more getworks, which makes a user see that their share count is still going up, and that (total # of shares in the round) / (number of shares a user submitted for the round) = their payout... for the round.

What I'm asking is, are we less likely to find the answer for THE BLOCK by not submitting these hashes?

...and I think we're entirely on topic considering we're discussing how m0mchill's miner is functioning, in the thread for m0mchill's miner.


If it takes you the same amount of time to draw 15 tickets from 1 box as it does to draw 1 ticket each from 15 boxes, you still have the same 15 tickets, but your chances of having a winning ticket from 1 box are higher if you hold 15 tickets from that box.

Lets say there are 100 tickets in a box, and 2 are winners. You have a 2% chance that the ticket you draw from that box will be the winning ticket.

If you draw 15 tickets from that box, you have a 15% chance.

Now, if you have 15 boxes, each with 100 tickets, and 2 winners, and you draw 1 ticket from each, you still only have a 2% chance that it will be the winner.

If it takes you the same amount of time to draw 15 tickets from 1 box as it does to draw 1 ticket each from 15 boxes, would you rather have a 2% chance, or a 15% chance?

So you have 4 winning tickets, and these tickets would make you eligible to win the grand prize of 50 bitcoins, but only 1 of the 4 tickets is the grand prize winning ticket.
If I choose to quit looking in box 1 after finding just 1 ticket, and do the same for box two, you only find half the tickets.  The grand prize winner ticket might have been left behind in the boxes, but I equally might get lucky and win the grand prize.

I don't know about you, but I'd like to find all 4 tickets, not half of them.

My metaphor was flawed due to my attempt at simplicity, so I will expand it:

There are an endless number of boxes. Each contains 100 tickets. The entire endless set of boxes as a whole has 1 winning ticket for every 99 non-winning tickets, though a single box may contain zero, one, or more winning tickets. The chance of drawing a winning ticket from any box is therefore 1 in 100. It does not matter whether you draw continuously from one box or draw only one ticket from each box: the odds are still 1 in 100.

Completing an entire work is like emptying each box in order. Getting new work after finding something is like moving to the next box after finding a winning ticket. You could also move to the next box every few minutes. There is no concept of efficiency, however, as the chance is always 1 in 100.

Likewise, there are an endless number of works. The entire set as a whole has an exact chance per hash. It doesn't matter how many hashes you do per work: the chance is always the pre-set amount.

This assumes there is only one answer per getwork. In some instances there are none, whereas in other instances there are multiple (for the sake of explanation we'll say there could be 5).

Also, you also have a fixed number of boxes, as there are only a fixed number of 2^32 chunks of a whole block, so I'll ignore your "endless number" logic.

So, lets talk say our "fixed number" is 100 boxes here, and we'll assume that there are a total of 100 winning tickets (shares) and of those 100 tickets, only 1 is the grand prize (the block). We'll also assume that 50 of the boxes are empty.

You take 1 ticket from each box and you have a total of 50 winning tickets, with each of those winning tickets having a 0.5% chance that it will win the grand prize, and a 50% chance that you never drew the grand prize ticket.

- OR -

You could grab EVERY winning ticket from each one of the boxes, and have a 1% chance that each winning ticket could be the grand prize winner, and a 100% chance that at least one of your tickets is going to be the grand prize winner.

Note: This also doesn't take into consideration the fact that one of the first boxes you drew tickets from could contain the winning ticket, but the winning ticket is not the first one drawn. In those instances, one of the ignored tickets (second, or later, ticket drawn from the box) could have been the grand prize winner. Using FairUser's fork of m0mchill's miner, the pool would get the block. Using m0mchill's miner, the pool would not.

The boxes are getwork responses. I said:


There are an unlimited number of unique getwork responses (nearly).

No, there are a fixed number. If every getwork request is unique, and each are giving a portion of the total block, as a 2^32 keyspace, it's a large number (4,294,967,296 to be exact), but not "unlimited".

At a speed of 24 billion hashes/s (roughly the speed of the pool, currently), it would take ~45 minutes to iterate through an entire block assuming the answer was not found until the last share of the last getwork.

In either instance, over the same 45 minute period of time, each miner working in the pool would see roughly the same number of shares contributed using either miner, so your end payout per round is not effected. The frequency at which rounds are solved, by actually submitting all of the possible answers instead of ignoring a large percentage of them, stands to be improved by iterating through each getwork in it's entirety instead of a hit & run method.

May I kindly ask to move this discussion to another/separate thread, please?

I had private discussion with geebus already. Will try to explain one more time here.


With bitcoin you have many much 'boxes' than 'tickets'. To be exact, the boxes and small prize tickets (pool shares) are 2^224. Grand prize tickets are currently ~ 2^209. Only one in 2^15 boxes contains a grand prize ticket. Deciding to begin another box is a probabilistic win - see the Monty Hall problem (http://en.wikipedia.org/wiki/Monty_Hall_problem). OK, not a win, but every box is equal - checking 100 tickets from a new box completely compensates not checking 100 tickets from the previous box.

@FairUser - poclbm makes some assumptions which are counter intuitive at first look. Because it pulls jobs, there is assumption that job should live at most N seconds because otherwise you risk solving already solved block. The probability for this is roughly N/600, but practically always worse because network is growing.

Because there is no single GPU capable of exhausting the 2^32 nonces in 5 (and even in 10) seconds, poclbm does not check for nonce overflow.

Again, I kindly ask to open another thread for discussions not related to poclbm.

I split this topic from python OpenCL bitcoin miner (http://bitcointalk.org/index.php?topic=1334.0) because, as m0mchil pointed out, the posts were largely unrelated to poclbm. Is this title OK?

Aside from the few times that direct questions were posed to Slush, all aspects of this conversation have been directly related to, or in connection to, aspects of the functionality of poclbm. Likewise, the topic is actually pretty much as far off as you can be.

We're not discussing duplicate work. At all. We're discussing how POCLBM is skipping work.

It would be better suited to name the topic, "The inefficiencies of poclbm".


The Monty Hall problem is not exactly what is going on here though. You're saying that the probability of moving on to the next getwork is more likely the case because you would statistically get a higher percent chance of solving the block by choosing a different answer, but the core basis of the argument is not true.

You can't really say, "I have a higher chance in winning if I change my decision" if you're not looking at all the choices. To use the Monty Hall problem as an example, this would be if you were presented with 3 doors, you chose the first door and before the host could open a different door (thus changing your odds in favor of switching), you were presented with a completely new set of doors. Rinse and repeat over and over.

Yes, you may get "lucky" and pick the correct door the first time, but in this instance, you have the option of opening all three doors, taking whatever prizes they may contain, and then moving on to the next set.

Using that as a basis, I could just as easily say ((Total # of 2^32 Keyspaces) / (Collective Pool Hashrate)) / (Number of Active Workers) = N and then hash an entire block myself, only process every Nth nonce and be just as effective as the collective pool is, skipping to the next getwork on each found hash.

Perhaps "How Python OpenCL (poclbm) is mining inefficiently"

This is the key point right here:

Due to the way hashes are essentially random, it doesn't matter if you switch before completing work.

Not every getwork is equal. Not every hash is equal. It's not random. There is a single answer per block. If that answer is never provided because you skipped it, it doesn't fucking matter how many wrong answers you provide to try and make up for it. They will still be wrong.

Yes it does.  It you don't complete your work, you *might* be skipping the correct answer/hash/nonce for the block.
If every getwork is only issued once, and the nonce/answer is skipped because your miner quit looking after finding only 1 answer (when more than 1 is possible), then YOU COULD HAVE SKIPPED THE ANSWER FOR THE BLOCK.  

The entire search-space for a single block is 2^256 hashes.
There are 2^224 answers per block when difficulty is 1.
At the present difficulty of 22012.4941572, there are 2^224 / 22012.4941572 valid answers.
That's 1.224 × 10^63 valid answers.
Out of 1.157 × 10^77 total answers.
The pool can process about 30,000,000,000 hashes per second.
That's 3.0 × 10^10 hashes per second.
It would take 3.859e+66 seconds for the pool to search through every possible hash in a single block.
That's 6.432 × 10^64 minutes.
That's 1.072 × 10^63 hours.
That's 4.467 × 10^61 days.
That's 1.223 × 10^59 years.
That's 8.901 × 10^48 times the age of the universe.

We are searching through a possible 115 quattuorvigintillion, 792 trevigintillion, 89 duovigintillion, 237 unvigintillion, 316 vigintillion, 195 novemdecillion, 423 octodecillion, 570 septendecillion, 985 sexdecillion, 8 quindecillion, 687 quattuordecillion, 907 tredecillion, 853 duodecillion, 269 undecillion, 984 decillion, 665 nonillion, 640 octillion, 564 septillion, 39 sextillion, 457 quintillion, 584 quadrillion, 7 trillion, 913 billion, 129 million, 639 thousand and 936 hashes for every block.

Trying to find, at the current difficulty, one of 1 vigintillion, 224 novemdecillion, 756 octodecillion, 562 septendecillion, 96 sexdecillion, 912 quindecillion, 245 quattuordecillion, 974 tredecillion, 145 duodecillion, 865 undecillion, 520 decillion, 4 nonillion, 272 octillion, 488 septillion, 786 sextillion, 20 quintillion, 128 quadrillion, 241 trillion, 774 billion, 877 million, 474 thousand and 816 valid answers.

You can skip a valid answer by skipping an entire getwork 22012 times.
This will leave you with a possible 1.224 × 10^63 - 1 valid answers.
That's 1.224 × 10^39 times more valid answers than there are stars in the universe.

Only 1 answer get's the block.  So when you say "You can skip an answer by going on to the next work", are you saying that the likely hood of that skipped getwork/answer being *the answer* is sooooooooo small that it's just not worth it to find it, and we should just move on to the next getwork?

I'm saying that there are 1.224 × 10^63 answers which get the block, so skipping one of them is inconsequential.

The answer which counts is simply the first one of those 1.224 × 10^63 valid answers which is found, but it is by no means the only answer.

We simply stop looking after we find it.  If we had wanted to, we could hash the same block for a month and find about 4,380 valid answers for it in that time.

OK, my mind just fucking flipped.  Nobody but you has said their are 1.224 × 10^63 answers to a block.  I've been under the impression (due to imformation provided by others) that only 1 answer was the correct answer to find the block, and that the getwork:solved ratio was always 1:1.
We've been talking about multiple solutions to a getwork....but that now makes a bit more sense as to why I'm seeing more than 1 answer in a getwork.

So ANY one of the possible 1.224 × 10^63 answers would catch me 50 bitcoins?


SO....

1.1579208923731619542357098500869e+77 (2^256) / 1.224e+63 (1.224x(10^63)) = 94601380095846.564888538386445008

94601380095846 / 30000000000 (pool speed) = 3153.3793365282 (seconds)
3153.3793365282 (seconds) / 60 (seconds) = 52.55632227547 (minutes)

That sounds about right.  You're the first one to explain this in that level of detail.  Thank you for clarifying.  Sure wish someone else had said it like that.
So if their are 1.224e+63 answers, the miner just says "10 seconds have passed so fuck it, move to the next getwork and hope we find something."  Something like that??

Man, everybody is talking you that finding a share from work is random. There is nothing as 'exactly one share hidden in every getwork'. There is 1 share in every getwork in AVERAGE, because difficulty 1 means there is one solution per every 2^32 attempts. And 2^32 is the size of nonce, which miners iterate. Nothing more.

And no, title of this topic should not be 'how is poclbm skipping blocks', because it isn't true.

You misquoted me.
I never said "how is poclbm skipping blocks". 
What I did say was "How Python OpenCL (poclbm) is mining inefficiently".
Can you read/see the difference?  If you're going to quote someone, get it right.

poclbm has found 10 blocks for your pool on my machines. 
It's the number of answer's per getwork that I've been questioning, NOT BLOCKS.

Yep, you are losing a negligible percentage of valid answers by skipping the rest of a getwork, but you would invalidate an entire 5% of any correct answers which you find by waiting 30 seconds between getworks.

In other words, you reduce your chances of solving a block by 1/600 for every second of working on a potentially stale getwork.

You'd have to skip 4.49 x 10^64 full getworks in order to skip 1/600th of all valid solutions.

If I read this right you're confirming it's more potentially efficient to skip stale getworks @ 10s rather than wait longer to run through the whole getwork request right?

Correct, you lose 1.67% efficiency with a 10s getwork interval, you might want to lower it to 5s.

If I run with an askrate of 5 seconds on an HD4850, that yields an average of 55M hash/s, it will take me roughly 78 seconds to iterate an entire 2^32 nonce, therefore I'm looking at 6.41% of the getwork and assuming I will find an answer, and that it will likely be within that 5 second span of time, each time. Correct? Theoretically thats what is being said, right?

I can see that working for a 6950 getting ~350M hash/s (13-14 seconds for a full 2^32) because I'd still be covering 40% of that getwork, but for slower cards, or CPU miners, it seems ridiculous to assume you would find an answer in the first 5, 10 or even 20 seconds.

m0mchills miner, as the code appears on the git hub, is forcing the askrate to be between 1 and 10 seconds. i.e. if I set my askrate to 20 seconds, the miner will automatically set it to 10.

It's inefficient to do so. Faster cards can iterate a getwork quick enough for 5 (or 10) seconds to be a worthwhile, slower cards cannot.

Lets assume for a moment that I have 2 cards. One running at ~55M hash/s and one at 350M hash/s. I process 1000 getworks with each, at a 5 second ask rate.

350M hash/s card:
2^32 / 350,000,000 = 12.7 s
39.7% of each getwork completed in 5 seconds.
Essentially, 397 of 1000 getworks were searched entirely.

55M hash/s card:
2^32 / 55,000,000 = 78.1 s
6.41% of each getwork completed in 5 seconds.
Essentially, 64 of 1000 getworks were searched entirely.

The statistical probability of an answer being found in the first 6.41% of a getwork is so low that you may as well not bother mining with an askrate that low, or switch to a CPU miner.

You are assuming that you are able iterate through some significant percentage of the entire available search space, which you cannot, even if you mined for the rest of your life on all of the hardware of the earth combined.

There is a set chance of finding a winning block on any single hash that you do, like playing the lottery.  It does not matter in what order you choose the tickets, out of a bucket of a near-infinite pile of tickets, one out of every X of which happens to be a winner.  Your chance of picking a winner is always the same on every draw.

One 32-bit getwork is equivalent to .0000000000000000000000000000000000000000000000000000000000000000037% of the entire search space.

That is really only a concern if I'm looking to solve "the block" with an answer. I realize that the likelihood of me solving the block is extremely low. My concern lies in finding a "share" in a pool environment similar to slush's pool.

With an askrate of 5 seconds, you likelihood to find a share in a getwork within 5 seconds on slower miners is so incredibly low that you're basically nullifying their chances of doing so.

Both of my previous examples cited GPUs. One at a fairly decent speed, and one much slower. That didn't even take into consideration CPU mining, where you may only be getting ~5M hash/s. It would take 859 seconds to process through a single getwork, and 5 seconds would be only 0.58% of that getwork.

This causes significantly high traffic on the server due to repetitive and constant getwork requests that yield little to no gains for the pool. Even 10 seconds would be low for a lot of miners.

If you adjusted the ask rate based on the speed of the card, and assumed that you could adjust anything slower than ~86M hash/s (50 seconds for 2^32 getwork) to a reasonable speed (around 20 - 25s perhaps) then you could significantly reduce traffic to the server, still yield roughly the same number of shares submitted over the same period of time, and would likely allow slower clients to discover results they normally would have missed or never gotten to (like, anything in the other 99.42% of the getwork).

Likewise, working off of the logic that it's all a matter of luck on whether or not those shares may solve the block, you would have the exact same chance of solving the block.

I don't know about you, but if I were the one running a pool, having my bandwidth and server resources reduced by a significant amount would make me happy.

The chance of finding a share is still exactly the same whether you spend 50 seconds on 1 getwork or 5 seconds each on 10 getworks in a row. 


I do run a pool, and I don't pay for stale shares since they are of no help to me in solving a block.  Slush does not pay for them for the same reason.

If your goal is to win, you should be playing today's lottery, not last week's.

If this still doesn't make sense, please re-read the technical specifications of bitcoin block generation and summarize them in a post, then I could correct any misunderstandings you may have about the process.