This library was developed using arkworks to accompany:

• Time-Space Trade-Offs for Sumcheck
  Anubhav Baweja, Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, Pratyush Mishra, Tushar Mopuri and Andrew Zitek-Estrada

• A Time-Space Tradeoff for the Sumcheck Prover
  Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, and Andrew Zitek-Estrada

It is a repository of algorithms and abstractions including but not limited to Blendy 🍹.

DISCLAIMER: This library has not received security review and is NOT recommended for production use.

The library provides implementation of sumcheck [LFKN92] including product sumcheck. For adaptability to different contexts, it implements three proving algorithms:

• The quasi-linear time and logarithmic space algorithm of [CTY11]

  • SpaceProver
  • SpaceProductProver

• The linear time and linear space algorithm of [VSBW13]

  • TimeProver
  • TimeProductProver

• The linear time and sublinear space algorithm Blendy🍹

  • BlendyProver
  • BlendyProductProver

The library can be used to obtain a sumcheck transcript over any implementation of Stream, which could be backed by an evaluations table held in memory or read from disk. For example, if $f = 4x_1x_2 + 7x_2x_3 + 2x_1 + 13x_2$ like in the test here, then:

let f_stream: MemoryStream<F> = MemoryStream::<F>::new(f.to_evaluations());
let mut multivariate_prover = TimeProver::<F, MemoryStream<F>>::new(
    <TimeProver<F, MemoryStream<F>> as Prover<F>>::ProverConfig::default(
        f_stream.claimed_sum,
        3,
        p_stream,
    ),
);
let transcript = Sumcheck::<F>::prove::<
    MemoryStream<F>,
    TimeProver<F, MemoryStream<F>>,
>(&mut multivariate_prover, &mut ark_std::test_rng()));

Or for the sum of $f * g$, then:

let f_stream: MemoryStream<F> = MemoryStream::<F>::new(f.to_evaluations());
let g_stream: MemoryStream<F> = MemoryStream::<F>::new(g.to_evaluations());
let streams: Vec<MemoryStream<F>> = vec![f_stream, g_stream]; 
let multivariate_product_prover = TimeProductProver::<F, MemoryStream<F>>::new(ProductProverConfig::default(
    multivariate_product_claim(streams.clone()),
    num_vars,
    streams,
));

In addition to the reference papers, to help selection of prover algorithm we give a brief evaluation. The asymptotic improvement of BlendyProver translates to significantly lower memory consumption than TimeProver across all configurations tested. TimeProver and BlendyProver have similar runtimes and are orders of magnitude faster than SpaceProver.

Contributions in the form of PRs and issues/ suggestions are welcome.

[LFNK92]: Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. “Algebraic Methods for Interactive Proof Systems”. In: Journal of the ACM 39.4 (1992).

[CTY11]: Graham Cormode, Justin Thaler, and Ke Yi. “Verifying computations with streaming interactive proofs”. In: Proceedings of the VLDB Endowment 5.1 (2011), pp. 25–36.

[VSBW13]: Victor Vu, Srinath Setty, Andrew J. Blumberg, and Michael Walfish. “A hybrid architecture for interactive verifiable computation”. In: Proceedings of the 34th IEEE Symposium on Security and Privacy. Oakland ’13. 2013, pp. 223–237.