feat: Data-driven BMT test generation and framework

[bvrooman]

Related issues:

• https://github.com/FuelLabs/fuel-core/issues/687

This PR introduces a test suite for generating BMT proofs and their expected verification result. The test suite includes a number of positive test cases (verification is expected to be true) and some negative test cases (verification is expected to be false).

The test suite can be generated using cargo run --bin write-bmt-test-suite. Test data is randomly sampled from the set of hashed integers. The RNG is seeded with a constant value such that each time the test suite is generated, the test data is consistent.

This PR also adds these tests to the fuel-merkle test suite executed during cargo test. The framework used by SMT data-driven tests has been refactored to apply to BMTs as well.

[bvrooman]

Thanks for the review!

If I understand your suggestion correctly, you're proposing:

• A fixture has a "known valid tree", a root, and a proof set
• A root is defined by a coordinate pointing to a value in the tree, as well as a tag for valid or invalid
• A proof set is defined by a set of coordinates pointing to a value in the tree, as well as a tag for valid or invalid

My concern with this approach is that it is coupling a proof with the tree that generated it. In this format, it seems I need to have a valid tree to begin with so that the coordinates point to a spot in the tree. How do I specify an invalid root hash or invalid proof hash?

I would also argue that the test vectors should align syntactically with the system being tested. In this case, the contract's verify function takes in the parameters supplied by the test, almost as-is. If we go with an alternative format, the test implementor is responsible for transforming the test vector into a format that it can consume.

Perhaps if you can elaborate on the suggested format, I can understand better how it meets the goals of the test suite.

[bvrooman]

This PR in fuel-merkle-sol demonstrates how the generated test suite is used to validate the solidity implementation. This would need final confirmation on the format of the generated tests before we can commit the tests in fuel-merkle-sol.

[freesig]

Yeh maybe my idea was not the best. I guess the bigger picture is it would be nice if I could look at the fixtures and understand why it should be expected to verify or not. Currently it's not clear why each fixture would be valid or not. Maybe even something as simple as a comment in the yaml stating why it should validate or not?

[bvrooman]

I agree that it would certainly be helpful to have the extra context as to why the test case should verify or not. I updated the test cases to include a description field that briefly describes why the test case should result in a passed or failed verification.

[xgreenx]

Hmm, is it okay that yaml files are not the same as in TS PR?

[bvrooman]

I will copy the files over to the TS PR once the files here are finalized and merged. Thanks for the review @xgreenx. I will wait today for anyone else on the client team to review if they wish.