7

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

Improve this question
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. Murch's answer goes into more detail.
    – Jannes
    Jan 28, 2016 at 17:40

1 Answer 1

Reset to default
5

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

Improve this answer
5
  • So can I securely affirm that blockchain transactions could be traversed in logarithimic time, right? Or am I missing some detail?
    – Henrique Barcelos
    Jan 28, 2016 at 14:47
  • @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 ♦
    Jan 28, 2016 at 14:51
  • @HenriqueBarcelos: Heeeey, no taksies backsies. :p Hope you have another question, this one was fun. :D
    – Murch ♦
    Jan 28, 2016 at 14:54
  • 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
    Jan 28, 2016 at 14:56
  • @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 ♦
    Jan 28, 2016 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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