Port mpt-witness-generator back to zkevm-circuits

[ChihChengLiang]

Describe the feature you would like

We've merged the MPT circuit, but it has yet to be able to generate witnesses for our EVM computation. So, our next step is to add the witness generation feature in the circuit input builder, as described in #811.

But #811 was written in the context before the mpt-witness-generator (MPTWG hereafter) became an independent repo.

MPTWG as an external dependency would cause issues, and we should move it back to this repo as a crate.

Additional context

Before we explain why it causes issues, let me share my understanding of the current status.

We currently test the MPT circuit by feeding a list of generated witnesses to the MPT circuit.

zkevm-circuits/zkevm-circuits/src/mpt_circuit.rs

Lines 813 to 826 in 5d01150

	fn test_mpt() {
	let path = "src/mpt_circuit/tests";
	let files = fs::read_dir(path).unwrap();
	files
	.filter_map(Result::ok)
	.filter(|d| {
	if let Some(e) = d.path().extension() {
	e == "json"
	} else {
	false
	}
	})
	.enumerate()
	.for_each(|(idx, f)| {

The generated witnesses are in the form of JSON files located at https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/484c1ae8cdb16ce0d1d8a8645f29a968206bb4fe/zkevm-circuits/src/mpt_circuit/tests

We can run this command to run the MPT tests.

 cargo test --package zkevm-circuits --lib -- mpt_circuit::tests --nocapture 

The JSON witnesses are generated using MPTWG. To generate witnesses, run cd witness then go test gen_witness_from_infura_blockchain_test.go prepare_witness.go leaf.go extension_node.go modified_extension_node.go nodes.go test_tools.go branch.go util.go.

This causes some problems. Say we want to update the MPTWG. The flow would be

1. Work on a PR at MPTWG and get it merged.
2. Work on a PR at zkevm-circuits repo and get it merged.

But for step 2, we have to carefully run the MPTWG and generate new JSON files in the zkevm-circuit PR. Note that these JSON files are matrices of hax compressed in one line, which is not easy to review.

The proposed approach is we

1. Move MPTWG as a crate in zkevm-circuits. The new flow of updating MPTWG would become one PR.
2. JSONs are only generated in the test run and passed directly to the circuit. We make sure the MPT circuit consumes the correct version of witness automatically.
3. We don't dump JSON in files and add them in the commits. JSON witnesses are useful to be printed out as debug information but are not reviewable in the PRs.

[miha-stopar]

@ChihChengLiang Great summary! One additional thing is that MPTWG is in Go (and there is Rust binding to it) - does this change things a bit?

[ChihChengLiang]

Good question. We already have geth-utils crate in this repo, which is a Go implementation with a Rust binding. So I think it should be fine to do that.

Eventually, we want to port MPTWG to Rust for consistency. Here's a possible way to do it.

1. First, we move MPTWG to this repo.
2. We build unit tests in Rust to ensure the output remains the same.
3. Rewrite MPTWG in Rust. We can ensure the correctness of the implementation because it is protected by unit tests.

[ed255]

Before actively working on this, check if @Brechtpd plans to refactor some of the code.

[miha-stopar]

Before actively working on this, check if @Brechtpd plans to refactor some of the code.

We can move it, Brecht doesn't plan to refactor it.