I care about three properties, prover cost, verifier cost, and proof size, when we run sumcheck over $B \in \{0, ..., k - 1\}$

Shared Variables
- n - number of data points
- v - number of rounds
- $v = log_{k}(n)$
- ieval(k)
- cost of interpolating k points to get a polynomial + evaluation of the polynomial at some random field element.

Proof Size
- the proof is supposed to consist of the round polynomials, with larger product sets, we have less rounds but more data points per round.
- assuming we consider all the round polynomials to have the same degree (in our case, $k$ - 1)
- then we send $k$ points per round, for v rounds
- hence proof size formula is given by $k \cdot log_{k}(n)$
- some concrete relations
- [[2HC]]: $B \in \{0, 1\}$ i.e $k = 2$
- proof size = $2 \cdot log_2(n)$
- [[3HC]]: $B \in \{0, 1, 2\}$ i.e $k = 3$
- proof size = $3 \cdot log_3(n)$

Prover Cost
- I believe here the prover does the same work v times, which involves computing the current round poly and partially evaluating to get a smaller evaluation array at some random verifier challenge.
- computing the round polynomials
- every round is just a streaming sum over the current number of evaluations, but the number of evaluations change over time.
- hence we just need to keep track of the number of evaluations per round.
- $n + \frac{n}{k} + \frac{n}{k^2} + ... + k^2$ total additions
- this simplifies to $\frac{k \cdot (n - k)}{k - 1}$ additions
- what about the partial evaluation step?
- we are doing $\frac{n}{k} + \frac{n}{k^2} + \frac{n}{k^3} + ... + k$ ievals
- this simplifies down to $\frac{n - k}{k - 1}$ ievals
- hence total prover cost
- $\frac{k \cdot (n - k)}{k - 1}$ additions
- $\frac{n - k}{k - 1} \cdot ievals(k)$
- some concrete relations
- [[2HC]]
- $2n - 4$ additions
- $(n - 2) \cdot ievals(2)$
- [[3HC]]
- $\frac{3}{2} \cdot (n - 3)$ additions
- $\frac{n - 3}{2} \cdot ievals(3)$

Verifier Cost
- needs to perform k sums per round, to ensure given round poly matches the claimed sum.
- claimed_sum_verification = $k \cdot v$ additions
- and we need to do one ieval per round
- so total verifier cost
- $k \cdot v$ additions
- $v \cdot ievals(k)$
- some concrete relations
- [[2HC]]
- $2 \cdot log_2(n)$ additions
- $log_2(n) \cdot ievals(2)$
- [[3HC]]
- $3 \cdot log_3(n)$ additions
- $log_3(n) \cdot ievals(3)$