# General Grant Proposal

* **Project:** Investigation of VOLE itH and its verification cost

## Project Overview :page_facing_up:

### Overview

Recently, VOLE-based zero-knowledge (ZK) systems have gained attention for their computational efficiency, particularly in the context of client proving. For example, in use cases like zkTLS, VOLE-based ZK has demonstrated significant advantages over SNARKs in terms of memory usage and computational complexity. However, VOLE-based ZK systems face challenges with proof size and communication cost compared to other ZK systems, limiting their broader adoption.

This project focuses on VOLE in the Head (VOLE itH), an efficient and publicly verifiable variant of VOLE-based ZK. Our primary goal is to enable on-chain verification of VOLE itH ZK proofs, paving the way for practical blockchain integration. The project includes benchmarking and analysis of verification costs within a public blockchain setting. Key metrics include verification time, memory usage, data transmission size, and gas costs. Additionally, we aim to explore cost optimization using blobs and compare the results with traditional Solidity-based verification methods. Finally, we will assess the feasibility of encapsulating VOLE-based ZK proofs within SNARKs to achieve succinctness.

### Short Rationale

VOLE-based ZK significantly reduces the computational and memory burden on provers, making it feasible to generate proofs efficiently even on consumer hardware such as mobile devices. This breakthrough can democratize access to Ethereum's cryptographic ecosystem, enabling a broader range of users to participate in privacy-preserving and scalable blockchain applications.

However, despite its advantages for client-side proving, on-chain verification of VOLE-based ZK systems remains a significant hurdle, primarily due to high gas costs and inefficiencies in traditional verification methods. By leveraging blobs, this project aims to address these challenges and determine the feasibility of deploying VOLE itH proofs on-chain. The successful implementation of this project could lower the barriers to client-side proving and establish VOLE-based ZK as a viable alternative for scalable and privacy-oriented blockchain applications.

### Project Details

This project investigates the feasibility of on-chain verification for VOLE in the Head (VOLE itH), a publicly verifiable and efficient variant of VOLE-based zero-knowledge (ZK) proofs. While VOLE-based ZK systems significantly reduce computational complexity for provers, the challenge lies in implementing cost-effective and scalable on-chain verification.

VOLE-based ZK systems are typically designed for efficient prover but are not yet widely implemented for on-chain verification due to challenges such as proof size, communication costs, and gas costs. VOLE itH introduces public verifiability, making it a promising candidate for practical zk schemes for on-chain applications via client-side provers. However, the exact costs and technical bottlenecks of integrating VOLE itH into a public blockchain, such as Ethereum, remain unclear.

The project seeks to answer the following key questions:

1. On-Chain Verification Cost: What are the computational and gas costs of verifying VOLE itH proofs on-chain, and how can they be optimized?
2. Prover Cost and Feasibility: What is the computational cost of proof generation for provers, and is it feasible on consumer-grade hardware such as laptops or mobile devices?
3. Proof Size and Communication Cost: What are the size of the generated proofs and the associated communication costs between the prover and the verifier?
4. Technical Challenges: What are the primary technical challenges in implementing cost-efficient on-chain verification for VOLE itH, and how can they be addressed?
5. Integration with SNARKs: Can VOLE-based ZK proofs be encapsulated within SNARKs to reduce on-chain verification costs and improve succinctness?

Milestone 1 will focus on investigating the theoretical and practical aspects of VOLE itH and design blob-based on-chain verification architecture.
In milestone 2, we develop and take benchmarks to evaluate the on-chain verification cost, prover cost and other aspects. We will deploy 2 methods, naive solidity verifier and verifier utilizing blobs. The benchmarks will be designed so that we can evaluate the practicality of VOLE itH in client side proving settings and will be discussed in the report in milestone3.
In milestone 3, we will conclude whether VOLE itH can be used for on-chain verification at a realistic cost based on the results so far. It will also summarize the challenges and future work and discuss the possibilities for client proving.

The items to be measured at Milestone 2 are listed in the table below.

| Metric | Description | Unit | Example Measurement Method |
|--------------------------|---------------------------------------------------------------------------------------------|---------------------|-----------------------------------------------------------------------------------------------|
| Proof Generation Time | Time required for the prover to generate the proof | Milliseconds (ms) | Measure the execution time of the proof generation process |
| Proof Verification Time | Time required for the verifier to verify the proof | Milliseconds (ms) | Measure the execution time of the proof verification process |
| Proof Size | Size of the generated proof data | Bytes | Measure the size of the proof after generation |
| Prover Computation Load | Computational cost for the prover (e.g., memory usage, CPU usage) | CPU Load (%), MB | Monitor resource usage during the proof generation process |
| Verifier Computation Load| Computational cost for the verifier (e.g., memory usage, CPU usage) | CPU Load (%), MB | Monitor resource usage during the proof verification process |
| Setup Time | Time required for the initial system setup (if applicable) | Seconds (s) | Measure the execution time of the setup process |
| Communication Overhead | Total amount of data exchanged between prover and verifier | Bytes | Capture communication logs and measure the total data exchanged |
| On-Chain Verification Gas Cost| Cost of verifying the proof on-chain in gas | Gas units | Measure gas cost using a blockchain environment (e.g., Ethereum) |

gantt
    title Project Roadmap
       dateFormat  MM-DD
    axisFormat %m-%d
    section Milestones
    Milestone 1 (Investigation) :m1, 1-01, 31d
    Milestone 2 (Measuring)       :m2, after m1, 28d
    Milestone 3 (Analysis)      :m3, after m2, 31d

## Team :busts_in_silhouette:

### Team members

* Shouki Tsuda
* [e-mail]
* Telegram handle: adust09
* Discord handle: adust09
* Notion Account (If different from the above email)

### Team Website

* https://t.co/4OJWbVrEI7

### Team's experience

Obtained a Computer Science degree with a focus on blockchain and cryptography theory. Gained practical experience during university, working with Japanese startups on dApps development and protocol auditing.Post-graduation, joined Rakuten.inc, where I was involved in the development and operation of traditional financial systems. Subsequently led the development of Hana Network, addressing challenges in privacy-preserving payments and on/off-ramp solutions.Currently, I am leading a working group researching zero-knowledge proof systems in Japan. My work combines theoretical knowledge with practical application, focusing on the implementation of cutting-edge cryptographic technologies. My recent talk at Devcon is [here](https://www.youtube.com/watch?v=j9YnU1-MeiU)

### Team Code Repos

* https://github.com/adust09

## Development Roadmap :nut_and_bolt:

### Overview

* **Total Estimated Duration:** 3 month
* **Full-time equivalent (FTE):** 3FTE
* **Total Costs:** $15,000

### Milestone 1 Investigation

* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $5,000
* **Estimated delivery date**: Jan 31st 2025

The primary goal of Milestone 1 is to conduct an in-depth theoretical and practical investigation of VOLE in the Head (VOLE itH) to identify key challenges and opportunities for on-chain verification. This includes analyzing proof size, communication costs, and computational requirements while designing an architecture for blob-based verification on Ethereum.

Paper:https://eprint.iacr.org/2023/996
Implementation:https://github.com/faest-sign/faest-rs/blob/crypto-2023/src/voleith.rs

#### Deliverables

##### Report on VOLE itH
A comprehensive report summarizing findings on VOLE itH, including:

Proof size and communication cost analysis.
Identification of bottlenecks in on-chain verification.
Verification Architecture Specification:

##### A detailed specification of the blob-based on-chain verification framework.
Comparisons with traditional Solidity-based verification approaches.

### Milestone 2 Benchmarks

* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $5,000
* **Estimated delivery date**: Feb 28st 2025

The goal of Milestone 2 is to implement the designed on-chain verifiers and measure the performance of VOLE itH in a blockchain environment. This includes benchmarking the Solidity-based on-chain verifier and blob-based on-chain verifier to evaluate on-chain verification costs, prover efficiency, proof size, and communication overhead.

We're planning to use a laptop Apple M1 with 16GB memory as a consumer grade machine which we will take benchmark with. Target circuit for the benchmarking is typical hash function(SHA and AES) because VOLE itH is designed for boolean circuit operations. The base VOLE itH implementation we use is [this](https://github.com/faest-sign/faest-rs/blob/master/src/voleith.rs).

As a method for on-chain verification, we will implement the naive solidity verifier contract and the new blob based verifier to be explored. As well as measuring benchmarks of these two solutions, we will also measure the performance of a VOLE-itH in non-blockchain setting.

#### Deliverables and Specifications
##### Implementation
- Implementation of solidity verifier
- Implementation of blob verifier

##### Benchmark report
VOLE itH in non-blockchain setting
- Proving Time
- Verification Time
- Proof Size
- Prover Computation Load
- Verifier Computation Load
- Communication Overhead

Naive on-chain verifier and blob verifier
- Proving Time
- Verification Time
- Proof Size
- Prover Computation Load
- Verifier Gas Cost
- Communication Overhead

### Milestone 3 Analysis

* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $5,000
* **Estimated delivery date**: Mar 31st 2025

Milestone 3 aims to analyze the results from Milestone 2 to assess the feasibility of on-chain verification for VOLE itH and identify remaining challenges. We will write a comprehensive final report, summarizing findings, comparisons, and recommendations for future work. Additionally, this milestone explores the potential of integrating VOLE itH with SNARKs to optimize performance and scalability.

#### Deliverables and Specifications

Final Report:
A comprehensive document including:
- Feasibility analysis and key findings from Milestone 1 and 2.
- Comparative analysis of on-chain verifiers.
- Insights into SNARK integration for VOLE itH.
- Identification of technical bottlenecks and solutions.

## Additional Information :heavy_plus_sign: