<p>The Merkle root of the transactions is calculated by building a binary tree from the transactions as leaves where each parent node is the hash of its two children. As the coinbase transaction is the first transaction in the block, you can store the hashing partners on the coinbase transaction's Merkle branch and only repeat all the hashes to which the coinbase transaction contributes. This reduces the required number of hashes to calculate the new Merkle root for n transactions from <code>O(n)</code> to <code>O(log(n))</code> given that no other transactions in the block were changed.</p>
<p>There is no way around repeating the whole left flank of hashes in the binary tree, since changing the extranonce in the coinbase transaction changes the outcome of the bottom left hash combining coinbase transaction and first regular transaction.</p>

CC BY-SA 4.0
2020-07-18T17:18:22.803Z
2020-07-18T17:23:46.347Z
2020-07-18T17:23:46.347Z
Murch
<p>The extranonce is a part of the coinbase transaction, inside the coinbase transaction there is an arbitrary data, and when you change this data, your merkle will change too</p>

CC BY-SA 4.0
2020-06-18T14:31:02.267Z
I ask about algorithms to achieve this efficiently, not what the extranonce is
Wil
CC BY-SA 4.0
2020-06-17T12:56:28.160Z
2020-06-17T12:56:28.160Z
Hamita
<p>I'm trying to learn how to block headers are created and an efficient way of doing so. Given a list .of transactions, can I change the extranonce without having to rehash the entire list?</p>
<p>EDIT: To clarify, I am not asking about what the extranonce is but whether there are algorithms to recompute the merkletree better than others.</p>

CC BY-SA 4.0
2020-06-18T15:07:01.097Z
If one has only one change in the Merkle tree the complexity to compute the hash is `O(lg(n))` because other branches are hashes are reused. No further speedup is possible (except Asicboost) as even one bit change in coinbase transaction causes avalon effect.
MCCCS
CC BY-SA 4.0
2020-06-18T17:20:30.230Z
Thanks! This answers the question. I take it that the coinbase Tx must go into the start then
Wil
CC BY-SA 4.0
2020-06-19T07:54:20.350Z
The extra nonce is indeed additional space in coinbase. I don't see any reason why you cannot precompute all the extranonce fields. So, even the `log(n)` time could be amortized
sanket1729
CC BY-SA 4.0
2020-06-20T09:00:06.340Z
I think you can get ln(n)/ln(2) with precomputation. But it is less if the coinbase tx didn’t go into the bottom.
And I guess it needs to go into the bottom?
Wil
CC BY-SA 4.0
2020-07-18T17:20:08.783Z
Each transactions is a leaf at the bottom level of the Merkle tree.
Murch
<mining-theory><algorithms><block-header>
What is the optimal way to increment extranonce?
Wil
# What is the optimal way to increment extranonce?

(Asked by: username_0 on 2020-06-17)

I'm trying to learn how to block headers are created and an efficient way of doing so. Given a list .of transactions, can I change the extranonce without having to rehash the entire list?

EDIT: To clarify, I am not asking about what the extranonce is but whether there are algorithms to recompute the merkletree better than others.

**Tags:** mining-theory, algorithms, block-header

> **Comments:**
> **username_1**: If one has only one change in the Merkle tree the complexity to compute the hash is `O(lg(n))` because other branches are hashes are reused. No further speedup is possible (except Asicboost) as even one bit change in coinbase transaction causes avalon effect.  
> **username_0**: Thanks! This answers the question. I take it that the coinbase Tx must go into the start then  
> **username_2**: The extra nonce is indeed additional space in coinbase. I don't see any reason why you cannot precompute all the extranonce fields. So, even the `log(n)` time could be amortized  
> **username_0**: I think you can get ln(n)/ln(2) with precomputation. But it is less if the coinbase tx didn’t go into the bottom. And I guess it needs to go into the bottom?  
> **username_3**: Each transactions is a leaf at the bottom level of the Merkle tree.  

---

## 2 answers

### Answer by username_3 on 2020-07-18. Score: 3 | Accepted answer

The Merkle root of the transactions is calculated by building a binary tree from the transactions as leaves where each parent node is the hash of its two children. As the coinbase transaction is the first transaction in the block, you can store the hashing partners on the coinbase transaction's Merkle branch and only repeat all the hashes to which the coinbase transaction contributes. This reduces the required number of hashes to calculate the new Merkle root for n transactions from `O(n)` to `O(log(n))` given that no other transactions in the block were changed.

There is no way around repeating the whole left flank of hashes in the binary tree, since changing the extranonce in the coinbase transaction changes the outcome of the bottom left hash combining coinbase transaction and first regular transaction.


---

### Answer by username_4 on 2020-06-17. Score: -1

The extranonce is a part of the coinbase transaction, inside the coinbase transaction there is an arbitrary data, and when you change this data, your merkle will change too

> **Comments:**
> **username_0**: I ask about algorithms to achieve this efficiently, not what the extranonce is  

---

