about
blog
subscribe

Apply for PARC Squad: Proof Aggregation, Recursion, and Composition

by Ying Tong Lai and Nalin Bhardwaj

Modern zero-knowledge applications such as the zkEVM or zkML involve increasingly large and complex relations. Most practical implementations have made use of composition of proof systems to achieve performance gains and navigate prover-verifier tradeoffs. 0xPARC's PARC Squad is a full-stack effort to advance recursion, composability and aggregation capabilities of modern proof systems and bring more interesting applications using these to production. Our efforts can loosely be categorised as:

  1. Understand: Taxonomies, benchmarks, and security analyses for existing methods;
  2. Innovate: New strategies for proof composition;
  3. Build: Developer tooling and APIs for modular proof systems;
  4. Ship: Applications uniquely enabled by proof composition, aggregation, and recursion.

In this post, we'll describe the goals and scope of PARC Squad, as well as how to get involved. Grant funding is available for PARC Squad applicants; to apply to the PARC Squad Session 1 (December '22 - January '23), submit a project proposal here by November 18th.

Layers of PARC, the feedback loops between them and some suggested projects

How to get involved

PARC Squad aims to find and connect teams that are working either part-time or full-time on projects related to proof aggregation, recursion, and composition.

This working group will run in at least two sessions. The first session will run from December 2022 to January 2023 (apply here by November 18th). The second session will run from late February through March 2023.

Contributors to PARC Squad may include:

  • proof system core library engineers, who are interested in building more ergonomic tools or APIs for proof aggregation, recursion, and composition;
  • circuit engineers, who are building circuits or circuit primitives implementing PARC;
  • application developers, whose use cases directly motivate PARC infrastructure;
  • and researchers, who are building new proof systems or composition strategies.

In the first half of this post (PARC Squad: Scope), we'll share some notes about how we are modelling the PARC Squad project scope, and suggest different ideas we're thinking about. These are not projects set in stone, but rather are intended to serve as weak suggestions for what would advance the space most.

In the second half of this post (PARC Squad: Structure), we'll share more details about how we're structuring the PARC Squad, grants, and what participants can expect to get out of the program.

PARC Squad: Scope

Understand

We categorise projects aiming to advance our understanding of proof compositions as "Understand" projects. A systematic overview of existing protocols and implementations would inform us of common strategies, as well as comparative performance and security properties. Further metrics of interest may emerge as we begin to classify these strategies. Ideas and open questions in this category include:

Taxonomy of composition strategies

A variety of composition strategies have emerged for constructing “hybrid” proof systems that combine components across the stack. Identifying common characteristics, models, and assumptions across these constructions would help us to categorise them. Similar efforts that we draw inspiration from include: Complexity Zoo, and the "Concrete Schemes" section of ZKProof Standards.

Benchmarking

Primitives such as boolean functions, range proofs, big-integer arithmetic, and matrix multiplication form the building blocks in many proof relations of interest. Many of these have purpose-built proof systems that exploit the specific problem structure; however, some are still commonly re-implemented across general-purpose proof systems. We would benefit from a benchmark suite which allows us to semi-automatically measure the performance of different circuits / proof systems under consistent conditions.

We think we can look at benchmarking in the ML/AI space as inspiration for this sub-category. In particular, it would be interesting to figure out what the equivalent of Imagenet benchmarks for PARC look like, or perhaps build out an equivalent of MLPerf for modern ZK proving systems.

Security analysis

As we compose proof systems which use different assumptions, security models, and cryptographic instantiations, how will security properties compose, and under which composition strategies? Which steps in proof composition present the greatest challenge to security analysis?

Innovate

We are just beginning to see compositional proof systems in production. This introduces new vectors of optimisation and motivates new constructions. Projects in this category aim to explore exotic compositions and clever arrangements of the modular stack of proving systems. Here we will summarise some cool ideas. The zkresear.ch post on this topic goes further in-depth, listing several representative constructions as a starting point.

Better "inner proofs" for recursive verification

Recursive verification reduces prover space complexity by breaking down a large statement into smaller subprotocols, which can be proven in parallel and then composed using proof-carrying data. Expensive computations such as non-native field arithmetic or bitwise operations can also be performed in embedded sub-protocols, which are cheaper to verify in-circuit than to prove. Examples include:

Most proof systems are designed to be "end-to-end" efficient: i.e., to have both a performant prover and verifier. By composing fast-prover “inner” proofs with fast-verifier “outer” proofs, we achieve both prover space-efficiency and verifier time-efficiency. This highlights an interesting optimisation vector: to design better “inner” proofs, whose provers can be efficient and non-succinct, but whose verifiers can be efficiently encoded?

Standardised "outer" protocols

Certain protocols can be applied generically to "inner" proof systems, with the effect of "rephrasing" them in terms of a common API. These are of theoretical interest, since they reveal deeper similarities in structure, and possibly simplify security analysis. They can also be of practical interest, enabling efficient and interoperable instantiations. Examples include:

  • MPC-in-the-head [GGAK21]; and
  • sumcheck argument [BCS21].

How do we discover new "outer" protocols? Can we quantify the tradeoff between interoperability and efficiency?

Linkable commit-and-prove SNARKs

Large statements can be broken down into smaller, structured problem classes and proven in different special-purpose SNARKs. These heterogeneous proofs can then be linked to recover a proof of the overall statement. Examples include:

A comprehensive benchmarking of primitive circuits would greatly inform linking strategies for this class of compositional SNARKs.

Build

The arkworks libraries are informed by a highly modular design, allowing users to mix-and-match components like polynomial commitment schemes and cryptographic primitives. We would like to extend this philosophy to provide an API for composition and interoperability between proof systems. Understanding the available composition strategies and compatible proof systems would inform the scope of this API, and pave way for potential future conversations on standards, shared tooling and infrastructure, benchmarks, and more within the larger applied ZK ecosystem. How will ZK circuits be written in 10 years? What is the level of abstraction developers interact at? What can we hide away in the "compilers" of circuit languages?

Projects here may include:

  • recursive verification circuits or aggregation circuits: e.g., Polygon Hermez’s STARK verifier inside of a SNARK; ZCash’s IPA aggregation circuit; MAZE;
  • circuit primitives for recursive circuits: e.g., non-native field arithmetic in Halo2 arithmetization (in the interest of recursively verifying other proofs);
  • and compilers from common frontends to different backends: e.g., Nova Scotia, zkInterface, Lurk Language.

Ship

PARC uniquely enables new properties for application developers: composability and compression. As we develop the technology further, we would like to explore novel applications of this tech. We have some hunches for what these applications might look like, but no one knows for sure. Here are some ideas that might inspire you:

If any of these categories or general direction interests you, reach out on the form!

PARC Squad: Structure

Squad Expectations

We believe that PARC is a major ecosystem priority, and that PARC projects are likely to require substantial time commitment. We are looking to build a relatively small but committed cohort of Squad members who are spending substantial time contributing to projects in the PARC scope.

Squad members are responsible for:

  • Scoping a set of project deliverables: what you’ll accomplish in each of the two sessions of the Squad. See the projects section above for what deliverables ought to look like.
  • Shipping your project by the end of PARC Squad.
  • Attending a biweekly Squad meeting (time TBD). We use these biweekly meetings as regular checkins for participants—each team is usually expected to give a 3-5 minute presentation on their progress over the last two weeks, with a handful of informal slides.
  • Squad members are highly encouraged to try to attend at least one of the in-person activations we will be running in the next few months (see below). In the past, these hack weeks, retreats, and mini-conferences have often been crucial for uncovering new project directions and sharing methods.
  • Squad members are highly encouraged to give at least one longer virtual presentation, to do a deep dive into their project. We’ll schedule these in the next few weeks.
  • Squad members are highly encouraged to take part in asynchronous discussion on the communication channels mentioned below. In particular, we’re hoping to encourage long-form dialogue, and to push people to both build and think in the open.

Guidelines for Deliverables

Work produced within PARC Squad is expected to be made not just open-source but also accessible (i.e. appropriate writeups/documentation and interfaces) for outside consumption.

We encourage projects to orient around the following deliverables:

  • A technical writeup, well-written README, and/or explainer post.
  • An open-source repository.
  • (For RAC implementation projects) A package/crate, language feature, or other artifact that is consumable by developers other than yourself. This means that you should provide appropriate documentation and that your artifact should live in a relatively generic, standalone library, rather than being deeply embedded within your specific application use case.
    • In many cases, this Squad will be bringing together teams that are already working on RAC implementations. As mentioned above, our goal is to encourage these teams to make their work accessible to each other and the broader community.
    • Note that this implies that one category of acceptable project is modularizing and making generic an RAC tool that is currently used only in a specific application!
  • (For application-level projects) A live demonstration that can be used by others.

Communication

We’ll run a biweekly meeting for the PARC Squad community at large (recurring time TBD). Teams and individuals involved in specific projects and encouraged to set up recurring meetings as well.

Short-form discussion will take place in a 0xPARC Discord channel.

We’ve been working with a few other teams to start up zkresear.ch, a new long-form discussion forum for applied ZK teams from across the ecosystem. We’ll ask participating teams to post their project proposals on zkresear.ch, and we also encourage you to participate in general discussion on the forum!

Timelines

Biweekly Squad Meetings will begin in early-mid November. We’ll alternate Squad Meetings with weekly talks from Squad members who will present deep dives into their projects.

We’ll also be helping to support the following in-person activities:

  • November 3-7: 0xPARC @ SF
  • November 15-17: ZKProof Workshop 5 @ Tel Aviv
  • Late December: Holiday break - no meetings.
  • February - March: 0xPARC Winter Residency @ Vietnam
    • The second half of PARC Squad will coincide with the 0xPARC Winter Residency, which will tentatively take place in Vietnam from February - March 2023.
    • We will host a hack week in February, which all Squad members are all invited to join.

Grants

0xPARC supports individuals and teams participating in PARC Squad with grant funding (generally between $4,000-$40,000). Beyond financial support, grants can also help to act as a “forcing function” that encourages participants to define project milestones and commit to a deliverable, for participants who want to make the commitment upfront.

Grants for PARC Squad projects are awarded on an ad-hoc basis by 0xPARC, with grant decisions managed by a collection of coordinators. Tentatively, funding for this joint grants pool may come from other contributors as well.