[−][src]Crate bulletproofs

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:

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 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:

Comparative Performance

The following table gives comparative timings for proving and verification of a 64-bit rangeproof on an Intel Skylake-X i7-7800X (@3.5GHz, Turbo Boost disabled). Times are in microseconds (lower is better), with the relative speed compared to the fastest implementation.

ImplementationGroupProving (μs)relVerification (μs)rel
ours (avx2)ristretto25573001.00x10401.00x
ours (u64)ristretto255113001.54x14901.43x
libsecp+endosecp256k1143001.96x19001.83x
libsecp-endosecp256k1168002.30x20802.00x
Moneroed25519 (unsafe)533007.30x48104.63x

Use of the curve25519-dalek IFMA backend gives another 1.5x speedup on a Cannonlake i3-8121U, 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 32-bit rangeproof.

// 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()
);

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 rank-1 constraint system proofs. It is UNSTABLE AND UNSUITABLE FOR DEPLOYMENT, and PROVIDED FOR TESTING ONLY.

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.

Modules

r1cs

The rank-1 constraint system API for programmatically defining constraint systems.

range_proof_mpc

The range_proof_mpc module contains the API for performing the aggregated multiparty computation protocol for joint range proof proving.

Structs

BulletproofGens

The BulletproofGens struct contains all the generators needed for aggregating up to m range proofs of up to n bits each.

BulletproofGensShare

Represents a view of the generators used by a specific party in an aggregated proof.

PedersenGens

Represents a pair of base points for Pedersen commitments.

RangeProof

The RangeProof struct represents a proof that one or more values are in a range.

Enums

ProofError

Represents an error in proof creation, verification, or parsing.