zkMemory Project Delivered Milestones

Project: zkMemory

Timeline

Audited

29 Sep 2023, Complete Milestone 1: Implement state machine for zkMemory
10 Oct 2023, Complete Milestone 5: RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs
15 Mar 2024, Complete Milestone 2: Support KZG Commitment for zkMemory
5th Jun 2024, Complete Milestone 4: Merkle tree commitment fallback mode and Milestone 3: Integrate Verkle tree with KZG commitment
08 Oct 2024, Complete Milestone 6: Support Nova & SuperNova

Awaiting for audit

17 Feb 2025, Complete Milestone 7: Documentation

Upcoming

Milestone 7: Documentation

Milestone 1: Implement state machine for zkMemory

Number	Deliverable	Specification
0a.	Documentation	We will provide both inline documentation of the code and a basic tutorial that explains how a user can (for example) spin up the application.
0b.	Testing Guide	The code will have proper unit-test coverage (e.g. 80%) to ensure functionality and robustness. In the guide we will describe how to run these tests
1.	zkMemory crate	Build a zkMemory crate that generalize memory for zkVM
2.	Functionality: Memory state machine	Provide a simple state machine with `2` opcode `READ`, `WRITE` with configurable `WORD_SIZE` depend on target zkVM, support from (8 bits to 256 bits)
3.	Functionality: Memory cell	Manage every cell of the memory, translate `WRITE` and `READ` multiple cells to equivalent trace
4.	Functionality: Memory trace	Generate trace and grouping by memory address to prepare for memory commitment, translate arbitrary memory access to read and write on a memory cell.
5.	Functionality: Stack and virtual registers	Handle stack, virtual registers emulation for zkMemory (Some architecture like RISC-V might have both registers and stack)

Note (2-5): We write two examples to demo all of these functionalities:

Result of 64 bits machine:

Pop value: 0x0000000000000506
Read value: 0x0a0c0e1012141618
Execution record format is: Instruction(address, time_log, stack_depth, value)
        Write (0000000000000008, 0000000000000001, 0000000000000000, 0102030405060708)
        Read  (0000000000000008, 0000000000000002, 0000000000000000, 0102030405060708)
        Write (fffffffffffffef0, 0000000000000003, 0000000000000000, 0102030405060708)
        Write (0000000000000000, 0000000000000004, 0000000000000000, 090a0b0c0d0e0f10)
        Read  (0000000000000000, 0000000000000005, 0000000000000000, 090a0b0c0d0e0f10)
        Write (fffffffffffffef8, 0000000000000006, 0000000000000000, 090a0b0c0d0e0f10)
        Read  (fffffffffffffef0, 0000000000000007, 0000000000000000, 0102030405060708)
        Read  (fffffffffffffef8, 0000000000000008, 0000000000000000, 090a0b0c0d0e0f10)
        Write (fffffffffffffef0, 0000000000000009, 0000000000000000, 0a0c0e1012141618)
        Read  (fffffffffffffef0, 000000000000000a, 0000000000000000, 0a0c0e1012141618)
        Write (0000000000000010, 000000000000000b, 0000000000000000, 0a0c0e1012141618)
        Push  (ffffffffffffdee8, 000000000000000c, 0000000000000001, 0000000000000102)
        Push  (ffffffffffffdef0, 000000000000000d, 0000000000000002, 0000000000000304)
        Push  (ffffffffffffdef8, 000000000000000e, 0000000000000003, 0000000000000506)
        Pop   (ffffffffffffdef8, 000000000000000f, 0000000000000002, 0000000000000506)
        Read  (0000000000000010, 0000000000000010, 0000000000000002, 0a0c0e1012141618)

Milestone 5: Research "Tequila - Folding Scheme for Witness of Polynomials"

Number	Deliverable	Specification
1.	Scientific Paper	The scientific paper was renamed to RamenPasta: Parallelizable Succinct Transparent Arguments of Knowledge for RAM Programs https://eprint.iacr.org/2024/336

Milestone 2: Support KZG Commitment for zkMemory

Estimated Duration: 2 months
FTE: 1.4
Estimated delivery date: Jul 31th 2023

Number	Deliverable	Specification
0a.	Documentation	We will provide both inline documentation of the code and a basic tutorial that explains how a user can (for example) spin up the application. Note: We can't publish our document since it required `halo2_proof` and `halo2curve` to be a publish package
0b.	Testing Guide	The code will have proper unit-test coverage (e.g. 80%) to ensure functionality and robustness. In the guide we will describe how to run these tests
1.	Functionality: KZG Commitment	Utilize KZG commitment to generate witnesses that's necessary for proving the memory state
2.	Functionality: Halo2	Make the generated witnesses compatible with Halo2 proving system, write an example that can prove memory trace

Note: We can't publish our package and document due to halo2 wasn't published.

Milestone 4: Merkle tree commitment fallback mode

Estimated Duration: 1 month
FTE: 1
Estimated delivery date: Sep 30th 2023

Number	Deliverable	Specification
0b.	Documentation	We will provide both inline documentation of the code and a basic tutorial that explains how a user can (for example) spin up the application.
0c.	Testing Guide	The code will have proper unit-test coverage (e.g. 80%) to ensure functionality and robustness. In the guide we will describe how to run these tests
1.	Functionality: Poseidon Merkle tree	Implement Merkle tree that using ZK friendly hash function like Poseidon
2.	Functionality: Fallback mode	Implement Merkle tree fallback for incompatible proving system

Milestone 3: Integrate Verkle tree with KZG commitment

Estimated Duration: 1 month
FTE: 1.6
Estimated delivery date: Aug 31th 2023

Number	Deliverable	Specification
0a.	Documentation	We will provide both inline documentation of the code and a basic tutorial that explains how a user can (for example) spin up the application.
0b.	Testing Guide	The code will have proper unit-test coverage (e.g. 80%) to ensure functionality and robustness. In the guide we will describe how to run these tests
1.	Functionality: Verkle tree	Implement Verkle tree, write the code to test Verkle tree construction
2.	Functionality: Verkle tree with KZG commitment	Implement Verkle tree that support KZG commitment, add new example to prove memory trace with Verkle tree + KZG

Milestone 6 Support Nova & SuperNova

Estimated Duration: 3 months
FTE: 1.4
Estimated delivery date: Feb 29th 2024

Number	Deliverable	Specification
0b.	Documentation	We will provide both inline documentation of the code and a basic tutorial that explains how a user can (for example) spin up the application.
0c.	Testing Guide	The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide we will describe how to run these tests
1.	Functionality: Nova	Support Nova prover, allowed zkVM based on Nova could use zkMemory
2.	Functionality: SuperNova	Support SuperNova prover, allowed zk
3.	Examples 1 2	Write two examples to prove memory state in Nova and SuperNova

Note: We can't publish our package and document due to halo2 wasn't published.

Milestone 7 Documentation

Estimated Duration: 1 months
FTE: 1
Estimated delivery date: Feb 29th 2024

Number	Deliverable	Specification
1	Documentation	Add missing inline document, build rust document.
2	zkMemory website	Create a website of zkMemory, provide some example use cases. Reorganize document to make it much more friendly for developers.
3	Increase coverage	Add more unit test to cover 90% code or more.

Note: We can't publish our package and document due to halo2 wasn't published.

Mitsu Matsumoto

2024/08/08 08:37:41

Note: We can publish our package and document due to halo2 wasn't published.

@chiro-hiro Does this mean you cannot publish the doc due to halo2, right?

Chiro Hiro

2024/08/08 08:48:13

We can't publish document due to PSE didn't publish halo2 crate since ZCash is owning of halo2 name.

2024/08/08 08:38:23

Documentation

@chiro-hiro Would there be an output for this or removed for some reason?

2024/08/08 08:49:03

The document can be generated offline, but it can't be available online due to halo2 isn't a public crate. (Edited)

2024/08/08 08:39:25

Functionality: Fallback mode

@chiro-hiro The same for this. Would there be an output for this or removed for some reason?

2024/08/08 08:50:14

The fallback is configurable, this feature is depend on Nova and SuperNova implementation and it's on the way https://github.com/orochi-network/orochimaru/pull/75

2024/08/09 16:25:49

On the way means milestone 4 isn’t finished yet?

2024/08/16 07:26:26

No merkle tree is completed in https://github.com/orochi-network/orochimaru/pull/64 It wasn't use since we are using PSE's Halo2 and it has better commitment scheme (KZG).

2024/08/08 08:39:42

2024/08/08 08:50:59

The document can be generated offline, but it can't be available online due to halo2 isn't a public crate.