---
# System prepended metadata

title: variable-padding-for-sumcheck

---

some resources: 
- https://hackmd.io/s/HyxaupAAA

first I want to explore [[sumcheck-protocol|sumcheck]] over more variables than a polynomial native var count. 
- we want to run sumcheck for a 2 var polynomial $f(a, b)$ but we want to assume the number of variables is 3 i.e. $B \in \{0, 1\}^3$
- the goal here is to generate a new prover and verifier protocol $P'$ and $V'$ that work over $B \in \{0, 1\}^{n + m}$ such that if the original prover and verifier protocols $P$ and $V$ that work over $B \in \{0, 1\}^m$ accept or reject, $P', V'$ does the same respectively. 


[[variable-padding]]
- $f'(a_1, a_2, ..., a_{n + m}) = f(a_1, a_2, ..., a_n) \cdot \prod_{i = n + 1}^{n + m} a_i$ 
- when adding new variables to the back like above, you can see it as fixing the prefix and attaching all iteration of the new hypercube to each prefix. 
	- for example say I started with 2 variables and I am adding 2 variables. 
	- I take each prefix of my already existing hypercube i.e. 00, 01, 10, 11
	- then I attach the new hypercube to each of them (new [[hypercube]] = [00, 01, 10, 11])
		- 00 -> 00|00, 00|01, 00|10, 00|11
		- 01 -> 01|00, 01|01, 01|10, 01|11
		- ...
- $f(a_1, a_2, ..., a_{n + m}) = f(a_1, a_2, ..., a_n) \cdot \prod_{i = n + 1}^{n + m} a_i$ 
	- this equation has been constructed in such a way that unless all the padded variables are 1's then the entire evaluation will be 0. 
	- in a given [[boolean-hypercube]] there is only one instance of all 1's
	- hence the function above just duplicates the original function, but puts 0's everywhere else. 
		- specifically \[$2^m - 1$ 0's, F[0], $2^m - 1$ 0's, F[1], ..., F\[$2^n - 1$\]]
		- example: 
			- $f(a, b) = 4a + 2b + 3$
				- evaluation form = [3, 5, 7, 9]
			- after variable padding (just one variable)
				- n = 2, m = 1
			- $c \cdot f(a, b) = 4ac + 2bc + 3c$ 
				- evaluation form = [0, 3, 0, 5, 0, 7, 0, 9]

checking constraints
- it is evident that the claimed sum for $f$ and $f'$ will be the same, as $f'$ is just $f$ with interleaved 0's. 
- given that the 0's are uniformly distributed then the top half will still contain the same concrete values in $f'$ as in $f$ hence the round polynomials are also going to be the same. 
- assuming left to right sumcheck then challenge assignment is done by splitting the evaluations in half, overlaying and performing [[linear-interpolation-and-extrapolation]]
	- given that concrete elements in top half and bottom half are displaced equally, then mirror overlap will still overlap concrete elements together and 0's together. 
	- i.e $f_2'$ is just a displaced version of $f_2$ with the same concrete values
- putting the above together, this proves that $f$ and $f'$ will have identical sumcheck messages for the first n rounds, at which $f$ will stop and $f'$ will generate m more messages. 


exploring what happens during the last m rounds. 
- at some point for $f$ we have [a, b] as the last two concrete values
- whereas $f'$ will have those but with some distributed 0's 
	- let us assume we have two variables padded
	- [0, 0, 0, a, 0, 0, 0, b] should be the evaluation form representation of $f'$ 
- the next randomness will concretize the oracle check claimed sum at the last location 
- [0, 0, 0, ieval(a, b, r) = c]
- subsequent rounds will perform the eval with 0
- [0, ieval(0, c)]
-  ieval = $(i - r) \cdot left + r \cdot right$ 
	- hence the reduction will just be $r \cdot lastclaim$

Algorithm summary for [[variable-padding-for-sumcheck]]
- run regular sumcheck for round $1..=n$
- return [0, oracle_claimed_sum] for round $n + 1$
- for round $n+1..=m$ return [0, last_claimed_sum * r]