[−][src]Module bulletproofs::notes

This module contains notes on how and why Bulletproofs work.

These notes are organized as follows:

Table of Contents

These notes explain how and why the proofs work:

The description of what the protocols actually do is contained in these notes:

The types from the above modules are publicly re-exported from the crate root, so that the external documentation describes how to use the API, while the internal documentation describes how it works.

(FIXME Streamline module structure?)

Notation

We change notation from the original Bulletproofs paper. The primary motivation is that our implementation uses additive notation, and we would like our description of the protocol to use the same notation as the implementation.

In general, we use lower-case letters \(a, b, c\) for scalars in \({\mathbb Z_p}\) and upper-case letters \(G,H,P,Q\) for group elements in \({\mathbb G}\). Vectors are denoted as \({\mathbf{a}}\) and \({\mathbf{G}}\), and the inner product of two vectors is denoted by \({\langle -, - \rangle}\). Notice that \({\langle {\mathbf{a}}, {\mathbf{b}} \rangle} \in {\mathbb Z_p}\) produces a scalar, while \({\langle {\mathbf{a}}, {\mathbf{G}} \rangle} \in {\mathbb G}\) is a multiscalar multiplication. The vectors of all \(0\) and all \(1\) are denoted by \({\mathbf{0}}\), \({\mathbf{1}}\) respectively.

Vectors are indexed starting from \(0\), unlike the paper, which indexes from \(1\). For a scalar \(y\), we write \[ \begin{aligned} {\mathbf{y}}^{n} &= (1,y,y^{2},\ldots,y^{n-1}) \end{aligned} \] for the vector whose \(i\)-th entry is \(y^{i}\). For vectors \({\mathbf{v}}\) of even length \(2k\), we define \({\mathbf{v}}_{\operatorname{lo}}\) and \({\mathbf{v}}_{\operatorname{hi}}\) to be the low and high halves of \({\mathbf{v}}\): \[ \begin{aligned} {\mathbf{v}}_{\operatorname{lo}} &= (v_0, \ldots, v_{k-1})\\ {\mathbf{v}}_{\operatorname{hi}} &= (v_{k}, \ldots, v_{2k-1}) \end{aligned} \] Pedersen commitments are written as \[ \begin{aligned} \operatorname{Com}(v) &= \operatorname{Com}(v, {\widetilde{v}}) = v \cdot B + {\widetilde{v}} \cdot {\widetilde{B}}, \end{aligned} \] where \(B\) and \({\widetilde{B}}\) are the generators used for the values and blinding factors, respectively. We denote the blinding factor for the value \(v\) by \({\widetilde{v}}\), so that it is clear which blinding factor corresponds to which value, and write \(\operatorname{Com}(v)\) instead of \(\operatorname{Com}(v, {\widetilde{v}})\) for brevity.

We also make use of vector Pedersen commitments, which we define for pairs of vectors as \[ \begin{aligned} \operatorname{Com}({\mathbf{a}}_{L}, {\mathbf{a}}_{R}) &= \operatorname{Com}({\mathbf{a}}_{L}, {\mathbf{a}}_{R}, {\widetilde{a}}) = {\langle {\mathbf{a}}_{L}, {\mathbf{G}} \rangle} + {\langle {\mathbf{a}}_{R}, {\mathbf{H}} \rangle} + {\widetilde{a}} {\widetilde{B}},\end{aligned} \] where \({\mathbf{G}}\) and \({\mathbf{H}}\) are vectors of generators. Notice that this is exactly the same as taking a commitment to the vector of values \({\mathbf{a}}_{L} \Vert {\mathbf{a}}_{R}\) with the vector of bases \({\mathbf{G}} \Vert {\mathbf{H}}\), but defining the commitment on pairs of vectors is a more convenient notation.

The variable renaming is as follows: \[ \begin{aligned} g &\xrightarrow{} B & \gamma &\xrightarrow{} \tilde{v} \\ h &\xrightarrow{} \widetilde{B} & \alpha &\xrightarrow{} \tilde{a} \\ {\mathbf{g}} &\xrightarrow{} {\mathbf{G}} & \rho &\xrightarrow{} \tilde{s} \\ {\mathbf{h}} &\xrightarrow{} {\mathbf{H}} & \tau_i &\xrightarrow{} \tilde{t}_i \\ & & \mu &\xrightarrow{} \tilde{e} \\ \end{aligned} \]

Modules

inner_product_proof

This module contains notes on how and why the inner product proof protocol works.

r1cs_proof

This module contains notes on how and why constraint system proofs work.

range_proof

This module contains notes on how and why range proofs work.