<p>Merkle trees in general can have more child nodes, but the Merkle tree for transactional data in Bitcoin is a binary tree.</p>
<blockquote>
<p>&quot;Merkle trees are binary trees of hashes.&quot; –<a href="https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees" rel="noreferrer">Bitcoin-Wiki Protocol Documentation</a></p>
<p>&quot;From these txids, the merkle tree is constructed by pairing each txid with one other txid and then hashing them together.&quot; –<a href="https://bitcoin.org/en/developer-guide#transaction-data" rel="noreferrer">Developer Guide: Transaction Data</a></p>
</blockquote>
<p>This has the advantage that only a list of root, log<sub>2</sub>(n) hash partners and the index of the transaction are sufficient to reconstruct a Merkle branch, allowing Simplified Payment Verification with much less data than the complete block.</p>
<p>If I am not mistaken, the binary format minimizes the amount of hashes that need to be transferred for full reconstruction of the Merkle branch, e.g. for 16 transactions</p>
<ul>
<li>binary tree: root + 4*1 hashpartners + txid + position</li>
<li>three children tree: root + 3*2 hashpartners + txid + position</li>
<li>four children tree: root + 2*3 hashpartners + txid + position</li>
</ul>
<p>Lookup is likely less of an issue than the wish to minimize bandwidth usage.</p>
<p><sub>Yes, I'm committing the fallacy of &quot;proof by example&quot; here. ;)</sub></p>

CC BY-SA 3.0
2016-01-28T14:47:39.973Z
So can I securely affirm that blockchain transactions could be traversed in logarithimic time, right? Or am I missing some detail?
Henrique Barcelos
CC BY-SA 3.0
2016-01-28T14:51:46.037Z
@HenriqueBarcelos: what kind of operation are you thinking of performing during the traversion? Just looking at each transaction would be linear of course, checking all their inputs would seem to be at least `O(n*log(n))` (= linear for transaction logarithmic uplook of ~2 inputs). – Perhaps that would be best asked as a new question.
Murch
CC BY-SA 3.0
2016-01-28T14:54:41.680Z
@HenriqueBarcelos: Heeeey, no taksies backsies. :p Hope you have another question, this one was fun. :D
Murch
CC BY-SA 3.0
2016-01-28T14:56:38.067Z
I'm at the point where I have too much questions and too few reliable sources of answers :v. We're considering some serious use of the blockchain technology here at work, and as a technical architect, I must understand it till the bones (:
Henrique Barcelos
CC BY-SA 3.0
2016-01-28T15:16:47.700Z
@HenriqueBarcelos: As long as your questions are of this quality level. Please ask as many as you can come up with. Actually getting some really interesting questions would be a real breather. :D
Murch
CC BY-SA 3.0
2016-01-28T14:15:52.513Z
2016-01-28T14:44:04.800Z
2020-06-16T11:10:03.350Z
Murch
<p>I've been doing a lot of research about bitcoin, trying to understand it at the bit &amp; byte level.</p>

<p>I was wondering about the lookup efficiency of the Merkle tree.</p>

<p>I haven't found any evidence that Merkle trees are mandatory binary, which would allow a <code>O(log2 n)</code> lookup algorithm.</p>

<p>If a node may have an arbitrary number of children, then the lookup function would have a <code>O(logK n * K)</code>, where <code>K</code> is the maximum number of allowed child nodes (as far as I remember).</p>

CC BY-SA 3.0
2016-01-28T17:40:14.690Z
Just to clarify a possible misunderstanding: "binary Merkle trees" (in Bitcoin blocks) are not used for looking up transactions. They're used to construct proofs that a transaction is contained within a block, in as few bytes as possible. Murch's answer goes into more detail.
Jannes
<algorithms><merkle-tree>
Are bitcoin Merkle trees always binary?
Henrique Barcelos
# Are bitcoin Merkle trees always binary?

(Asked by: username_0 on 2016-01-28)

I've been doing a lot of research about bitcoin, trying to understand it at the bit & byte level.

I was wondering about the lookup efficiency of the Merkle tree.

I haven't found any evidence that Merkle trees are mandatory binary, which would allow a `O(log2 n)` lookup algorithm.

If a node may have an arbitrary number of children, then the lookup function would have a `O(logK n * K)`, where `K` is the maximum number of allowed child nodes (as far as I remember).

**Tags:** algorithms, merkle-tree

> **Comments:**
> **username_1**: Just to clarify a possible misunderstanding: "binary Merkle trees" (in Bitcoin blocks) are not used for looking up transactions. They're used to construct proofs that a transaction is contained within a block, in as few bytes as possible. username_2's answer goes into more detail.  

---

## 1 answers

### Answer by username_2 on 2016-01-28. Score: 5 | Accepted answer

Merkle trees in general can have more child nodes, but the Merkle tree for transactional data in Bitcoin is a binary tree.

> "Merkle trees are binary trees of hashes." –[Bitcoin-Wiki Protocol Documentation](https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees)
>
> "From these txids, the merkle tree is constructed by pairing each txid with one other txid and then hashing them together." –[Developer Guide: Transaction Data](https://bitcoin.org/en/developer-guide#transaction-data)

This has the advantage that only a list of root, log2(n) hash partners and the index of the transaction are sufficient to reconstruct a Merkle branch, allowing Simplified Payment Verification with much less data than the complete block.

If I am not mistaken, the binary format minimizes the amount of hashes that need to be transferred for full reconstruction of the Merkle branch, e.g. for 16 transactions

* binary tree: root + 4\*1 hashpartners + txid + position
* three children tree: root + 3\*2 hashpartners + txid + position
* four children tree: root + 2\*3 hashpartners + txid + position

Lookup is likely less of an issue than the wish to minimize bandwidth usage.

Yes, I'm committing the fallacy of "proof by example" here. ;)

> **Comments:**
> **username_0**: So can I securely affirm that blockchain transactions could be traversed in logarithimic time, right? Or am I missing some detail?  
> **username_2**: @username_0: what kind of operation are you thinking of performing during the traversion? Just looking at each transaction would be linear of course, checking all their inputs would seem to be at least `O(n*log(n))` (= linear for transaction logarithmic uplook of ~2 inputs). – Perhaps that would be best asked as a new question.  
> **username_2**: @username_0: Heeeey, no taksies backsies. :p Hope you have another question, this one was fun. :D  
> **username_0**: I'm at the point where I have too much questions and too few reliable sources of answers :v. We're considering some serious use of the blockchain technology here at work, and as a technical architect, I must understand it till the bones (:  
> **username_2**: @username_0: As long as your questions are of this quality level. Please ask as many as you can come up with. Actually getting some really interesting questions would be a real breather. :D  

---

