Proposal: A SNARK to prove X prime numbers exist below Y
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 👥
Team members
Team members
Team Website
Team's experience
Logan Norman
I am a third year university student studying computer science. Some previous projects I've worked on are
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 🔩
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 that X prime numbers exist below Y.
- 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
Proposal: A SNARK to prove X prime numbers exist below Y
Project Overview
Overview
This project aims to produce a SNARK using IVC to prove that
Xprime numbers exist below a thresholdY. 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
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.
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
Wikipedia primality testing
Miller-Rabin primality test
Sieve algorithm in O(n) time
Team 👥
Team members
Team members
Team Website
Team's experience
Logan Norman
I am a third year university student studying computer science. Some previous projects I've worked on are
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 🔩
Overview
Milestone 1: Implement POC Prime Checking SNARK
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
n, generates a proof stating whether or not the number is prime.Milestone 2: Threshold Primality Testing
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
Y, proves thatXprime numbers exist belowY.Milestone 3: Article
Write an article/tutorial detailing the development process and theoretical knowledge required for the project.
Deliverables and Specifications