Optimize: Remove final batching sumcheck

[sragss]

The final batching sumcheck of Snark::prove is unneeded for us as we only need to support R1CS rather than Relaxed R1CS. This final sumcheck accounts for ~25% of Spartan e2e prover time.

We can cut all of the following:

Spartan2/src/spartan/snark.rs

Lines 289 to 353 in d78a504

	// We will now reduce a vector of claims of evaluations at different points into claims about them at the same point.
	// For example, eval_W =? W(r_y[1..]) and eval_E =? E(r_x) into
	// two claims: eval_W_prime =? W(rz) and eval_E_prime =? E(rz)
	// We can them combine the two into one: eval_W_prime + gamma * eval_E_prime =? (W + gamma*E)(rz),
	// where gamma is a public challenge
	// Since commitments to W and E are homomorphic, the verifier can compute a commitment
	// to the batched polynomial.
	assert!(w_u_vec.len() >= 2);
	let (w_vec, u_vec): (Vec<PolyEvalWitness<G>>, Vec<PolyEvalInstance<G>>) =
	w_u_vec.into_iter().unzip();
	let w_vec_padded = PolyEvalWitness::pad(&w_vec); // pad the polynomials to be of the same size
	let u_vec_padded = PolyEvalInstance::pad(&u_vec); // pad the evaluation points
	// generate a challenge
	let rho = transcript.squeeze(b"r")?;
	let num_claims = w_vec_padded.len();
	let powers_of_rho = powers::<G>(&rho, num_claims);
	let claim_batch_joint = u_vec_padded
	.iter()
	.zip(powers_of_rho.iter())
	.map(|(u, p)| u.e * p)
	.sum();
	let mut polys_left: Vec<MultilinearPolynomial<G::Scalar>> = w_vec_padded
	.iter()
	.map(|w| MultilinearPolynomial::new(w.p.clone()))
	.collect();
	let mut polys_right: Vec<MultilinearPolynomial<G::Scalar>> = u_vec_padded
	.iter()
	.map(|u| MultilinearPolynomial::new(EqPolynomial::new(u.x.clone()).evals()))
	.collect();
	let num_rounds_z = u_vec_padded[0].x.len();
	let comb_func = |poly_A_comp: &G::Scalar, poly_B_comp: &G::Scalar| -> G::Scalar {
	*poly_A_comp * *poly_B_comp
	};
	let (sc_proof_batch, r_z, claims_batch) = SumcheckProof::prove_quad_batch(
	&claim_batch_joint,
	num_rounds_z,
	&mut polys_left,
	&mut polys_right,
	&powers_of_rho,
	comb_func,
	&mut transcript,
	)?;
	let (claims_batch_left, _): (Vec<G::Scalar>, Vec<G::Scalar>) = claims_batch;
	transcript.absorb(b"l", &claims_batch_left.as_slice());
	// we now combine evaluation claims at the same point rz into one
	let gamma = transcript.squeeze(b"g")?;
	let powers_of_gamma: Vec<G::Scalar> = powers::<G>(&gamma, num_claims);
	let comm_joint = u_vec_padded
	.iter()
	.zip(powers_of_gamma.iter())
	.map(|(u, g_i)| u.c * *g_i)
	.fold(Commitment::<G>::default(), |acc, item| acc + item);
	let poly_joint = PolyEvalWitness::weighted_sum(&w_vec_padded, &powers_of_gamma);
	let eval_joint = claims_batch_left
	.iter()
	.zip(powers_of_gamma.iter())
	.map(|(e, g_i)| *e * *g_i)
	.sum();

1. Cut above
2. Modify the final let eval_arg = EE::prove(...) to use eval_W instead.
3. Verifier checks eval_E is zero

[sragss]

Looks like we can remove w_u_vec and associated expensive cloning as well.

[sragss]

Arasu is handling here: #17