This PR provides a new Merkle tree implementation which does not unnecessarily store extra digests and does not do extra hashes.
Previous versions are renamed: incremental_merkle_tree_legacy, calculate_merkle_legacy.
New versions are named: incremental_merkle_tree, calculate_merkle.
Note: Even though the files have been renamed incremental_merkle_legacy.hpp and merkle_legacy.hpp, the implementation has not been modified (besides remoning the canonical template parameter).
New incremental_merkle_tree
does not store extra hashes (root matches calculate_merkle)
provides the root on demand, does not compute it on append().
is about 20x faster than incremental_merkle_tree_legacy.
storage is minimal. Just one uint64_t and a vector<digest_type> whose size() is std::popcount(num_digest_appended).
New calculate_merkle
does not store extra hashes. (root matches incremental_merkle_tree).
is about 25% faster than calculate_merkle_legacy without multithreading
supports internal multithreading for computing roots of collections whose size() > 4096, in which case it is 2x to almost 4x faster (2x for sequences of at least 10k digests, 4x for very large sequences).
doesn't mutate the passed deque<digest_type>.
New performance tests
This PR adds two performance tests comparing the legacy and new merkle tree implementations
Resolves #2333
This PR provides a new Merkle tree implementation which does not unnecessarily store extra digests and does not do extra hashes.
Previous versions are renamed:
incremental_merkle_tree_legacy
,calculate_merkle_legacy
. New versions are named:incremental_merkle_tree
,calculate_merkle
.Note: Even though the files have been renamed
incremental_merkle_legacy.hpp
andmerkle_legacy.hpp
, the implementation has not been modified (besides remoning thecanonical
template parameter).New
incremental_merkle_tree
calculate_merkle
)append()
.incremental_merkle_tree_legacy
.uint64_t
and avector<digest_type>
whose size() isstd::popcount(num_digest_appended)
.New
calculate_merkle
incremental_merkle_tree
).calculate_merkle_legacy
without multithreadingsize() > 4096
, in which case it is 2x to almost 4x faster (2x for sequences of at least 10k digests, 4x for very large sequences).deque<digest_type>
.New performance tests
This PR adds two performance tests comparing the
legacy
andnew
merkle tree implementations./unittests/unit_test "--run_test=merkle_tree_tests/perf_test_one_large"
./unittests/unit_test "--run_test=merkle_tree_tests/perf_test_many_small"
New consistency test
This PR adds a test checking consistency between
incremental_merkle_tree
andcalculate_merkle
when adding from 1 to 1000 digests:./unittests/unit_test "--run_test=merkle_tree_tests/consistency_over_large_range"