---
# System prepended metadata

title: libra-notes

---

- number of gates on a layer is S
- number of bits for that layer is $s = log S$ 
- number of variables in poly we sum is $f(b, c)$ where $|b| = s$ and $|c| = s$ 
	- so total number of variables = $2s$ 
- prover time for sumcheck is $O(2^v)$ 
	- #todo show how thalers prover time got to this
		- $O(2^v \cdot T - T) = O(2^v)$ 
		- then $\sum_{i} 2^{v-1}  = 2^v - 1$
- linear time sumcheck for multilinear functions
	- evaluation form representation of the polynomial
	- get the halves and sum to get the round message
	- get the r
	- fold using r
	- repeat
	- basic stuff
- linear time sumcheck for product of multilinear functions
	- similar to regular sumcheck over multilinear functions
	- but now returns round poly in {0, 1, 2}
		- and two bookkeeping tables

- linear time sumcheck for gkr functions
	- gkr functions are of the following form
	- $\sum_{x, y \in \{0, 1\}^l} f_1(g, x, y) \cdot f_2(x) \cdot f_3(y)$ 
		- where $f_1$ represents a sparse polynomial i.e $O(2^l)$ non-zero elements out of the possible $O(2^{3l})$
	- libra achieves linear time by rewriting the equation above 
	- $\sum_{x, y \in \{0, 1\}^l} f_1(g, x, y) \cdot f_2(x) \cdot f_3(y)$  = $\sum_{x \in \{0,1\}^l} f_2(x) \sum_{y \in \{0,1\}^l} f_1(g, x, y) \cdot f_3(y)$ = $\sum_{x \in \{0,1\}^l} f_2(x) h_g(x)$ 
	- where $h_g(x) = \sum_{y \in \{0,1\}^l} f_1(g, x, y) \cdot f_3(y)$ 
	- so the equation $\sum_{x \in \{0,1\}^l} f_2(x)h_g(x)$ is only in terms of x
		- this is exactly the same as performing sumcheck over the product of two multilinear polynomials
		- the only thing missing is generating the book-keeping table for $h_g(x)$ 
		- the book-keeping table for $f_2(x)$ is already known as the polynomial was gotten from the multilinear extension of some array. 

- detour
	- if I have some multilinear function $f(a, b, c)$ 
	- I can interpret this in the lagrange basis 
	- a dot product between the evaluation form values and the bit checkers for each evaluation form value. 
		- i.e $f(a, b, c) = \sum_{x, y, z \in \{0,1\}^l} eq_{xyz}(a, b, c) \cdot F[x, y, z]$ 
			- where F is the array that defines the multilinear form array representation of $f$ 
	- only the non-zero elements in F will contribute to the sum
	- if we knew all the locations of F that were non-zero can we optimize this computation?
		- imagine we had a mapping (a, b, c) -> non_zero_ouptut
			- let us call this mapping $N$ 
		- we can use this to compute the final output
			- $\sum_{(x, y, z) \in N} eq_{xyz}(a, b, c) \cdot F[x, y, z]$ 
			- this will give the same answer, but reduces the amount of computations we are required to do (drastically if F is sparse).

- can eq be decomposed?
	- seems we indeed can, we can express a big eq equation as a product of smaller eq equations
	- $eq(x_1, x_2, x_3, y_1, y_2, y_3) = \prod_{i = 1} (1 - x_i)(1 - y_i) + x_i \cdot y_i$ 
		- each product term is an eq for $x_i$ and $y_i$ 
	- hence we can rewrite as follows
	- $eq(x_1, x_2, x_3, y_1, y_2, y_3) = eq(x_1, y_1) \cdot eq(x_2, y_2) \cdot eq(x_3, y_3)$ 

- idea summary
	- it is assumed one has a sparse function, where the non-zero entries are know i.e both index and non-zero output. 
	- we have some equation that uses the sparse function as a multiplication term. 
		- knowing the zero / non-zero entries of this function makes computing that equation a lot more efficient, because you only look at the non-zero terms. 
	- hence this means that you need to keep the sparse function in the lagrange basis. 
	- that way, you know what is 0 and you can avoid doing wasted computations.

- generating the book-keeping table $A_{h_g}$ 
	- we need a table that evaluates $h_g(x)$ over the boolean hypercube.
	- recall $h_g(x) = \sum_{y \in \{0, 1\}^l} f_1(g, x, y)f_3(y)$ 
		- here $f_1$ is partially evaluated at g, our sparse entries are no longer valid
		- to keep it sparse, we can extract $g$ into it's own eq
	- $h_g(x) = \sum_{z, y \in \{0, 1\}^l} eq(g, z) \cdot f_1(z, x, y) \cdot f_3(y)$ 
	- now given any x we should be able to compute the corresponding value of $h_g(x)$ 
		- we have the map (a, b, c) -> non_zero
		- the value of x we want to evaluate $h_g(x)$ is known and it is also boolean
		- so we can filter the map based on $b == x$ 
			- let us call this filtered map $N_x$ 
	- the final equation becomes
		- $h_g(x) = \sum_{(z, y) \in N_x} eq(g, z) \cdot F_i[z, x, y] \cdot f_3(y)$ 
	- the above is computable without ever needing to compute the full $f_1$ table

- after running sumcheck on $\sum_{x \in \{0,1\}^l} f_2(x)h_g(x)$
	- we'd have randomness associated with x, let us call this u.
	- going to back to the original equal we can replace all x with u to give
	- $\sum_{y \in \{0, 1\}^l} f_1(g, u, y)f_2(u)f_3(y)$ 
		- $f_2(u)$ will be a scalar, we can do scalar mul with all entries in $f_3(y)$ and that gives us the book-keeping table
		- we also need a book-keeping table for $f_1(g, u, y)$ we want to get that table without constructing the entire $f_1$ table and then partially evaluating at g and u
	- we can use the same idea, keep $f_1$ in the lagrange basis, we get
	- $\sum_{x, y, z \in \{0, 1\}^l} eq(g, z) \cdot eq(u, x) \cdot F[z, x, y] \cdot f_2(u) \cdot f_3(y)$ 
	- now that F is entirely in the lagrange basis and we also know all the non-zero entries we can make the computation compute the $A_{f_1}$ table efficiently. 
		- $A_{f_1}[y]$ = $\sum_{x, z \in \{0, 1\}^l} eq(g, z) \cdot eq(u,x) \cdot F[z, x, y]$
		- let $N$ be the mapping of all entries in $f_1$ that are non-zero
		- given that we know y we can filter that mapping to get $N_y$ 
		- $A_{f_1}[y] = \sum_{(x, z) \in N_y} eq(g, z) \cdot eq(u, x) \cdot F[z, x, y]$ 
			- but this is much faster to compute

- see [[generalize-libra-sumcheck-to-c-phases]]

- 2 to 1 trick
	- initially we have $\sum f(g, x, y) \cdot f_2(x) \cdot f_3(y)$ 
	- at the folding step we have two different evaluations of g i.e $g_1$ and $g_2$ 
		- $c_1 = \sum f(g_1, x, y) \cdot f_2(x) \cdot f_3(y)$ and
		- $c_2 = \sum f(g_2, x, y) \cdot f_2(x) \cdot f_3(y)$ 
	- rather than performing two libra sumchecks we want to perform just one
	- we can perform this reduction via the [[random-linear-combination]]
	- LHS
		- $C = \alpha \cdot c_1 + \beta \cdot c_2$ 
	- RHS
		- $\alpha \cdot f(g_1, x, y) \cdot f_2(x) \cdot f_3(y) + \beta \cdot f(g_1, x, y) \cdot f_2(x) \cdot f_3(y)$
		- we can factorize $f_2(x)$ and $f_3(y)$ 
			- $(\alpha \cdot f(g_1, x, y) + \beta \cdot f(g_2, x, y)) \cdot f_2(x) \cdot f_3(y)$
		- we can further simplify the sum via $I(g,z)$ 
			- $((\alpha \cdot I(g_1, z) \cdot f(z, x, y)) + (\beta \cdot I(g_2, z) \cdot f(z, x, y)) \cdot f_2(x) \cdot f_3(y)$ 
		- which allows us to factor out $f(z, x, y)$ 
			- $(\alpha \cdot I(g_1, z) + \beta \cdot I(g_2, z)) \cdot f(z, x, y) \cdot f_2(x) \cdot f_3(y)$ 
	- hence the only change to account for folding is the building of the $I(g, z)$ table
