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

  • 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 '16 at 17:40
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. ;)

  • 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 '16 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 '16 at 14:51
  • @HenriqueBarcelos: Heeeey, no taksies backsies. :p Hope you have another question, this one was fun. :D – Murch Jan 28 '16 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 '16 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 '16 at 15:16

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.