Minimal Viable Prover

Below is an inefficent Prover protocol. Implement a Rust-code with the most efficient prover possible. You can use lambdaworks or arkworks. Use the Curve: BLS12-381 and assume $n=2^{17}$. we refer to base field as $\mathbb{F}_q$ and scalar field as $\mathbb{F}_r$.

Setup

  1. Generate a SRS in lagrange basis
    a. generate random $\tau\in \mathbb{F}_r$ and compute    $$\{1,\tau,\tau^2,\ldots\tau^{2n-1}\}$$  
    b. generate a random group element $G\in \mathbb{G}_1$ of BLS12-381 and compute the SRS in monomial basis    $$[G]_{SRS} = \{G,\tau\cdot G,\tau^2\cdot G,\ldots\tau^{2n-1}\cdot G\}\equiv\{G_0,G_1,\ldots G_{2n-1}\}$$    
    c. convert it into a Lagrange basis

  2. Generate random polynomial with $c_i\in\mathbb{F}_r$ in Lagrange basis    $$c^{eval}_{2n} = \{c_0,c_1,\ldots,c_{2n-1}\}$$

  3. prover gets $[G]^{Lag}_{SRS}$ and $c_{2n}^{eval}$ at the end of setup.

Prover

  1. **Witness**: Let $x_i\in \mathbb{F}_r$ (you can use random field elements) for $i=0,1\ldots n-1$    $$f_i = Hash(x_i) \ ; \ f_i\in \mathbb{F}_r$$

  2. Now we want to commit to the witness as follows. Convert the vector of $f_i$ into a vector of length $2n$ using an FFT$$f^{eval}_{2n} = FFT_{2n}[f_0, f_1,\ldots f_{n-1}||0_{n}]$$

  3. Compute the commitment\begin{align}G_{comm} = & (c^{eval}_{2n} \circ f_{2n}^{eval})^T\cdot[G]^{Lag}_{SRS}\end{align}The $\circ$ refers to Hadamard product, and the $\cdot$ is a Multiscalar multiplication.