---
# System prepended metadata

title: sumcheck-cost-model-different-product-sets

---

how is [[sumcheck]] affected (proof size, prover time e.t.c.) when one uses different [[product-set]]s

sumcheck steps
1. compute round univariate polynomial (by keeping a variable free and summing the rest over the [[product-set]])
2. partially evaluate free variable at some random challenge point
3. oracle check

prover time cost model
- step 1
	- keeping one variable free we sum $2^{v-1}$ points 
	- where v represents the total number of variables
	- no_field_additions = $2^{v - 1} - 1$ 
	- no_field_multiplications = 0
- step 2
	- let r be the point you want to partially evaluate
	- for B = {0, 1}, the interpolate and evaluate function is given as follows
		- $(1 - r) \cdot y_1 + r \cdot y_2$ 
		- further simplified to 
			- $y_1 - x(y_1 + y_2)$
		- no_field_additions = 2
		- no_field_multiplications = 1
	- for B = {0, 1, 2} the interpolate and evaluate function is given as follows
		- $\frac{x^2 - 3x + 2}{2} \cdot y_1 + 2x^2 - x^2 \cdot y_2 + \frac{x^2 - x}{2} \cdot y_3$
		- further simplified to
			- $2^{-1} \cdot (x^2 \cdot (y_1 - 2y_2 + y_3) - x \cdot (3y_1 - 4y_2 + y_3) + 2y_1)$ 
		- no_field_additions = 6
		- no_field_multiplications = 3
	- I believe it gets more complicated for bigger [[product-set]]s
- step 3
	- going to assume the same cost
	
- total prover time cost
	- |data| - size of the evaluation array we want to perform sumcheck over
	- n = product set size
	- v = $log_n(|data|)$ = number of variables

	#todo potential mistake in how I compute the total number of sums (can potentially make it independent of the $\cdot v_i$)

	- for B = {0, 1} (2HC)
		- no_field_additions:
			- $v_1 \cdot (2^{v_1-1} - 1 + 2)$ = $v_1 \cdot (2^{v_1-1} + 1)$
			- $v_1\cdot 2^{v_1-1} + v_1$ 
		- no_field_multiplications = $v_1$

	- for B = {0, 1, 2} (3HC)
		- no_field_additions:
			- $v_2 \cdot (2^{v_2-1} -1 + 6$ = $v_2 \cdot (2^{v_2-1} + 5)$
			- $v_2 \cdot 2^{v_2 - 1} + 5v_2$ 
		- no_field_multiplications = $3v_2$ 

#todo 2HC has a lot more additions, while 3HC has a lot more multiplications (the battle depends on how much slower field multiplication is than addition)
see: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=4f8d08c61434c838507ffe1c359f04a0

proof size cost model
- |data| - size of the evaluation array we want to perform sumcheck over
-  n = product set size
-  v = $log_n(|data|)$ = number of variables
- proof_size = number_of_rounds * number_of_field_elements_per_round
- if we assume variable degree is one less than product set size then
	- proof_size = $v \cdot n$ 
- e.g. B = {0, 1} will use a multilinear poly with variable degree 1 

| evaluation_array_size | n_vars (2hc) | proof_size (2hc) | n_vars (3hc) | proof_size (3hc) |
| --------------------: | -----------: | ---------------: | -----------: | ---------------: |
|             1,000,000 |           20 |               40 |           13 |               39 |
|            11,000,000 |           24 |               48 |           15 |               45 |
|            81,000,000 |           27 |               54 |           17 |               51 |

see: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=12dffd12c70098ce90c44928020c4176

- 3HC has better proof size than 2HC (but only marginally)