Linear-Time Sumcheck

linear-sumcheck is a Rust library that implements the sumcheck protocol.

This crate implements the following protocols:

• MLSumcheck: The sumcheck protocol for products of multilinear polynomials in evaluation form over boolean hypercube.
• GKRRoundSumcheck: The sumcheck protocol for GKR Round Function. This protocol takes MLSumcheck as a subroutine.

WARNING: This is an academic proof-of-concept prototype, and in particular has not received careful code review. This implementation is NOT ready for production use.

Build guide

The library compiles on the stable toolchain of the Rust compiler. To install the latest version of Rust, first install rustup by following the instructions here, or via your platform's package manager. Once rustup is installed, install the Rust toolchain by invoking:

rustup install stable

After that, use cargo (the standard Rust build tool) to build the library:

git clone https://github.com/arkworks-rs/sumcheck.git
cd sumcheck
cargo build --release

This library comes with some unit and integration tests. Run these tests with:

cargo test

Lastly, this library is instrumented with profiling infrastructure that prints detailed traces of execution time. To enable this, compile with cargo build --features print-trace.

Benchmarks

To run the benchmarks, install the nightly Rust toolchain, via rustup install nightly, and then run the following command:

cargo +nightly bench --all-features

All benchmarks below are performed over BLS12-381 scalar field implemented in the ark-test-curves library. Benchmarks were run on a machine with an Intel Xeon 6136 CPU running at 3.0 GHz.

Benchmarks for MLSumcheck

Benchmarks for GKRRoundSumcheck

License

This library is licensed under either of the following licenses, at your discretion.

• Apache License Version 2.0
• MIT License

Unless you explicitly state otherwise, any contribution that you submit to this library shall be dual licensed as above (as defined in the Apache v2 License), without any additional terms or conditions.

Reference Paper

Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation
Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, Dawn Song

Time-Optimal Interactive Proofs for Circuit Evaluation
Justin Thaler