# Bulletproofs

## Linear Range Proof

First we give the relation of range proof.

Decode the value $v$ into $\mathbf{a}_L\in{0,1}^n$ s.t. $\langle\mathbf{a}_L,\mathbf{2}^n\rangle=v$ and $\mathbf{a}_R=\mathbf{a}_L-\mathbf{1}^n$.

For a random $y\in\mathbb{Z}_p$ from verifier, the prover should prove that

For a random $z\in\mathbb{Z}_p$, it follows that

where $\delta(y,z)=(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\mathbf{1}^n,\mathbf{2}^n\rangle\in\mathbb{Z}_p$.

Prover picks randomly $\alpha,\rho\leftarrow\mathbb{Z}_p$ and $\mathbf{s}_L,\mathbf{s}_R\leftarrow\mathbb{Z}_p^n$, computes

Verifier receives $A$ and $S$, sends $y$ and $z$ to prover.

Prover picks $\tau_1,\tau_2\leftarrow\mathbb{Z}_p$ and computes $T_i=g^{t_i}h^{\tau_i}$, sends $T_i$ to verifier.

Verifier picks $x\leftarrow\mathbb{Z}_p^\star$ and sends it to prover.

Prover computes

where $\mathbf{s}\in\mathbb{Z}_p$ are used to blind $\mathbf{a}$. Pvover sends $\tau_x,\mu,\hat{t},\mathbf{l},\mathbf{r}$ to verifier.

Verifier checks