Issue in new sparse polynomial evaluation approach

[sashafrolov]

Hi,
I was testing a slightly weird use case for spartan2 (a use case where the number of public inputs is pretty close to the total number of constraints).
Here is the circuit I was testing:
https://gist.github.com/sashafrolov/5c4b3a567fb269289dcdd6311c6dc397

The resulting circuit has ~76800 constraints and ~76800 public inputs.
When running it, I got the following error:

thread 'main' panicked at /Users/sasha/Documents/Spartan2/src/polys/multilinear.rs:150:50:
range start index 18446744073709551615 out of range for slice of length 17
stack backtrace:
   0:        0x10460b508 - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h92dda645f072dcaf
   1:        0x104526fa8 - core::fmt::write::hbc92919d8e8f9a96
   2:        0x104609d60 - std::io::Write::write_fmt::hcee3b5dc9ab531be
   3:        0x10460b318 - std::sys::backtrace::BacktraceLock::print::h0f497abce563e5d2
   4:        0x104609974 - std::panicking::rust_panic_with_hook::h1882a30575fbb763
   5:        0x10462f474 - std::panicking::begin_panic_handler::{{closure}}::h39275ef3005e6337
   6:        0x10462f3e4 - std::sys::backtrace::__rust_end_short_backtrace::h6ede323c05a76849
   7:        0x10462fc0c - __rustc[95feac21a9532783]::rust_begin_unwind
   8:        0x104645514 - core::panicking::panic_fmt::h529fda7ea817ba4f
   9:        0x104645570 - core::slice::index::slice_start_index_len_fail::do_panic::runtime::h970119d125af5363
  10:        0x104645520 - core::slice::index::slice_start_index_len_fail::h07f33eb5dee8df43
  11:        0x1045896bc - spartan2::polys::multilinear::SparsePolynomial<Scalar>::evaluate::h06213570bd40a16e
  12:        0x104563730 - <spartan2::spartan::R1CSSNARK<E> as spartan2::traits::snark::R1CSSNARKTrait<E>>::verify::h4f05801380f657f3
  13:        0x104581f58 - naive_lc_blur::main::h85ed19aa8ac2e7bc
  14:        0x104593b0c - std::sys::backtrace::__rust_begin_short_backtrace::hf00d7c12ef769c24

The issue is in multilinear.rs, in this function:

 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
    assert_eq!(self.num_vars, r.len());

    let num_vars_z = self.Z.len().next_power_of_two().log_2();
    let chis = EqPolynomial::evals_from_points(&r[self.num_vars - 1 - num_vars_z..]);
    let eval_partial: Scalar = self
      .Z
      .iter()
      .zip(chis.iter())
      .map(|(z, chi)| *z * *chi)
      .sum();

    let common = (0..self.num_vars - 1 - num_vars_z)
      .map(|i| (Scalar::ONE - r[i]))
      .product::<Scalar>();

    common * eval_partial
  }
}
  }

In my use case, self.num_vars and num_vars_z are equal (because there are so many outputs), that this computation underflows, and causes the slide into &r to be wrong.

By making this patch to multilinear.rs, I was able to fix the bug and get everything working:

  pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
    assert_eq!(self.num_vars, r.len());

    let num_vars_z = self.Z.len().next_power_of_two().log_2();
    let slice_start_idx = if 1 + num_vars_z > self.num_vars {0} else {self.num_vars - 1 - num_vars_z};
    let chis = EqPolynomial::evals_from_points(&r[slice_start_idx..]);
    let eval_partial: Scalar = self
      .Z
      .iter()
      .zip(chis.iter())
      .map(|(z, chi)| *z * *chi)
      .sum();

    let common = (0..slice_start_idx)
      .map(|i| (Scalar::ONE - r[i]))
      .product::<Scalar>();

    common * eval_partial
  }

I just replaced the calculation with something that defaults to 0 when an underflow is detected.

I am not sending a pull request because I am not sure I understand the Spartan2 codebase well enough yet to know if this is the right way to fix it.
Thanks!

[srinathsetty]

Thanks @sashafrolov! Could you please make a PR?