Bulletproofs

Source: Proofs, Arguments, and Zero-Knowledge, Section 14.4

This scheme achieves:

• Constant commitment size
• Logarithmic evaluation proof size
• Linear verifier time

Key idea

The commitment is a Generalized Pedersen Commitment (but without the blinding factor). However, in this section, we use additive notation, so a commitment can be seen as a dot product of the coefficient vector $u$ with a vector of group elements $\mathbf{g}$:

$$Com(z)=⟨u,\mathbf{g}⟩=\sum _{i=1}^n{u}_i\cdot g_i$$

Let’s break the vectors into two halves, $u=u_L\circ u_R$ and $\mathbf{g}={\mathbf{g}}_L\circ {\mathbf{g}}_R$ (where $\circ$ denotes concatenation). Note that $⟨u,\mathbf{g}⟩=⟨u_L,{\mathbf{g}}_L⟩+⟨u_R,{\mathbf{g}}_R⟩$.

Now, for a randomly picked $\alpha$, let:

$$\begin{array}{rl}{u}^{\prime }& =\alpha \cdot u_L+{\alpha }^{-1}\cdot u_R\\ {\mathbf{g}}^{\prime }& =\alpha \cdot {\mathbf{g}}_L+{\alpha }^{-1}\cdot {\mathbf{g}}_R\end{array}$$

This cuts the length of $u$ and $\mathbf{g}$ in half. Their dot products are related as follows:

$$⟨u^{\prime },{\mathbf{g}}^{\prime }⟩=⟨u,\mathbf{g}⟩+{\alpha }^2⟨u_L,{\mathbf{g}}_R⟩+{\alpha }^{-2}⟨u_R,{\mathbf{g}}_L⟩$$

With these ideas, one can build a protocol that let’s the prover prove that it knows an opening to the commitment:

• Prover sends the commitment $c=⟨u,\mathbf{g}⟩$
• For $\log n$ rounds:
  • Prover sends $v_L,v_R$ claimed to equal $⟨u_L,{\mathbf{g}}_R⟩$ and $⟨u_R,{\mathbf{g}}_L⟩$
  • The verifier picks a random challenge $\alpha$ and sets $c:=c+{\alpha }^2{v}_L+{\alpha }^{-2}{v}_R$ and $\mathbf{g}=\alpha \cdot {\mathbf{g}}_L+{\alpha }^{-1}\cdot {\mathbf{g}}_R$
• Now, there is a derived “vector” $u$ of size $1$ (which the prover can compute) such that $c=⟨u,\mathbf{g}⟩$. The prover sends $u$ and the verifier checks the equality

The polynomial commitment scheme

What we’re actually interested in is $⟨u,y⟩$ for $y=(1,z,z^2,...,z^{n-1})$. The idea is to run the protocol in parallel for both $⟨u,\mathbf{g}⟩$ and $⟨u,y⟩$. Note that $\mathbf{g}$ is a vector of group elements and $y$ is a vector of field elements, but since both support addition, we can perform the same calculations on them.

The algorithm

Zero Knowledge

Using commit-and-prove style techniques, the prover can send hiding Pedersen Commitments and prove in zero knowledge that the committed values do pass the final verifier check.

Relation to other commitment schemes

Compared to Hyrax, verification time is worse ($O(n)$ vs. $O(\sqrt{n})$) but evaluation proof size is better. Both ideas can be combined which would:

• Increases the commitment size from $O(1)$ to $O(\sqrt{n})$
• Reduces the public parameter size and verifier runtime from $O(n)$ to $O(\sqrt{n})$
• Maintains the $O(\log n)$ evaluation proof size

Dory reduces the verifier runtime from $O(n)$ to $O(\log n)$ but requires pairings.