search

sipa / bitcoin

Bitcoin integration/staging tree
http://www.bitcoin.org
MIT License
88 stars 21 forks source link

[segwit3 hard-fork] Fast Merkle trees #49

Closed maaku closed 8 years ago

maaku commented 8 years ago

Switch to fast Merkle trees for witness.

A fast Merkle branch uses midstate to perform a single SHA-256 compression per branch, and is not vulnerable to CVE-2012-2459. It produces different hashes though, so can only be used for new hash trees going forward.

Builds off #48 but could be separable.

jl2012 commented 8 years ago

What is the benefit of doing this?

maaku commented 8 years ago

A slightly better than 3x run-time improvement to validating commitments. It is a particularly useful optimization for chained verifications, such as compact SPV header proofs.

sipa commented 8 years ago

Performance matters, but is there no way that doesn't require midstate-hacking SHA256?

maaku commented 8 years ago

You could reduce the security by truncating hashes.

But is it really fair to call this a hack? It's just SHA256 without the mandated padding.

sipa commented 8 years ago

I do consider this a hack, sorry. I'm really not keen on doing such things to give a constant factor improvement for an already-fast operation.