user21351: 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).

user5406: 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
"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

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. ;)

21351: <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>
 5406: <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>
