Bulletproofs

The fastest Bulletproofs implementation ever, featuring single and aggregated range proofs, strongly-typed 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 curve25519-dalek. When using the parallel formulas in the curve25519-dalek AVX2 backend, it can verify 64-bit rangeproofs approximately twice as fast as the original libsecp256k1-based Bulletproofs implementation.

This library provides implementations of:

Single-party proofs of single or multiple ranges, using the aggregated rangeproof construction;
Online multi-party computation for rangeproof aggregation between multiple parties, using session types to statically enforce correct protocol flow;
A programmable constraint system API for expressing rank-1 constraint systems, and proving and verifying proofs of arbitrary statements (under development in the circuit branch);
Online multi-party computation for aggregated circuit proofs (planned future work).

These proofs are implemented using Merlin transcripts, allowing them to be arbitrarily composed with other proofs without implementation changes.

Documentation

The user-facing 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 circuit proofs work (under development);
how the constraint system reduction works (under development);
how the aggregated circuit proofs work (future work).

Comparative Performance

The following table gives comparative timings for proving and verification of a 64-bit rangeproof on an i7-7800X with 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
libsecp-endo	secp256k1	16800	2.30x	2080	2.00x
Monero	ed25519 (unsafe)	53300	7.30x	4810	4.63x

This crate also contains other benchmarks; see the Tests and Benchmarks section below for details.

WARNING

This code is still research-quality. It is not (yet) suitable for deployment. The development roadmap can be found in the Milestones section of the Github repo.

Example

# 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 32-bit 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()
);
# }

Tests and Benchmarks

Run tests with cargo test. Run benchmarks with cargo bench. This crate uses criterion.rs for benchmarks.

Features

The avx2_backend feature enables curve25519-dalek'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"

Skylake-X CPUs have double the AVX2 registers. To use them, try

RUSTFLAGS="-C target_cpu=skylake-avx512" 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.

isislovecruft/bulletproofs