When a block is solved, is everyone else's work wasted?

[cjcole8]

I have several questions, but the topic is my biggest:

1) When a block is solved, does everyone else have to start over, create a new block, and begin looking for the right hash again?  For example, Slush's pool, ASICminer, and BTCGuild are all mining.  Slush solves a block, so ASICminer and BTCGuild both forget their current block, make a new one, and start over again.  Is that right? Seems a waste that way, and actually better to have 2-3 big pools rather than 30 or more smaller ones.

2) How are the transactions chosen to be put in a block? Do you just basically grab whatever transactions are floating out there that are not in a block, put them together, and start trying to find the right hash solution?

3) If you can just put any transactions you want in a block, what is the incentive to include any transaction that does not include a fee?

4) Double SHA-256 hash for hello here https://en.bitcoin.it/wiki/Protocol_specification I can't repeat.  The first round I get the same, but the 2nd round I get d7914fe546b684688bb95f4f888a92dfc680603a75f23eb823658031fff766d9 instead.  What am I doing wrong?

Thanks!  I've done some searching of the forums, wiki, etc. and haven't found those answers on my own.

[rme]

I have several questions, but the topic is my biggest:

1) When a block is solved, does everyone else have to start over, create a new block, and begin looking for the right hash again?  For example, Slush's pool, ASICminer, and BTCGuild are all mining.  Slush solves a block, so ASICminer and BTCGuild both forget their current block, make a new one, and start over again.  Is that right? Seems a waste that way, and actually better to have 2-3 big pools rather than 30 or more smaller ones.
Blocks are created thousands of time in a second, but they do not have the right hash to be valid blocks (so you have to try again).
Any block contains last block hash so if a new block is found you have to change your blocks (the ones you are generating), that does not interrupt you because you still have the same probabilities.


2) How are the transactions chosen to be put in a block? Do you just basically grab whatever transactions are floating out there that are not in a block, put them together, and start trying to find the right hash solution?
There is a list of unconfirmed tx in every Bitcoin client (you can see it on http://blockchain.info/unconfirmed-transactions).
If you are mining you include all the tx that can fit into a block (up to 1MB right now). You want to profit so you include the ones that have higher fees.

3) If you can just put any transactions you want in a block, what is the incentive to include any transaction that does not include a fee?
You can decide, if you have space left in a block (up to 1MB) you can include no-fee transactions, but if a block can only have 500tx (example, not real data) and you have 500tx with fee and 100 without you will only include the ones that have. (Its up to the miner but they all want money).

Thanks!  I've done some searching of the forums, wiki, etc. and haven't found those answers on my own.

Answered in bold

[cjcole8]

So in response to your answer to my question #1. Do you create an entirely new block every time you attempt to find a new, valid hash for it?  Again, that seems like a waste. If you try one hash and it doesn't work, you move on to the next because you know the old one doesn't work. So your odds improve every time - unless you change your block every time. Then it's just playing the lottery over and over again. Or maybe I'm falling for the gambler's fallacy?

So I'm seeing 2 scenarios.  Scenario 1, Slush tries to figure out the same block over and over again until BTCGuild finds the solution to a block.  Then Slush needs to grab a new set of unconfirmed transactions, update the previous block hash to the one that BTCGuild just solved, and then start over again, trying the hash over and over again.  For scenario 2, Slush forms a block, tries a hash solution, then forms a new block, tries a hash solution, etc. until he wins the lottery.  Which is it?  I just can't help but see wasted effort every time Slush has to form a new block without solving the old one.

[DannyHamilton]

If you re-hash the exact same block, you will get the exact same hash.  That is useless.

To get a different hash result you HAVE to change the data you are hashing.  Generally this is done by modifying a piece of data in the block header called a nonce.  Incrementing the nonce results in a slightly different block header which then results in a completely different hash.

Miners are so fast now (and difficulty is so high), that they typically try every possible nonce without finding a valid solution.  Then the miner HAS TO modify the transactions and rebuild the block so they can try again.

So miners (or pools) already have to rebuild the entore block MANY times before a solution is even found.

There is no "making progress" towards a solution.  Every attempt has as good of a chance of being the right solution as every other attempt.  Think of it like rolling dice.  If 2 people each roll a die until one of them rolls a 1, are all the previous rolls "wasted"?  Has anyone's chances of rolling a 1 gotten better (or worse) just because a 1 has (or hasn't) been rolled yet?

[cjcole8]

That clears things up for me I think.  I had thought you could just change the nonce until you eventually found the right hash (that's what I meant by checking the same block over and over - changing the nonce and nothing else).  I didn't realize you could go all the way through every possible nonce value and still not find a good hash.  Thanks!

Anybody have an answer to my last question on double hashing?

Hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 (first round on sha-256)
d7914fe546b684688bb95f4f888a92dfc680603a75f23eb823658031fff766d9 (2nd round of sha-256, from hashing the above value)

However the wiki page above says the 2nd round should yield this value:
9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50

What am I doing wrong?

[infinitecoin]

How does the change of nonce work? does it do in order, or completely random?

[linuxer]

thanks rme

[DannyHamilton]

Anybody have an answer to my last question on double hashing?

Hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 (first round on sha-256)
d7914fe546b684688bb95f4f888a92dfc680603a75f23eb823658031fff766d9 (2nd round of sha-256, from hashing the above value)

However the wiki page above says the 2nd round should yield this value:
9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50

What am I doing wrong?

Usually when someone asks this question it is because they are hashing the result of the first hash as a string of characters rather than as a block of binary data.

(ex. 0A would be a hex representation of  00001010, but as a string it would be represented as 00110000 01000001)

[debianlinux]

There is no "making progress" towards a solution.  Every attempt has as good of a chance of being the right solution as every other attempt.  Think of it like rolling dice.  If 2 people each roll a die until one of them rolls a 1, are all the previous rolls "wasted"?  Has anyone's chances of rolling a 1 gotten better (or worse) just because a 1 has (or hasn't) been rolled yet?

I don't entirely agree with this. In the dice analogy it would be more accurate to say that once a "1" is rolled the person who rolled the "1" will no longer roll another "1" because "1" has been proven to not be the solution to the problem at hand. That is, he would reduce the number of faces on the dice before rolling again. I agree that each attempt has equal chance of being the right solution in that the chance of rolling a "1" was just as good as rolling a "6" and that on the successive roll the chance of rolling a "5" will be just as good as rolling a "6" but chance of rolling another "1" has now been made zero and the available pool of possible answers has been reduced. Since the pool of possible answers is finite and thus every attempt proven incorrect will not be reattemtped  the next attempt does run a statistically higher chance of being the correct answer than the previous attempt.

[DannyHamilton]

How does the change of nonce work? does it do in order, or completely random?

While in theory the order shouldn't matter, for simplicity sake I believe miners all do it in order.  It makes it much easier for the program to keep track of which nonces it has already tried.

[cjcole8]

I don't entirely agree with this. In the dice analogy it would be more accurate to say that once a "1" is rolled the person who rolled the "1" will no longer roll another "1" because "1" has been proven to not be the solution to the problem at hand. That is, he would reduce the number of faces on the dice before rolling again. I agree that each attempt has equal chance of being the right solution in that the chance of rolling a "1" was just as good as rolling a "6" and that on the successive roll the chance of rolling a "5" will be just as good as rolling a "6" but chance of rolling another "1" has now been made zero and the available pool of possible answers has been reduced. Since the pool of possible answers is finite and thus every attempt proven incorrect will not be reattemtped  the next attempt does run a statistically higher chance of being the correct answer than the previous attempt.

This is exactly what I mean by wasted work when a block solution is found by someone else. This analogy seems better to me.  Anytime you have to change something besides the nonce in your block, you're starting over.

[DannyHamilton]

I don't entirely agree with this. In the dice analogy it would be more accurate to say that once a "1" is rolled the person who rolled the "1" will no longer roll another "1" because "1" has been proven to not be the solution to the problem at hand. That is, he would reduce the number of faces on the dice before rolling again. I agree that each attempt has equal chance of being the right solution in that the chance of rolling a "1" was just as good as rolling a "6" and that on the successive roll the chance of rolling a "5" will be just as good as rolling a "6" but chance of rolling another "1" has now been made zero and the available pool of possible answers has been reduced. Since the pool of possible answers is finite and thus every attempt proven incorrect will not be reattemtped  the next attempt does run a statistically higher chance of being the correct answer than the previous attempt.

I think you are mistaken.  There is no guarantee that a any solution will work for any given block.  While the pool of possible answers is finite, it is so large that it can essentially be considered infinite for the purposes of considering an increase in statistical probability.  If we consider the pool of potential hashes to be "finite" then we also have to consider that a resulting hash is not removed from the pool, since that same hash could be calculated again with a different set of data.

The next hash you calculate after incrementing the nonce is no more or less likely to result in a solution than then previous or the next hash.

[DannyHamilton]

I don't entirely agree with this. In the dice analogy it would be more accurate to say that once a "1" is rolled the person who rolled the "1" will no longer roll another "1" because "1" has been proven to not be the solution to the problem at hand. That is, he would reduce the number of faces on the dice before rolling again. I agree that each attempt has equal chance of being the right solution in that the chance of rolling a "1" was just as good as rolling a "6" and that on the successive roll the chance of rolling a "5" will be just as good as rolling a "6" but chance of rolling another "1" has now been made zero and the available pool of possible answers has been reduced. Since the pool of possible answers is finite and thus every attempt proven incorrect will not be reattemtped  the next attempt does run a statistically higher chance of being the correct answer than the previous attempt.

This is exactly what I mean by wasted work when a block solution is found by someone else. This analogy seems better to me.  Anytime you have to chance something besides the nonce in your block, you're starting over.

Sure, but that has as good of a chance of helping you (by preventing you from wasting time on a block that wasn't solvable) as it does of hurting you (by keeping you from getting to the later solution that might have been in that block).  In the end it's a wash.

[cjcole8]

Thanks Danny.  Cryptography is one of those topics that sometimes seems simple on the surface, but the further you dig, the more complicated it can get. Nice to get some answers.

[debianlinux]

I think you are mistaken.  There is no guarantee that a any solution will work for any given block.  While the pool of possible answers is finite, it is so large that it can essentially be considered infinite for the purposes of considering an increase in statistical probability.  If we consider the pool of potential hashes to be "finite" then we also have to consider that a resulting hash is not removed from the pool, since that same hash could be calculated again with a different set of data.

The next hash you calculate after incrementing the nonce is no more or less likely to result in a solution than then previous or the next hash.

I'm trying hard to follow you here. Your first statement insinuates that it is possible to build a block that has no solution whatsoever which I think is patently false. In the next statement you conflate a finite pool in which there is a correct answer with being so large as to be infinitely sized. If that is the case then it would possible and even likely that any given block could result in an infinite amount of time being required to solve it. Strangely enough, the network tends to solve blocks at roughly 10 minutes each with no happenstances where the network stalls out because it is going to take infinite years to solve this one. I will concede the point that hash collisions can be found in a sufficiently sized pool.

[DannyHamilton]

Note that the nonce is a 32 bit integer.  This means there are only 4.2 billion possibilities to try for a given block.  A miner with 4.2 gigahash/second can try every possibility in 1 second. (or is it 2 seconds because of the double hash? I can't remember).  Regardless, in a given 10 minute timeframe on average, new blocks are frequently generated.  Any pool (or solo miner) with access to significant hash power would be wise to pre-generate multiple potential blocks while the current one is being hashed.  They'd keep a queue of these pre-generated potential blocks ready so there is no delay between the exhaustion of nonces on one block and the beginning of hashing the next.

[DeathAndTaxes]

I don't entirely agree with this. In the dice analogy it would be more accurate to say that once a "1" is rolled the person who rolled the "1" will no longer roll another "1" because "1" has been proven to not be the solution to the problem at hand. That is, he would reduce the number of faces on the dice before rolling again. I agree that each attempt has equal chance of being the right solution in that the chance of rolling a "1" was just as good as rolling a "6" and that on the successive roll the chance of rolling a "5" will be just as good as rolling a "6" but chance of rolling another "1" has now been made zero and the available pool of possible answers has been reduced. Since the pool of possible answers is finite and thus every attempt proven incorrect will not be reattemtped  the next attempt does run a statistically higher chance of being the correct answer than the previous attempt.

I think you are mistaken.  There is no guarantee that a any solution will work for any given block.  While the pool of possible answers is finite, it is so large that it can essentially be considered infinite for the purposes of considering an increase in statistical probability.  If we consider the pool of potential hashes to be "finite" then we also have to consider that a resulting hash is not removed from the pool, since that same hash could be calculated again with a different set of data.

The next hash you calculate after incrementing the nonce is no more or less likely to result in a solution than then previous or the next hash.

This.

The set of possible solutions 2^256 and globally in the time period of a block being solved a negligible percentage have been completed.  However there is no 1:1 mapping between inputs and hashes in a hashing function.  An infinite number of inputs can produce the same hash. 

Routinely within one block "window" the two elements of the blockheader that are changed are the timestamp, the merkleroot hash, and the nonce.  That provides 2^320 potential solutions.   Any potential progress is so negligible that for all practical purposes it can be considered zero and thus each attempt is independent. 

https://en.bitcoin.it/wiki/Block_hashing_algorithm

Each hash has a 1 in (difficulty)*(2^32) chance of solving a block.   At current difficulty that means each hash has an independent chance of 1 in  52,198,505,828,311,400 chance of winning the block jackpot.   Each hash/ticket is checked and discarded. If it doesn't solve the block much like a losing lottery ticket there is no progress (in any usable sense).  You are just as far from wining the jackpot on the next ticket.

[DannyHamilton]

The set of possible solutions 2^256 and globally in the time period of a block being solved a negligible percentage have been completed.  However there is no 1:1 mapping between inputs and hashes in a hashing function.  An infinite number of inputs can produce the same hash. 

Routinely within one block "window" the two elements of the blockheader that are changed are the timestamp, the merkleroot hash, and the nonce.  That provides 2^320 potential solutions.   Any potential progress is so negligible that for all practical purposes it can be considered zero and thus each attempt is independent. 

https://en.bitcoin.it/wiki/Block_hashing_algorithm

Each hash has a 1 in (difficulty)*(2^32) chance of solving a block.   At current difficulty that means each hash has an independent chance of 1 in  52,198,505,828,311,400 chance of winning the block jackpot.   Each hash/ticket is checked and discarded. If it doesn't solve the block much like a losing lottery ticket there is no progress (in any usable sense).  You are just as far from wining the jackpot on the next ticket.

Thanks!  You just saved me a bunch of typing.

 

[DeathAndTaxes]

I'm trying hard to follow you here. Your first statement insinuates that it is possible to build a block that has no solution whatsoever which I think is patently false. In the next statement you conflate a finite pool in which there is a correct answer with being so large as to be infinitely sized. If that is the case then it would possible and even likely that any given block could result in an infinite amount of time being required to solve it. Strangely enough, the network tends to solve blocks at roughly 10 minutes each with no happenstances where the network stalls out because it is going to take infinite years to solve this one. I will concede the point that hash collisions can be found in a sufficiently sized pool.

The solution isn't infinitely hard the set of possible blocks is so large as to be practically infinite.  When solving a block even if one only modifies nonce, merkleroot hash, and timestamp the set of potential blocks is 2^320 this is even larger than the number of potential hashes (2^256) and is a number so large that for all practical purposes (related to mining) can be considered infinite).

I think you might be confused in thinking there is only one possible solution.  There is a LOT (once again pretty much infinite) possible solutions which could be the next valid block. 

Lastly you seem to think that all blocks must need a solution in order for the next valid (solved) block to be found.  That isn't true.  MOST blocks have no solution eventually miners will (collectively) by random chance find a block which does have a solution.   A particular block is created and then an incrementing nonce is added to the rest of the blockheader.  All nonce values are tried and if none of them produce a solution (hash below target based on difficulty) then that block will never have a solution.  Miners simply discard that block and attempt a new block (either by changing the coinbase tx or the timestamp).

Every 4 billion attempted hashes you have to change "something" all solutions for the current block (call it block candidate if you like) have been tried.  You can't attempt more solutions without changing the block in some manner.  Changing the timestamp or merklehash is not materially different than changing the prior block hash (because someone else found a block).  There is no progress.  You either solve a block or you don't.  Each attempt is a random chance like a lottery ticket. 


When difficulty is X that means on average miners (globally and collectively) attempted to find solutions for X blocks and failed before finding one which meets the difficulty target.

[debianlinux]

Lastly you seem to think that all blocks must need a solution in order for the next valid (solved) block to be found.  That isn't true.  MOST blocks have no solution eventually miners will (collectively) by random chance find a block which does have a solution.

This clarifies things a great deal for me. I was operating under the assumption that all miners were attempting to solve the same block.