|
Title: Calculating a block - merkle root question Post by: Pibers on June 06, 2011, 08:08:07 PM Hey,
I've read a lot but there still are questions for writing my own (test-)miner :) I guess I know how to get all data for calculation a block except for how to 'calculate' the merkle root. I far as I understand I first have to get all recent transactions. Let's say these are only four with the hashes 1, 2, 3 and 4 (I know that this aren't real hashes). Now I take these and hash them like this: Code: masterhash Code: SHA256( SHA256(1 + 2) + SHA256(3 + 4) ) Do I have to write just the masterhash in the block or all transactions? (On blockexplorer.com there are all transactions but I don't know...) And how do I know what are new transactions and what are old? I guess I look in the old block but what is the newest transaction in the old block? If I now have the (for example) four newest block and the right merkle root what happens if a new transaction is made while I calculate the block? Is the block still valid? It woul be so nice if someone could explain me that. Thank you! :) Oh and one other question.. what happens if two users calculate a valid block at the exact same time? I guess both blocks could be share through the network and at the and one half has the one and the other half the other block. Which one is the valid then!? Thanks! Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 06, 2011, 11:16:38 PM it would be also helpful to understand how a miner chooses or is forced to choose amongst tx's? why not just choose the one simplest tx and hash that to speed block win?
Title: Re: Calculating a block - merkle root question Post by: theymos on June 07, 2011, 06:16:46 PM Miners don't deal with that. Bitcoin does that stuff and returns the result to miners in getwork.
Here's an example of a tree: https://en.bitcoin.it/wiki/Dump_format#CBlock If you find the full hashes used here (search Bitcoin Block Explorer), you can try hashing them yourself. They will work. You take each pair of transaction hashes, concatenate them, and hash them twice with SHA-256. Keep doing this until you have only one hash left. When there is an odd number of hashes, concatenate the last hash with itself. So your example is correct if you double each hash. The top hash (Merkle root) is included in the block header. The transactions are in the block body. Intermediate hashes in the tree are not included in the block. Bitcoin has a database of all transactions, which lets it know which transactions are new. It also needs to check the validity of all transactions before including them. In the case of a tie, only one block will end up being accepted. Whoever ends up solving the next block will decide which one. Bitcoin gets transactions from the network. You're not forced to include any transactions, though in the future most of your income will come from transaction fees. So your block is still valid if you miss a transaction (or even all transactions). Again, nothing I described in this post is done by mining software. Title: Re: Calculating a block - merkle root question Post by: Pibers on June 07, 2011, 10:13:50 PM Thank you so far, that helps :)
A few questions are left... Miners don't deal with that. Bitcoin does that stuff and returns the result to miners in getwork. getwork is new for me! I googled it and wonder if you mean m0mchils patch? I patch the bitcoin client (or server?) with it and so I'm able to get block data and return it to the network if I find a block? That would be easier than I thought but not really a own miner implementation I guess? :)You take each pair of transaction hashes, concatenate them, and hash them twice with SHA-256. Keep doing this until you have only one hash left. When there is an odd number of hashes, concatenate the last hash with itself. If I understand you right I could take only one of the new transactions and double SHA256 it with the concatenation of itself? Like SHA256(SHA256(hash + hash))?So your example is correct if you double each hash. The top hash (Merkle root) is included in the block header. The transactions are in the block body. Intermediate hashes in the tree are not included in the block. Bitcoin has a database of all transactions, which lets it know which transactions are new. It also needs to check the validity of all transactions before including them. So what I have then is a really small merkle root isn't it? I could use it for a valid block but I guess that isn't really good for the quality of the network!? Is there nothing to ensure that as many transactions as possible will be putted in a new block? In the case of a tie, only one block will end up being accepted. Whoever ends up solving the next block will decide which one. Only the longest chain is valid right? So there is a tie of two chains cause of two valid blocks and the next block for one of it decided that this on is the valid chain. But now there could be also been found a newblock for the other chain and after that one again one more new block. So now the other chain is longer than the first one! Is this one now the new valid?? My englisch is too bad I hope you understand :) Thanks! Title: Re: Calculating a block - merkle root question Post by: theymos on June 07, 2011, 11:19:23 PM getwork is new for me! I googled it and wonder if you mean m0mchils patch? I patch the bitcoin client (or server?) with it and so I'm able to get block data and return it to the network if I find a block? That would be easier than I thought but not really a own miner implementation I guess? :) It's an official RPC method now. Every recent version of Bitcoin has it. It allows miners to get the necessary data from Bitcoin. Quote If I understand you right I could take only one of the new transactions and double SHA256 it with the concatenation of itself? Like SHA256(SHA256(hash + hash))? So what I have then is a really small merkle root isn't it? I could use it for a valid block but I guess that isn't really good for the quality of the network!? "Keep doing this until you have only one hash left." If you have only one transaction in the block, then the hash of that transaction is the Merkle root. Quote Is there nothing to ensure that as many transactions as possible will be putted in a new block? No. Only transaction fees. Quote Only the longest chain is valid right? So there is a tie of two chains cause of two valid blocks and the next block for one of it decided that this on is the valid chain. But now there could be also been found a new block for the other chain and after that one again one more new block. So now the other chain is longer than the first one! Is this one now the new valid?? That could happen, though it is unlikely. The ties will be broken eventually. Whoever gets the last block in the series of ties will decide it. Title: Re: Calculating a block - merkle root question Post by: Pibers on June 08, 2011, 02:49:43 PM Thank you again, you're great help :)
I found out how to "get work" and I also found the format description on that site: https://en.bitcoin.it/wiki/Original_Bitcoin_client/API_calls_list What I understand ist "target" but I have no idea what I have to do with midstate, data and hash1? Where is the body with the transactions? How can I calculate the block without that? Maybe bitcoin don't give me this data but only what I need for calculation? But when I calculate a while how did bitcoin now with which data I made my calculation when I send it back? And thats my next question. I can send data back with "getwork [data]" but in which format? Sorry if that's explained somewhere in the wiki but I haven't found something (nor on google). Title: Re: Calculating a block - merkle root question Post by: theymos on June 08, 2011, 04:09:42 PM "midstate" and "hash1" are optionally used for a mining optimization. Some of the work doesn't need to be repeated for each attempt: this is the data that allows you to skip it.
"data" is what you're hashing. You hash this, modify the nonce in the data if the hash is not below the target, and repeat. You only need to hash the header, which is the "data" getwork gives you. The block body is not hashed by miners. Bitcoin deals with this. When you return a block, Bitcoin just checks to see if it's valid. It doesn't need to match anything. I assume that you pass hexadecimal data back to getblock. I'm not sure. Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 04:31:42 PM Thank you again, you're great help :) theymos is The Man. Title: Re: Calculating a block - merkle root question Post by: Pibers on June 08, 2011, 04:35:22 PM Ah ok, but how do I know which part in that big hexadecimal string is the nonce?
Isn't there somewhere a more specific documentation about all that? Or where did you learn all this? I did a lot of googling but couldn't find out :) If I pass the data back to the server in hexadecimal is there a way to test or get an answer if that was right? Did the server answert with something like "ok" or "bad data"? Thanks! Thank you again, you're great help :) theymos is The Man. [Edit] Or I guess you mean it like that then I have to say "indeed!" ;) Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 04:36:20 PM "midstate" and "hash1" are optionally used for a mining optimization. Some of the work doesn't need to be repeated for each attempt: this is the data that allows you to skip it. "data" is what you're hashing. You hash this, modify the nonce in the data if the hash is not below the target, and repeat. You only need to hash the header, which is the "data" getwork gives you. The block body is not hashed by miners. Bitcoin deals with this. When you return a block, Bitcoin just checks to see if it's valid. It doesn't need to match anything. I assume that you pass hexadecimal data back to getblock. I'm not sure. theymos, so miners can choose the tx's they want to include initially in the midstate or hash1 to form the Merkle root which is included in the header and then from there forward they can hash away with only the nonce changing until they undercut the target? Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 04:36:42 PM Ah ok, but how do I know which part in that big hexadecimal string is the nonce? Isn't there somewhere a more specific documentation about all that? Or where did you learn all this? I did a lot of googling but couldn't find out :) If I pass the data back to the server in hexadecimal is there a way to test or get an answer if that was right? Did the server answert with something like "ok" or "bad data"? Thanks! Thank you again, you're great help :) theymos is The Man. hardly Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 04:39:28 PM Ah ok, but how do I know which part in that big hexadecimal string is the nonce? as i understand it your computer starts the nonce at 1 and for each hash you increase its value by 1 until u hit the max and then u start with the Extra Nonce values. Title: Re: Calculating a block - merkle root question Post by: Pibers on June 08, 2011, 04:42:44 PM as i understand it your computer starts the nonce at 1 and for each hash you increase its value by 1 until u hit the max and then u start with the Extra Nonce values. But where do you but the nonce? Here is an example answer of getwork:Code: {I guess it's smarter to put a random value in nonce and not starting from 1 to X isn't it? Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 04:57:35 PM as i understand it your computer starts the nonce at 1 and for each hash you increase its value by 1 until u hit the max and then u start with the Extra Nonce values. But where do you but the nonce? Here is an example answer of getwork:Code: {Quote from: Pibers I guess it's smarter to put a random value in nonce and not starting from 1 to X isn't it? why? 1 or 1000001 will change the hash equally.Title: Re: Calculating a block - merkle root question Post by: Pibers on June 08, 2011, 05:55:56 PM the hence is 32 bit so it is 1 to 4294967296. I guess it's to slow to check all these out but on the other hand it's the same chance to find a block with your method than mit the random one I guess. Someone maybe knows how it is done in practice?
Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 05:58:40 PM the hence it 32 bit so it is 1 to 4294967296. I guess it's to slow to check all these out but on the other hand it's the same chance to find a block with your method than mit the random one I guess. Someone maybe knows how it is done in practice? http://blockexplorer.com/block/00000000000011f44a8c2144764423180532c6c557b479503b78b1b548881abc hover your pointer over the nonce ? mark and it defines how its done Title: Re: Calculating a block - merkle root question Post by: theymos on June 08, 2011, 07:51:39 PM Code: 00000001 version Title: Re: Calculating a block - merkle root question Post by: theymos on June 08, 2011, 07:53:46 PM theymos, so miners can choose the tx's they want to include initially in the midstate or hash1 to form the Merkle root which is included in the header and then from there forward they can hash away with only the nonce changing until they undercut the target? No. The transactions are already chosen when you get getwork. midstate and hash1 are used only to make hashing faster. Title: Re: Calculating a block - merkle root question Post by: theymos on June 08, 2011, 07:55:03 PM If I pass the data back to the server in hexadecimal is there a way to test or get an answer if that was right? Did the server answert with something like "ok" or "bad data"? It returns true or false. Title: Re: Calculating a block - merkle root question Post by: cypherdoc on June 08, 2011, 08:09:19 PM theymos, so miners can choose the tx's they want to include initially in the midstate or hash1 to form the Merkle root which is included in the header and then from there forward they can hash away with only the nonce changing until they undercut the target? No. The transactions are already chosen when you get getwork. midstate and hash1 are used only to make hashing faster. wait, i thought it was a given that miners could choose btwn paying tx's and non paying? Title: Re: Calculating a block - merkle root question Post by: theymos on June 08, 2011, 08:13:49 PM You need to modify the Bitcoin code for that. You can't do it just by using getwork.
Title: Re: Calculating a block - merkle root question Post by: Pibers on June 09, 2011, 02:48:37 PM Hey,
I took data with getwork while block 129593 was the newest on blockexplorer.com and also with bitcoind getinfo it said "block" : 129593. But now I have a Problem. This is what "bitcoind getwork" gave me (already formated): Code: 00000001 000000004e600000273de2fa70e4aaff5da70123bd19cecb3c0c7b0f24da7ab9 But bitexplorer said that previous hash is: 000000000000169df290bd7628e59dae18405aba2f660b4ff832f93dc9a10fb0 The first hash also hasn't enough zeros I guess!? What's wrong there? What can I do to convert the data from blockexplorer to a valid data string for getwork? I would like to test to send a valid block (after it is solved) and see no other way to do it than taking the data from blockexplorer... Title: Re: Calculating a block - merkle root question Post by: theymos on June 09, 2011, 06:18:24 PM The hashes have been reversed on 8-byte boundaries. I guess this is a hashing optimization. I'm not sure.
Title: Re: Calculating a block - merkle root question Post by: Pibers on June 09, 2011, 08:20:44 PM Mh thanks but I don't get that but I think it is not so important :)
Though I have one last question. When I want to calculate a block am I on the right way with that? - I take the data string from getwork (without line breakes) - I try many values at the place in the string where the nonce is (should be from char at position 153 to 161) - After each nonce value I SHA256 the whole string - Now I test if there is the right count of leading zeros!? I dont understand the last step. Afaik I have to check if the hash is smaller than the current target. But how can I do this? For example the hash from previous post: 000000000000169df290bd7628e59dae18405aba2f660b4ff832f93dc9a10fb0 How can I check if it is valid? (I dont mean the check bitcoin does like if the merkle tree or the timestamp is right. I mean just the check if it hast the right difficulty) Title: Re: Calculating a block - merkle root question Post by: theymos on June 09, 2011, 09:11:57 PM They're both large numbers. Just see if the hash is less than the target.
You shouldn't do this every try, though. It's more efficient to count the zeroes and then do a full test when you have a candidate. Title: Re: Calculating a block - merkle root question Post by: Pibers on June 10, 2011, 04:21:43 PM Oh yes, now where you have said it it is obvious :-[
Thanks! :) I guess you have no solved old data block or know where I can get one? Maybe for testnet? Title: Re: Calculating a block - merkle root question Post by: theymos on June 10, 2011, 05:56:04 PM I don't have old getdata output. Here's a block header you can try hashing, though this does not have the reversal on 8-bytes:
Code: 010000001d8f4ec0443e1f19f305e488c1085c95de7cc3fd25e0d2c5bb5d0000000000009762547903d36881a86751f3f5049e23050113f779735ef82734ebf0b4450081d8c8c84db3936a1a334b035b |