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