---
# System prepended metadata

title: virgo++

---

paper: https://eprint.iacr.org/2020/1247.pdf

### [[arbitrary-arithmetic-circuits]]
- for [[layered-arithmetic-circuits]] each gate can only take it's input from the layer below. 
- for the purposes of [[virgo++]] the [[arbitrary-arithmetic-circuits]] is defined as follows
	- the circuit can be seen as a directed acyclic graph
	- with fan-in 2 nodes (meaning each gate takes a maximum of 2 inputs)
	- the depth of the circuit $d$ is the length of the longest path in the graph
	- input gates are at layer d, output gates are at layer 0
	- each gate in the graph can be assigned a layer id via topological sorting
		- we can determine a gates layer via the following: layer(g) = min(layer(u), layer(v)) - 1
			- where u and v represents the input to gate g
			- note: if g is the input gate then it's layer id is just $d$ 
		- this leads to the conclusion that every gate at layer i must have an input from layer i + 1

- rough intuition
	- inputs are fixed at layer d
	- all other gates depend on the inputs or depend on things that have been derived from the input. 
	- if you depend exclusively on the input then layer d - 1
	- if you depend on something that depends on the input (say 1 step) then layer d - 2
		- the idea here is the layers might represent some kind of computational step, so the gate has to wait a layer for all it's needed inputs to be ready, only then can it perform it's computation. 
		- hence the layer id can represent how long you have to wait for all your inputs to be ready!!
	- topological sorting puts every gate in the exact layer they need to be, nothing more, nothing less (in terms of input ready wait time).


### generalizing [[gkr]] for [[arbitrary-arithmetic-circuits]] (naive)
- the idea is to perform statement reductions from the output layer to the input layer, where the verifier can then confirm the last reduced statement on the input. 
- we do this for [[layered-arithmetic-circuits]] as follows
	- given that layer i depends on layer i + 1, we construct a relation that can get all elements in layer i but using only values from layer i + 1
	- we then prove this relation via the appropriate argument, this will lead to a reduced statement about layer i + 1
	- we continue this process recursively until we get to a reduced statement about the input layer
	- which the verifier can check directly. fin. 
- the key thing here is that we have some relation that can produce all the elements at layer i, but doesn't make use of layer i itself. 
- for the [[arbitrary-arithmetic-circuits]] layer i depends not only on layer i + 1 but potentially on all layers $j > i$
- so to generate some relation that produces all elements at layer i, we need to capture all layers $j > i$ 

- construction notes
	- a given gate is either an addition gate or a multiplication gate
	- the gate takes in two inputs
	- one of those inputs must come from layer i + 1
	- the other input can come from any layer $j > i$ 
	- hence the relation just has to have all possible combination of layers
	- $add_{i,j}(z, x, y)$ -> represents an addition gate at layer i - 1 with inputs from layer i and j respectively. 

- The relation is given as follows $$
	\begin{matrix}
	V_i(z) = \sum_{x, y \in \{0,1\}^s} add_{i+1, i+1}(z, x, y)(V_{i+1}(x) + V_{i + 1}(y)) + mul_{i+1,i+1}(z, x, y)(V_{i+1}(x) \cdot V_{i+1}(y)) + \\
	
	 add_{i+1,i+2}(z, x, y)(V_{i+1}(x) + V_{i+2}(y)) + mul_{i+1,i+2}(z, x, y)(V_{i+1}(x) \cdot V_{i+2}(y) + ... + \\ 
	 
	 add_{i+1,d}(z, x, y)(V_{i+1}(x) + V_d(y)) + mul_{i+1,d}(z, x, y)(V_{i+1}(x) \cdot V_d(y))
	\end{matrix}
$$
- running sumcheck on the above relation will lead to claims for every $V_j$ where $j > i$ 
- hence once we reach some layer $V_i$ to reduce, we'd have accumulated multiple claims for that layer.

### problems with naively generalizing [[gkr]] for [[arbitrary-arithmetic-circuits]]
- assuming that all layers have S gates
- the polynomial size for a given layer in the generalized relation is O((d - i)S)
- and the sumcheck cost is linear in polynomial size
- hence the total cost of running sumcheck for all layers is given as follows
	- $O(dS + (d - 1)S + ... + S) = O(d^2S) = O(d|C|)$ 
	- recall S is the total number of gates in a layer if we have d layers then $dS = |C|$ 
- we need to somehow reduce the size of the polynomials per round to reduce the cost of sumcheck, reducing the cost of the protocol. 


### generalizing [[gkr]] for [[arbitrary-arithmetic-circuits]] (optimal)
- assuming layer i has S gates and each gate can take only two inputs, then at most layer i is defined by 2S gates. 
- below is a relation that can still allow you compute the correct $V_i(z)$ at some point z based on layers $j > i$, but with cheaper sumcheck costs. 
- rather than considering all the gates as input, when trying to evaluate a layer's eval, we only consider the subset of gates that actually have wirings to the target layer. 
- we define $V_{i,j}$ as the subset of gates from layer $V_j$ that have wirings to gates in $V_i$ 
	- this will affect the way the $add_i$ and $mul_i$ equations are constructed. 

- the relation is given as follows
	- $$
		\begin{matrix}
		V_i(z) = \sum_{x \in \{0, 1\}^{s_i, i+1}} ( \\
			\sum_{y \in \{0, 1\}^{s_i, i+1} add_{i+1, i+1}(z, x, y)(V_{i,i+1}(x) + V_{i,i+1}(y))} \\ + ... + \sum_{y \in \{0,1\}^{s_i, d} add{i + 1, d}(z, x, y)(V_{i,i+1}(x) + V_{i,d}(y))} \\
			\sum_{y \in \{0, 1\}^{s_i, i+1} mul_{i+1, i+1}(z, x, y)(V_{i,i+1}(x) \cdot V_{i,i+1}(y))} \\ + ... + \sum_{y \in \{0,1\}^{s_i, d} mul{i + 1, d}(z, x, y)(V_{i,i+1}(x) \cdot V_{i,d}(y))})
		\end{matrix}
	$$
- ![[Pasted image 20250528155932.png]]

- to prove the [[arbitrary-arithmetic-circuits]] 
	- we'd need to prove each relation above, which will produce claims for the v_subset values. 
	- the claims will be given as hints by the prover, for the next round the verifier will need to verify the accumulated subset claims. 
		- reducing it to one claim about the full polynomial, which can then be proved via the standard virgo process. 


### performing sumcheck on the relation
- phase 1
	- we recall libra phase 1
		- we are trying to prove a relation of the following form
			- $H(a) = \sum_{b, c} f(a, b, c) \cdot v(b) \cdot v(c)$ 
		- the goal is to not materialize $f(a, b, c)$ as it is sparse and we should be able to take advantage of that sparsity. 
		- to achieve efficiency we compute the sumcheck messages in phases, first for the b variables (phase 1) and then for c variables (phase 2).
		- we perform the following rewrite
			- $H(a) = v(b) \cdot h_a(b)$ 
			- where $h_a(b) = \sum_c f(a, b, c) \cdot v(c)$
		- we turn $f(a, b, c)$ into a vector over the [[boolean-hypercube]] as follows
			- $h_a(b) = \sum_x I(a, z) \cdot f[z, b, c] \cdot v(c)$
		
		- constructing $h_a(b)$ 
			- first we initialize an empty vector $A_{h_a}$ with $2^{|b|}$ zeroes
			- we iterate over the sparse vector $f[z, b, c]$ for each entry to perform the following
				- $A_{h_a}[b] += I[z] \cdot V_c(c)$ 
		
		- once we have the table $A_{h_a}$ and $V(b)$ we just apply [[sumcheck-over-products]]

	- effect of the c variable padding for phase 1
		- what if instead we wanted to run phase 1 sumcheck on the following relation
			- $H(a) = \sum_{b, c} c_{k+1} \cdot ... \cdot c_l \cdot f(a, b, c_0, ... c_k) \cdot v(b) \cdot v(c_0, ..., c_k)$ 
		- applying the rewrite process
			- $H(a) = v(b) \cdot h_a'(b)$
			- $h_a'(b) = \sum_c c_{k+1} \cdot ... \cdot c_l \cdot f(a, b, c_0, ..., c_k) \cdot v(c_0, ..., c_k)$
		- we showed in [[variable-padding-for-sumcheck]] that variable padded sumcheck has the same claimed sum. 
			- hence $h_a(b) == h'_a(b)$ 
		- which means that as it is related to the construction of $A_{h_a}$ variable padding doesn't matter. 
	
	- how do we determine the size of the $A_{h_a}$ table
		- this should depend entirely on the size of a
		- in [[virgo++]] size of a is the same for all terms in the layer equation sum i.e. no of variables of $V_{i + 1}$ 

	- to fully solve phase 1 for [[virgo++]] we need to know the effect of sum of sums on table generation. 
		- we look at the following relation
		- $\begin{matrix} H(a) = \sum_{b,c} f_1(a, b, c) \cdot v_1(b) \cdot v_2(c) + f_2(a, b, c) \cdot v_1(b) \cdot v_3(b) + \\ ... + f_n(a, b, c) \cdot v_1(b) \cdot v_n(c) \end{matrix}$
			- where $f_1(..), f_2(..), ..., f_n(..)$ are sparse 
		- given that $v_1(b)$ is common across all we can apply the following rewrite
		- $H(a) = v_1(b) \cdot h_a(b)$
		- where  $h_a(b) = \sum_c f_1(a, b, c) \cdot v_2(c) + f_2(a, b, c) \cdot v_3(c) + ... + f_n(a, b, c) \cdot v_n(c)$ 
		- we can turn the sparse polynomials into vectors over the [[boolean-hypercube]] by extracting $I(a, z)$
		- $\begin{matrix} h_a(b) = \sum_c I(a, z) \cdot f_1[z, b, c] \cdot v_2(c) + I(a, z) \cdot f_2[z, b, c] \cdot v_3(c) \\ + ... + I(a, z) \cdot f_n[z, b, c] \cdot v_n(c) \end{matrix}$ 

		- an obvious solution is to do them one after the other as follows
			- first we set up the $A_{h_a}$ table with all zeroes
			- we also initialize the $I_a(z)$ table
			- then we start with the first pair $(f_1[z, b, c], v_2(c))$ 
				- applying the following routine $A_{h_a}[b] += I_a[z] \cdot v_2(c)$ 
			- repeat for all relevant pairs
		
- phase 2
	- in phase 2 we start to see the effect of the variable padding, we showed in [[variable-padding-for-sumcheck]] how to perform sumcheck on a variable padded polynomial. 
	- we also know that you can perform sumcheck on sums of polynomials by just adding the round messages together and applying the same challenges to each polynomial. 
	- this also works for sums of product polynomials, we just treat the product polynomial as a single polynomial (via abstraction), which reduces to the last case. 
	
	- the only thing left for phase 2 is figuring out how to build the bookkeeping tables. 
		- $\sum_{i = 0}^m \sum_c c_{k+1} \cdot ... \cdot c_l \cdot f_i(a, u, c_0, ..., c_k) \cdot t(u) \cdot v_i(c_0, ..., c_k)$ 
			- where $t(u)$ = $V_{i + 1}(u)$ = scalar
		- since we are performing [[variable-padding-for-sumcheck]] we can ignore the padded variables
		- $\sum_{i = 0}^m \sum_c f_i(a, u, c_0, ..., c_k) \cdot t(u) \cdot v_i(c_0, ..., c_k)$ 
		- we can take advantage of sparsity
		- $\sum_{i = 0}^m \sum_c I_a(z) \cdot I_u(b) \cdot f_i[z, b, c_0, ..., c_k] \cdot t(u) \cdot v_i(c_0, ..., c_k)$ 
		- we already have the table representing $v_i(..)$ 
		- we can construct $A_{f_i}$ as follows: 
			- where $A_{f_i} [c_0, ..., c_k] += I_a[z] \cdot I_u[b] \cdot t(u)$  
			- for all non-zero entries in $f$ 


### combining multiple claims into 1
- when it is time to prove any layer (except the output layer), we'd already have a set of claims of the layer or subsets of the layer. 
	- specifically if we try to prove layer i, we have claims from $V_{0, i}, V_{1, i}, ..., V_{i-1,i}, V_{i-1,i}'$ 
		- we have two claims for $V_{i-1,i}$ 
- the objective is to prove that all claims are valid. 

- first we focus on proving a single subset claim. 
	- we have the following claim $V_{j, i}(r^{(j,i)}) = H_{j,i}$ and $V_{j,i} \in V_i$ 
	- we need to prove two things
		1. $V_{j,i}$ was constructed correctly from $V_i$ based on the circuit description
		2. Evaluating this subset $V_{j,i}$ at $r^{(j,i)}$ gives the target value $H_{j,i}$ 

	- to extract the subset, we can construct a function $C_{j,i}(z, x) : \{0,1\}^{s_{j,i}} \times \{0,1\}^{s_i}$ 
		- where z represents the index of subset and x represents the index in the main polynomials
		- $C_{j,i}(z, x) = 1$  if $V_{j,i}[z] == V_i[x]$ i.e. they represent the same gate
		- $C_{j,i}(z, x) = 0$  otherwise
	- we can compute the sum of subset values as follows
		- $\sum_{z,x \in {0,1}} C_{j,i}[z, x] \cdot V_i(x)$ 
		- rough intuition
			- it start with the first subset entry e.g. 0
			- then it pairs 0 with every entry in the main array $V_i(x)$ 
			- if the subset has an entry at index 0 then for some value of x, $C_{j,i}[z, x] = 1$ 
				- allowing $V_i(x)$ to contribute to the sum. 
	- to fully prove the subset claim, we also have to prove correct evaluation at $r^{(j,i)}$ 
		- evaluation can be seen as a dot product of the $y$ values and the lagrange basis 
		- subset entries are already ordered by $z$ i.e. $z_0$ is the first entry, $z_1$ the second, ...
		- as long as we multiply the right subset entry with the right basis element we should get the same evaluation
		- this leads to the following function
			- $H_{j, i} = \sum_{z,x \in \{0, 1\}} I_r^{(j,i)}(z) \cdot C_{j,i}[z, x] \cdot V_i(x)$ 
				- where $I_r(z)$ represents the Lagrange basis generator gotten from $r^{(j,i)}$ 
			- rough intuition
				- z tells us the current subset entry we are working with
				- then we have found the entry $C_{j, i}[z, x] = 1$
				- hence we contribute $I_r(z) \cdot V_i(x)$ to the sum
				- as long as $I_r(z)$ produces the correct basis element, the above across all z will lead to the evaluation of $V_{j, i}$ 
	- conclusion
		- running sumcheck on:
			- $H_{j, i} = \sum_{z,x \in \{0, 1\}} I_r(z) \cdot C_{j,i}[z, x] \cdot V_i(x)$ 
		- is sufficient to prove the subset claim $H_{j,i} = V_{j, i}(r^{(j,i)})$

- next we need to handle proving multiple claims
	- we can do this via [[batch-sumcheck]] 
	- we sample a random $\alpha_i$ for every claims, perform a random linear combination and prove the final sumcheck.
	- as follows: 
		- sample $\alpha_{0,i}, \alpha_{1,i}, ..., \alpha_{i-1, i}, \alpha_{i-1, i}'$ 
		- compute the new claimed sum as follows:
			- $H = \alpha_{0, i} \cdot V_{0, i}(r^{(0,i)}) + ... + \alpha_{i-1, i} \cdot V_{i-1, i}(r^{(j, i)}) + \alpha_{i-1, i}' \cdot V_{i-1, i}(r^{(j, i)'})$ 
		- the sumcheck body: 
			- $\begin{matrix} (\sum_{j = 0}^{i - 1} \alpha_{j, i} \sum_{z,x \in \{0, 1\}} I_r^{(j,i)}(z) \cdot C_{j,i}[z, x] \cdot V_i(x)) \\ + \alpha_{i-1, i}' \cdot \sum_{z, x \in \{0,1\}} I_r^{(i-1, i)} \cdot C_{i-1, i}[z, x] \cdot V_i(x) \end{matrix}$ 
			- given that $V_i(x)$ is common across all terms we can rewrite:
			- $\sum_x V_i(x)g_i(x)$
			- $g_i(x) = \begin{matrix} (\sum_{j = 0}^{i - 1} \alpha_{j, i} \sum_{z,x \in \{0, 1\}} I_r^{(j,i)}(z) \cdot C_{j,i}[z, x]) \\ + \alpha_{i-1, i}' \cdot \sum_{z, x \in \{0,1\}} I_r^{(i-1, i)} \cdot C_{i-1, i}[z, x] \end{matrix}$ 

- computing the $g_i(x)$ bookkeping table
	- initialize the table to the all zeros tables indexed via x
	- for each subset
		- compute the basis vector indexed via z, based on r call it $G_j$
		- for every entry in $C_{j,i}[z, x]$ that is non-zero
			- compute: $A_{g_i}[x] += \alpha_{j, i} \cdot G_j[t]$

- [ ] clean up the combining multiple claims to 1, there is something deeper going on here, also look into jagged poly (feel they must be related).