<blockquote>
<p>But the merkle root must be different to each miner/node due to transaction order and the generation transaction,</p>
</blockquote>
<p>Correct.</p>
<blockquote>
<p>so how do other nodes come to consensus if their transactions are different.</p>
</blockquote>
<p>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).</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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), ...</p>
<blockquote>
<p>Wouldnt the tree have to be hashed again</p>
</blockquote>
<p>Yes.</p>
<p>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:</p>
<ol>
<li><p>Typically the mining software will occasionally (say, every few seconds) build a new block template to work on, which includes transaction selection.</p>
</li>
<li><p>An intermediate layer changes the coinbase transaction (which includes payout address, as well as an &quot;extra nonce&quot;) 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 <em>O(log(n))</em> work in the number of transactions (e.g. a block with 2048 transactions only needs 11 hashing steps to recompute the Merkle root).</p>
</li>
<li><p>The lowest-level hardware layer cycles through the <em>2<sup>32</sup></em> nonces in the block header, all with the same Merkle root. This is extremely efficient.</p>
</li>
</ol>
<blockquote>
<p>and the PoW would have to start from the beginning.</p>
</blockquote>
<p>Yes, but this is irrelevant. PoW doesn't have &quot;progress&quot;. 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 <em>2<sup>256</sup> / target</em>). If that chance is <em>1/c</em>, and you perform h hashes per day, you will find <em>h/c</em> blocks per day - regardless of which transactions those attempts are for.</p>

CC BY-SA 4.0
2021-04-27T22:36:35.480Z
Thank you Peiter! Very helpful answer indeed. I understand that blocks are assumed legitimate unless rejected afterward, which causes a fork. How do nodes get transaction information from the block that has just been mined to validate them? Do full nodes have to store transactions in plain text, and other nodes request this information. I don't understand how transactions can be found from a merkle root, it would have to be "unhashed". As for confirming transactions via cryptography, is this done nodes before they are appended to the merkle tree? Or in the mempool somehow? Thanks
Matt Tainsh
CC BY-SA 4.0
2021-04-28T00:54:39.977Z
Adding to my comment; I understand that the merkle root is part of the block header and txns are stored by full nodes. Nodes can verify transaction inclusion in a merkle tree just from its root? How is this possible when the root is a hash that is one-way? Similarly, how do blockchain explorers gain the information of transactions (input, output etc.) with only the transaction ID?
Matt Tainsh
CC BY-SA 4.0
2021-04-28T02:01:49.890Z
Nodes request the full block data from each other when relaying a new block. They verify the Merkle root by recomputing it from the transactions.
Pieter Wuille
CC BY-SA 4.0
2021-04-27T16:09:30.560Z
2024-11-24T14:55:30.203Z
2024-11-24T14:55:30.203Z
Pieter Wuille
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
<p>Thank you heaps.</p>

<transactions><blockchain><proof-of-work><mempool><merkle-tree>
How are txns sorted correctly in Merkle trees between nodes and validated via Proof of Work
Matt Tainsh
# How are txns sorted correctly in Merkle trees between nodes and validated via Proof of Work

(Asked by: username_0 on 2021-04-27)

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.

**Tags:** transactions, blockchain, proof-of-work, mempool, merkle-tree


---

## 1 answers

### Answer by username_1 on 2021-04-27. Score: 5

> 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 *232* 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 *2256 / 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.

> **Comments:**
> **username_0**: Thank you Peiter! Very helpful answer indeed. I understand that blocks are assumed legitimate unless rejected afterward, which causes a fork. How do nodes get transaction information from the block that has just been mined to validate them? Do full nodes have to store transactions in plain text, and other nodes request this information. I don't understand how transactions can be found from a merkle root, it would have to be "unhashed". As for confirming transactions via cryptography, is this done nodes before they are appended to the merkle tree? Or in the mempool somehow? Thanks  
> **username_0**: Adding to my comment; I understand that the merkle root is part of the block header and txns are stored by full nodes. Nodes can verify transaction inclusion in a merkle tree just from its root? How is this possible when the root is a hash that is one-way? Similarly, how do blockchain explorers gain the information of transactions (input, output etc.) with only the transaction ID?  
> **username_1**: Nodes request the full block data from each other when relaying a new block. They verify the Merkle root by recomputing it from the transactions.  

---

