Steve Wang's Post Grant Report

For easier reference and evaluation purpose, **the following document is an exact copy of my grant proposal,** **but annotated with my actual progress so far (as of July 11th) in red**. The official grant end date is August 1st. * **Project:** PSE Chiquito (helping with Leo Lara) ## Project Overview :page_facing_up: ### Overview Chiquito is a high-level DSL that provides syntax sugar and abstraction for constraint building and column placement when writing Halo2 circuits. It allows the user to manipulate an AST that’s compiled to a Chiquito Halo2 backend, which can be integrated into any Halo2 circuit. ### Project Details **The following is a holistic list of project ideas, while I only plan to focus on two or three of them.** **In reality, I worked on 6 out of 7 project idea categories in the original grant proposal. My primary focuses are on: Chiquito core features, product research for other zkDSLs, and Python front end for Chiquito.** #### Technology Stack * Rust (for circuit library and additional features for the compiler and backend) * Technical writing in Markdown (for documentation, product research, and integration research) #### Core Components to be Deployed ##### Chiquito Library * Additional circuit examples library written in Rust. Examples can include hash functions or primitives such as the xor function. Inspiration will come from existing Halo2 and Circom libraries. Libraries will not only demonstrate the versatility and syntax simplicity of Chiquito but also provide hands on examples for developers to use. * MiMC7 example: * https://github.com/privacy-scaling-explorations/chiquito/pull/11 * Annotated Fibonacci and MiMC7 examples: * https://github.com/privacy-scaling-explorations/chiquito/commits/main/examples/fibonacci.rs * Develop gadgets for the standard library, such as the IsZero gadget. Again, inspiration will come from existing Halo2 and Circom libraries. * Developed "less than" gadget: * https://github.com/privacy-scaling-explorations/chiquito/pull/29 ##### Chiquito Core Features * Implement additional constraint builder, compiler, and Halo2 backend features in Rust. * Fixed signal: * https://github.com/privacy-scaling-explorations/chiquito/pull/53 * https://github.com/privacy-scaling-explorations/chiquito/pull/54 * https://github.com/privacy-scaling-explorations/chiquito/pull/55 * Shared signal: * https://github.com/privacy-scaling-explorations/chiquito/pull/49 * https://github.com/privacy-scaling-explorations/chiquito/pull/50 * https://github.com/privacy-scaling-explorations/chiquito/pull/51 * Lookup table abstraction: * https://github.com/privacy-scaling-explorations/chiquito/pull/47 * Public signal: * https://github.com/privacy-scaling-explorations/chiquito/pull/42 * Typed constraint builder: * https://github.com/privacy-scaling-explorations/chiquito/pull/35 * Additional backend for Plaf: * https://github.com/privacy-scaling-explorations/chiquito/pull/34 * Write unit tests for existing features. * Unit test for constraint builder: * https://github.com/privacy-scaling-explorations/chiquito/pull/19 ##### Potential Integration with zkEVM * Rewrite existing circuit components of the zkEVM * Not started * Conduct performance benchmarking using existing Halo2 code v.s. Chiquito adaptation * Benchmarked bytecode circuit witness assignment in PSE zkEVM vs Chiquito and found Chiquito to be 30x faster: * https://github.com/privacy-scaling-explorations/chiquito/issues/36 ##### Product Research * Compare the technical implementation of fellow zkDSLs, such as Aztec Noir and Zokrates. Publish the research as blog posts. * Researched 10 products in conjunction with PSE's zkDSL working group: * https://mud-jaguar-906.notion.site/cc5b5071240143d1805aad8bbc6cd583?v=aecbd25df3db44a3912112c48672be63&pvs=4 * Also in conjunction with the zkDSL working group, summarized the technical route of these products: * https://mud-jaguar-906.notion.site/zkDSL-Technical-Routes-1027097ca441422a816034cca75376d9?pvs=4 * Not published as blog post yet ##### Community and Adoption * Partner with AntAlpha Lab's PLONK-themed zk co-learning camp to teach a Chiquito course to circuit developers * Not started ##### Miscellaneous * Json standard for different frontends, such as Python, which can be written by other developers * Research done. To be implemented this week as a part of Python frontend of Chiquito. ##### Leo's Visions (probably not me to implement) * Backend for additional proof system * Not started, but Leo mentioned that there might be such work for the CCS proof system in the future. * Cmd tool and npm package for developers * Not started * Python frontend * Finished 2/3 of the first pass and successfully tested existing progress on an example. Not reviewed yet. ##### Additional Work not Mentioned in the Original Proposal * README and API docs * https://github.com/privacy-scaling-explorations/chiquito/pull/18 * https://github.com/privacy-scaling-explorations/chiquito/pull/13 * https://github.com/privacy-scaling-explorations/chiquito/pull/12 * CI workflows * https://github.com/privacy-scaling-explorations/chiquito/pull/30 * https://github.com/privacy-scaling-explorations/chiquito/pull/15 * Better debug messages * https://github.com/privacy-scaling-explorations/chiquito/pull/26 #### Prior Work (by Leo) The current implementation includes: * A DSL in Rust * A backend in Halo2 * Composability with Halo2 circuits * A working prototype that passes zkEVM bytecode circuit tests ## Team :busts_in_silhouette: ### Team members Leo Lara * Email: leo@leolara.me * TG: @leolara Steve Wang * Email: qian.wang.wg24@wharton.upenn.edu * TG: @SteveIsEmployed ### Team Website https://github.com/privacy-scaling-explorations/chiquito ### Team's experience Leo Lara * 20 years experience in software engineering, experience in embedded and distributed systems * Graduated 1st class Comp Sci, at University of Bath * Worked at ARM, on server software * Co-founder CTO Uniplaces * 2021 start Blockchain journey, Gitcoin Kernel -> EthLisbon hackathon -> Ethereum Protocol Fellowship grantee (prysm) -> zkEVM < PSE < Ethereum Foundation * Working on zkEVM of EF Steve Wang * Current MBA/Computer Science dual degree student at University of Pennsylvania * Worked on Chiquito library, additional compiler features, and documentation while at AntAlpha Chiang Mai Hackerhouse * Repo link: https://github.com/privacy-scaling-explorations/chiquito * Won Aptos Official Grant for a DAO management tool. Was frontend and smart contract developer of the team. Smart contract written in Move, a Rust-based lanaguage. * Grant link: https://dorahacks.io/buidl/4334 * Repo (fork) link: https://github.com/qwang98/Airdropper-Based-On-Github * Technical research report about ERC4337: * Link: https://mirror.xyz/0x7333aB7AE068Ef92fb77A2bcab32FA273c45185c/cF55-mUlStUDn0aqrhEAfNRRY8sLVM97sJgLNor1BUw * Other personal Move and Solidity projects (mostly frontend and smart contract): * Github page: https://github.com/qwang98?tab=repositories * 3 years experience in data science using R and SQL at a consulting firm in the US * Math and Economics double major and Computer Science minor at Macalester College, full tuition scholarship and graduated rank 1 in both majors ### Team Code Repos * https://github.com/privacy-scaling-explorations/chiquito ## Development Roadmap :nut_and_bolt: This section should break out the development roadmap into a number of milestones. Since the milestones will appear in the grant contract, it helps to describe the functionality we should expect, plus how we can check that such functionality exists. Below we provide an **example roadmap**. We recommend that the scope of the work can fit within a 3 month period and that teams structure their roadmap as 2 weeks = 1 milestone. For each milestone: * Please be sure to include a specification of the software. The level of detail must be enough so that we are able to verify that the software meets the specification. * Please include total amount of funding requested per milestone. * Please note that we require documentation (e.g. tutorials, API specifications, architecture details) in each milestone. This ensures that the code can be widely used by the community. * Please provide a test suite, comprising unit and integration tests, along with a guide on how to run these. * Please indicate the milestone duration, as well as number of Full-Time Employees working on each milestone, and include the number of days along with their cost per day. ### Overview * **Total Estimated Duration:** Duration of the whole project * **Full-time equivalent (FTE):** Workload of an employed person ([see](https://en.wikipedia.org/wiki/Full-time_equivalent)) * **Total Costs:** Amount of Payment for the whole project. ### Milestone 1 * **Estimated Duration:** 1 month * **FTE:** 1 * **Costs:** $62.5/hr, i.e. $10k for the milestone * **Estimated delivery date**: May 31st, 2023 **WORK ON TWO OF THE FOLLOWING** | Number | Deliverable | Specification | | ------------- | ------------- | ------------- | | 0a. | README | Provide a README file explaining the high level design principles, architecture, and a getting started boiler plate code suite for devs. | | 0b. | API docs | Provide a full API documentation for DSL functions exposed to devs, including an example file using these APIs | | 1. | Research | Compare the technical architecture and feature difference of fellow zkDSLs such as Aztec Noir and Zokrates. Will document our understanding in Notion. | | 2. | Circuit library | Write 1-2 more circuit examples in Chiquito, adapted from base Halo2 library or Circom library | | 3. | Chiquito features | Work on implementing TODOs in the compiler and backend at Leo's discretion | | 4. | Learning | Understand the zkEVM bytecode example in both base Halo2 and Chiquito. A stretch goal is to understand the testing requirements and performance specs as well. | ### Milestone 2 * **Estimated Duration:** 1 month * **FTE:** 1 * **Costs:** $62.5/hr, i.e. $10k for the milestone * **Estimated delivery date**: June 30th, 2023 **WORK ON TWO OF THE FOLLOWING** | Number | Deliverable | Specification | | ------------- | ------------- | ------------- | | 1. | Research | Keep researching zkDSLs such as Aztec Noir and Zokrates. Go into the technical details, such as PLONK table construction, circuit performance, and computation complexity of large circuits. Research will be documented in Notion | | 2. | Circuit library | Write 1-2 more circuit examples in Chiquito, adapted from base Halo2 library or Circom library | | 3. | Chiquito features | Work on implementing TODOs in the compiler and backend at Leo's discretion | | 4. | Potential zkEVM integration | Adapt one more Halo2 circuit in the zkEVM to Chiquito | | 5. | Learning | Analyze more zkEVM circuits. A stretch goal is to dive into the source code of base Halo2. | ### Milestone 3 * **Estimated Duration:** 1 month * **FTE:** 1 * **Costs:** $62.5/hr, i.e. $10k for the milestone * **Estimated delivery date**: July 31st, 2023 **WORK ON TWO OF THE FOLLOWING** | Number | Deliverable | Specification | | ------------- | ------------- | ------------- | | 1. | Research | Publish zkDSL research piece as a blog post. | | 2. | Circuit library | Write 1-2 more circuit examples in Chiquito, adapted from base Halo2 library or Circom library | | 3. | Chiquito features | Work on implementing TODOs in the compiler and backend at Leo's discretion | | 4. | Potential zkEVM integration | Adapt one more Halo2 circuit in the zkEVM to Chiquito | | 5. | Learning | Analyze more zkEVM circuits. A stretch goal is to dive into the source code of base Halo2. | ## Additional Information :heavy_plus_sign: The following are general information about Chiquito ### Design Principles **Abstraction**. As circuit complexity increases, abstraction is inevitable. By abstracting constraint building and column placement, Chiquito improves the readability and learnability of Halo2 circuits, which can not only standardize and simplify the code base for complex projects such as the zkEVM, but also onboard more circuit developers. **Composability**. Chiquito circuits are fully composable with Halo2 circuits, which allows developers to write any part or the entirety of a circuit in Chiquito and integrate with other Halo2 circuits. **Modularity**. The AST and IR representations of a circuit allow Chiquito to integrate any frontend that can compile into the AST data structure and any backend that can compile from the IR data structure. For example, we can have a Python frontend that compiles to Chiquito AST/IR, which compiles to a Sangria backend. Modularity allows for future extensions. **User Experience**. Chiquito simplifies and optimizes user experience. For example, annotations for constraints are automatically generated for debugging messages. ### Architecture There are two major architectural differences between Chiquito and Halo2: - Chiquito circuit is composed of “steps”. Each step defines the constraints among witnesses, fixed columns, and lookup tables, and can be composed of one or multiple rows in a PLONKish table. That’s why steps are also called “super rows”. We made this design choice to allow for more complex constraints, which sometimes require allocating multiple Halo2 rows. - Chiquito DSL is based on “signals” rather than columns in order to abstract away column placements. One signal can be placed in different columns across different steps, all handled by Chiquito’s compiler. Chiquito circuit has the following architecture - Circuit (with optional input from Halo2) - Forward signals (signals with constraints across different steps) - Fixed columns - Step types - Internal signals (signals with constraints only within one step) - Internal constraints (constraints for internal signals only) - Transition constraints (constraints involving forward signals) - Witness generation function for one step type instance - Trace (global circuit witness generation) - Adds instances of step types