RFC-0181/BulletproofsPlus

Bulletproofs+ range proving

status: stable

Maintainer(s): Aaron Feickert

Licence

The 3-Clause BSD Licence.

Copyright 2022 The Tari Development Community

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of this document must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS DOCUMENT IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS", AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Language

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY" and "OPTIONAL" in this document are to be interpreted as described in BCP 14 (covering RFC2119 and RFC8174) when, and only when, they appear in all capitals, as shown here.

Disclaimer

This document and its content are intended for information purposes only and may be subject to change or update without notice.

This document may include preliminary concepts that may or may not be in the process of being developed by the Tari community. The release of this document is intended solely for review and discussion by the community of the technological merits of the potential system outlined herein.

Goals

This Request for Comment (RFC) describes Tari-specific implementation details for Bulletproofs+ range proving and verifying.

Introduction

The Tari implementation of the Bulletproofs+ range proving system makes several changes and optimizations that we describe here. In particular, it supports the following useful features:

  • Commitments can be extended; that is, they can commit to a value using multiple masks.
  • Range proofs can be aggregated; that is, a single range proof can assert valid range for multiple commitments in an efficient way.
  • A set of arbitrary range proofs can be verified in a batch; that is, the verifier can check the validity of all proofs in the set at once in an efficient way.
  • The prover can assert a nonzero minimum value bound to a commitment.
  • The prover can delegate to certain verifiers the ability to recover the masks used for the extended commitment in a non-aggregated proof.

The Bulletproofs+ preprint does not address extended commitments, as it only defines its range proving system using Pedersen commitments. However, a later preprint for Zarcanum updates the algorithms and security proofs to accommodate one additional mask, and the reasoning extends generally. Aggregation of range assertions using Pedersen commitments is described in the Bulletproofs+ preprint, and the Zarcanum preprint describes the corresponding changes for extended commitments. Batch verification is described only informally in the Bulletproofs+ preprint, and in an incomplete fashion. Minimum value assertion is not addressed in the preprint. An approach to mask and value recovery was used by Grin for the Bulletproofs range proving system, implemented as described by the deprecated RFC-0180, and can be modified to support Bulletproofs+ range proofs with extended commitments.

Notation

To reduce confusion in our description and more closely match implementation libraries, we use additive notation and uppercase letters for group elements, and otherwise assume notation from the preprints. Denote the commitment value generator by $G_c$ and the commitment mask generator vector by $\vec{H}_c$. We note that the terms of the vector $\vec{d}$ can be succinctly expressed by noting that for $0 \leq i < n$ and $0 \leq j < m$ we have $d_{jn+i} = z^{2(j+1)} 2^i$, which can be efficiently defined iteratively. Because the preprint uses the notation $A$ differently in the weighted inner product and range proving protocols, we rename it to $A'$ in the weighted inner product protocol.

Finally, we note one additional unfortunate notation change that applies to the implementation. Both the Bulletproofs+ and Zarcanum preprints use $G$ as the commitment value generator, and either $H$ or $\vec{H}_c$ (in our notation) for masking. However, in the Tari protocol (as in other similar protocols), this notation is switched! This is because of how generators are defined and used elsewhere in the protocol and elliptic curve library implementation. The only resulting change is a switch in generator notation in the Tari implementation: $H$ for the value component generator, and $\vec{G}_c$ (in our notation) for masking.

Minimum value assertion

We first briefly note how to achieve minimum value assertion. Let $0 \leq v_{\text{min}} \leq v \leq v_{\text{max}}$, where $v_{\text{min}}$ is a minimum value specified by the prover, $v$ is the value bound to the prover's commitment $V$, and $v_{\text{max}}$ is a globally-fixed maximum value. When generating the proof, the prover uses $v - v_{\text{min}}$ as the value witness, and additionally binds $v_{\text{min}}$ into the Fiat-Shamir transcript. When verifying the proof, the verifier uses $V - v_{\text{min}} G_c$ as the commitment (but binds the original commitment $V$ in the transcript). This asserts that $v_{\text{min}} \leq v \leq v_{\text{min}} + v_{\text{max}}$. While this approach modifies the upper bound allowed for value binding, it does not pose problems in practice, as the intent of range proving is to ensure no overflow when performing balance computations elsewhere in the Tari protocol.

Extended commitments and aggregation

We now describe how to reduce verification of a single aggregated range proof using extended commitments to a single multiscalar multiplication operation. A partial approach is described in the Bulletproofs+ preprint. The single multiscalar multiplication used to verify an aggregated range proof (given in Section 6.1 of the Bulletproofs+ preprint) can be written more explicitly in our case by accounting for the extra steps used to support extended commitments, and by noting that the $P$ input term to the weighted inner product argument (given in Figure 1 of the Bulletproofs+ preprint and Figure D.1 of the Zarcanum preprint) is replaced by the term $\widehat{A}$ defined in the overall range proving protocol (given in Figure 3 of the Bulletproofs+ preprint and Figure D.3 of the Zarcanum preprint).

Suppose we index the inner product generator vectors $\vec{G}$ and $\vec{H}$ using $i$, the inner product recursion generator vectors $\vec{L}$ and $\vec{R}$ using $j$, the aggregated commitment vector $\vec{V}$ by $k$, and the extended commitment mask generator vector $\vec{H}_c$ by $l$. We assume indexing starts at zero unless otherwise noted. Single aggregated proof verification reduces (by suitable modification of the equation given in Section 6.1 of the Bulletproofs+ preprint) to checking that the following equation holds: \[ \sum_i (r'es_i) G_i + \sum_i (s'es_i') H_i + \sum_l \delta_l' H_{c,l} = e^2 \widehat{A} + \sum_j (e^2e_j^2) L_j + \sum_j (e^2e_j^{-2}) R_j + e A' + B \] But we also have (from suitable modification of the definition given in Figure 3 of the Bulletproofs+ preprint) that \[ \widehat{A} = A - \sum_i z G_i + \sum_i (z + d_iy^{mn-i}) H_i + x G_c + y^{mn+1}\sum_k z^{2(k+1)} (V_k - v_{\text{min},k} G_c) \] defined by the range proving system outside of the inner product argument. Here \[ \begin{align*} x &= \langle \vec{1}^{mn}, \overrightarrow{y}^{mn} \rangle z - \langle \vec{1}^{mn}, \vec{d} \rangle y^{mn+1}z - \langle \vec{1}^{mn}, \overrightarrow{y}^{mn} \rangle z^2 \\ &= z\sum_{i=1}^{mn} y^i - y^{mn+1}z\sum_{i=0}^{mn-1}d_i - z^2\sum_{i=1}^{mn} y^i \end{align*} \] is a scalar defined entirely in terms of constants and challenge values from the proof. Grouping terms, we find that a single aggregated range proof can be verified by checking that the following equation holds: \[ \begin{multline*} \sum_i (r'es_i + e^2z) G_i + \sum_i (s'es_i' - e^2(z + d_iy^{mn-i})) H_i + \left( r'ys' - e^2x + e^2y^{mn+1}\sum_k z^{2(k+1)}v_{\text{min},k} \right) G_c \\ + \sum_l \delta_l' H_{c,i} - \sum_k (y^{mn+1}z^{2(k+1)}e^2) V_k - e^2 A - \sum_j (e^2e_j^2) L_j - \sum_j (e^2e_j^{-2}) R_j - e A' - B = 0 \end{multline*} \]

Batch verification

To verify a batch of proofs, we apply a separate random multiplicative scalar weight $w \neq 0$ to each proof's verification equation, form a linear combination of these equations, and group like terms. Because each equation receives a separate random weight, successful evaluation of the resulting linear combination means that each constituent equation holds with high probability, and therefore that all proofs in the set are valid. If the linear combination evaluation fails, at least one included proof is invalid. The verifier must then test each proof in turn, or use a more efficient approach like binary search to identify each failure. This follows the general approach informally discussed in Section 6.1 of the Bulletproofs+ preprint.

The reason for this rather convoluted algebra is twofold. First, grouping like terms means that each unique generator used across a batch is only evaluated in the resulting multiscalar multiplication once; since the generators $\vec{G}, \vec{H}, G_c, \vec{H}_c$ are globally fixed, this provides significant efficiency improvement. Second, the use of algorithms (like those of Straus and Pippenger and others) to evaluate the multiscalar multiplication scale slightly sublinearly, such that it is generally beneficial to minimize the number of multiscalar multiplications for a given set of generators. This means our approach to batch verification is effectively optimal.

Designated mask recovery

It is possible for the prover to perform careful modifications to a non-aggregated range proof in order to allow a designated verifier to recover the masks used in the corresponding extended commitment. The construction we describe here does not affect the verification process for non-designated verifiers. Note that this construction requires a non-aggregated proof that contains a range assertion for only a single commitment. Unlike the approach used initially in RFC-0180, it is not possible to embed additional data (like the commitment value) into a Bulletproofs+ range proof.

The general approach is that the prover and designated verifier share a common nonce seed. The prover uses this value to determinstically derive and replace certain nonces used in the proof. During the verification process, the designated verifier performs the same deterministic derivation and is able to extract the commitment masks from the proof. Because the resulting proof is still special honest-verifier zero knowledge, as long as the nonce seed is sampled uniformly at random, a non-designated verifier is not able to gain any information about the masks.

After sampling a nonce seed, the prover passes it through an appropriate set of domain-separated hash functions with scalar output to generate the following nonces used in the proof: \[ \{\eta_k\}, \{\delta_k\}, \{\alpha_k\}, \{d_{L,j,k}\}, \{d_{R,j,k}\} \] Here, as before, $k$ is indexed over the number of masks used in the extended commitment, and $j$ is indexed over the weighted inner product argument rounds.

By doing this, the prover effectively defines the proof element set $\{\delta_k'\}$ as follows: \[ \delta_k' = \eta_k + \delta_ke + e^2 \left( \alpha_k + \gamma_ky^{n+1}z^2 + \sum_j(e_j^2d_{L,j,k} + e_j^{-2}d_{R,j,k}) \right) \]

When verifying the proof, the designated verifier uses the nonce seed to perform the same nonce derivation as the prover. It then computes the mask set $\{\gamma_k\}$ as follows: \[ \gamma_k = \left( (\delta_k' - \eta_k - \delta_ke)e^{-2} - \alpha_k - \sum_j(e_j^2d_{L,j,k} + e_j^{-2}d_{R,j,k}) \right) y^{-(n+1)}z^{-2} \] The recovered masks must then be checked against the extended commitment once the value is separately communicated to the verifier. Otherwise, if the verifier uses a different nonce seed than the prover did (or if the prover otherwise did not derive the nonces using a nonce seed at all), it will recover incorrect masks. If the verifier is able to construct the extended commitment from the value and recovered masks, the recovery succeeds; otherwise, the recovery fails.

Comparative performance

As we moved from Bulletproofs [1] to Bulletproofs+ [2] in our blockchain project, the natural benchmark comparison is with the experimental results in [2] and Dalek's Bulletproofs [3]. Compared with Dalek's Bulletproofs, our average proof creation is 30% slower, while verification is on par. Compared with the experimental results in [2], we could not recreate the 16% reduction in prover time; however, our 1% increase in verification time is on par with their 3%. Immediate benefits are evident when employing batch verification; exponential gains range from 37% to 79% for batch sizes from 2 to 256 proofs.

Extended commitments add virtually no overhead in single or aggregated range proof creation or verification time, neither in batched verification time nor when compared to regular Pedersen commitments.

Mask/blinding factor recovery adds moderate (5% for single proof-verification with extension degree zero) to significant (22% for 256 single batched proofs verification with extension degree two) overhead to verification performance; comparisons below were made without activating the recovery feature. Deactivating proof verification for a "mask-recovery-only" mode of operation is possible and omits the expensive multi-exponentiation multiplication, resulting in linear performance (as opposed to exponential gains/cost). Batched "mask-recovery-only" is approximately 10% more costly on average when compared to non-batched recovery.

Note: The test results listed here are relative; the numbers are not absolute. The tests were run on an Intel(R) Core(TM) i7-7820HQ CPU laptop without using the simd_backend feature.

Aggregated 64-bit range proof creation

Notes:

  • Median values are used for comparison.
  • In the headings and legends:
    • ed_0 means extension degree zero
    • ed_1 means extension degree one
    • ed_2 means extension degree two

BP vs. BP+ (creation)

BP+ creation is 30% slower than BP.

SizeBP Med (ms)BP+ Med (ms)Diff Med (%)
116.2921.24130%
231.6341.08130%
460.4780.46133%
8119.18156.56131%
16240.18306.03127%
32460.67598.57130%
Average130%

BP+ extension degrees (creation)

Extended commitments add virtually no overhead to creation time.

SizeBP+ Med ed_0 (ms)BP+ Med ed_1 (ms)BP+ Med ed_2 (ms)Diff Med ed_0-1 (%)Diff Med ed_0-2 (%)
121.2421.4822.467101.12%105.77%
241.0841.4542.074100.91%102.43%
480.4680.7080.76100.31%100.38%
8156.56157.07157.06100.33%100.32%
16306.03306.28305.49100.08%99.82%
32598.57598.47598.0199.98%99.91%
Average100%101%

Aggregated 64-bit range proof verification

BP vs. BP+ (verification)

BP+ verification showed gains for smaller aggregation sizes compared to BP, but is slower for larger aggregation sizes.

SizeBP Med (ms)BP+ Med (ms)Diff Med (%)
12.342.1793%
23.763.7199%
46.446.1896%
811.1010.9699%
1617.5719.52111%
3233.6936.97110%
Average101%

BP+ extension degrees (verification)

Extended commitments add virtually no overhead to verification time.

SizeBP+ Med ed_0 (ms)BP+ Med ed_1 (ms)BP+ Med ed_2 (ms)Diff Med ed_0-1 (%)Diff Med ed_0-2 (%)
12.172.202.20102%102%
23.713.743.76101%101%
46.186.266.28101%102%
810.9611.0510.97101%100%
1619.5219.6619.51101%100%
3236.9736.9936.87100%100%
Average101%101%

Batched 64-bit single range proof verification

Batched verification shows significant gains when compared to linear verification.

Batch sizeBP+ linear (ms)BP+ ext_deg 0 (ms)BP+ ext_deg 1 (ms)BP+ ext_deg 2 (ms)Diff (%)Gains (%)
12.172.172.182.20100%0%
24.342.732.732.7663%37%
48.683.823.823.8044%56%
817.365.745.765.7533%67%
1634.729.579.609.7428%72%
3269.4417.1017.0617.0525%75%
64138.8932.0432.0631.8523%77%
128277.7760.5660.7560.7122%78%
256555.55118.55118.69119.1521%79%

Batched 64-bit single range proof mask recovery

Mask-recovery-only mode is linear and does not benefit from batched operations; batched recovery is suboptimal.

Batch sizeNo mask ed_0 (ms)Mask only ed_0 (ms)Linear mask only (ms)Linear vs. mask only (%)No mask vs. mask only (%)
12.100.220.22100.0%10.4%
22.590.430.44102.2%16.5%
43.590.900.8797.0%25.0%
85.461.871.7493.4%34.2%
169.313.783.4992.3%40.6%
3216.549.316.9774.9%56.3%
6430.3915.2713.9591.3%50.3%
12858.2530.6027.9091.2%52.5%
256113.1861.3655.8090.9%54.2%

DateChangeAuthor
7 Dec 2022First draftAaron
13 Jan 2022Performan updatesbrianp

References