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')$ |
PREVIOUSHow to reshare a secret