Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix bitcoin's broken merkle tree #5

Closed
chjj opened this issue May 29, 2018 · 2 comments
Closed

Fix bitcoin's broken merkle tree #5

chjj opened this issue May 29, 2018 · 2 comments

Comments

@chjj
Copy link
Contributor

chjj commented May 29, 2018

Bitcoin's merkle tree hashes odd nodes with themselves (or nodes without a right sibling, I should say), leading to the duplicate txid vulnerability (a duplicate txid placed after an odd leaf ends up creating the same root as the valid block's commitment).

Switching to the type of merkle tree described in RFC6962 would be preferrable (it simply propagates odd nodes up a level without hashing them). It also has some other benefits: i.e. the ability to prove a leaf vs. an internal node.

We could also require the leaves to be sorted for non-existence proofs.

edit: RFC6962: https://tools.ietf.org/html/rfc6962#section-2.1

@chjj
Copy link
Contributor Author

chjj commented Jun 8, 2018

RFC7574 is also an option. It looks like it pads the leaves with zero hashes until the amount of leaves reaches the nearest power of two (?). This is nicer than rfc6962 in that all the leaves are guaranteed to be the same depth. Might make dealing with proofs more sane.

Though, if we just wanted the leaves to be the same depth, we could do a combination of both. RFC6962-style, but if the leaves are odd, we pad them with a single zero-hash. This ensures that the odd leaf never gets propagated up. For all levels above the leaves, we propagate the odd hash up.

edit: See also, bittorrent's BEP 0030: http://bittorrent.org/beps/bep_0030.html

@chjj
Copy link
Contributor Author

chjj commented Jun 8, 2018

Note that changing any of this will also require changing the bip37-style SPV (which we should remove in the future anyway).

@chjj chjj closed this as completed Aug 2, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant