acceleration-program
acceleration-program copied to clipboard
privacy-scaling-explorations
Proposal: Simple (educational) python lookup argument implementation
General Grant Proposal
- Project: simple (educational) python lookup argument implementation https://github.com/privacy-scaling-explorations/acceleration-program/issues/20
Project Overview :page_facing_up:
Overview
simple (educational) python lookup argument implementation
Project Details
- implement plookup, Caulk+, baloo, cq, lasso, LogUp+GKR in python
- provide
Team :busts_in_silhouette:
Team members
- Names of team members
- Yu-Ming Hsu
- Jing-Jie Wang
- Paul Yu
- Harry Liu
- Discord handle
- cornercorn_yuming
- jingjiewang
- nooma42
- harryx1x1
Team's experience
Yu-Ming Hsu
- 2nd author of HeadStart: Efficiently Verifiable and Low-Latency Participatory Randomness Generation at Scale
Jing-Jie Wang
- Author of Securing Fair Loot Box Games: An Efficient Approach to Verifying Loot Box Probability Statement Without Source Code Disclosure
- 3nd author of HeadStart: Efficiently Verifiable and Low-Latency Participatory Randomness Generation at Scale
Paul Yu
- PSE ZK Summer Open Source Contribution Fellow
Team Code Repos
- https://github.com/NOOMA-42/pylookup
Development Roadmap :nut_and_bolt:
Overview
Terminology
- Total Estimated Duration: 2 months
- Full-time equivalent (FTE): 0.5
- Start date expected to be Nov 15th 2023
Milestone 1: cq, plookup, Caulk+, Baloo (Univariate Commitment)
- Estimated Duration: 1 month
- FTE: 0.5
- Estimated delivery date: Jan 15th 2024
- FTE for us: 8+5+12
Milestone 2 multilinear KZG or Hyrax (Multivariate Commitment)
- Estimated Duration: 0.5 month
- FTE: 0.5
- Estimated delivery date: Feb 1st 2024
- FTE for us: 8+5+12
Milestone 3 Lasso, Logup + GKR
- Estimated Duration: 1 month
- FTE: 0.625
- Estimated delivery date: Mar 1st 2024
- FTE for us: 8+5+12
Deliverables and Specifications
0a. Codebase Specification
We aim to implement baseline protocol according to paper and will not implement extra optimization over it. Take cq for example, our code covers FK algorithm for faster amortized kzg proof but won't implement optimized multiscalar multiplication (msm) because we purely rely on pyecc lib unless key components are needed.
We plan to review these 2 codebase and see which multivariavte commitment scheme is easier to implement in Python
- https://github.com/EspressoSystems/hyperplonk
- https://github.com/hyraxZK/fennel
0b. Documentation
We will provide a markdown file explaining the detail implementation of each protocol and util function, for example, why radix 4 fft. If there're already good resources out there. We'll reference it in write up and summarize how we utilize them.
0c. Testing Guide
similar to plonkathon, cover unit test for each components, let's say fft, we unit test fft overall rather than subfunction of it. dummy_test, basic testcase
Additional Information :heavy_plus_sign:
- What work has been done so far? part of cq's util function has been done
Overall seems good, I have a one suggestion and one question:
-
Suggestion is how about putting Baloo implementation to Milestone 1 and make it longer? Since Baloo is based on univariate polynomial commitment scheme, I think it would be good to divide lookup arguments based on univariate/multivariate polynomial commitment schemes into milestone 1, 2 respectively.
-
Question is about whether there is exact plan for implementing underlying polynomial commitment scheme. There are multiple options for multivariate polynomial commitment scheme, for example, multilinear KZG, Brakedown, Hyrax, etc. I think it would be too painful to implement all of them, however I'm not sure whether there already exist Python implementations of them. I think you should choose some of them to implement. It may take some time, so I think milestone 2 would be quite tight. I think it would be better to divide milestone 2's work into separate milestone, for implementing multivariate PCS and writing some articles introducing how they work under the hood.
How do you think?
