1

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?

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.