# Morgana: simple reduction

Spartan reduces the R1CS constraint satisfaction problem to evaluating a matrix using Spark:

$E_M=M(r_x,r_y)$

Spark then reduces the problem to evaluations of multi-variate polynomials (no matrix anymore)
$E_{row}(r_0,...,r_n)=\sum\limits_{i_j\in\{0,1\}}(\quad row(i_0,..,i_n)\cdot eq(r_x,row(i_0,..,i_n)) \quad )eq(r_0,..,r_n,\quad i_1,..,i_n)$

$E_{row}=\sum\limits_{i_j\in\{0,1\}}(\quad col(i_0,..,i_n)\cdot eq(r_x,col(i_0,..,i_n)) \quad )eq(r_0,..,r_n,\quad i_1,..,i_n)$

Optimise the above type of MLE evaluations will then lead to optimization of Spartan. So no need to start with matrix, optimise MLE of polynomial coming from an array would be easier. This blog give a more simple version of demonstrate the structure of $E_{row}=eq(r_x,row[r_z])$, which can be used to create a recursive method to do the computation.

## $E_{row}$

let's expand this equation fully, use binary representation

set $[a_0,a_1,..,a_q]=[i_{k},..i_n]$ namely $q=n-k$

index $[i_0,..,i_n]$ is represeted as $[i_0,..,i_{k-1},a_0,..,a_q]$

$E_{row}=\sum\limits_{i_j\in\{0,1\}}(\quad row(i_0,..,i_n)\cdot eq(r_x,row(i_0,..,i_n)) \quad )eq(r_0,..,r_n,\quad i_0,..,i_n)$

subtitute $[i_0,..,i_n]$ with $[i_0,..,i_{k-1},a_0,..,a_q]$

$=\sum\limits_{i_j,a_h\in\{0,1\}}(\quad row(i_0,..,i_{k-1},a_0,..,a_q)\cdot eq(r_x,row(i_0,..,i_{k-1},a_0,..,a_q)) \quad )eq(r_0,..,r_n,\quad i_0,..,i_{k-1},a_0,..,a_q)$

$=\sum\limits_{a_h\in\{0,1\}} eq(r_{k},..,r_n,\quad a_0,..,a_q)$
$\cdot \underbrace{\sum\limits_{i_j\in\{0,1\}}(\quad row(i_0,..,i_{k-1},a_0,..,a_q)\cdot eq(r_x,row(i_0,..,i_{k-1},a_0,..,a_q)) \quad )eq(r_0,..,r_k,\quad i_0,..,i_k)}_{f^{(a_0,...,a_q)}(r_0,..,r_{k-1})}$

create a table for each $a_0,...,a_q$ to map index $i_0,...,i_k$ to the value $row(i_0,..,i_{k-1},a_0,..,a_q)\cdot eq(r_x,row(i_0,..,i_{k-1},a_0,..,a_q))$, call it function $f^{(a_0,...,a_q)}$, working on boolean hypercube $[i_0,...,i_{k-1}]$, this becomes a new table mapping sub-table to values $E_{row}$, let's give its multilinear extension a notation $E_{(a_0,...,a_q)}$

then
$E_{row}(r_0,..,r_m)=\sum\limits_{a_h\in\{0,1\}} eq(r_{k},..,r_n,\quad a_0,..,a_q)\sum_{i_j\in\{0,1\}}f^{(a_0,...,a_q)}(i_0,..,i_{k-1})\cdot eq(r_0,..,r_{k-1},i_0,..,i_{k-1})$
$=\sum\limits_{a_h\in\{0,1\}} eq(r_{k},..,r_n,\quad a_0,..,a_q)\cdot E_{(a_0,...,a_q)}(r_0,..,r_{k-1})$

this step can go recursively, which means split $E_{(a_0,...,a_q)}$ further

creating $f^{(a_0,...,a_q)}$ is lookup table operation, in total $2^{q+1}$ smaller tables built from the big table

for each smaller table, the cached info is $eq(r_{k},..,r_n,\quad a_0,..,a_q)$ and $E_{(a_0,...,a_q)}(r_0,..,r_{k-1})$

when a prover get a input instance for a circuit
- run a VM circuit that compute each sub-table's cached info, each subtable matrix, lookup arguments for splitting process (the is the circuit key,maybe end up in commitment form, then its the verification key)
- Verifier verifies the lookup argument, the sub-circuit (using sub-table evaluations) sub-witness commitments?

## VM circuit sample implementation

In the first step of Morgana, a VM circuit takes a circuit $C$ and its inputs/outputs (witness) as inputs. The circuit $C$ is the monolithic circuit for the computation to be verified. The VM circuit output cached sparse matrixs and their evaluations (maybe in commitment format)

In this section a sample implementation of this VM, it's sparse matrix evaluation circuit is described, an additionaly explanation for the circuit in 1.3.5 chapter of Morgana.

inputs:
$r$ is the evaluation points, when the VM circuit takes inputs of circuit $C$, its evaluation points is determined.
$u$ cached sparse description, the sizes of the sparse matrixs are decided by allocator. The length of $u$ is how many rounds for recursively compute the evaluation of the array $u_i$ stores the information of sparse arrays of the same size, their evaluations

explanation of the code:


$n$ is the length of $u_i$, for example, an array with length $2^8$, split it to 4 admissive arrays, each with length $2^6$, $n=4$ --> $u_1$

these 4 admissive array can be further split to 8 arrayes with length 4, $n=8$, suppose this the the smallest addmissive sets. ---> $u_0$

each of these admissive array will get its evaluation. for $u_0$, only $Sp$, for $u_i,i>0$, they have $Rec$

for round 0: $u_0$ is $Sp$, computes its evaluation:$E_{(a_0,...,a_q)}(r_0,..,r_{k-1})=\underbrace{\sum\limits_{i_j\in\{0,1\}}(\quad row(i_0,..,i_{k-1},a_0,..,a_q)\cdot eq(r_x,row(i_0,..,i_{k-1},a_0,..,a_q)) \quad )eq(r_0,..,r_k,\quad i_0,..,i_k)}_{f^{(a_0,...,a_q)}(r_0,..,r_{k-1})}$, there will be total number of $2^q$ evaluations

$i$ is $[a_0,...,a_q]$

for round 1: $u_1$, assume its sparse matrix size is $2^{k+l}$, use $a'$ as equivalent notation for $a$, the evalation is computed from $Rec$ $E_{(a'_0,...,a'_{q-l})}(r_0,..,r_{k+l-1})=\sum\limits_{i_j\in\{0,1\}}(\quad row(i_0,..,i_{k+l-1},a'_0,..,a'_{q-l})\cdot eq(r_x,row(i_0,..,i_{k+l-1},a'_0,..,a'_{q-l})) \quad )$
$\cdot eq(r_0,..,r_{k+l-1},\quad i_0,..,i_{k+l-1})$,

recursive compute:
$E_{(a'_0,...,a'_{q-l})}(r_0,..,r_{k+l-1})=\sum\limits_{a_h\in\{0,1\} }eq(r_k,...,r_{k+l-1},a_0,...,a_l)\cdot E_{(a_0,...al,a'_0,...,a'_{q-l})}$

is the code

## circuit with branching example
***step1: a VM circuit, take another circuit c and its witness as input, generate cached sparse matrixs and their evaluations***

***step2: the cached sparse matrixs are the actually used circuit, verify them use spartan, and also use spartan to verify VM circuit execution***

$f=a\cdot \underbrace{(b*d+b*g)}_{pre-compile_0}+(1-a)\cdot \underbrace{((c*e)*c*c)}_{pre-compile_1}$, $a$ is the branching condition, the R1CS circuit only include pre-compile circuits, no $a$, no intersection between different pre-compilers' circuits

R1CS encoding:
G0: $z_{b} * z_{d} = z_{bd}$
G1: $z_{b} * z_{g} = z_{bg}$
G2: ($z_{bd}+z_{bg}) * 1 = z_{bd+bg}$
G_3:$0*0=0$
G4: $z_{c} * z_{e} = z_{ce}$
G5: $z_{ce} * z_{c} = z_{cec}$
G6: $z_{cec} * z_{c} = z_{cecc}$
G_7:$0*0=0$

witness $z:[1,z_{b},z_{d},z_{bd},z_{g},z_{bg},z_{bd+bg},z_c,z_{e},z_{ce},z_{cec},z_{cecc}]$, with length 8

matrix A:

|1|$z_{b}$|$z_{d}$|$z_{bd}$|$z_{g}$|$z_{bg}$|$z_{bd+bg}$|_|1|$z_c$|$z_{e}$|$z_{ce}$|$z_{cec}$|$z_{cecc}$|_
| -------- | -------- | -------- |-------- |-------- |-------- |-------- |--------|--------|--------|--------|--------|--------|--------|--------|
| 0 | 1 | 0 |0|0|0|0|0||
| 0 | 1 | 0 |0|0 |0|0|0||
| 0 | 0 | 0 |1|0|1|0|0||
| 0 | 0 | 0 |0|0|0 |0|0||
| | | ||| |||0|1|0|0|0|0|0
| | | ||| |||0|0|0|1|0|0|0
| | | ||| |||0|0|0|0|1|0|0
| | | ||||||0|0|0|0|0|0|0

just taking matrix A as example, same trick applies to B and C

$val(k)$
| value index k | value in Matrix |
| -------- | -------- |
| 000 | 1 |
| 001 | 1 |
| 010 | 1 |
| 011 | -1 |
| 100 | 1 |
| 101 | 0 |
| 110 | 0 |
| 111 | 0 |

$row(k)$
| value index k | value row index in Matrix |
| -------- | -------- |
| 00 | 0 |

splitting to 2 sub-tables, $f^0,f^1$

## loop circuit e