The `num_nz_entries` should be more generic

[3for]

Hi, the num_nz_entries is fixed to be equal to num_cons, and there's some assertion in the commit and prove schedule，as:

assert_eq!(gens_n.n, self.len());

But actually, though it's sparse, the non zero entries can be more than the constraint number, e.g., Vitalik Buterin's blog Quardratic Arithmetic Programs: from Zero to Hero . I think it would be better to make it more generic?

    //let max_nz_entries = num_cons;
    let max_nz_entries = ((num_cons * (num_vars + num_inputs + 1))as usize).next_power_of_two(); //make it more generic, for one constraint for A should have more than 1 zeros.

[srinathsetty]

@3for Setting max_nz_entries to the product of num_cons and num_vars doesn't help. Can you please point where we hard code the number of non-zero entries to the number of constraints?

[3for]

Change the corresponding code in produce_synthetic_r1cs to be:

    let mut Z: Vec<Scalar> = Vec::new();
    Z.push((3 as usize).to_scalar());
    Z.push((9 as usize).to_scalar());
    Z.push((27 as usize).to_scalar());
    Z.push((30 as usize).to_scalar());
    Z.push(Scalar::one());
    Z.push((35 as usize).to_scalar());

    // three sparse matrices
    let mut A: Vec<SparseMatEntry> = Vec::new();
    let mut B: Vec<SparseMatEntry> = Vec::new();
    let mut C: Vec<SparseMatEntry> = Vec::new();
    let one = Scalar::one();

    A.push(SparseMatEntry::new(0, 0, one));
    B.push(SparseMatEntry::new(0, 0, one));
    C.push(SparseMatEntry::new(0, 1, one));

    A.push(SparseMatEntry::new(1, 1, one));
    B.push(SparseMatEntry::new(1, 0, one));
    C.push(SparseMatEntry::new(1, 2, one));

    A.push(SparseMatEntry::new(2, 2, one));
    A.push(SparseMatEntry::new(2, 0, one));
    B.push(SparseMatEntry::new(2, 4, one));
    C.push(SparseMatEntry::new(2, 3, one)); 

    A.push(SparseMatEntry::new(3, 3, one));
    A.push(SparseMatEntry::new(3, 4, (5 as usize).to_scalar()));
    B.push(SparseMatEntry::new(3, 4, one));
    C.push(SparseMatEntry::new(3, 5, one));

Then the cargo test check_snark failed for assertion assert_eq!(gens_n.n, self.len());, for the generator number is not enough. Would it be better to generate enough generators at first, and while commit and prove, selecting part of the generators? Such as:

let max_nz_entries = ((num_cons * (num_vars + num_inputs + 1))as usize).next_power_of_two(); 

And use gens_n_balanced instead of gens_n :

    assert!(gens_n.n >= self.len());
    let (G1, _G2) = gens_n.G.split_at(self.len());
    let gens_n_balanced =  MultiCommitGens {
      n: G1.len(),
      G: G1.to_vec(),
      h: gens_n.h,
    };

[srinathsetty]

@3for I'll take a look to see why the assert check fails with the number of generators, for the example that you depict. Making max_nz_entries to be the product of num_cons and num_vars +num_inputs+1 is not an option because then it means the memory for holding generators is quadratic in the size of the statement (we want the prover to use memory that is only linear in the statement size).

In the meantime, have you seen: https://github.com/microsoft/Spartan/blob/master/examples/cubic.rs? This represents the constraint system that you depicted with Spartan's public APIs.

[3for]

I have not seen cubic.rs before now, it's exactly what I do in check_snark test. And when change let num_non_zero_entries = 8; to let num_non_zero_entries=num_cons;, the same assertion error occurred. The generator number in gens_ops depends on num_nz_entries, which maybe bigger than num_cons. In check_snark test, the r1cs to be proven accidently has num_nz_entries equal with num_cons.

[srinathsetty]

In the example you depicted, matrix A has 5 non-zero entries, whereas the number of constraints is 4 (so, yes, num_non_zero_entries can be different than num_cons). Hence, in cubic.rs, the num_non_zero_entries is set to 8 (the next power of 2 after 5).

If you can point me to your repo with the changes that don't work, I'll be happy to help. Alternatively, do you have an example (analogous to cubic.rs) that uses the public APIs of Spartan, but fails to produce a proof?

[3for]

I know the reason now, fix a proper value of num_nz_entries would be okay. Both num_cons and num_nz_entries are relevant to specific R1CS.

Thanks for your help, I've gotten a better understanding of Spartan.

[srinathsetty]

Sounds good! Please let me know if you run into any more issues. Thanks!