template<typename Curve_, size_t log_poly_length = CONST_ECCVM_LOG_N>
class bb::IPA< Curve_, log_poly_length >
IPA (inner product argument) commitment scheme class.
This implementation of IPA uses the optimized version that only multiplies half of the elements of each vector in each prover round. The implementation uses:
- An SRS (Structured Reference String) \(\vec{G}=(G_0,G_1...,G_{d-1})\) with \(G_i ∈ E(\mathbb{F}_p)\) and \(\mathbb{F}_r\) - the scalar field of the elliptic curve as well as \(G\) which is an independent generator on the same curve.
- A polynomial \(f(x)=\sum_{i=0}^{d-1}f_ix^i\) over field \(F_r\), where the polynomial degree \(d-1\) is such that \(d=2^k\)
The opening and verification procedures expect that there already exists a commitment to \(f(x)\) which is the scalar product \([f(x)]=\langle\vec{f},\vec{G}\rangle\), where \(\vec{f}=(f_0, f_1,..., f_{d-1})\)
The opening procedure documentation can be found in the description of compute_opening_proof_internal . The verification procedure documentation is in verify_internal
- Template Parameters
-
- Originally we have two vectors \(\vec{a}\) and \(\vec{b}\), whose product we want to prove, but the prover can't just send vector \(\vec{a}\) to the verifier, it can only provide a commitment \(\langle\vec{a},\vec{G}\rangle\)
- The verifier computes the \(C'=C+\langle\vec{a},\vec{b}\rangle\cdot U\) to "bind" together the commitment and the evaluation ( \(C=\langle\vec{a},\vec{G}\rangle\) is the commitment and \(U=u⋅G\) is the auxiliary generator independent from \(\vec{G}\))
- The prover wants to reduce the problem of verifying the inner product of \(\vec{a}\), \(\vec{b}\) of length \(n\) to a problem of verifying the IPA of 2 vectors \(\vec{a}_{new}\), \(\vec{b}_{new}\) of size \(\frac{n}{2}\)
- If \(\vec{a}_{new}=\vec{a}_{low}+\alpha\cdot \vec{a}_{high}\) and \(\vec{b}_{new}=\vec{b}_{low}+\alpha^{-1}\cdot
\vec{b}_{high}\), then \(\langle \vec{a}_{new},\vec{b}_{new}\rangle = \langle\vec{a}_{low},\vec{b}_{low}\rangle +
\alpha^{-1}\langle\vec{a}_{low},\vec{b}_{high}\rangle+\alpha \langle \vec{a}_{high},\vec{b}_{low}\rangle +
\langle\vec{a}_{high},\vec{b}_{high}\rangle=
\langle\vec{a},\vec{b}\rangle+\alpha^{-1}\langle\vec{a}_{low},\vec{b}_{high}\rangle+\alpha \langle
\vec{a}_{high},\vec{b}_{low}\rangle\), so if we provide commitments to the cross-terms \(\langle\vec{a}_{low},\vec{b}_{high}\rangle\) and \(\langle \vec{a}_{high},\vec{b}_{low}\rangle\), the verifier can reduce initial commitment to the result \(\langle \vec{a},\vec{b}\rangle U\) to the new commitment \(\langle
\vec{a}_{new},\vec{b}_{new}\rangle U\)
- Analogously, if \(\vec{G}_{new}=\vec{G}_{low}+\alpha^{-1}\vec{G}_{high}\), then we can reduce the initial commitment to \(\vec{a}\) by providing \(\langle\vec{a}_{low},\vec{G}_{high}\rangle\) and \(\langle
\vec{a}_{high},\vec{G}_{low}\rangle\). \(\langle \vec{a}_{new},\vec{G}_{new}\rangle =
\langle\vec{a},\vec{G}\rangle+\alpha^{-1}\langle\vec{a}_{low},\vec{G}_{high}\rangle+\alpha \langle
\vec{a}_{high},\vec{G}_{low}\rangle\)
- We can batch the two reductions together \(\langle \vec{a}_{new},\vec{b}_{new}\rangle U + \langle
\vec{a}_{new},\vec{G}_{new}\rangle= \langle\vec{a},\vec{b}\rangle U+ \langle\vec{a},\vec{G}\rangle+
\alpha^{-1}(\langle\vec{a}_{low},\vec{b}_{high}\rangle U +\langle\vec{a}_{low},\vec{G}_{high}\rangle) +\alpha (\langle
\vec{a}_{high},\vec{b}_{low}\rangle U+\langle \vec{a}_{high},\vec{G}_{low}\rangle)\)
After \(k\) steps of reductions we are left with \(\langle \vec{a}_{0},\vec{b}_{0}\rangle U + \langle
\vec{a}_{0},\vec{G}_{s}\rangle= a_0 b_0 U+a_0G_s\). The prover provides \(a_0\). The independence of \(U\) and \(\vec{G}\) from which we construct \(G_s\) ensures that \(a_0\) is constructed from \(\vec{a}_k=\vec{p}\) correctly, while the correctness of \(a_0 b_0 U\) ensures that the polynomial opening is indeed \(f(\beta)\)
The old version of documentation is available at Old IPA documentation
Definition at line 95 of file ipa.hpp.
1.9.8