search

tradecraftio / tradecraft

Tradecraft integration/staging tree https://tradecraft.io/download
Other
13 stars 9 forks source link

Add support for BIP98: fast Merkle trees and proof structures #42

Closed maaku closed 5 years ago

maaku commented 5 years ago

This is a back-porting of the code for fast Merkle trees originally proposed for bitcoin as an implementation of BIP98: Fast Merkle Trees. Includes squashed fixes from @kallewoof pulled from the branch he maintained for inclusion in Bitcoin Core (which didn't happen).

The only substantive changes made in the back-port is throwing a std::range_error in MerkleNodeReference::GetCode and MerkleNodeReference::SetCode if the internal state of the reference is corrupted. Previously an assertion would have triggered in GetCode and SetCode would have silently done nothing.

The back-port changes are a separate commit that will be squashed before merging.

maaku commented 5 years ago

I believe all nits in @kallewoof's review have been addressed. I've also done a fresh review of the entire codebase myself, making numerous edits to the code documentation. I also moved the new Merkle proof structures to merkleproof.h/merkleproof.cpp since the two components are really quite different.

I believe this PR is done.

maaku commented 5 years ago

After doing some review of the taproot proposals, I think this approach can be tweaked a little bit to be cleaner. Instead of having the inner-node hashing function be salted with the hash of the first 512 fractional bits of sqrt(2), which is repeatable but not easy to calculate, we should use the empty-string tag. The salt value for inner-node hashes would be SHA256("") || SHA256("") (the hash of the empty string, twice). This is easier to quickly code up in other languages when reference sources are not available.

We could specify a tag value, but being the first application of tagged hashing we are lucky enough to be able to use empty-string. We'll simply define empty-string to be the UTF-8 encoded tag value to use for fast Merkle hashes for inner-nodes in tree structures.

maaku commented 5 years ago

I've updated this PR to use the tagged SHA-256 hash function, with the empty string as the key.