# General Grant Proposal

* **Project:** Anonimity in MACI

## Project Overview :page_facing_up:

### Overview

In the current MACI protocol, when a voter's public key is changed, the coordinator knows that the change has occurred. From there, the coordinator knows how the voter voted (although the public key change helped the voter to deceive the blackmailer).

As we do not want the coordinator to know who is the "owner" of the new public key, we need to disable the coordinator from seeing the link between the old and new public key of the voter. To achieve this, the voter must prove (he needs to make ZK proof) that he owns the private key for the old public key and be able to create a new one based on that. For this purpose, we will need to create a set containing all deactivated public keys and their encrypted states. This is where we have to be careful. We must ensure that the voter can create precisely one new key based on the previous public key. For this reason, we will need nullifiers and the set where we store them.

In conclusion, we will need two new sets. Let's mark the first with D and the second with N. We must expand the set of states. There should be a field in that set that says whether the voter's public key is active or inactive.

Also, we will need two new message types. The first type of message should be to deactivate the old public key. After deactivation, the coordinator adds the old public key with its encrypted state (using ElGamal encryption) to set D. Second type of message is that the voter creates a new public key, proving that he is the owner of the old deactivated one.

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

* An overview of the technology stack to be used

Technology stack to be used includes:
1. TypeScript for implementing message handling.
2. Solidity for implementing smart contract changes.
3. Circom for implementing additional circuits.
4. ZK proof that the user owns the private key for the old public keys and is able to create a new one based on that and exactly one new; ElGamal encryption-decryption and rerandomization.

* Documentation of core components, protocols, architecture etc. to be deployed

We will add two new sets. Set D is a set of all deactivated keys and set N is a set of all nullifiers. We must expand the set of states in the current protocol. There should be a field in that set that flags whether the voter's public key is active or inactive. We will add two new types of messages: to deactivate the old public key and the second one

Changes will be made to the existing MACI protocol by introducing two new commands for key reissuing and devalidation. Additionally, smart contract will be modifier to enable processing of new commands, as well as new Circom circuits to support the verification of the commands. New commands will also require implementation of hash-to-curve function for baby JubJub curve.

* PoC/MVP or other relevant prior work or research on the topic

Research paper - [link](https://0x3327.github.io/research/documents/research/posts/ERFC-375.hugo.html)

An article - [link](https://3327.io/anonymity-in-maci/)

## Team :busts_in_silhouette:

### Team members

Name: Aleksandar Veljković
Email: [e-mail]
Telegram handle: @aleksandarveljkovic

Name: Marija Mikić
Email: [e-mail]
Telegram handle:@marijamikic

Name: Uroš Kukić
Email: [e-mail]
Telegram handle: @kukic_uros

### Team Website
* [3327.io](https://3327.io/)

### Team's experience

**Aleksandar Veljković**
Working in software engineering for more than 7 years, in Web 3.0 domain as researcher and engineer for 4 years. Currently working as Senior Researcher in 3337 team at MVP Workshop in domain of cryptography, decentralization and zero-knowledge. Teaching assistant at University of Belgrade, Faculty of Mathematics.
Linkedin - [link]( https://www.linkedin.com/in/aleksandar-veljkovi%C4%87-9a617456/)

**Marija Mikić**
Senior Researcher in team 3337 at MVP Workshop company (domain: cryptography and zero knowledge; for 2 years); Head of the Department of Differential equation at Faculty of Mathematics, University of Belgrade; Assistant professor at Department of Differential equations, at the same faculty; PhD thesis are in the field of Theoretical mathematics; Detailed biography you can find [here](http://www.matf.bg.ac.rs/p/files/1668424827-31-CVMikic2022.pdf)
LinkedIn - [link](https://rs.linkedin.com/in/marija-miki%C4%87-878842a2)

**Uroš Kukić**
Backend engineer with 5 years of experience in developing smart contracts and distributed systems; BSc of Computer Science at the School of Electrical Engineering, University of Belgrade; Graduate thesis was on implementation of blind signatures and stealth addresses within smart contracts;
LinkedIn - [link](https://www.linkedin.com/in/kukic-uros/)

### Team Code Repos

- https://0x3327.github.io/research/documents/research/
- https://github.com/MarijaMikic/
- https://github.com/aleksandar-veljkovic
- https://github.com/Kuki145

## Development Roadmap :nut_and_bolt:

### Overview
* **Total Estimated Duration:** 4 months
* **Full-time equivalent (FTE):** 3 (Marija Mikić , Aleksandar Veljković, Uroš Kukić)
* **Total Costs:** $104,780

### Milestone 1
- **Estimated Duration:** 1 month
FTE: 3
Total hours: 476
- **Costs:** $29,512
- **Estimated delivery date:** April 27th 2023

| Number | Deliverable | Specification |
| ------------- | ------------- | ------------- |
| 0 | General Documentation | Documentation of the overall process on how to achieve the desired goals for obtaining anonymity in MACI. The documentation will cover detailed description of the protocol changes to the current MACI protocol. (Marija Mikic 16h; Aleksandar Veljkovic 16h)|
| 1. | Functionality: El Gamal encryption | Implementation of Circom circuit templates for verifying El Gamal encryption and decryption on elliptic curve. (Marija Mikic 80h; Aleksandar Veljkovic 40h) |
| 2. | Functionality: re-randomization | Implementation of Circom circuit templates for verifying values generated using re-randomization. (Marija Mikic 40h; Aleksandar Veljkovic 24h) |
| 3. | Functionality: Generate a set of deactivated keys | Implementation of Merkle tree Circom circuit templates for membership proofs in set of deactivated keys. (Aleksandar Veljkovic 40h; Marija Mikic 20h) |
| 4. | Testing | Test suites covering all software components implemented within this milestone. In addition, a guide on how to run these.(Uros Kukic 100h; Marija Mikic, Aleksandar Veljkovic 20h) |
| 5. | Documentation | Document everything that is developed under the 1st, 2nd and 3rd deliverables (El Gamal encryption, Re-randomization and generation of set of deactivated keys). (Uros Kukic 40h; Marija Mikic 20h, Aleksandar Veljkovic 20h)|
| Total hours estimate | | Uros Kukic 140h; Marija Mikic 176h, Aleksandar Veljkovic 160h|
| Total | | 476h|

### Milestone 2

- **Estimated Duration:** 1.5 month
FTE: 3
Total hours: 710
- **Costs**: $44,020
- **Estimated delivery date:** June 9th 2023

| Number | Deliverable | Specification |
| ------------- | ------------- | ------------- |
| 1. | Functionality: ZK proof of knowledge of the user’s private key| Implementartion of Circom circuit templates for verifying proof of knowledge of the private key. (Marija Mikic 40h; Aleksandar Veljkovic 16h) |
| 2. | Functionality: ZK proof that user proves that he has deactivated key | Implementation of Circom circuit templates for verifying proof of key deactivation. (Marija Mikic 40h; Aleksandar Veljkovic 40h) |
| 3. | Functionality: Key deactivation | Implementation of changes to the protocol to enable user to deactivate the public key. (Aleksandar Veljkovic 120h; Uros Kukic 120h) |
| 4. | Onboarding into MACI codebase | Familiarizing with MACI code repositories. (Aleksandar Veljkovic 10h; Marija Mikic 10h, Uros Kukic 10h) |
| 5. | Functionality: Hash to curve | Implememntation of hash to curve function for mapping message hashes to curve points. (Aleksandar Veljkovic 40h; Marija Mikic 20h) |
| 6. | Testing | Test suites covering all software components implemented within this milestone. In addition, a guide on how to run these. (Uros Kukic 100h; Aleksandar Veljkovic 24h) |
| 7. | Documentation | Document everything that is developed under the 1st, 2nd, 3rd and 4th deliverable. (Uros Kukic 40h; Marija Mikic 20h; Aleksandar Veljkovic 20h) |
| Total hours estimate | | Uros Kukic 270h; Marija Mikic 150h; Aleksandar Veljkovic 290h.|
| Total | | 710h|

### Milestone 3

- **Estimated Duration:** 1.5 month
FTE: 3
Total hours: 504
- **Costs:** $ 31,248
- **Estimated delivery date:** July 21st 2023

| Number | Deliverable | Specification |
| ------------- | ------------- | ------------- |
| 1. | Functionality: Generating new keys following deactivated keys| Implement of logic for generation new public keys based on the previously deactivated ones. (Aleksandar Veljkovic 40h; Uros Kukic 80h; Marija Mikic 16h) |
| 2. | Functionality: Handling nullifiers | Implementation of logic for handling nullifiers. (Aleksandar Veljkovic 40h, Uros Kukic 80h; Marija Mikic 16h)|
| 3. | Tests| Test suites covering all software components implemented within this milestone. In addition, a guide on how to run these. (Aleksandar Veljkovic 24h; Uros Kukic 80h)|
| 4. | Documentation | Document everything that is developed under the 1st and 2nd deliverable. (Marija Mikic 32h; Aleksandar Veljkovic 16h)|
| 5. | API specification and tutorials | User-centric documentation and tutorials with API specification and recommendations for proper usage of the modified protocol. (Aleksandar Veljkovic 16h; Uros Kukic 32h)|
| 6. | Blog post | Blog post that explains work done under this project. (Marija Mikic 24h; Aleksandar Veljkovic 8h) |
| Total hours estimate | | Uros Kukic: 272h; Marija Mikic: 88h; Aleksandar Veljkovic 144h)|
| Total | | 504h|

## Additional Information :heavy_plus_sign:
So far we have done research on this topic, written an article, and created a portion of the code for El Gamal encryption, decryption, and re-randomization. Still, changes to the existing code need to be made.