IPA in Bulletproof, a rough description

Building blocks

Vector Commitment on elliptic curve, useful for its additive homomorphic

Statement

$$\{(\textbf{g,h}\in \mathbb{G}^n, P \in \mathbb{G}, c \in \mathbb{Z}_p; \textbf{a,b}\in \mathbb{Z}_p^n): P=\textbf{g}^{\textbf{a}}\textbf{h}^{\textbf{b}} \wedge c=<\textbf{a},\textbf{b}>\}$$

Proving

the strategy is recursive proof. For every recursive step, keep the public statement in the same format, but the vector length, together with the number of the base points, become half, and after \(\log n\) rounds of recursive, the remaining statement \(P=\textbf{g}^{\textbf{a}}\textbf{h}^{\textbf{b}}u^c\) will become a vector commitment for single length vectors \(a\) and \(b\).

before recurring

recurring

inputs

the recursive steps are aiming to reduce \(n\)

for \(n>1\) prover does the “shrinking step”, shrink the group base vectors to half, with a randomness sent by the verifier

\(\textbf{a},\textbf{b}\) will also shrink to new vectors \(\textbf{a’}, \textbf{b’}\).

after shrinking the vectors to \(\textbf{a’}, \textbf{b’}\), their inner product will also change. We need to provide auxiliary computation to keep the same format of the inputs, so we can continue the recursion. \(L,R\) here is to keep \(P’\) such that \(P’=\textbf{g}^{\textbf{a’}}\textbf{h}^{\textbf{b’}} u^{<\textbf{a’},\textbf{b’}>}\)

at the end of the recursion

TO DO: batch proof in Halo