# nova lookup arguments * Using lemma 5 from https://eprint.iacr.org/2022/1530.pdf give us a lookup argument that can liveinside r1cs. * This means we could have a lookup argument for r1cs * $\sum(\frac{1}{x+a_i}) = \sum(\frac{m_i}{x + b_i}$) * $a_i \subseteq b_i$ if $m_i$ exists in the feild and is a rational function * We have to remove multplicities of values ## r1cs version ### Halo2 lib subset argument approach * https://zcash.github.io/halo2/design/proving-system/lookup.html#technique-description * halo2 lib has lookup arguments by permuting and removing dulicates * We can apply that here * We allow hte prover to supply a permutation argument for $A$ such that like values are vertically aligned * the prover commmits to $a$ and $a'$ we use this to generate challenge $\beta$ we then check $z_{i+1} = z_i * \frac{a_i+\beta}{a'_i+\beta}$ * We can rearrange this to $z_{i+1}* (a'_i + \beta) - z_i * (a_i + \beta) = 0$ * Using roots of unity we can represent this as polynomials that are shifted $z(wx) *(a'(x) + \beta) - z(x) * (a(x) + \beta) = 0$ * Instead of using the inverser root representation we can use the permutation based approach from halo2 on our already sorted polynomial $(A'(x) - B(x))(A'(x) - A'(wx)) = 0$ * We can use pedersen commitments to commit to the $a_i$ and $a'_i$ this will allow us to avoid o(A + B) work in the verifier. Instead we can just open these commitments using bullet proofs (or something else ?) at the random point which is log(n) work for the verifier ### Randomness * Randomeness can be generated by hashing the polynomial commiemnt to $a$ , $b$ and $a'$ * The randomness is not required until the proofs are being verified so this could happen in the nova verifier or inside the r1cs * If its being done inside the r1cs we need to seperate the witness into values that depend on r in on colume and values that don't in another ### Relaxed Lookup TODO: