Simpler inner product argument

Note that this protocol is not zero-knowledge, but can be trivially made so. I am also not claiming to have come up with this, this design (roughly) appears in several papers I've seen.

URS: \(n = 2^k\), \(\mathbf{G}_k \in \mathbb{G}^n\), \(U \in \mathbb{G}\).

• Prover sends \(P\), a commitment to \(p(X) = \mathbf{a}_{k,0} + \mathbf{a}_{k,1} X + ... \mathbf{a}_{k,n-1} X^{n - 1}\) i.e. \(P = \langle \mathbf{a}_k, \mathbf{G}_k \rangle\).
• Verifier samples \(x\).
• Prover sends \(v = p(x) = \langle \mathbf{a}_k, \mathbf{x}^n \rangle\).
• Prover and verifier set \(P' = P - [v] \mathbf{G}_{k,0}\).
• Verifier samples \(z\).
• Prover and verifier initialize \(\mathbf{b}_k = \mathbf{x}^n\).
• In \(k\) rounds, starting in round \(r = k-1\) and ending at \(r = 0\), we do the following:
  • Assert: \(\mathbf{G}_{r+1}, \mathbf{a}_{r+1}, \mathbf{b}_{r+1}\) are of length \(2^{r+1}\).
  • Prover sends \(L_{r}, R_{r}\) such that
    • \(L_{r} = \langle \mathbf{a}_{r+1,\text{hi}}, \ \mathbf{G}_{r+1,\text{lo}} \rangle + [z \cdot \langle \mathbf{a}_{r+1,\text{hi}}, \mathbf{b}_{r+1,\text{lo}} \rangle] U\)
    • \(R_{r} = \langle \mathbf{a}_{r+1,\text{lo}}, \ \mathbf{G}_{r+1,\text{hi}} \rangle + [z \cdot \langle \mathbf{a}_{r+1,\text{lo}}, \mathbf{b}_{r+1,\text{hi}} \rangle] U\)
  • Verifier samples \(u_{r}\).
  • Prover and verifier set \(\mathbf{b}_r = \mathbf{b}_{r+1,\text{lo}} + u_{r} \cdot \mathbf{b}_{r+1,\text{hi}}\)
  • Prover and verifier set \(\mathbf{G}_r = \mathbf{G}_{r+1,\text{lo}} + u_{r} \cdot \mathbf{G}_{r+1,\text{hi}}\)
  • Prover sets \(\mathbf{a}_r = \mathbf{G}_{r+1,\text{lo}} + u_{r}^{-1} \cdot \mathbf{G}_{r+1,\text{hi}}\)
  • Assert: \(\mathbf{G}_r, \mathbf{a}_r, \mathbf{b}_r\) are of length \(2^r\).
• Prover sends \(c = \mathbf{a}_{0,0}\).
• Verifier checks
  \[ \left( \sum\limits_{j=0}^{k - 1} u_{j}^{-1} L_j \right) + P' + \left( \sum\limits_{j=0}^{k - 1} u_{j} R_j \right) = [c] \mathbf{G}_{0,0} + [cz\mathbf{b}_{0,0}] U. \]