search

privacy-scaling-explorations / acceleration-program

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

Proposal: implement liam-eagen-msm gadget in halo2 #28

Open ssjeon-p opened 9 months ago

ssjeon-p commented 9 months ago

General Grant Proposal

Project Overview :page_facing_up:

Overview

Liam Eagen's paper suggested a protocol to prove a point on an elliptic curve is the multi-scalar multiplication of some points. We want to implement this on halo2.

Project Details

Applying the protocol on a zk-SNARK will improve performance compared to directly proving the multiplication. The main idea of reducing proof size is to express the information of points on an element in the function field of the elliptic curve. The performance of this will depend on which proof system we use. To optimize, we want to first study about how zk-proof systems work, especially focusing on halo2 using KZG and IPA. We will summarize proof systems and materials in Liam Eagen's paper, and post it.

Next, we will implement the protocol using halo2, and compare the performance. The protocol can make the information of points or scalars zero-knowledge, or both. Every three versions can be optimized using the techniques described in the paper. The final output will be

Team :busts_in_silhouette:

Team members

Team Website

Team's experience

PSE summer contribution 2023, learning about zkp and halo2. Ph.D major in number theory and algebraic geometry (ongoing)

Team Code Repos

Development Roadmap :nut_and_bolt:

Overview

Milestone 1

Deliverables and Specifications

We want to study carefully about Liam Eagen's paper and some proof systems. We will focus on how the halo2 works and want to explore ways to optimize the ecip protocol if possible. The summary of what we studied will be posted on blog. After milestone 1, we will make concrete milestones such as functions we need or optimizations, for implementing the protocol at milestones 2 and 3.

Milestone 2

Deliverables and Specifications

We will first implement the simplest version of the ecip protocol. This doesn't require a zero-knowledge setting. But, this needs some general functions and algorithms, for example calculating function field elements of an elliptic curve using incremental construction or Mumford representation. We will deliver test functions to check these.

Milestone 3

Deliverables and Specifications

Now, we plan to make the protocol zero knowledge in scalars and points, and both. Each version needs some improvements using techniques in the paper. Plus, using elliptic curves with complex multiplication structure will reduce proof size so we want to explore this. After implementing every version of the protocol, we want to compare how this protocol improves performance compared to simply calculating multi-scalar multiplications on a circuit.

NOOMA-42 commented 9 months ago
  • Estimated delivery date: Jan 11st 2024

Hi @ssjeon-p should milestone 3 Estimated delivery date be Feb 11st 2024?

ssjeon-p commented 9 months ago
  • Estimated delivery date: Jan 11st 2024

Hi @ssjeon-p should milestone 3 Estimated delivery date be Feb 11st 2024?

Yes, that is a typo. Thank you.

DoHoonKim8 commented 8 months ago

Overall seems good to me for now. I think we should develop the concrete plan for implementation in milestone 2, 3 which seems in-depth understanding of ecip protocol should be advanced in milestone 1. I think we can get things moving first.

NOOMA-42 commented 8 months ago

Overall seems good to me for now. I think we should develop the concrete plan for implementation in milestone 2, 3 which seems in-depth understanding of ecip protocol should be advanced in milestone 1. I think we can get things moving first.

@ssjeon-p could you modify proposal according to dohoon's suggestion?

ssjeon-p commented 8 months ago

Overall seems good to me for now. I think we should develop the concrete plan for implementation in milestone 2, 3 which seems in-depth understanding of ecip protocol should be advanced in milestone 1. I think we can get things moving first.

@ssjeon-p could you modify proposal according to dohoon's suggestion?

I modified the proposal at milestone 1.

DoHoonKim8 commented 8 months ago

Seems good! Let's move forward :)