Bitcoin uses a Merkle tree with hash functions. I mean I do not get it why there must be a full binary tree? A complete could also be possible?

  • 1
    Bitcoin messed up their merkle trees . I guess requiring a power-of-two as leaves is their workaround for this flaw. – CodesInChaos Jan 12 '17 at 19:40
  • Related: [Full Disclosure] CVE-2012-2459 (block merkle calculation exploit) on bitcointalk. – CodesInChaos Jan 12 '17 at 20:15
  • @CodesInChaos: The second link is interesting, but I don't see what the first link has to do with the question? – Murch Jan 13 '17 at 9:14
  • @Murch It's about how you to design a proper merkle tree that doesn't suffer from ambiguities between different length inputs. Such a merkle tree won't need silly restrictions like a power-of-two number of leaves. But bitcoin didn't use leaf-tagging (or one of the alternative safe constructions) which led to problems. – CodesInChaos Jan 13 '17 at 9:19
  • @CodesInChaos: Bitcoin doesn't require a full binary tree, it only requires a complete binary tree. I thought you were saying that you didn't understand why a binary tree was chosen over more children. – Murch Jan 13 '17 at 9:27

Bitcoin does work with full or complete binary trees. For complete trees, leaves without a partner are simply hashed with themselves instead. The attack that CodesInChaos links was solved by checking that every transaction is unique which is required for valid blocks anyway.

enter image description here

Image from Bitcoin Developer Guide

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.