merkle tree – Transaction ordering for constructing the same merkel node from a given merkel path

Fees & reward

The order of transactions in a block does not affect the transaction fees or the block reward. Or vice versa.

Therefore, after exhausting nonce and extra-nonce etc values for a transaction order, the miner can vary the order of unconfirmed transactions in a block template without the miner needing any change to the coinbase transaction (at position 1).

As you say, changing the order of transactions means the miner has to recalculate the Merkle root. But until a block is published with a specific transaction order, no one else knows or cares about prior unsuccessful transaction orders.

Merkle proof / Merkle path

A thin client can check if a transaction is in a block without knowing about the contents or ordering of almost all other transactions in the block.

Here’s an example of a Merkle tree calculated from a block of eleven transactions.

                                      da07
                    ┌──────────────────┴────────────────┐
                   7460                                f94a
          ┌─────────┴─────────┐                   ┌─────┴─────┐
         b5fb                87fd                fcc1        fcc1*
     ┌────┴────┐         ┌────┴────┐         ┌────┴────┐
    0238      5ed3      8fca      1013      ee23      8c51
  ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐
 95cd 709b 27ca 1f3c 41b6 a8c0 d20a 281b df74 3e81 3ebc 3ebc*

_{Source: Reference 3 below. Note that a duplicate hash is inserted if there is an odd number of transactions (3ebc*), or an odd number of hashes (fcc1*) at any level of the tree.}

To prove transaction 41b6 is in block da07 we only need Merkle path a8c0 1013 b5fb f94a. We don’t care about the value or order of 95cd and 709b etc.

                                    da07
                    ┌──────────────────┴────────────────┐
                   7460                                𝗳𝟵𝟰𝗮
          ┌─────────┴─────────┐                   ┌─────┴─────┐
         𝗯𝟱𝗳𝗯                87fd                ····        ····
     ┌────┴────┐         ┌────┴────┐         ┌────┴────┐
    ····      ····      8fca      𝟭𝟬𝟭𝟯      ····      ····
  ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐   ┌──┴──┐
 ···· ···· ···· ···· 𝟜𝟙𝕓𝟞 𝗮𝟴𝗰𝟬 ···· ···· ···· ···· ···· ····

Note that we can do this check without any need to know the number of transactions in the block. From the length of the Merkle path we only know it is somewhere between nine and sixteen transactions, but this is unimportant.

References:

1. How is a Merkle tree path generated? (stackoverflow.com)
2. Why is the full Merkle path needed to verify a transaction?
3. Merkle Tree, a simple explanation and implementation (Jeremy Then, medium.com)