what stream prover exactly means? find definition here (page 5):
So the “streaming” means that the witness of the sumcheck protocol, i.e., the evaluations of a multilinear polynomial, is not counted in the RAM of the prover, prover doesn’t need to store this information, but only re-generated it when every time prover needs to access it, and when accessing, prover read the evaluation in a sequential manner (that’s the streaming), and I suppose because of this, even when regenerating the witness, there is no need for a big RAM to store the whole execution info, which might take \(number of cycle\) space.
The below description is from Proving CPU Executions in Small Space page 15
this paragraph points out the execution trace can be enumerated by emulating the computation cycle by cycle. (from paper speeding up sum-check proving, page 10)
Given this definition, we can discuss some known sum-check protocols implementation
Algorithm 1, in speeding up sum-check proving page 12
space usage: to compute \(s_i\) and \(p_k\), prover needs to store \(p_k(r_0,…,r_i, x’)\), it is \(2^{l-i}\) evaluations in each round.
How to choose the evaluation points?
since each \(p_k\) is degree-1 polynomial, knowing \(p(0)\) and \(p(1)\), one can compute the evaluations for the other points. This is specified in Time-Space Trade-Offs for Sumcheck page 10.
