Consider removing support for Spark

[sragss]

Currently Surge supports using Surge as a multi-dimensional sparse polynomial commitment scheme known in the Lasso paper as "Spark". To support, we generate and pass through a 'C' different log2(sparsity) sized randomness vectors for evaluating the multilinear extension of the $\tilde{eq}_i(x,r)$ polynomial.

Currently we generate both eq_randomness: Vec<F> of size log-s and spark_randomness: [Vec<F>; C] with each vec of size log-m. For Surge we use only eq_randomness.

The SubtableStrategy::materialize_subtables and SubtableStrategy::evaluate_subtable_mle function signatures depend on r: &[Vec<F>; C] despite being an unused parameter in all Subtable strategies beyond Spark.

This means that we pass spark_randomness deep into prover and verifier workflows.

Spark is useful in it's own right – support would be nice, but it does carry a substantial readability / maintainability cost.

[sragss]

Spark within Surge is broken as of commit. Tests will still pass but there is an excess $\tilde{eq}(k, r)$ in front. To re-enable Spark, the poly degree should be reduced for the SparkSubtableStrategy and the front eq eval should be removed from the prove and verify sumcheck evaluations.

[wyattbenno777]

Are the notes in pg. 37 already implemented/ in what form?
https://people.cs.georgetown.edu/jthaler/Lasso-paper.pdf

I am curious if Tha13 is being used over SL20 for the GKR memory checking portion?

[wyattbenno777]

Never mind. I think it is using the optimizations in both Tha13 and SL20.