search

privacy-scaling-explorations / acceleration-program

Accelerate Early Stage Programmable Cryptography Talents
100 stars 7 forks source link

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

Open lognorman20 opened 6 months ago

lognorman20 commented 6 months ago

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

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 :busts_in_silhouette:

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 :nut_and_bolt:

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

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

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

Write an article/tutorial detailing the development process and theoretical knowledge required for the project.

Deliverables and Specifications

1) Article

NOOMA-42 commented 6 months ago

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 commented 6 months ago

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

NOOMA-42 commented 6 months ago

Hi @lognorman20 @DoHoonKim8 will review this proposal

lognorman20 commented 6 months ago

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

Kim8584 commented 6 months ago

how does one join you guys

lognorman20 commented 6 months ago

how does one join you guys

Please DM me on Discord to discuss @Kim8584