Bulletproofs
The fastest Bulletproofs implementation ever, featuring single and aggregated range proofs, stronglytyped multiparty computation, and a programmable constraint system API for proving arbitrary statements (under development).
This library implements Bulletproofs using Ristretto,
using the ristretto255
implementation in
curve25519dalek
. When using the parallel
formulas in the curve25519dalek
AVX2 backend, it
can verify 64bit rangeproofs approximately twice as fast as the
original libsecp256k1
based Bulletproofs implementation.
This library provides implementations of:

Singleparty proofs of single or multiple ranges, using the aggregated rangeproof construction;

Online multiparty computation for rangeproof aggregation between multiple parties, using session types to statically enforce correct protocol flow;

A programmable constraint system API for expressing rank1 constraint systems, and proving and verifying proofs of arbitrary statements (unstable, under development with the
yoloproofs
feature); 
Online multiparty computation for aggregated constraint system proofs (planned future work).
These proofs are implemented using Merlin transcripts, allowing them to be arbitrarily composed with other proofs without implementation changes.
The development roadmap can be found in the Milestones section of the Github repo.
The constraint system API is provided FOR EXPERIMENTS ONLY, and must be
enabled by specifying the yoloproofs
feature. It is not covered by semver
compatibility and is SUBJECT TO CHANGE WITHOUT NOTICE.
Currently, the yoloproofs
feature is disabled in the published version of the
crate, so it can only be used by specifying a git dependency on the develop
branch. This means that it is not possible to publish a crate using the R1CS
API, because it is FOR EXPERIMENTS ONLY.
Documentation
The userfacing documentation for this functionality can be found here. In addition, the library also contains extensive notes on how Bulletproofs work. These notes can be found in the library's internal documentation:
 how Bulletproofs work;
 how the range proof protocol works;
 how the inner product proof protocol works;
 how the aggregation protocol works;
 how the Bulletproof constraint system proofs work (under development);
 how the constraint system reduction works (under development);
 how the aggregated constraint system proofs work (future work).
Comparative Performance
The following table gives comparative timings for proving and verification of a 64bit rangeproof on an Intel SkylakeX i77800X (@3.5GHz, Turbo Boost disabled). Times are in microseconds (lower is better), with the relative speed compared to the fastest implementation.
Implementation  Group  Proving (μs)  rel  Verification (μs)  rel 

ours (avx2)  ristretto255  7300  1.00x  1040  1.00x 
ours (u64)  ristretto255  11300  1.54x  1490  1.43x 
libsecp+endo  secp256k1  14300  1.96x  1900  1.83x 
libsecpendo  secp256k1  16800  2.30x  2080  2.00x 
Monero  ed25519 (unsafe)  53300  7.30x  4810  4.63x 
Use of the curve25519dalek
IFMA backend gives another 1.5x speedup on a
Cannonlake i38121U, increasing the verification speedup 3x over libsecp
and 7x over Monero, but these processors are not yet generally available.
This crate also contains other benchmarks; see the Tests and Benchmarks section below for details on how to run them all.
Example
The following example shows how to create and verify a 32bit rangeproof.
# // The #commented lines are hidden in Rustdoc but not in raw
# // markdown rendering, and contain boilerplate code so that the
# // code in the README.md is actually run as part of the test suite.
#
# extern crate rand;
# use rand::thread_rng;
#
# extern crate curve25519_dalek;
# use curve25519_dalek::scalar::Scalar;
#
# extern crate merlin;
# use merlin::Transcript;
#
# extern crate bulletproofs;
# use bulletproofs::{BulletproofGens, PedersenGens, RangeProof};
#
# fn main() {
// Generators for Pedersen commitments. These can be selected
// independently of the Bulletproofs generators.
let pc_gens = PedersenGens::default();
// Generators for Bulletproofs, valid for proofs up to bitsize 64
// and aggregation size up to 1.
let bp_gens = BulletproofGens::new(64, 1);
// A secret value we want to prove lies in the range [0, 2^32)
let secret_value = 1037578891u64;
// The API takes a blinding factor for the commitment.
let blinding = Scalar::random(&mut thread_rng());
// The proof can be chained to an existing transcript.
// Here we create a transcript with a doctest domain separator.
let mut prover_transcript = Transcript::new(b"doctest example");
// Create a 32bit rangeproof.
let (proof, committed_value) = RangeProof::prove_single(
&bp_gens,
&pc_gens,
&mut prover_transcript,
secret_value,
&blinding,
32,
).expect("A real program could handle errors");
// Verification requires a transcript with identical initial state:
let mut verifier_transcript = Transcript::new(b"doctest example");
assert!(
proof
.verify_single(&bp_gens, &pc_gens, &mut verifier_transcript, &committed_value, 32)
.is_ok()
);
# }
Building
To compile successfully, you will need to have nightly Rust installed, rather than stable.
You can install nightly Rust with rustup:
rustup default nightly
Tests and Benchmarks
Run tests with cargo test
. Run benchmarks with cargo bench
. This crate
uses criterion.rs for benchmarks.
Features
The yoloproofs
feature enables support for rank1 constraint system proofs.
It is UNSTABLE AND UNSUITABLE FOR DEPLOYMENT, and PROVIDED FOR TESTING
ONLY.
The avx2_backend
feature enables curve25519dalek
's AVX2 backend,
which implements curve arithmetic using parallel
formulas. To use it for Bulletproofs, the
target_cpu
must support AVX2:
RUSTFLAGS="C target_cpu=skylake" cargo bench features "avx2_backend"
SkylakeX CPUs have double the AVX2 registers. To use them, try
RUSTFLAGS="C target_cpu=skylakeavx512" cargo bench features "avx2_backend"
This prevents spills in the AVX2 parallel field multiplication code, but causes worse code generation elsewhere ¯\_(ツ)_/¯
About
This is a research project sponsored by Interstellar, developed by Henry de Valence, Cathie Yun, and Oleg Andreev.