| // Copyright 2026 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| #include "bindings/merkle.h" |
| |
| #include <cstdint> |
| #include <memory> |
| #include <string> |
| #include <variant> |
| #include <vector> |
| |
| #include "absl/status/status.h" |
| #include "absl/status/status_matchers.h" |
| #include "absl/status/statusor.h" |
| #include "absl/strings/str_cat.h" |
| #include "absl/strings/str_format.h" |
| #include "absl/strings/string_view.h" |
| #include "crypto/algorithms.h" |
| #include "crypto/hash.h" |
| #include "gmock/gmock.h" |
| #include "gtest/gtest.h" |
| #include "proto/bmff_based_hash_assertion.pb.h" |
| #include "riegeli/bytes/string_reader.h" |
| #include "testing/proto_test_utils.h" |
| |
| namespace credentio { |
| namespace { |
| |
| class JoiningHasher : public Hasher { |
| public: |
| void Update(absl::string_view content) override { |
| digest_ = absl::StrCat(digest_, content); |
| } |
| |
| std::string Digest() override { return digest_; } |
| |
| protected: |
| std::string digest_ = ""; |
| }; |
| |
| class JoiningHasherFactory : public HasherFactory { |
| public: |
| absl::StatusOr<std::unique_ptr<Hasher>> Create() const override { |
| return std::make_unique<JoiningHasher>(); |
| } |
| HashAlgorithm algorithm() const override { return HashAlgorithm::kSha256; } |
| }; |
| |
| using ::absl_testing::IsOkAndHolds; |
| using ::absl_testing::StatusIs; |
| using ::credentio_testing::ParseTextProtoOrDie; |
| using ::testing::Eq; |
| using ::testing::HasSubstr; |
| |
| struct BlockSizesCase { |
| std::string name; |
| BmffMerkle merkle_map; |
| uint64_t mdat_size; |
| absl::StatusOr<std::vector<int64_t>> expected; |
| }; |
| |
| using DeriveBlockSizesTest = testing::TestWithParam<BlockSizesCase>; |
| |
| TEST_P(DeriveBlockSizesTest, DerivesBlockSizes) { |
| const BlockSizesCase& params = GetParam(); |
| |
| if (params.expected.ok()) { |
| EXPECT_THAT(DeriveMerkleBlockSizes(params.merkle_map, params.mdat_size), |
| IsOkAndHolds(Eq(params.expected.value()))); |
| } else { |
| EXPECT_THAT(DeriveMerkleBlockSizes(params.merkle_map, params.mdat_size), |
| StatusIs(params.expected.status().code(), |
| params.expected.status().message())); |
| } |
| } |
| |
| INSTANTIATE_TEST_SUITE_P( |
| DeriveMerkleDataTests, DeriveBlockSizesTest, |
| ::testing::Values( |
| BlockSizesCase{ |
| .name = "BothSizeTypes", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 5 |
| fixed_block_size: 10 |
| variable_block_sizes: 1 |
| variable_block_sizes: 3 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map has both fixed and variable block sizes"), |
| }, |
| BlockSizesCase{ |
| .name = "FixedSizeZero", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 5 |
| fixed_block_size: 0 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map has an invalid fixed block size"), |
| }, |
| BlockSizesCase{ |
| .name = "FixedSizeBlocksNotMatchingCount", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 3 |
| fixed_block_size: 3 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map's block sizes do not " |
| "match the expected leaf count"), |
| }, |
| BlockSizesCase{ |
| .name = "VariableHasInvalidSize", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 4 |
| variable_block_sizes: 3 |
| variable_block_sizes: 0 |
| variable_block_sizes: 2 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map has an invalid variable block size"), |
| }, |
| BlockSizesCase{ |
| .name = "VariableBlockSumTooLarge", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 4 |
| variable_block_sizes: 3 |
| variable_block_sizes: 4 |
| variable_block_sizes: 2 |
| variable_block_sizes: 6 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map's variable block sizes " |
| "do not sum to the mdat box size"), |
| }, |
| BlockSizesCase{ |
| .name = "ValidVariableBlockSizes", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 4 |
| variable_block_sizes: 3 |
| variable_block_sizes: 2 |
| variable_block_sizes: 3 |
| variable_block_sizes: 2 |
| )pb"), |
| .mdat_size = 10, |
| .expected = std::vector<int64_t>{3, 2, 3, 2}, |
| }, |
| BlockSizesCase{ |
| .name = "NoBlockSizesSpecifiedTooLargeMdat", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 1 |
| )pb"), |
| .mdat_size = static_cast<uint64_t>(INT64_MAX) + 1, |
| .expected = absl::InvalidArgumentError( |
| "mdat atom's box size is too large to fit in an int64_t"), |
| }, |
| BlockSizesCase{ |
| .name = "FixedBlockSizeExceedsLimit", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 1048577 |
| fixed_block_size: 1 |
| )pb"), |
| .mdat_size = 1048577, |
| .expected = absl::InvalidArgumentError( |
| "merkle map block count exceeds maximum allowable limit: " |
| "1048577 > 1048576"), |
| }, |
| BlockSizesCase{ |
| .name = "VariableBlockSizesOverflow", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 2 |
| variable_block_sizes: 9223372036854775807 |
| variable_block_sizes: 1 |
| )pb"), |
| .mdat_size = 10, |
| .expected = absl::InvalidArgumentError( |
| "merkle map's variable block sizes overflow int64_t"), |
| }, |
| BlockSizesCase{ |
| .name = "ValidNoBlockSizesSpecified", |
| .merkle_map = ParseTextProtoOrDie<BmffMerkle>(R"pb( |
| count: 1 |
| )pb"), |
| .mdat_size = 100, |
| .expected = std::vector<int64_t>{100}, |
| }), |
| [](const testing::TestParamInfo<BlockSizesCase>& info) { |
| return info.param.name; |
| }); |
| |
| TEST(MerkleTest, VariableBlockSizesExceedsLimit) { |
| BmffMerkle merkle_map; |
| merkle_map.set_count(1048577); |
| for (int i = 0; i < 1048577; ++i) { |
| merkle_map.add_variable_block_sizes(1); |
| } |
| EXPECT_THAT(DeriveMerkleBlockSizes(merkle_map, 1048577), |
| StatusIs(absl::StatusCode::kInvalidArgument, |
| HasSubstr("merkle map block count exceeds maximum " |
| "allowable limit: 1048577 > 1048576"))); |
| } |
| |
| struct TreeDataCase { |
| std::string name; |
| int64_t leaf_count; |
| int64_t hashes_count; |
| int64_t auxiliary_count; |
| absl::StatusOr<DerivedTreeData> expected; |
| }; |
| |
| using DeriveTreeDataTest = testing::TestWithParam<TreeDataCase>; |
| |
| TEST_P(DeriveTreeDataTest, DerivesTreeData) { |
| const TreeDataCase& params = GetParam(); |
| |
| if (params.expected.ok()) { |
| EXPECT_THAT(DeriveMerkleTreeData(params.leaf_count, params.hashes_count, |
| params.auxiliary_count), |
| IsOkAndHolds(Eq(params.expected.value()))); |
| } else { |
| EXPECT_THAT(DeriveMerkleTreeData(params.leaf_count, params.hashes_count, |
| params.auxiliary_count), |
| StatusIs(params.expected.status().code(), |
| params.expected.status().message())); |
| } |
| } |
| |
| INSTANTIATE_TEST_SUITE_P( |
| DeriveTreeDataTests, DeriveTreeDataTest, |
| ::testing::Values( |
| TreeDataCase{ |
| .name = "LeafCountTooLarge", |
| .leaf_count = 0x8000'0001, |
| .hashes_count = 3, |
| .auxiliary_count = 0, |
| .expected = absl::InvalidArgumentError(absl::StrFormat( |
| "Value is negative or too large: %d", 0x8000'0001)), |
| }, |
| TreeDataCase{ |
| .name = "HashesCountTooLarge", |
| .leaf_count = 5, |
| .hashes_count = 0x8000'0001, |
| .auxiliary_count = 0, |
| .expected = absl::InvalidArgumentError(absl::StrFormat( |
| "Value is negative or too large: %d", 0x8000'0001)), |
| }, |
| TreeDataCase{ |
| .name = "HashesBelowLeafRow", |
| .leaf_count = 3, |
| .hashes_count = 5, |
| .auxiliary_count = 0, |
| .expected = absl::InvalidArgumentError( |
| "hashes row size is larger than the leaf row size"), |
| }, |
| TreeDataCase{ |
| .name = "IncorrectHashesCountSameRow", |
| .leaf_count = 5, |
| .hashes_count = 6, |
| .auxiliary_count = 0, |
| .expected = absl::InvalidArgumentError( |
| "hashes count is not equal to the expected hashes count: " |
| "Hashes Count: 6, Leaf Count: 5, Expected Hashes Count: 5"), |
| }, |
| TreeDataCase{ |
| .name = "IncorrectHashesCountDifferentRows", |
| .leaf_count = 5, |
| .hashes_count = 4, |
| .auxiliary_count = 0, |
| .expected = absl::InvalidArgumentError( |
| "hashes count is not equal to the expected hashes count: " |
| "Hashes Count: 4, Leaf Count: 5, Expected Hashes Count: 3"), |
| }, |
| TreeDataCase{ |
| .name = "IncorrectAuxiliaryCountSameRows", |
| .leaf_count = 5, |
| .hashes_count = 5, |
| .auxiliary_count = 3, |
| .expected = absl::InvalidArgumentError( |
| "incorrect count of auxiliary data boxes: Auxiliary Data " |
| "Count: 3, Leaf Count: 5"), |
| }, |
| TreeDataCase{ |
| .name = "IncorrectAuxiliaryCountDifferentRows", |
| .leaf_count = 5, |
| .hashes_count = 3, |
| .auxiliary_count = 3, |
| .expected = absl::InvalidArgumentError( |
| "incorrect count of auxiliary data boxes: Auxiliary Data " |
| "Count: 3, Leaf Count: 5"), |
| }, |
| TreeDataCase{ |
| .name = "ValidTreeDataSameRowNoAuxiliary", |
| .leaf_count = 5, |
| .hashes_count = 5, |
| .auxiliary_count = 0, |
| .expected = |
| DerivedTreeData{ |
| .full_leaf_count = 8, |
| .full_hashes_count = 8, |
| .delta_rows = 0, |
| }, |
| }, |
| TreeDataCase{ |
| .name = "ValidTreeDataSameRowWithAuxiliary", |
| .leaf_count = 5, |
| .hashes_count = 5, |
| .auxiliary_count = 5, |
| .expected = |
| DerivedTreeData{ |
| .full_leaf_count = 8, |
| .full_hashes_count = 8, |
| .delta_rows = 0, |
| }, |
| }, |
| TreeDataCase{ |
| .name = "ValidTreeDataDifferentRows", |
| .leaf_count = 5, |
| .hashes_count = 3, |
| .auxiliary_count = 5, |
| .expected = |
| DerivedTreeData{ |
| .full_leaf_count = 8, |
| .full_hashes_count = 4, |
| .delta_rows = 1, |
| }, |
| }), |
| [](const testing::TestParamInfo<TreeDataCase>& info) { |
| return info.param.name; |
| }); |
| |
| struct CreateWithOptionsCase { |
| std::string name; |
| std::string contents; |
| int64_t starting_offset; |
| int64_t length; |
| CreateMerkleTreeOptions options; |
| std::variant<MerkleTree, absl::Status> expected; |
| }; |
| |
| using CreateWithOptionsTest = testing::TestWithParam<CreateWithOptionsCase>; |
| |
| TEST_P(CreateWithOptionsTest, CreatesMerkleTree) { |
| const CreateWithOptionsCase& params = GetParam(); |
| |
| riegeli::StringReader<> input(params.contents); |
| |
| JoiningHasherFactory factory; |
| |
| if (std::holds_alternative<absl::Status>(params.expected)) { |
| EXPECT_THAT( |
| CreateMerkleTree(&factory, input, params.starting_offset, params.length, |
| params.options), |
| StatusIs(std::get<absl::Status>(params.expected).code(), |
| HasSubstr(std::get<absl::Status>(params.expected).message()))); |
| } else { |
| EXPECT_THAT(CreateMerkleTree(&factory, input, params.starting_offset, |
| params.length, params.options), |
| IsOkAndHolds(Eq(std::get<MerkleTree>(params.expected)))); |
| } |
| } |
| |
| INSTANTIATE_TEST_SUITE_P( |
| OptionBasedTests, CreateWithOptionsTest, |
| ::testing::Values( |
| CreateWithOptionsCase{.name = "EmptyOptions", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {}, |
| .expected = |
| MerkleTree{ |
| {"abcde"}, |
| }}, |
| CreateWithOptionsCase{.name = "FixedBlockSizeSingleByte", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.fixed_block_size = 1}, |
| .expected = |
| MerkleTree{ |
| {"a", "b", "c", "d", "e", "", "", ""}, |
| {"ab", "cd", "e", ""}, |
| {"abcd", "e"}, |
| {"abcde"}, |
| }}, |
| CreateWithOptionsCase{.name = "FixedBlockSizeTwoBytes", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.fixed_block_size = 2}, |
| .expected = |
| MerkleTree{ |
| {"ab", "cd", "e", ""}, |
| {"abcd", "e"}, |
| {"abcde"}, |
| }}, |
| CreateWithOptionsCase{.name = "VariableBlockSizes", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.variable_block_sizes = {3, 1, 1}}, |
| .expected = |
| MerkleTree{ |
| {"abc", "d", "e", ""}, |
| {"abcd", "e"}, |
| {"abcde"}, |
| }}, |
| CreateWithOptionsCase{ |
| .name = "FailsWithBothFixedAndVariableBlockSizes", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.fixed_block_size = 1, |
| .variable_block_sizes = {3, 1, 1}}, |
| .expected = absl::InvalidArgumentError( |
| "Must specify a fixed block size or " |
| "variable block sizes, not both."), |
| }, |
| CreateWithOptionsCase{ |
| .name = "FailsWithZeroFixedBlockSize", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.fixed_block_size = 0}, |
| .expected = absl::InvalidArgumentError( |
| "Fixed block size must be greater than 0. Found: 0"), |
| }, |
| CreateWithOptionsCase{ |
| .name = "FailsWithInputTooSmall", |
| .contents = "abcde", |
| .starting_offset = 3, |
| .length = 5, |
| .options = {.fixed_block_size = 10}, |
| .expected = absl::DataLossError("Failed to read leaf data"), |
| }, |
| CreateWithOptionsCase{ |
| .name = "FixedBlockSizeLargerThanInput", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.fixed_block_size = 10}, |
| .expected = MerkleTree{{"abcde"}}, |
| }, |
| CreateWithOptionsCase{ |
| .name = "FailsWithVariableBlockSizesTooLarge", |
| .contents = "abcde", |
| .starting_offset = 0, |
| .length = 5, |
| .options = {.variable_block_sizes = {2, 3, 5}}, |
| .expected = absl::InvalidArgumentError( |
| "Total block size is too large. " |
| "Total Block size: 10, Length: 5"), |
| }), |
| [](const testing::TestParamInfo<CreateWithOptionsCase>& info) { |
| return info.param.name; |
| }); |
| |
| } // namespace |
| } // namespace credentio |
