# Notes - August 31

## Nat's Shifting Notes

Nat's [Shifting](https://hackmd.io/8o74MXKMTZig61WkzcntcQ) notes provides an arugment for providing a Shift that removes a commitment that is included in [Filter](https://github.com/spaceandtimelabs/proofs/blob/main/docs/protocols/PIPs_Query/pips_subquery_filter.md).

Specifically, let ${\mathbf{a}}$ be a vector of length $n$. Now, if, in a larger protocol, it is necessary to use a shift of ${\mathbf{a}}$, say ${\mathbf{a'}}$. WLOG, define ${\mathbf{a'}}[i] = {\mathbf{a}}[i+1 \pmod{n}]$.

In particularly, we can view a shift as a permutation: ${\mathbf{a'}} = {\mathbf{S}} {\mathbf{a}}$. This particular shift has
${\mathbf{S}} = \begin{pmatrix} {\mathbf{e_1}}\\ {\mathbf{e_2}}\\ \vdots \\ {\mathbf{e_{n-1}}}\\{\mathbf{e_0}}
\end{pmatrix}$ where ${\mathbf{e_i}}$ is the $i$th standard basis vector.

If we wish to use this shift as a part of a PIP, then it is used in an equation that contains vectors that are either already known to the Verifier, or will be sent. Examples:
- $\langle {\mathbf{b}}, {\mathbf{a'}}\rangle = c$
- ${\mathbf{b}} \boxtimes {\mathbf{a'}} = {\mathbf{c}}$.

In both of these cases we can require the computation of ${\mathbf{a'}}$ to the Verifier instead of having the Prover send the commitment of ${\mathbf{a'}}$.

Note that ${\mathbf{Sa}}$ has complexity $O(n)$; due to specific choice of ${\mathbf{S}}$. Additionally, ${\mathbf{S}}$ has to be known (and easily constructable) by the Verifier. Moreover, wouldn't the commitment to ${\mathbf{Sa}}$ be necessary for the proof checks?