What are the transactions of a merkle tree for an *unsolved* block?

bcforum

full member

Activity: 140

Merit: 100

Quote from: perfectfire on September 02, 2011, 11:45:20 PM

So the bitcoin daemon gives you the merkle root? From the above posts it sounded like you could decide for yourself what transactions to include in the calculation of the merkle root. But now it sounds like the daemon decides for you.

The CheckBlock method in the bitcoin source only checks that vector of transactions is non-empty, that the first transaction is the coinbase, and that each subsequent transaction is not the coinbase and is a valid transaction. If there is only one transaction and that transaction is the coinbase then the block is valid. So it seems that no matter what merkle root the daemon gives you, if you change it to be the merkle root of only the coinbase transaction you can still legitimately solve the block.

A block is shaped like this (from memory):

Version
Previous block hash
Merkle Root hash of transaction list
Timestamp
Nonce
pad
Transactions

Only the header (from version through pad) is sent to the miner. If you change the Merkle root it doesn't match up with the transactions (not provided) and the whole block is invalid. I believe the whole header is returned to the daemon when a nonce is found, and it uses the Merkle root to determine which transactions it included in the block. If it can't do that, the share is rejected. If what you are saying was possible, you could submit shares from any pool to any other pool and quadruple your income. The pools would unfortunately go out of business pretty quickly though.

perfectfire

newbie

Activity: 6

Merit: 0

Quote from: bcforum on September 02, 2011, 10:49:02 PM

The data field contains the top of the Merkle tree and that is all that is required to solve the block. You don't know what transactions were included in the block you are given to solve.

So the bitcoin daemon gives you the merkle root? From the above posts it sounded like you could decide for yourself what transactions to include in the calculation of the merkle root. But now it sounds like the daemon decides for you.

The CheckBlock method in the bitcoin source only checks that vector of transactions is non-empty, that the first transaction is the coinbase, and that each subsequent transaction is not the coinbase and is a valid transaction. If there is only one transaction and that transaction is the coinbase then the block is valid. So it seems that no matter what merkle root the daemon gives you, if you change it to be the merkle root of only the coinbase transaction you can still legitimately solve the block.

Code:

    // First transaction must be coinbase, the rest must not be
    if (vtx.empty() || !vtx[0].IsCoinBase())
        return error("CheckBlock() : first tx is not coinbase");
    for (int i = 1; i < vtx.size(); i++)
        if (vtx[i].IsCoinBase())
            return error("CheckBlock() : more than one coinbase");

    // Check transactions
    BOOST_FOREACH(const CTransaction& tx, vtx)
        if (!tx.CheckTransaction())
            return error("CheckBlock() : CheckTransaction failed");

bcforum

full member

Activity: 140

Merit: 100

Quote from: perfectfire on September 02, 2011, 08:32:03 PM

One last question. I've been looking through the cpuminer source and from what I can tell the miner requests work, gets back a data value containing the entire block header. What will data's merkle root field contain? It can't be the root of your generation transaction unless you tell it how to distribute the BTC mined by solving that block. When you call getwork do you specify the transactions you want to include?

The interface between the miner and pool (or bitcoin daemon) is stripped down to the minimum(*) amount of information. The data field contains the top of the Merkle tree and that is all that is required to solve the block. You don't know what transactions were included in the block you are given to solve.

(*) Actually, only the midstate and 12 bytes of the data field are required, but many miners compute the midstate from the data provided and throw away the midstate. This translates to a lot of excess data, but it's the internet so who cares.

Maged

legendary

Activity: 1204

Merit: 1015

Quote from: perfectfire on September 02, 2011, 08:32:03 PM

When you call getwork do you specify the transactions you want to include?

Currently, Bitcoin figures that out on its own. As for your other questions, I'm not really understanding what you are asking.

perfectfire

newbie

Activity: 6

Merit: 0

One last question. I've been looking through the cpuminer source and from what I can tell the miner requests work, gets back a data value containing the entire block header. What will data's merkle root field contain? It can't be the root of your generation transaction unless you tell it how to distribute the BTC mined by solving that block. When you call getwork do you specify the transactions you want to include?

Maged

legendary

Activity: 1204

Merit: 1015

Quote from: perfectfire on September 02, 2011, 05:35:43 PM

Quote from: Maged on September 02, 2011, 04:46:58 PM

Put simply, your client always assumes that it will find a block first until it doesn't. Then it just moves on to the next one.

I hope this makes sense....

This is what I was looking for. You (your client) chooses what transactions to put into the block except that it has to have a generation transaction that represents what you would do with the 50 BTC assuming you are the one that solved the block, correct?

Thanks for the explanation. I think I'll go put it up on the wiki.

That is, indeed, correct.

perfectfire

newbie

Activity: 6

Merit: 0

Quote from: Maged on September 02, 2011, 04:46:58 PM

Put simply, your client always assumes that it will find a block first until it doesn't. Then it just moves on to the next one.

I hope this makes sense....

This is what I was looking for. You (your client) chooses what transactions to put into the block except that it has to have a generation transaction that represents what you would do with the 50 BTC assuming you are the one that solved the block, correct?

Thanks for the explanation. I think I'll go put it up on the wiki.

Maged

legendary

Activity: 1204

Merit: 1015

Quote from: perfectfire on September 02, 2011, 04:24:09 PM

The question now is: How can the block have the generation transaction when generation has happened yet?

It's much simpler than you think it is. First off, a block is generated by your client locally using whatever transactions it knows and feels like using, as well as a transaction for yourself to claim the block reward plus fees. Your client then attempts to "solve" this block. Only if it is "solved", does whatever was in the block matter to the rest of the network.

Put simply, your client always assumes that it will find a block first until it doesn't. Then it just moves on to the next one.

I hope this makes sense....

perfectfire

newbie

Activity: 6

Merit: 0

Bump, but with NEW! NEW! NEW! ~~DISCOUNTED!~~ information courtesy of reddit users theymos and wcoenen:

Quote

[–]theymos 1 point 13 hours ago
The miner can optionally add transactions to the block. The miner then gets the fees for those transactions if they end up solving the block first. The transactions are received from the TCP relay network.
A block can't hold billions of transactions (it's capped at 1MB currently). A wise miner will refuse to add transactions below a certain fee level as the block gets closer to being full. The default client does this.

[–]perfectfire 1 point 12 hours ago
Ah, so if a miner doesn't add any transactions to the block then the value of the merkle root field will just me the SHA2-256 hash of 0 or just plain 0?
Thanks so much for explaining!

[–]wcoenen 1 point 12 hours ago
There is always at least one transaction in the block - the first one is a special one that sends the block reward to one or more addresses under control of the miner.
For an example, see this block.

[–]perfectfire 1 point 2 hours ago
But, how could that transaction exist until the block is solved and 50 BTC are generated?

So a miner can choose to accept transactions to go into the merkle tree from which the merkle root is derived from. And apparently the tree has at least one transaction: the generation transaction.

The question now is: How can the block have the generation transaction when generation has happened yet?

Side note: I dowloaded the poclbm source and looked over it a bit. I got sidetracked on learning how to program in OpenCL though.

perfectfire

newbie

Activity: 6

Merit: 0

I've been wondering this for a while and have been searching and asking for days trying to figure it out, but nobody seems to have a straight answer. I thought I had struck gold when I found this thread: https://bitcointalksearch.org/topic/what-is-to-be-hashed-in-the-bolck-and-where-does-they-come-from-10986

However the responses in the thread just point to wikipedia articles and blockexplorer. I have a computer science background so I already know what a hash tree, merkle tree and merkle root are. Just like the OP of that thread I want to know what transactions make up the leaf node/s of the merkle tree of an unsolved block. It doesn't make sense to me that an unsolved block could have any transactions. But if it can, what are they, where do they come from?

Also, in the above referenced thread the OP mentions a block header field called txn_count that comes after the nonce. I've never seen that before. Is the wiki page about block header hashing incorrect or out of date? If that thread is correct is txn_count appended after the nonce? What is the size of the data?

This is my last ditch effort before I just go grepping through the source code of one of the miners.

Topic: What are the transactions of a merkle tree for an *unsolved* block? (Read 1323 times)

Topic: What are the transactions of a merkle tree for an unsolved block? (Read 1323 times)