feat(nifs): `compute_F`

[cyphersnake]

fn compute_F(
    beta: F,
    delta: F,
    w: PlonkWitness,
    S: PlonkStructure // S.gates
) -> UnivariatePoly<F> {
   // evaluate over t+1 points
   // do ifft to get coefficient form
   // 1. Take gates, eval for witness to get f_i(w)
   // 2. Calc pow_i(\beta + X * \delta) over X={1,w',w'^2,...}
   // 3. pow_i()*f_i(w) over X={1,w',w'^2,....}
   // 4. ifft
   todo!()
}

[cyphersnake]

$$F(X)=\sum{i=0}^{n-1}pow{i}(\boldsymbol{\beta}+X\cdot\boldsymbol{\delta})f_i(w)$$

[chaosma]

Define an internal function to calculate this with complexity $O(n)$:

$$\sum{i=0}^{n-1}pow{i}(\beta_1,\cdots,\beta_t)v_i$$

Here the $(\beta_1,\cdots,\beta_t)$ can be of the form $(\beta_1+\alpha_i\delta_1,\cdots,\beta_t+\alpha_i\delta_t)$ for different points $\alpha_i$ in case of compute_F. Or it can be of the form $(\beta_1+\alpha\delta_1,\cdots,\beta_t+\alpha\delta_t)$ for some fixed $\alpha$ in compute_G

 // suppose  n = values.len()
// t = beta.len() with t = log(n)
 // this algorithm gives O(n) complexity
//  values = {v_0,...,v_{n-1}}
fn random_linear_combination(beta: Vec<F>, values: Vec<F>) -> F {

}

[chaosma]

Define an internal function to evaluate all $v_i$ from $f_i$. Suppose there are $m$ gates, and $n$ rows. We convert it to a size $m\cdot n$ vector $(fi){i=0}^{m\cdot n-1}$. Then we evaluate them f_i(witness)=v_i to become the valuation vector {v_i}.

// here the witness can be
// (1) in compute_F, it is the witness of relaxed plonk instance
// (2) in compute_G, it is some rlc of witnesses: sum_i L_i(gamma)w_i, each w_i is the witness of one of the instances
fn evaluate_all_gates(S: &PlonkStructure<C>, witness: Vec<F>) -> Vec<F> {

}

[chaosma]

Define a new data evaluation domain instead of PlonkEvalDomain, since we don't have cross term anymore:

pub struct ProtogalaxyEvalDomain {
            num_advice,
            num_lookup,
            selectors,
            fixed,
            challenges,
            W,
}

[cyphersnake]

Define a new data evaluation domain instead of PlonkEvalDomain, since we don't have cross term anymore:

The new domain will repeat the old one almost completely. It would be better to generalize the domains to a single type later, simplifying index handling. However, it's not a priority right now, so I'll just fill the W2s with a blank, which won't affect the result. Let me know if I've overlooked something here

[cyphersnake]

Define an internal function to evaluate witness

https://github.com/snarkify/sirius/pull/279/files

@chaosma

[cyphersnake]

Within the framework of the task (especially the part that evaluate_witness) we need a real circuit for testing and evaluating the performance of the solution. The point is that the approach to counting and parallelization of calculations is very different depending on performance.

That's why at this stage I plan to create a separate repository where I will copy real circuits from other repositories (they are not imported normally) and use them in tests