privacy-scaling-explorations
Proposal: A SNARK to prove X prime numbers exist below Y
Proposal: A SNARK to prove X prime numbers exist below Y
- Project: https://github.com/privacy-scaling-explorations/acceleration-program/issues/7
Project Overview
Overview
This project aims to produce a SNARK using IVC to prove that X prime numbers exist below a threshold Y. The end result is an implementation of a folding scheme on a circuit to generate a SNARK to prove the previous statement. The project will contain a codebase with documentation and an accompanying blog post.
Project Details
- An overview of the technology stack to be used
The main exploration will be of the different folding schemes applied on top of Circom, Lurk, or Arkworks. A potential exploration of circuits written using Halo2 can also be explored as an extension of this project.
- Documentation of core components, protocols, architecture etc. to be deployed
Circom - circuit development language Nova-Scotia - Circom folding middleware for Nova Sonobe - Multiple folding schemes for Arkworks/Circom circuits Lurk - zkDSL using Nova IVC as a backend Protogalaxy - Folding scheme for arithmetic circuits Protostar - Folding scheme for circuits written with Halo2 API
- PoC/MVP or other relevant prior work or research on the topic
Wikipedia primality testing Miller-Rabin primality test Sieve algorithm in O(n) time
Team :busts_in_silhouette:
Team members
- Logan Norman
- Email: [email protected]
- Telegram: @discretelogno
- Discord: @discretelogno
Team members
- Subhasish Behera
- Email: [email protected]
- Telegram: @subVeera
- Discord: @kenny_007_
Team Website
- Logan's Github
- Subhasish's Github
Team's experience
Logan Norman I am a third year university student studying computer science. Some previous projects I've worked on are
- Three Coloring in Circom
- STARK implementation (in progress)
- LLaMa Operations in FHE
- Contributions to the zk benchmarking library zkalc
- Currently writing a research paper with a professor at my university on ZKP
I have been studying ZKP through various means such as the ZKP MOOC, the Moon Math Manual, attending PSE Learn & Share lectures, reading fundamental papers, and more. I hope to use this project as a learning opportunity.
Subhasish Behera I am an Open Source developer interested in programmable cryptography and zero knowledge. I am currently in my final year of bachelor's majoring in computer science. I have learnt my basics about zero knowledge, its related maths and technologies from courses of https://github.com/ZK-University/ZKU. I am comfortable with writing circuits in Circom. I have studied IVC and the projects implementing it in preparation for this use case.
Development Roadmap :nut_and_bolt:
Overview
- Total Estimated Duration: 1 month
- Total Estimated Working Hours: 72.4 hrs
- Full-time equivalent (FTE): 1.5
- Expected Start Date: 8/1/24
- Expected End Date: 8/24/24
Milestone 1: Implement POC Prime Checking SNARK
- Estimated Duration: 2 weeks
- FTE: 0.5
- Estimated Delivery Date: 8/8/24
To get started on the project, we propose an implementation of a SNARK that checks whether or not a number is prime. This starting point will allow us to continue developing the project in a more familiar manner. An exploration of various tech stacks (Circom, Nova-Scotia, Sonobe, etc.) will be explored and narrowed down in this phase.
Deliverables and Specifications
- A SNARK that, given a number
n, generates a proof stating whether or not the number is prime. - Code documentation.
Milestone 2: Threshold Primality Testing
- Estimated Duration: 1 week
- FTE: 0.75
- Estimated Delivery Date: 8/17/24
After the previous implementation of a SNARK to prove if a number is prime, this milestone aims to extend that work to find all prime numbers under a given threshold n.
Deliverables and Specifications
- A SNARK that, given a number
Y, proves thatXprime numbers exist belowY. - Code documentation.
Milestone 3: Article
- Estimated Duration: 3 days
- FTE: 0.1
- Estimated Delivery Date: 8/20/24
Write an article/tutorial detailing the development process and theoretical knowledge required for the project.
Deliverables and Specifications
- Article
Your Total Estimated Working Hours looks inconsistent with the sum of all milestones. I calculated and got the hours totaling to 82.4 hrs. Would you correct?
@NOOMA-42 Yes, my apologies. I'd also like to add a team member: https://github.com/Subhasish-Behera
