Remainder CE: Reasonable Machine learning Doubly-Efficient prover (Community Edition)

Overview

Remainder is an open-source "GKR-ish" implementation, with a custom circuit creation frontend, prover, and verifier. Remainder is fully written in Rust and only has CPU bindings, and seamlessly bundles together a basket of techniques, including

• Structured layers and linear-time sumcheck prover from Tha13
• Time-optimal sumcheck for matrix multiplication from Tha13
• Linear-time dataparallel $\widetilde{\text{add}}$ and $\widetilde{\text{mul}}$ prover algorithms a la Mod24, which combines ideas from WJB+17 and XZZ+19
• Interpolative claim aggregation from Tha13 and random linear combination claim aggregation from XZZ+19
• Polynomial commitment schemes implicit in AHIV22 ("Ligero PCS") and WTS+17 ("Hyrax PCS")
• Pedersen commitment-based zero-knowledge wrapper for all of the above, drawing heavily from WTS+17

See our companion Remainder book for an in-depth overview of all the above components and more!

Documentation

Remainder comes with two primary official documentation resources:

• The highly-recommended Remainder book, which offers an intuitive introduction to GKR and Hyrax, and dives into both the GKR/Hyrax theory and concrete examples of how to use various circuit layer types in circuit-building.
• Our autogenerated Rust docs, which provide code-level detail on specific functions and structs.

Status

Parts of Remainder have been audited in the past, although we currently provide no official guarantees on the security of the current implementation. Past audits can be found in our audit_reports/ directory.

Installation

Remainder is fully implemented in Rust, and requires the (stable) version specified in the rust-toolchain.toml file. Once you have installed Rust --

git clone https://github.com/worldcoin/Remainder_CE.git
cd Remainder
make check # Compiles + lints
make test-dev # Runs all fast unit tests; skips slower integration tests

This will compile, lint, and run all tests but the particularly expensive ones. You may run make test to run all tests (this will compile in release mode and may take >5 minutes).

Repository Structure

• frontend: Crate containing circuit creation components.
• prover: Crate containing modules for GKR proving and verifying proofs over a pre-defined circuit.
• ligero: Crate containing an implementation of the Ligero polynomial commitment scheme.
• hyrax: Crate containing an implementation of the Hyrax zero-knowledge Pedersen commitment GKR wrapper.
• shared_types: Crate defining base traits/types (finite field, elliptic curve, multilinear extension, transcript, etc).

Examples

See the frontend/examples directory for circuit examples! Additionally, see the Remainder book's quickstart and frontend tutorial sections for more details. To run the basic example highlighted in the quickstart:

cargo run --package frontend --example tutorial

Contributing

Note: We plan to accept contributions at a later date, and have minimal bandwidth to review PRs currently.

Likewise, we are providing this source code for the benefit of the community, but cannot commit to any SemVer or API stability guarantees. Be warned: we may change things in a backwards-incompatible way at any time!

For soundness or other security-related issues, see SECURITY.md.

License

Unless otherwise specified, all code in this repository is dual-licensed under either:

• MIT License (LICENSE-MIT)
• Apache License, Version 2.0, with LLVM Exceptions (LICENSE-APACHE) at your option. This means you may select the license you prefer to use.

Any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Acknowledgements

In addition to the primary contributors listed on GitHub, we would like to especially thank the following individuals/teams for their advice and contributions to Remainder:

• Zhenfei Zhang, for endless optimization and implementation discussions, and for being our first believer
• Riad Wahby, for greatly assisting in our implementation of Hyrax and always putting a smile on our face
• The Hungry Cats Studio team, for writing a Halo2-based recursive verifier for an early version of Remainder
• Justin Thaler, for dispensing wisdom about sumcheck and GKR and helping us understand when not to use sumcheck
• Tianyi Zhang, for sharing numerous tips and tricks with us from the zkCNN codebase, a super fast GKR implementation written in C++.

And countless others who pointed out bugs, optimizations, and so much more (see CONTRIBUTORS.md for a list of current and past code contributors)!

Additionally, Remainder's early design was heavily inspired by the Arkworks and Halo2 repositories, and the Remainder book itself is also inspired by the Halo2 book.