# General Grant Proposal

* **Project** Protostar folding optimization

## Project Overview :page_facing_up:

### Overview

A DSL allowing to write high degree circuits and compile them to recursion-optimized Protostar.

### Project Details
The project consists of three parts: the DSL, the Protostar compiler, and recursion optimizations (all written in Rust).

The main goal is to optimize the IVC recursion in Protostar by transferring some of the computational work currently lying on the grumpkin side of the folding to the BN254.

There are two optimizations to test: high-degree gates and circuit cutting. These optimizations require an R1CS-like intermediate language allowing the use of gates of degree higher than two. This is the motivation for the DSL.

## Team :busts_in_silhouette:

### Team members
* Amir Ismailov
* [e-mail]
* https://t.me/@sodalium

### Team Code Repos
* https://github.com/Aliventer/lightbeam

## Development Roadmap :nut_and_bolt:

### Overview
* **Total Estimated Duration:** 3 months
* **Full-time equivalent (FTE):** 3
* **Total Costs:** $18,000

### Milestone 1 General arithmetization DSL
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $6,000
* **Estimated delivery date**: July 20th 2023

#### Deliverables and Specifications

##### 0a. Documentation
We will provide both inline documentation of the code and a basic tutorial that explains how a user can express different circuits in terms of the DSL.

##### 0b. Testing Guide
The code will have proper unit-test coverage (>80%) to ensure functionality and robustness. In the guide we will describe how to run these tests.

##### 1. Functionality: Signals
An in-circuit signal abstraction analogues to the circom signals.

##### 2. Functionality: Gates
Polynomials of arbitrary degree used to enforce constraints on signals.

##### 3. Functionality: Constraint system
An abstraction responsible for allocation and management of the signals and the enforcement of constraints. Similar to that of bellperson library.

##### 4. Application
These components together would allow one to express circuits in form of an arithmetic scheme with constraints of arbitrary degree.

### Milestone 2 Protostar compiler
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $6,000
* **Estimated delivery date**: Aug 20th 2023

##### 0a. Documentation
We will provide both inline documentation of the code and a basic tutorial that explains how to run the compiler.

##### 0b. Testing Guide
The code will have proper unit-test coverage (>80%) to ensure functionality and robustness. In the guide we will describe how to run these tests.

##### 1. Application
Produce the protostar circuit and its witness generator from the synthesized DSL circuit and its witness generator as described in the Protostar paper.

### Milestone 3 Grumpkin unloading
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $6,000
* **Estimated delivery date**: Sep 20th 2023

##### 1. Optimization: High degree gates
We will leverage the power of high degree gates inside the compiler in order to speed up the non-native grumpkin arithmetic.

##### 2. Optimization: Circuit cutting
We will cut the circuit into smaller pieces inside the compiler in order to speed up the non-native grumpkin arithmetic.

##### 3. Speedup measurement
We will measure the impact of our optimizations and assemble it into an easily readable form.