How are txns sorted correctly in Merkle trees between nodes and validated via Proof of Work

Question

I am interested in exactly what happens to transactions in the pending block (block that is being mined at the time). From what I understand, transactions are the stored as a Merkle tree hash inside the block, along with the parent hash, timestamp and nonce. During mining, the miner is hashing the block data with a different nonces' trying to achieve the target hash. I assume what they are hashing is all the block data including the merkle root. But the merkle root must be different to each miner/node due to transaction order and the generation transaction, so how do other nodes come to consensus if their transactions are different. There is a hole in my understanding.

Furthermore, when transactions are broadcasted across the network, nodes will receive them at different times due to network latency etc. and miners can rearrange the order of transactions due to fee incentives, but this changes the merkle root. I understand that miners prove they have done the work to validate the transactions, but what steps do other nodes take to go 'looks legit'. I imagine they would use the nonce provided by the block creator to hash their own copy of the block and see if it in within the target.

Also, If PoW is done on the block data with the merkle root, how can new transactions be added to the block? Wouldnt the tree have to be hashed again and the PoW would have to start from the beginning. Does a miner wait for the block size limit to be reached before performing PoW? I don't understand how PoW can be done on a dynamic flow of transactions, and how every node can have the exact same set of everything to do PoW on.

Can someone please explain what I am missing? How are transactions sorted by different nodes? How do transactions enter the merkle tree? How do other nodes validate the new block?

Thank you heaps.

Answer 1

But the merkle root must be different to each miner/node due to transaction order and the generation transaction,

Correct.

so how do other nodes come to consensus if their transactions are different.

They don't. Every miner is fully responsible for the choice of their own transactions. There is no need for different miners to agree on the transaction selection. The winning miner decides the contents of the winning block, and others go along with it, accepting their transaction selection (unless the included transactions are objectively invalid, which makes the block invalid - to miners and other nodes).

I imagine they would use the nonce provided by the block creator to hash their own copy of the block and see if it in within the target.

There are many block validity rules that are performed by all nodes, including the verification of proof-of-work, like you say. Other rules include verifying that all transactions are valid, that no theft occurred, that no double spending occurred, that no money is printed by the block (beyond the permitted subsidy), ...

Wouldnt the tree have to be hashed again

Yes.

There are a number of layers involved to updating a miner's candidate block. Each is much faster than the previous one, but done much more often:

1. Typically the mining software will occasionally (say, every few seconds) build a new block template to work on, which includes transaction selection.

2. An intermediate layer changes the coinbase transaction (which includes payout address, as well as an "extra nonce") every so often. Every time this happens the Merkle root changes. However, by caching the inner nodes of the Merkle tree that are just right of the leftmost branch in the tree, this is just O(log(n)) work in the number of transactions (e.g. a block with 2048 transactions only needs 11 hashing steps to recompute the Merkle root).

3. The lowest-level hardware layer cycles through the 2³² nonces in the block header, all with the same Merkle root. This is extremely efficient.

and the PoW would have to start from the beginning.

Yes, but this is irrelevant. PoW doesn't have "progress". You don't lose anything by starting over, as long as you're still trying hashes all the time. Every candidate block you try (combination of tx selection, coinbase tx, nonce) has an independent chance of meeting the PoW target (a chance equal to 2²⁵⁶ / target). If that chance is 1/c, and you perform h hashes per day, you will find h/c blocks per day - regardless of which transactions those attempts are for.