arkworks-rs / sumcheck Goto Github PK

Hi!
I think something is missing in the implementation. Please correct me if I'm wrong!

In each layer of the circuit we have 3 instances of the sumcheck protocol that can be performed in paraller but not entirely seperately! because these instances use the same public randomness provided by the verifier!
In this implementation, The GKRLinearSumchek works fine on its own, but is not applicable in the GKR scenario, since each instance uses its own randomness! In other words, in your implementation, each prover instance creates the randomness from the previous prover messages; However, all the prover messages should be summed and the randomness should be created upon the summed value.

Suggestion: I think it would be better if each instance had a handle to a common prover state.

Thanks

ark-bcs is almost done. While univariate sumcheck is IP, we can still use the transcript by implementing ark-bcs::iop::IOPProver.

Also, write constraints for sumcheck (should not be too much work)

One thing special in Libra/Virgo is that it supports many customized gates, particularly:

1. a gate that sums 2^L values together.
2. an expsum gate that computes the bit composition of 2^L values.

These gates have the potential to reduce the amount of computation---adding 2^L values together with the 2-input, 1-output addition gates would take about 2^{L}-1 gates and L layers.

Reducing the number of layers would have multiple benefits: (1) cut the rounds, so fewer sumchecks, fewer poly-commits and (2) in general fewer gates, so smaller FFT (in Virgo).

add prove_round
add verify_round

Dependabot couldn't parse the Cargo.toml found at /Cargo.toml.

The error Dependabot encountered was:

Dependabot::DependencyFileNotParseable

View the update logs.

Your dependency file specified a branch or reference for ark-ff, but Dependabot couldn't find it at the project's source. Has it been removed?

View the update logs.

Use ark-sponge instead of Blake2s512Rng after it becomes stable

Hello,

First of all thank you for this great crate, it's really helping me a lot.

I had a remark concerning the latest version of the crate available on github. When I try to use it and build my project, I have some errors connected to the crate ark-serialize.
The content of my Cargo.tolm is the following:

[package]
name = "test_sumcheck"
version = "0.1.0"
edition = "2021"

[dependencies]
ark-linear-sumcheck = { version = "^0.3.0" }

[patch.crates-io]
ark-linear-sumcheck = { git = "https://github.com/arkworks-rs/sumcheck" }

And when I run cargo build I get several errors of the form:

error[E0412]: cannot find type `SerializationError` in this scope
  --> /home/XXXXX/.cargo/git/checkouts/sumcheck-2b3187b65cdc1384/91bde9a/src/ml_sumcheck/data_structures.rs:47:30
   |
47 | #[derive(CanonicalSerialize, CanonicalDeserialize, Clone)]
   |                              ^^^^^^^^^^^^^^^^^^^^ not found in this scope
   |
   = note: this error originates in the derive macro `CanonicalDeserialize` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider importing this enum
   |
3  | use ark_serialize::SerializationError;
   |

Some errors have detailed explanations: E0405, E0412.
For more information about an error, try `rustc --explain E0405`.
error: could not compile `ark-linear-sumcheck` due to 12 previous errors

However, this problem does not arise when using the latest release of the crate, i.e. by commenting the line of [patch.crates-io].

I wanted to know if it was a setup error on my part or a problem linked with updates in the ark crates?
For now I will keep using the previous full release as it is working great.

Thank you for your time!

todo:

• generate_proof should return the subclaim as well
• generate_proof and verify should allow an initial vector as first randomness

I am not a rust developer and may be missing something, but does this repo contain unit tests to prove implementation correctness?

Add CI, patterned on https://github.com/scipr-lab/poly-commit/blob/efff1c113bbddd726144bd4ed922301a63b5d334/.github/workflows/ci.yml

For the polynomial f1(x)f2(x)...*fn(x) and the randomness r_x, it is useful to output [f1(r_x), f2(r_x), ..., f3(r_x)] instead of merely their products.

Add dynamic reference for sharing the evaluation tables

Given P(x1, x2, x3, x4) and r1, r2, add partial evaluation feature so that the function can output P'(x3,x4) such that P'(x3, x4) = P(r1, r2, x3, x4)

Inspired by Pratyush's comment in PR #1, it's good to use Cow<'a, Vec<F>> smart pointer to combine MLExtensionArray and MLExtensionRefArray to reduce duplicate code.

This feature should be implemented in later PRs.

If I understand correctly, the current API allows running the sumcheck protocol over products of DenseMultilinearExtension.
If one wanted to prove knowledge of evaluations over arbitrary multivariate (not just multilinear) g, then sure it's possible by multiplying a few multilinear polynomials, but I feel that this turns out to be unneccearily complex for the end user.

Is there a reason why this API was chosen as such?
Perhaps we could rework it to support DenseMVPolynomial instead?

Also would be good to hear how/if poeple use this library in their proof systems, or what would they require from arkworks sumcheck to be practical?

Hello,

I am using the MLSumcheck implementation to prove the result of a multiplication of two polynomials but I need to get access to the state of their MLEs at the end of the prover rounds for further computations. However the MLSumcheck::prove function only returns the value of the messages sent by the prover.

pub fn prove(polynomial: &ListOfProductsOfPolynomials<F>) -> Result<Proof<F>, Error> {
    let mut fs_rng = Blake2s512Rng::setup();
    fs_rng.feed(&polynomial.info())?;

    let mut prover_state = IPForMLSumcheck::prover_init(&polynomial);
    let mut verifier_msg = None;
    let mut prover_msgs = Vec::with_capacity(polynomial.num_variables);
    for _ in 0..polynomial.num_variables {
        let (prover_msg, prover_state_new) = IPForMLSumcheck::prove_round(prover_state, &verifier_msg);
        prover_state = prover_state_new;
        fs_rng.feed(&prover_msg)?;
        prover_msgs.push(prover_msg);
        verifier_msg = Some(IPForMLSumcheck::sample_round(&mut fs_rng));
    }

    Ok(prover_msgs)
}

I was wondering if it was somehow possible to access the final value of prover_state after the function call without rewriting the function?

Thank you for your time!

add from_vec constructor for MLExtensionArray to avoid one data copy

See poly-commit or algebra-core for examples of how to do this cleanly.

After updating dependencies (which currently prevents building), clippy lints currently fail.