Calculating a block - merkle root question

[Pibers]

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
        /        \
    hash12       hash34
    /    \        /    \
  1       2      3      4

Is that right? And how exately do I hash them? Is it

Code:

SHA256( SHA256(1 + 2) + SHA256(3 + 4) )

where + is writing it just one after the other?

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!

[1713909572]

1713909572

[cypherdoc]

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?

[theymos]

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.

[Pibers]

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.
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.

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!?
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 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?? My englisch is too bad I hope you understand

Thanks!

[theymos]

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.

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.

Is there nothing to ensure that as many transactions as possible will be putted in a new block?

No. Only transaction fees.

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.

[Pibers]

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).

[theymos]

"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.

[cypherdoc]

Thank you again, you're great help

theymos is The Man.

[Pibers]

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.

jealous?
[Edit]
Or I guess you mean it like that then I have to say "indeed!"

[cypherdoc]

"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?

[cypherdoc]

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.

jealous?

hardly

[cypherdoc]

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.

[Pibers]

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:

{
    "midstate" : "695d56ae173bbd0fd5f51d8f7753438b940b7cdd61eb62039036acd1af5e51e3",
    "data" : "000000013d9dcbbc2d120137c5b1cb1da96bd45b249fd1014ae2c2b400001511000000009726fba001940ebb5c04adc4450bdc0c20b50db44951d9ca22fc5e75d51d501f4deec2711a1d932f00000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000",
    "hash1" : "00000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000010000",
    "target" : "00000000000000000000000000000000000000000000002f931d000000000000"
}

I guess it's smarter to put a random value in nonce and not starting from 1 to X isn't it?

[cypherdoc]

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:

{
    "midstate" : "695d56ae173bbd0fd5f51d8f7753438b940b7cdd61eb62039036acd1af5e51e3",
    "data" : "000000013d9dcbbc2d120137c5b1cb1da96bd45b249fd1014ae2c2b400001511000000009726fba001940ebb5c04adc4450bdc0c20b50db44951d9ca22fc5e75d51d501f4deec2711a1d932f00000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000",
    "hash1" : "00000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000010000",
    "target" : "00000000000000000000000000000000000000000000002f931d000000000000"
}

for these types of detailed programming questions i'll defer to theymos

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.

[Pibers]

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?

[cypherdoc]

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

[theymos]

Code:

00000001 version
3d9dcbbc2d120137c5b1cb1da96bd45b249fd1014ae2c2b40000151100000000 prev
9726fba001940ebb5c04adc4450bdc0c20b50db44951d9ca22fc5e75d51d501f root
4deec271 timestamp
1a1d932f target
00000000 **This is the nonce**
000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

[theymos]

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.

[theymos]

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.

[cypherdoc]

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?