# Nat and Marvin Discussion (9/1)

> ``we can require the computation of a′ to the Verifier instead of having the Prover send the commitment of a′``
>
> **Nat:** This isn't correct. We get the verifier to compute b' := S^T b (the random challenge vector, but shifted in the opposite direction). Correct me if I'm wrong, but with our Halo-style inner product, neither party has to compute a commitment to this.
> Then in the case of the inner product we have the equality <b, a'> = <b', a> = c. In the case of expressions/hadamard, I haven't worked it out yet (so I can go ahead and do that) but I suspect and hope that since the reduction is Hadamard --> sum-check --> inner product check <a, u> where u is known to the verifier, that we'll get something similar where a Hadamard check on a' ultimately reduces to <a, u'>.
>
> > **Marvin:** In the cases I am thinking of, ${\mathbf{a}}$ and ${\mathbf{b}}$ is already known to the Verifier, or can be assumed is sent to the Verifier along with the proof. I may be wrong. Which is why computing ${\mathbf{b'}}$ vs ${\mathbf{a'}}$ on the Verifier's side seemingly makes little difference on which.
> > > **Nat:** It makes a difference in aggregate. For the prover to compute commitments to shifts of $a_1, a_2, \ldots, a_k$ requires an extra $k$ multiexponentiations. In that case the verifier would still only have to compute two commitments, one to $\mathbf{b}$ and one to $\mathbf{b'}$.
> > > > **Marvin:** Given this context: reasonable.

> ``Moreover, wouldn’t the commitment to Sa be necessary for the proof checks?``
>
> **Nat:** I'm not sure. I was pretty :disappointed: when I realized it made checks like w = z - 𝛾z' almost trivial (and so this might not be sound), but I don't think such checks end up being necessary.
>
> > **Marvin:** The Hadamard implementation seems that it would need ${\mathbf{Sa}}$ or ${\mathbf{Sb}}$ where it's been used. I could be wrong though. Soundness is always the worry...
> > > **Nat:** The Hadamard implementation can be changed. It doesn't even work with $\mathbf{a}$ or $\mathbf{b}$ directly. It requires the prover to compute a sum using multilinear extensions $f_a$ and $f_b$, but these are not committed to using expensive Pedersen commitments. The final check involves inner product arguments that $f_a(r) = \langle \mathbf{a}, \mathbf{u} \rangle$ (and similar for $b$ and $a \boxtimes b$) but $\mathbf{u} = [\chi_1(r), \ldots, \chi_n(r)]$, so $f_{a'}(r)$ is just $\langle \mathbf{a}, \mathbf{u'} \rangle$ where $\mathbf{u'} = [\chi_n(r), \chi_1(r), \ldots, \chi_{n-1}(r)]$
> > > > **Marvin:** True. I'll accept this for the moment as it depends on the specific implementation.

> **Nat:** In the case of the filter, we compute the commitment to y = z', but then the check w = z - 𝛾z' ends up mostly just checking that y was indeed a commitment to ths shift of z.
> So I think there's two kinds of checks involving shifts in our current proofs: one is for well-formedness of the shift (which we can get rid of, as we're not commiting to any alleged shifts, we're checking the shifts directly). the second kind of check is a statement involving the shift of z and a vector d unrelated to z. then checking that an expression, for example d ⊠ z', can be checked as a statement relating d and z.
>
> > **Marvin:** I still feel like the commitment to the shift is necessary as it is part of the verification proof. Whether it is ${\mathbf{S^T b}}$ or ${\mathbf{Sa}}$. Halo gets around the issue by having the vector ${\mathbf{b}}$ known (in their case powers of $x$), but that essentially uses that the Verifier knows the commitment for ${\mathbf{b}}$.
> > > **Nat:**
> > > `the commitment to the shift is necessary as it is part of the verification proof.`
> > > My point with the Hadamard proof is that I don't think it actually is necessary to the verification proof.
> > > > **Marvin:** In that case, I think so.
> > >
> > > `the Verifier knows the commitment for ${\mathbf{b}}$.`
> > > Okay, that's good to know. We still get an aggregated benefit from doing this (see first comment). The verifier knows (computes) the commitment to $\mathbf{b} = [1, x, x^2, \ldots, x^{n-1}]$. This is the part of verification that's $O(n)$. If the verifier also has to compute the commitment to $S^T \mathbf{b}$ then that's fine, they can do that also since they know it's a commitment to $[x^{n-1}, 1, x, \ldots, x^{n-2}]$
> > > > **Marvin:** The note about the complexity is more of a reference concerning the specific choice ${\mathbf{S}}$. During the meeting on Wednesday, Jay mentioned that this could be done for any Matrix, or potentially $\log$-space matrices. I think, that this is only viable for matrices that can be easily conveyed to the Verifier. So, for shift, reverse, shift by 2...etc I think this would be okay.
> > > > For matrices with more than $n$ non-zero entries, I'm not sure.