RISC-V: Merkleise large vectors as subtrees

Closes RV-510.

What

This MR changes the way Many values of the state are hashed and Merkleised, from a single node whose children are all the elements in the vector, to a subtree in which each node has MERKLE_ARITY children. This is the same method used for DynArray.

Why

Many are meant to represent large vectors. The current Merkleisation method results in extremely large proofs since, for any single access to the vector, the hashes of all other elements need to be stored in the proof in order to recompute the hash of the Many node during proof verifiction.

Proof size is drastically reduced, but proof generation time is increased since more intermediary hashes need to be computed. For example, before:

> Running 1461416 steps ...
> Producing proof ...
> Proof of size 33025 KiB produced in 32.325682s

And after:

> Running 1461416 steps ...
> Producing proof ...
> Proof of size 2 KiB produced in 51.22634975s

How

By replicating hashing and Merkleisation for DynArray. Some of the common logic is abstracted.

Manually Testing

make -C src/riscv all
cargo test -- test_jstz_proofs_one_step --ignored --nocapture

Benchmarking

No impact on interpreter performance.

Regressions

Initial and final hashes have changed since hashing Many nodes is done differently.

Tasks for the Author

• Link all Linear issues related to this MR using magic words (e.g. part of, relates to, closes).
• Eliminate dead code and other spurious artefacts introduced in your changes.
• Document new public functions, methods and types.
• Make sure the documentation for updated functions, methods, and types is correct.
• Add tests for bugs that have been fixed.
• Put in reasonable effort to ensure that CI will pass.
  • make -C src/riscv
  • dune build src/lib_riscv
  • dune build src/rust_deps
• Benchmark performance and populate the table above if needed.
• Explain changes to regression test captures when applicable.
• Write commit messages to reflect the changes they're about.
• Self-review your changes to ensure they are high-quality.
• Complete all of the above before assigning this MR to reviewers.

Summary by CodeRabbit

• Refactor

  • Streamlined state integrity and proof tree generation, reducing redundancy and improving overall efficiency.
  • Enhanced branch management and error handling for more robust proof validation and processing.

• Tests

  • Updated expected outputs to align with the new computation process.
  • Introduced timing and size logging during proof production for improved diagnostic insights.