# General Grant Proposal

* **Project:** Non-native opening with GKR and MSM

## Project Overview :page_facing_up:

### Overview

Implement non-native opening of a multilinear polynomial and MSM using GKR. Investigating if it is possible to create a recursive proof system using those primitives.

### Short Rationale

Using GKR protocol accelerates dramatically many computations, including MSM. MSM is a crucial component in many proof system. Hence, it one would reasonably be curious whether a GKR-based proof sysem would show good performance. Possible applications include batch-verification of digital signatures.

### Project Details
<!-- Provide as much detail as possible about the project's expected final state.

* An overview of the technology stack to be used
* Documentation of core components, protocols, architecture etc. to be deployed
* PoC/MVP or other relevant prior work or research on the topic -->
* The scheme will be implemented in rust, potentially taking advantage of already implemented features.
* The scheme is largely based on morgana's GKR-MSM library.
<!-- * , such as [fft](https://github.com/privacy-scaling-explorations/halo2/blob/360020745ee68447af82ec4427ba1434d9b3d23f/halo2_backend/src/poly/domain.rs#L343). -->
* The scheme consists of
* A gadget for non-native opening.
* A gadget for non-native MSM.
* Possibly a recursive proof system on on the basis of the non-native machinery.
* Documentation will be written.

## Team :busts_in_silhouette:

### Team members
* Yulia Kotelnikova
* Email: [e-mail]
* Telegram: [@yuliakote](https://t.me/yuliakote)

### Team Website
* [github](https://github.com/yuliakot)

### Team's experience
The team previously participated in Axiom's Open Source Program, which resulted in the following [gem](https://github.com/yuliakot/multiplication_in_big_field).

### Team Code Repos
* https://github.com/morgana-proofs/GKR-MSM/tree/non_native_opening_fragmented

## Development Roadmap :nut_and_bolt:

----

1. Create some tools to handle polynomials over the non-native field efficiently.
2. Implement the non-native opening protocol: the protocol that confirms the value of a polynomial at a given point.
3. Implement the non-native MSM-protocol.
4. Assess whether it is appropriate and possible to write a recursive verifier with those primitives.
5. (Optional) Write the recursive verifier.

----

<!-- This section should break out the development roadmap into a number of milestones. Since the milestones will appear in the grant contract, it helps to describe the functionality we should expect, plus how we can check that such functionality exists.

Below we provide an **example roadmap**. We recommend that the scope of the work can fit within a 3 month period and that teams structure their roadmap as 2 weeks = 1 milestone.
-->
<!-- For each milestone:
* Please be sure to include a specification of the software. The level of detail must be enough so that we are able to verify that the software meets the specification.
* Please include total amount of funding requested per milestone.
* Please note that we require documentation (e.g. tutorials, API specifications, architecture details) in each milestone. This ensures that the code can be widely used by the community.
* Please provide a test suite, comprising unit and integration tests, along with a guide on how to run these.
* Please indicate the milestone duration, as well as number of Full-Time Employees working on each milestone, and include the number of days along with their cost per day. -->

### Overview
* **Total Estimated Duration:** 3 months
* **Full-time equivalent (FTE):** 1
* **Total Costs:** Amount of Payment for the whole project.

### Milestone 1: Non-native opening protocol.
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $10,000
* **Estimated delivery date**: November 1st 2024

#### Deliverables and Specifications

##### 0a. Code
##### 0b. Documentation

We will provide both inline documentation of the code and a write-up.

##### 0c. Testing Guide

The code will have 80% unit-test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests.

##### 1. Functionality:

The protocol accepts as input a multilinear polynomial over a finite field. The protocol produces polynomial(s) over a different (native) field that are limbs of the original polynomial. Then the protocol produces a circuit as well as claims about values of the native polynomial that are equivalent to the original evaluation claim. Then a GKR protocol is used to evaluate the circuit and prove those claims.
##### Application

The core part of the project.

### Milestone 2: Non-native MSM.
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $10,000
* **Estimated delivery date**: December 1st 2024
* #### Deliverables and Specifications

##### 0a. Code
##### 0b. Documentation

We will provide both inline documentation of the code and a write-up.

##### 0c. Testing Guide

The code will have 80% unit-test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests.

##### 1. Functionality:

The protocol accepts two arrays of non-native field elements as inputs. The protocol then produces polynomials over the native field, corresponding to the native field elements, that are thought of as limbs of the original inputs. The protocol produces the MSM circuit (or multiple circuits) and uses the GKR protocol to prove the circuit.

##### Application

The core part of the project.

### Milestone 3: Recursive verifier.
* **Estimated Duration:** 1 month
* **FTE:** 1
* **Costs:** $9,000
* **Estimated delivery date**: December 31st 2024

##### 0a. Write-up

The team will provide a write-up describing the potential design of a recursive verifier using the non-native gadgets described in the previous sections.

##### 0b. Prototype code and tests

Possibly, a prototype will be provided. The code will have 80% unit-test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests.

##### 1. Functionality:

##### Application

The core part of the project.

<!--
## Additional Information :heavy_plus_sign:
Any additional information that you think is relevant to this application that hasn't already been included.

Possible additional information to include:
* What work has been done so far?
-->