---
# System prepended metadata

title: Sumcheck cost over different product sets

---

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)$