# Bulletproofs IPA for multiexp

$\def\prove{\mathsf{Prove}} \def\ver{\mathsf{Ver}} \def\A{\mathbf{A}} \def\B{\mathbf{B}} \def\bb{\mathbf{b}}$

tl;dr: This is a post-mortem write-up on how I failed to use the Bulletproofs IPA to convince a verifier that a multi-exponentiation $\A^\bb = \prod_i (A_i)^{b_i}$ was done correctly. The problem is that the Bulletproof verifier has to “fold” the $\A$ vector by using individual exponentiations, which would be even slower than the verifier naively doing the $\A^\bb$ multiexp.

## Notation

• We are assuming a multiplicative group $\Gr$ of order $p$
• “In the exponent”, we will have an associated field $\F$ of the same order $p$.
• Bolded, lower-case symbols such as $\bb=[b_0,\dots,b_{n-1}]\in\F^n$ typically denote vectors of field elements.
• Bolded, UPPPER-case symbols such as $\A = [A_1, \dots, A_m]\in \Gr^m$ typically denote vectors of group elements.
• $|\A|$ denotes the size of a vector $\A$
• $\A^x = [A_1^x, \dots, A_m^x], \forall x\in \F$
• $\A^\bb = \prod_{i=1}^m A_i^{b_i},\forall b\in\F^m$
• $\A \circ \B = [ A_1 B_1, A_2 B_2, \dots, A_m B_m]$
• $\textbf{A}_L=[A_1,\dots,A_{m/2}]$ and $\textbf{A}_R=[A_{m/2+1},\dots, A_m]$ denote the left and right halves of $\A$

## (Pointless) Bulletproofs IPA for multiexp

The protocol below assumes thes vector $\A$ and $\bb$ are both of size $m = 2^k$ for some integer $k \ge 0$.

 $\underline{\prove(\A, \bb)}$ $\underline{\ver(V, \A, \bb)\rightarrow \{0,1\}}$ $\rule[2.5pt]{8em}{0.5pt}\fbox{$\textbf{if }m = 1$}\rule[2.5pt]{8em}{0.5pt}$ $\xrightarrow{\mbox{$\A = [A_1], \bb = [b_1]$}}$ return 1 iff. $V \equals A_1^{b_1}$ $\rule[2.5pt]{6em}{0.5pt}\fbox{$\textbf{else}\text{ (i.e., if }m \ge 2\text{)}$}\rule[2.5pt]{6em}{0.5pt}$ $V_L = (\A_R)^{\bb_L}$ $V_R = (\A_L)^{\bb_R}$ $\xrightarrow{\mbox{$V_L, V_R$}}$ $\xleftarrow{\mbox{$x\randget \F$}}$ $\color{red}\A' = \A_L \circ (\A_R)^x$ $\bb' = \bb_L \circ (\bb_R)^{(x^{-1})}$ Computes ${\color{red}\A'},\bb'$ just like the prover $V' = (V_L)^x \cdot V \cdot (V_R)^{(x^{-1})}$ Recurse on $(\A',\bb')$ Recurse on $(V', \A',\bb')$