<p>Bitcoin transactions are not <em>stored</em> in a Merkle tree. That is just one way of representing them.</p>
<p>The most common serialization for blocks is just:</p>
<ul>
<li>Header (prevhash, merkleroot, time, nonce, difficulty, version)</li>
<li>Number of transactions</li>
<li>Concatenation of all those transactions</li>
</ul>
<p>This serialization is used on the P2P network in <code>block</code> messages, as well as on disk for various software implementations. Other serializations exist, for example BIP152 compact blocks serialize them as a concatenation of transactions, where most of them are replaced with a short identifier, hoping that the receiver already have them.</p>
<p>The Merkle tree is relevant to block's <em>commitment structure</em>; the question on how you compute the hash of a block from its contents. That's all - the tree is never actually materialized.</p>
<p>This matters for one purpose only: being able to give short proofs inclusion of a transaction in a block. To do that, you must provide the transaction, as well as all partners that transaction is hashed with, so the receiver can recompute the parent, recursively, until they hit the merkle root (which they knew ahead of time).</p>
<p>What happens if you'd use a ternary tree? Yes, you'd have <em>log(3)/log(2)</em> times fewer steps in the tree, but for every inner node, you'd need to give <em>two</em> partner hashes. Using any higher number just makes the bandwidth cost worse.</p>
<p>In short: in terms of inclusion proof size, binary Merkle trees are best.</p>

CC BY-SA 4.0
2021-10-02T17:06:57.767Z
Just a follow on question: Since inclusion (merkle proofs) are used only (AFAIK!) for verifying transactions for SPV wallets - the only bandwidth cost is for SPV clients (and the servers they're talking to) - that's the bandwidth impact you're talking about?
davidbak
CC BY-SA 4.0
2020-10-22T20:11:07.667Z
2020-10-22T20:11:07.667Z
Pieter Wuille
<p>Bitcoin stores transactions in binary Merkle trees. They take O(log2 n) to traverse.</p>
<p>If I used something like a ternary tree, where each node (including the root) references three branches/leaves instead of two, it would take O(log3 n) to traverse. Why not pick a radix higher than 2? Is it because of space efficiency for SPV, or something like that?</p>

<merkle-tree><spv><storage-footprint>
Why binary trees? Is there any particular benefit to using binary trees instead of some higher radix?
Expectator
# Why binary trees? Is there any particular benefit to using binary trees instead of some higher radix?

(Asked by: username_0 on 2020-10-22)

Bitcoin stores transactions in binary Merkle trees. They take O(log2 n) to traverse.

If I used something like a ternary tree, where each node (including the root) references three branches/leaves instead of two, it would take O(log3 n) to traverse. Why not pick a radix higher than 2? Is it because of space efficiency for SPV, or something like that?

**Tags:** merkle-tree, spv, storage-footprint


---

## 1 answers

### Answer by username_1 on 2020-10-22. Score: 3 | Accepted answer

Bitcoin transactions are not *stored* in a Merkle tree. That is just one way of representing them.

The most common serialization for blocks is just:

* Header (prevhash, merkleroot, time, nonce, difficulty, version)
* Number of transactions
* Concatenation of all those transactions

This serialization is used on the P2P network in `block` messages, as well as on disk for various software implementations. Other serializations exist, for example BIP152 compact blocks serialize them as a concatenation of transactions, where most of them are replaced with a short identifier, hoping that the receiver already have them.

The Merkle tree is relevant to block's *commitment structure*; the question on how you compute the hash of a block from its contents. That's all - the tree is never actually materialized.

This matters for one purpose only: being able to give short proofs inclusion of a transaction in a block. To do that, you must provide the transaction, as well as all partners that transaction is hashed with, so the receiver can recompute the parent, recursively, until they hit the merkle root (which they knew ahead of time).

What happens if you'd use a ternary tree? Yes, you'd have *log(3)/log(2)* times fewer steps in the tree, but for every inner node, you'd need to give *two* partner hashes. Using any higher number just makes the bandwidth cost worse.

In short: in terms of inclusion proof size, binary Merkle trees are best.

> **Comments:**
> **username_2**: Just a follow on question: Since inclusion (merkle proofs) are used only (AFAIK!) for verifying transactions for SPV wallets - the only bandwidth cost is for SPV clients (and the servers they're talking to) - that's the bandwidth impact you're talking about?  

---

