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?
-
1Bitcoin 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
Add a comment
|
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.
Image from Bitcoin Developer Guide
