mirror of
https://github.com/QuilibriumNetwork/ceremonyclient.git
synced 2026-02-21 18:37:26 +08:00
dbd95bd9e9
* v2.1.0 [omit consensus and adjacent] - this commit will be amended with the full release after the file copy is complete * 2.1.0 main node rollup
109 lines
4.4 KiB
Markdown
109 lines
4.4 KiB
Markdown
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:
|
|
|
|
* [Inner product proof](::notes::inner_product_proof)
|
|
* [Range proof](::notes::range_proof)
|
|
* [Rank-1 constraint system proof](::notes::r1cs_proof)
|
|
|
|
The description of what the protocols actually do is contained in these notes:
|
|
|
|
* [`range_proof`](::range_proof): aggregated range proof protocol.
|
|
* [`range_proof_mpc`](::range_proof_mpc): multi-party API for range proof aggregation.
|
|
* [`inner_product_proof`](::inner_product_proof): inner product argument protocol.
|
|
* [`r1cs`](::r1cs::notes): constraint system proof protocol.
|
|
|
|
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][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}
|
|
\\]
|
|
|
|
|
|
[bulletproofs_paper]: https://eprint.iacr.org/2017/1066.pdf
|
|
[bp_website]: https://crypto.stanford.edu/bulletproofs/
|