# zkMemory Project Delivered Milestones
- **Project:** zkMemory
## Timeline
### Audited
- 29 Sep 2023, Complete [Milestone 1: Implement state machine for zkMemory](https://hackmd.io/@chiro-hiro/r1c_-RQx6#Milestone-1-Implement-state-machine-for-zkMemory)
- 10 Oct 2023, Complete [Milestone 5: RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs](https://hackmd.io/@chiro-hiro/r1c_-RQx6#Milestone-5-Research-Tequila---Folding-Scheme-for-Witness-of-Polynomials)
- 15 Mar 2024, Complete [Milestone 2: Support KZG Commitment for zkMemory](https://hackmd.io/@chiro-hiro/r1c_-RQx6#Milestone-2-Support-KZG-Commitment-for-zkMemory)
- 5th Jun 2024, Complete [Milestone 4: Merkle tree commitment fallback mode](#Milestone-4-Merkle-tree-commitment-fallback-mode) and [Milestone 3: Integrate Verkle tree with KZG commitment](#Milestone-3-Integrate-Verkle-tree-with-KZG-commitment)
- 08 Oct 2024, Complete [Milestone 6: Support Nova & SuperNova](https://hackmd.io/@chiro-hiro/r1c_-RQx6#Milestone-6-Support-Nova-amp-SuperNova)
### Awaiting for audit
- 17 Feb 2025, Complete [Milestone 7: Documentation](https://hackmd.io/@chiro-hiro/r1c_-RQx6#Milestone-7-Documentation)
### Upcoming
- Milestone 7: Documentation
### Milestone 1: Implement state machine for zkMemory
| Number | Deliverable | Specification |
| ------ | ------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 0a. | [Documentation](https://docs.rs/zkmemory/0.1.1/zkmemory/) | 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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory#testing-and-coverage) | 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](https://crates.io/crates/zkmemory) | Build a zkMemory crate that generalize memory for zkVM |
| 2. | [Functionality: Memory state machine](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/machine.rs#L73) | 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](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/memory.rs#L7) | Manage every cell of the memory, translate `WRITE` and `READ` multiple cells to equivalent trace |
| 4. | [Functionality: Memory trace](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/machine.rs#L19) | 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](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/machine.rs#L95) | 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:
- [64 bits machine with stack and 4 virtual registers](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/examples/64bits-machine.rs)
- [256 bits machine](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/examples/256bits-machine.rs)
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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory) | 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](https://github.com/orochi-network/orochimaru/pull/59) | Utilize KZG commitment to generate witnesses that's necessary for proving the memory state |
| 2. | [Functionality: Halo2](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/examples/memory-consistency.rs) | 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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory) | 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](https://github.com/orochi-network/orochimaru/pull/64) | Implement Merkle tree that using ZK friendly hash function like Poseidon |
| 2. | [Functionality: Fallback mode](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/nova/memory_consistency_circuit.rs#L49) | 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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory) | 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](https://github.com/orochi-network/orochimaru/pull/69) | Implement Verkle tree, write the code to test Verkle tree construction |
| 2. | [Functionality: Verkle tree with KZG commitment](https://github.com/orochi-network/orochimaru/pull/69) | 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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory) | 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](https://github.com/orochi-network/orochimaru/tree/main/zkmemory/src/nova) | Support Nova prover, allowed zkVM based on Nova could use zkMemory |
| 2. | [Functionality: SuperNova](https://github.com/orochi-network/orochimaru/tree/main/zkmemory/src/supernova) | Support SuperNova prover, allowed zk |
| 3. | Examples [1](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/nova/testcases.rs) [2](https://github.com/orochi-network/orochimaru/blob/main/zkmemory/src/supernova/testcases.rs) | 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](https://zkmemory.orochi.network/intro) | Create a website of zkMemory, provide some example use cases. Reorganize document to make it much more friendly for developers. |
| 3 | [Increase coverage](https://github.com/orochi-network/orochimaru/pull/90) | 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.
Sign in with Wallet
Connect another wallet