4 ms·

Oh I maybe wrong on this but I was assuming something like this ABCDEEEE / \ ABCD EEEE / \ / AB CD EE /

Oh I maybe wrong on this but I was assuming something like this ABCDEEEE / \ ABCD EEEE / \ / AB CD EE / \ / \ / A B C D E From: https://bitcoin.org/en/developer-guide#transaction-data https://bitcoin.org/en/developer-guide#transaction-data

kerkeslager 9y ago
Okay, if I'm understanding correctly, that diagram is a little unclear. Like I said earlier, using the tree depth works if the number of items in your set is a power of two, because then all branches of the tree are the same depth. In this case, Bitcoin is forcing all branches to be the same depth by duplicating the final element to fill in the rest of the Merkle tree up to a power of 2. In the example, the power of 2 is 8, and the theoretical Merkle tree looks like this: ABCDEEEE / \ ABCD EEEE / \ / \ AB CD EE EE / \ / \ / \ / \ A B C D E E E E The diagram you linked doesn't show the full right side of the Merkle tree, because of a clever computational trick that they use to optimize storage and membership. Basically, if you compute and store hash(E) for the leftmost E, you don't have to compute or store hash(E) again to compute and store hash(hash(E) + hash(E)) for the leftmost EE. The diagram is showing the computations, not the full Merkle tree. Incidentally, a side effect of this is that you can't have duplicate transactions, because you wouldn't be able to tell between a E and F such that E=F, and E simply being duplicated to pad out to a power of 8. This works for Bitcoin because duplicate transactions aren't desirable, but it might not work for other applications.
- bluesign 9y ago
  Yeah I totally agree with you, my comment was, I learned first about merkle tree from bitcoin, so I was always assuming it is working like this in general. But seems they were filling leaves to power of 2

kerkeslager 9y ago

Okay, if I'm understanding correctly, that diagram is a little unclear. Like I said earlier, using the tree depth works if the number of items in your set is a power of two, because then all branches of the tree are the same depth. In this case, Bitcoin is forcing all branches to be the same depth by duplicating the final element to fill in the rest of the Merkle tree up to a power of 2. In the example, the power of 2 is 8, and the theoretical Merkle tree looks like this: ABCDEEEE / \ ABCD EEEE / \ / \ AB CD EE EE / \ / \ / \ / \ A B C D E E E E The diagram you linked doesn't show the full right side of the Merkle tree, because of a clever computational trick that they use to optimize storage and membership. Basically, if you compute and store hash(E) for the leftmost E, you don't have to compute or store hash(E) again to compute and store hash(hash(E) + hash(E)) for the leftmost EE. The diagram is showing the computations, not the full Merkle tree. Incidentally, a side effect of this is that you can't have duplicate transactions, because you wouldn't be able to tell between a E and F such that E=F, and E simply being duplicated to pad out to a power of 8. This works for Bitcoin because duplicate transactions aren't desirable, but it might not work for other applications.

bluesign 9y ago
Yeah I totally agree with you, my comment was, I learned first about merkle tree from bitcoin, so I was always assuming it is working like this in general. But seems they were filling leaves to power of 2