Proposal: A SNARK to prove X prime numbers exist below Y

[lognorman20]

Proposal: A SNARK to prove X prime numbers exist below Y

• Project: A SNARK to prove X prime numbers exist below Y #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 👥

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 🔩

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

1. A SNARK that, given a number n, generates a proof stating whether or not the number is prime.
2. 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

1. A SNARK that, given a number Y, proves that X prime numbers exist below Y.
2. 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

1. Article

[NOOMA-42]

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?

[lognorman20]

@NOOMA-42 Yes, my apologies. I'd also like to add a team member: https://github.com/Subhasish-Behera

[NOOMA-42]

Hi @lognorman20 @DoHoonKim8 will review this proposal

[lognorman20]

@NOOMA-42 got it, thanks for your assistance!

[lognorman20]

how does one join you guys

Please DM me on Discord to discuss @Kim8584