Understanding Inner Product Argument

The Bulletproofs paper introduces a log-sized inner-product argument and thereafter constructs the state-of-the-art range proof protocol in non-trusted setup setting. We will discuss the inner-product argument and how it motivated the idea of recursive proof systems like Halo. We assume basic familiarity of the reader with elliptic curve group operations and Pedersen commitments.

Introduction

Suppose you have some secret information (say, passkeys to two lockers) encoded in a couple of vectors a,b\textbf{a}, \textbf{b}. You (the prover) want to convince the government (the verifier) that you are the owner of those lockers, so naturally you will have to prove that you know the vectors a,b\textbf{a}, \textbf{b}. But you cannot just reveal them for obvious reasons. Can you prove the knowledge of a,b\textbf{a}, \textbf{b} without revealing them? The inner-product argument lets you do so such that the government would be convinved about your ownership without knowing much about your secrets. We assume that size of the vectors a,b\textbf{a}, \textbf{b} are a power of two, but it is fairly straghtforward to extend the analysis for cases otherwise.

The Inner-Product Argument

The inner-product argument proves the knowledge of witness vectors a,b∈Fqn\textbf{a}, \textbf{b} \in \mathbb{F}_q^{n} given a Pedersen vector commitment P∈GP \in \mathbb{G} to a,b\textbf{a}, \textbf{b} and the inner product c=⟨a,b⟩∈Fqc = \langle \textbf{a}, \textbf{b} \rangle \in \mathbb{F}_q. The following relation proves describes the inner-product argument in a mathematical form. LIP(σ)={g,h∈Gn,P∈G,c∈ Zq⏟statement; a,b∈Zqn⏟witness ∣ P=ga⋅hb⋅uc ∧ c=⟨a,b⟩⏟relation} \mathcal{L}_{\textsf{IP}}(\sigma) = \bigg\{ \underbrace{\textbf{g}, \textbf{h} \in \mathbb{G}^n, P \in \mathbb{G}, c \in \ \mathbb{Z}_q}_{\textsf{statement}}; \ \underbrace{\textbf{a}, \textbf{b} \in \mathbb{Z}_q^n}_{\textsf{witness}} \ \bigg| \ \underbrace{P = \textbf{g}^{\textbf{a}} \cdot \textbf{h}^{\textbf{b}} \cdot u^{c} \ \wedge \ c = \langle \textbf{a}, \textbf{b} \rangle}_{\textsf{relation}} \bigg\} where the common reference string σ\sigma contains the public information g,h∈Gn,u∈G\textbf{g}, \textbf{h} \in \mathbb{G}^n, u \in \mathbb{G}. To construct the inner-product argument, we first split the secret vectors into half, a=(a1,a1),b=(b1,b1) \textbf{a} = (\textcolor{red}{\textbf{a}}_{1}, \textcolor{blue}{\textbf{a}}_{1}), \quad \textbf{b} = (\textcolor{red}{\textbf{b}}_{1}, \textcolor{blue}{\textbf{b}}_{1}) where the red vector denotes the left half while the blue denotes right half. The 11 in the subscript denotes the step number in recursion. We now compute Pedersen vector commitments to (a1,b1)(\textcolor{red}{\textbf{a}}_{1}, \textcolor{blue}{\textbf{b}}_{1}) and (a1,b1)(\textcolor{blue}{\textbf{a}}_{1}, \textcolor{red}{\textbf{b}}_{1}). Note that we can split the base vectors too as g=(g1,g1),h=(h1,h1)\textbf{g} = (\textcolor{red}{\textbf{g}}_{1}, \textcolor{blue}{\textbf{g}}_{1}), \textbf{h} = (\textcolor{red}{\textbf{h}}_{1}, \textcolor{blue}{\textbf{h}}_{1}) and use them to compute: L1=g1a1⋅h1b1⋅u⟨a1,b1⟩,R1=g1a1⋅h1b1⋅u⟨a1,b1⟩. L_1 = \textcolor{blue}{\textbf{g}}_{1}^{\textcolor{red}{\textbf{a}}_{1}} \cdot \textcolor{red}{\textbf{h}}_{1}^{\textcolor{blue}{\textbf{b}}_{1}} \cdot u^{\langle \textcolor{red}{\textbf{a}}_{1} , \textcolor{blue}{\textbf{b}}_{1} \rangle}, \quad R_1 = \textcolor{red}{\textbf{g}}_{1}^{\textcolor{blue}{\textbf{a}}_{1}} \cdot \textcolor{blue}{\textbf{h}}_{1}^{\textcolor{red}{\textbf{b}}_{1}} \cdot u^{\langle \textcolor{blue}{\textbf{a}}_{1} , \textcolor{red}{\textbf{b}}_{1} \rangle}. We send L1,R1∈GL_1, R_1 \in \mathbb{G} to the verifier. The verifier sends back a challenge scalar x1∈Fqx_1 \in \mathbb{F}_q. For the next round, we (as well as the verifer) update the base vectors as the combined Pedersen commitment as g1=g1x1−1∘g1x1∈Gn2,h1=h1x1∘h1x1−1∈Gn2,P1=L1x2⋅P⋅R1x−2∈G. \begin{aligned} \textbf{g}_{1} &= \textcolor{red}{\textbf{g}}_{1}^{x_1^{-1}} \circ \textcolor{blue}{\textbf{g}}_{1}^{x_1} \in \mathbb{G}^{\frac{n}{2}}, \\ \textbf{h}_{1} &= \textcolor{red}{\textbf{h}}_{1}^{x_1} \circ \textcolor{blue}{\textbf{h}}_{1}^{x_1^{-1}} \in \mathbb{G}^{\frac{n}{2}}, \\ P_{1} &= L_1^{x^2} \cdot P \cdot R_1^{x^{-2}} \in \mathbb{G}. \end{aligned} Notice that on substituting for L1,R1L_1, R_1 and PP, the commitment P1P_1 has the form P1=(g1a1⋅h1b1⋅u⟨a1,b1⟩)x12⋅(g1a1⋅g1a1⋅h1b1⋅h1b1⋅u⟨a,b⟩)⋅(g1a1⋅h1b1⋅u⟨a1,b1⟩)x1−2=g1a1+x1−2a1⋅g1x12a1+a1⋅h1b1+x12b1⋅h1x1−2b1+b1⋅ux12⟨a1,b1⟩+⟨a1,b1⟩+⟨a1,b1⟩+x1−2⟨a1,b1⟩=g1x1−1⋅(x1a1+x1−1a1)⋅g1x1⋅(x1a1+x1−1a1)⋅h1x1⋅(x1−1b1+x1b1)⋅h1x1−1⋅(x1−1b1+x1b1)⋅u⟨x1a1,x1b1⟩+⟨x1a1,x1−1b1⟩+⟨x1−1a1,x1b1⟩+⟨x1−1a1,x1−1b1⟩=(g1x1−1∘g1x1)(x1a1+x1−1a1)⋅(h1x1∘h1x1−1)(x1−1b1+x1b1)⋅u⟨(x1a1+x1−1a1), (x1−1b1+x1b1)⟩=g1(x1a1+x1−1a1)⋅h1(x1−1b1+x1b1)⋅u⟨(x1a1+x1−1a1), (x1−1b1+x1b1)⟩ \begin{aligned} P_1 &= \left( \textcolor{blue}{\textbf{g}}_{1}^{\textcolor{red}{\textbf{a}}_{1}} \cdot \textcolor{red}{\textbf{h}}_{1}^{\textcolor{blue}{\textbf{b}}_{1}} \cdot u^{\langle \textcolor{red}{\textbf{a}}_{1} , \textcolor{blue}{\textbf{b}}_{1} \rangle} \right)^{x_1^2} \cdot \left( \textcolor{red}{\textbf{g}}_{1}^{\textcolor{red}{\textbf{a}}_{1}} \cdot \textcolor{blue}{\textbf{g}}_{1}^{\textcolor{blue}{\textbf{a}}_{1}} \cdot \textcolor{red}{\textbf{h}}_{1}^{\textcolor{red}{\textbf{b}}_{1}} \cdot \textcolor{blue}{\textbf{h}}_{1}^{\textcolor{blue}{\textbf{b}}_{1}} \cdot u^{\langle \textbf{a} , \textbf{b} \rangle} \right) \cdot \left( \textcolor{red}{\textbf{g}}_{1}^{\textcolor{blue}{\textbf{a}}_{1}} \cdot \textcolor{blue}{\textbf{h}}_{1}^{\textcolor{red}{\textbf{b}}_{1}} \cdot u^{\langle \textcolor{blue}{\textbf{a}}_{1} , \textcolor{red}{\textbf{b}}_{1} \rangle} \right)^{x_1^{-2}} \\ &= \textcolor{red}{\textbf{g}}_{1}^{\textcolor{red}{\textbf{a}}_{1} + x_1^{-2}\textcolor{blue}{\textbf{a}}_{1}} \cdot \textcolor{blue}{\textbf{g}}_{1}^{x_1^2\textcolor{red}{\textbf{a}}_{1} + \textcolor{blue}{\textbf{a}}_{1}} \cdot \textcolor{red}{\textbf{h}}_{1}^{\textcolor{red}{\textbf{b}}_{1} + x_1^{2}\textcolor{blue}{\textbf{b}}_{1}} \cdot \textcolor{blue}{\textbf{h}}_{1}^{x_1^{-2}\textcolor{red}{\textbf{b}}_{1} + \textcolor{blue}{\textbf{b}}_{1}} \cdot u^{ x_1^{2}\langle \textcolor{red}{\textbf{a}}_{1} , \textcolor{blue}{\textbf{b}}_{1} \rangle + \langle \textcolor{red}{\textbf{a}}_{1} , \textcolor{red}{\textbf{b}}_{1} \rangle + \langle \textcolor{blue}{\textbf{a}}_{1} , \textcolor{blue}{\textbf{b}}_{1} \rangle + x_1^{-2}\langle \textcolor{blue}{\textbf{a}}_{1} , \textcolor{red}{\textbf{b}}_{1} \rangle} \\ &= \textcolor{red}{\textbf{g}}_{1}^{x_1^{-1} \cdot (x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1})} \cdot \textcolor{blue}{\textbf{g}}_{1}^{x_1 \cdot (x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1})} \cdot \textcolor{red}{\textbf{h}}_{1}^{x_1 \cdot (x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1})} \cdot \textcolor{blue}{\textbf{h}}_{1}^{x_1^{-1} \cdot (x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1})} \cdot u^{ \langle x_1 \textcolor{red}{\textbf{a}}_{1} , x_1 \textcolor{blue}{\textbf{b}}_{1} \rangle + \langle x_1 \textcolor{red}{\textbf{a}}_{1} , x_1^{-1} \textcolor{red}{\textbf{b}}_{1} \rangle + \langle x_1^{-1} \textcolor{blue}{\textbf{a}}_{1} , x_1 \textcolor{blue}{\textbf{b}}_{1} \rangle + \langle x_1^{-1} \textcolor{blue}{\textbf{a}}_{1} , x_1^{-1} \textcolor{red}{\textbf{b}}_{1} \rangle} \\ &= \left( \textcolor{red}{\textbf{g}}_{1}^{x_1^{-1}} \circ \textcolor{blue}{\textbf{g}}_{1}^{x_1} \right)^{(x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1})} \cdot \left( \textcolor{red}{\textbf{h}}_{1}^{x_1} \circ \textcolor{blue}{\textbf{h}}_{1}^{x_1^{-1}} \right)^{(x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1})} \cdot u^{ \left\langle (x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1}), \ (x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1}) \right\rangle } \\ & = \textbf{g}_1^{(x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1})} \cdot \textbf{h}_1^{(x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1})} \cdot u^{ \left\langle (x_1\textcolor{red}{\textbf{a}}_{1} + x_1^{-1}\textcolor{blue}{\textbf{a}}_{1}), \ (x_1^{-1}\textcolor{red}{\textbf{b}}_{1} + x_1\textcolor{blue}{\textbf{b}}_{1}) \right\rangle } \end{aligned} Therefore, P1P_1 is in fact the Pedersen commitment to the quantities a1=(x1⋅a1+x1−1⋅a1)∈Fqn2b1=(x1−1⋅b1+x1⋅b1)∈Fqn2. \begin{aligned} \textbf{a}_1 &= (x_1 \cdot \textcolor{red}{\textbf{a}}_{1} + x_1^{-1} \cdot \textcolor{blue}{\textbf{a}}_{1}) \in \mathbb{F}_q^{\frac{n}{2}} \\ \textbf{b}_1 &= (x_1^{-1} \cdot \textcolor{red}{\textbf{b}}_{1} + x_1 \cdot \textcolor{blue}{\textbf{b}}_{1}) \in \mathbb{F}_q^{\frac{n}{2}}. \end{aligned} Note that we could send the vectors (a1,b1)(\textbf{a}_1, \textbf{b}_1) to the verifier and she could verify (and be convinced about our knowledge of vectors (a,b)(\textbf{a}, \textbf{b}) without actually knowing them!) the last equality above, but this results in prover communication to be nn field elements. We wish to reduce it to logarithmic in nn. With that in mind, we can now repeat the above process with the new secrets (a1,b1)(\textbf{a}_1, \textbf{b}_1), bases (g1,h1)(\textbf{g}_1, \textbf{h}_1) and commitment P1P_1. We can keep doing so until the size of the new bases is 11. In this process, the verifier would have sent l=log2(n)l = \text{log}_2(n) challenges, viz. (x1,x2,…,xl)(x_1, x_2, \dots, x_{l}) and we would have sent (L1,R1,L2,R2,…,Ll,Rl)∈G2l(L_1, R_1, L_2, R_2, \dots, L_l, R_l) \in \mathbb{G}^{2l} elements. For the last round, we send the elements (alast,blast)∈Fq2(a_{\text{last}}, b_{\text{last}}) \in \mathbb{F}_q^2 and all the verifier has to check is Plast=?glastalast⋅hlastblast⋅ualast⋅blast(1) \tag{1} P_{\text{last}} \stackrel{?}{=} g_{\text{last}}^{a_{\text{last}}} \cdot h_{\text{last}}^{b_{\text{last}}} \cdot u^{a_{\text{last}} \cdot b_{\text{last}}} where Plast,glast,hlastP_{\text{last}}, g_{\text{last}}, h_{\text{last}} can be computed by the verifier from all the information she has in the previous ll rounds! Thus, the total prover communication would then be 2log2(n)2 \text{log}_2(n) group elements plus 22 field elements.

Prover and Verifier Costs

In the ii-th round, the prover computes Li,Ri∈GL_i, R_i \in \mathbb{G} and base vectors gi,hi∈Gn2i\textbf{g}_i, \textbf{h}_i \in \mathbb{G}^{\frac{n}{2^i}}. This amounts to 2 group exponentiations of size 2⋅n2i+12 \cdot \frac{n}{2^i} + 1 and 2 group exponentiations of size 2⋅n2i2 \cdot \frac{n}{2^i}, so a total of n2i−3+2\frac{n}{2^{i-3}} + 2 group exponentiations. In total, the prover would need 8(n−1)8(n-1) group exponentiations. Since field operations are typically orders of magnitude faster than group exponentiations, we consider the costs only due to group exponentiations.

On the other hand, the verifier only needs to validate equation (1)(1) in the last round. All she needs for validation is to compute glast,hlastg_\text{last}, h_\text{last} and PlastP_\text{last}. Note that glast,hlastg_\text{last}, h_\text{last} would depend only on the challenges (x1,x2,…,xl)(x_1, x_2, \dots, x_l). Let us try to compute the base vector g2\textbf{g}_2 for round 2 for n=8n=8. g1=g1x1−1∘g1x1∈Gn2=(g1,g2,g3,g4)x1−1∘(g5,g6,g7,g8)x1=(g1x1−1g5x1, g2x1−1g6x1, g3x1−1g7x1, g4x1−1g8x1)∈G4g2=(g1x1−1g5x1, g2x1−1g6x1)x2−1∘(g3x1−1g7x1, g4x1−1g8x1)x2=(g1x1−1x2−1g5x1x2−1g3x1−1x2g7x1x2, g2x1−1x2−1g6x1x2−1g4x1−1x2g8x1x2)∈G2glast=g3=(g1x1−1x2−1g5x1x2−1g3x1−1x2g7x1x2)x3−1∘(g2x1−1x2−1g6x1x2−1g4x1−1x2g8x1x2)x3=g1x1−1x2−1x3−1g5x1x2−1x3−1g3x1−1x2x3−1g7x1x2x3−1g2x1−1x2−1x3g6x1x2−1x3g4x1−1x2x3g8x1x2x3=g1x1−1x2−1x3−1g2x1−1x2−1x31g3x1−1x21x3−1g4x1−1x21x31g5x11x2−1x3−1g6x11x2−1x31g7x11x21x3−1g8x11x21x31∈G \begin{aligned} \textbf{g}_1 &= \textcolor{red}{\textbf{g}}_{1}^{x_1^{-1}} \circ \textcolor{blue}{\textbf{g}}_{1}^{x_1} \in \mathbb{G}^{\frac{n}{2}} \\ &= (g_1, g_2, g_3, g_4)^{x_1^{-1}} \circ (g_5, g_6, g_7, g_8)^{x_1} \\ &= (g_1^{x_1^{-1}} g_5^{x_1}, \ g_2^{x_1^{-1}} g_6^{x_1}, \ g_3^{x_1^{-1}} g_7^{x_1}, \ g_4^{x_1^{-1}} g_8^{x_1}) \in \mathbb{G}^4 \\ \textbf{g}_2 &= \left( g_1^{x_1^{-1}} g_5^{x_1}, \ g_2^{x_1^{-1}} g_6^{x_1} \right)^{x_2^{-1}} \circ \left( g_3^{x_1^{-1}} g_7^{x_1}, \ g_4^{x_1^{-1}} g_8^{x_1} \right)^{x_2} \\ &= \left( g_1^{x_1^{-1} x_2^{-1}} g_5^{x_1 x_2^{-1}} g_3^{x_1^{-1} x_2} g_7^{x_1 x_2}, \ g_2^{x_1^{-1} x_2^{-1}} g_6^{x_1 x_2^{-1}} g_4^{x_1^{-1} x_2} g_8^{x_1 x_2} \right) \in \mathbb{G}^2 \\ g_\text{last} = \textbf{g}_3 &= \left( g_1^{x_1^{-1} x_2^{-1}} g_5^{x_1 x_2^{-1}} g_3^{x_1^{-1} x_2} g_7^{x_1 x_2} \right)^{x_3^{-1}} \circ \left( g_2^{x_1^{-1} x_2^{-1}} g_6^{x_1 x_2^{-1}} g_4^{x_1^{-1} x_2} g_8^{x_1 x_2} \right)^{x_3} \\ &= g_1^{x_1^{-1} x_2^{-1} x_3^{-1}} g_5^{x_1 x_2^{-1} x_3^{-1}} g_3^{x_1^{-1} x_2 x_3^{-1}} g_7^{x_1 x_2 x_3^{-1}} g_2^{x_1^{-1} x_2^{-1} x_3} g_6^{x_1 x_2^{-1} x_3} g_4^{x_1^{-1} x_2 x_3} g_8^{x_1 x_2 x_3} \\ &= g_1^{x_1^{-1} x_2^{-1} x_3^{-1}} g_2^{x_1^{-1} x_2^{-1} x_3^{1}} g_3^{x_1^{-1} x_2^{1} x_3^{-1}} g_4^{x_1^{-1} x_2^{1} x_3^{1}} g_5^{x_1^{1} x_2^{-1} x_3^{-1}} g_6^{x_1^{1} x_2^{-1} x_3^{1}} g_7^{x_1^{1} x_2^{1} x_3^{-1}} g_8^{x_1^{1} x_2^{1} x_3^{1}} \in \mathbb{G} \end{aligned} Note the following pattern in the powers of challenges (x1,x2,x3)(x_1, x_2, x_3).

generator powers of (x1,x2,x3)(x_1, x_2, x_3) binary form decimal
g1g_1 −1,−1,−1-1,-1,-1 000000 0
g2g_2 −1,−1,1-1,-1,1 001001 1
g3g_3 −1,1,−1-1,1,-1 010010 2
g4g_4 −1,1,1-1,1,1 011011 3
g5g_5 1,−1,−11,-1,-1 100100 4
g6g_6 1,−1,11,-1,1 101101 5
g7g_7 1,1,−11,1,-1 110110 6
g8g_8 1,1,11,1,1 111111 7

Similarly, we can compute hlasth_{\text{last}} with a difference that the powers of the challenges in the exponent get inverted. hlast=h3=h1x11x21x31h2x11x21x3−1h3x11x2−1x31h4x11x2−1x3−1h5x1−1x21x31h6x1−1x21x3−1h7x1−1x2−1x31h8x1−1x2−1x3−1∈G h_{\text{last}} = \textbf{h}_3 = h_1^{x_1^{1} x_2^{1} x_3^{1}} h_2^{x_1^{1} x_2^{1} x_3^{-1}} h_3^{x_1^{1} x_2^{-1} x_3^{1}} h_4^{x_1^{1} x_2^{-1} x_3^{-1}} h_5^{x_1^{-1} x_2^{1} x_3^{1}} h_6^{x_1^{-1} x_2^{1} x_3^{-1}} h_7^{x_1^{-1} x_2^{-1} x_3^{1}} h_8^{x_1^{-1} x_2^{-1} x_3^{-1}} \in \mathbb{G} The ghastly looking expressions for glastg_{\text{last}} and hlasth_{\text{last}} (for even n=3n=3) can be written in a much simpler form as glast=∏i=1ngisi,hlast=∏i=1nhisi−1, g_{\text{last}} = \prod_{i=1}^{n} g_i^{s_i}, \quad h_{\text{last}} = \prod_{i=1}^{n} h_i^{s_i^{-1}}, such that si=∏j=1lxjb(i,j), where b(i,j)={1if the j-th bit of (i−1) is 1−1otherwise. s_i = \prod_{j=1}^{l} x_j^{b(i,j)}, \quad \text{ where } \quad b(i,j) = \begin{cases} 1 & \text{if the $j$-th bit of } (i-1) \text{ is 1} \\ -1 & \text{otherwise}. \end{cases} On a similar note, we can compute PlastP_{\text{last}} as P2=L2x22⋅P1⋅R2x2−2=L2x22⋅(L1x12⋅P⋅R1x1−2)⋅R2x2−2=L2x22⋅L1x12⋅P⋅R1x22⋅R2x12∴Plast=(Llxl2⋅…⋅L2x22⋅L1x12)⋅P⋅(R1x22⋅R2x12⋅…⋅Rlxl2)=P⋅(∏j=1lLjxj2⋅Rjxj−2) \begin{aligned} P_2 &= L_2^{x_2^2} \cdot P_1 \cdot R_2^{x_2^{-2}} \\ &= L_2^{x_2^2} \cdot \left( L_1^{x_1^2} \cdot P \cdot R_1^{x_1^{-2}} \right) \cdot R_2^{x_2^{-2}} \\ &= L_2^{x_2^2} \cdot L_1^{x_1^2} \cdot P \cdot R_1^{x_2^2} \cdot R_2^{x_1^2} \\ \therefore \quad P_{\text{last}} &= \left(L_l^{x_l^2} \cdot \ldots \cdot L_2^{x_2^2} \cdot L_1^{x_1^2}\right) \cdot P \cdot \left( R_1^{x_2^2} \cdot R_2^{x_1^2} \cdot \ldots \cdot R_l^{x_l^2} \right) \\ &= P \cdot \left(\prod_{j=1}^{l} L_j^{x_j^2} \cdot R_j^{x_j^{-2}}\right) \end{aligned}

Therefore from (1)(1), the verification of an inner-product argument boils to a single multi-exponentiation check of size (2n+2l+1)(2n + 2l + 1) P⋅(∏j=1lLjxj2⋅Rjxj−2)=?ga⋅s⋅hb⋅s−1⋅ua⋅b P \cdot \left(\prod_{j=1}^{l} L_j^{x_j^2} \cdot R_j^{x_j^{-2}}\right) \stackrel{?}{=} \textbf{g}^{a \cdot \textbf{s}} \cdot \textbf{h}^{b \cdot \textbf{s}^{-1}} \cdot u^{a \cdot b} where s=(s1,s2,…,sn)\textbf{s} = (s_1, s_2, \dots, s_n).

Closing Comments

The log-sized inner-product in a non-trusted setup was an important breakthrough in applied cryptography research. For cryptocurrencies like Monero, the inner-product powered range proof protocol bulletproofs helped reduce the transaction sizes by a whopping 80%1. The downside, however, of the inner-product argument is the linear verification times in spite of aggregated proof verification, causing practical bottlenecks for deployment for large arithmetic circuits. Nevertheless, the inner-product argument opened up avenues for future research in the direction of recursive proofs. Stay tuned to understand how the beautiful technique of inner-product argument helped in construction of Halo.

  1. Bulletproofs in Moneropedia, Link: https://web.getmonero.org/resources/moneropedia/bulletproofs.html ↩