Crate curdleproofs

Source

Expand description

§Curdleproofs

Curdleproofs is a zero-knowledge shuffle argument inspired by BG12.

Zero-knowledge shuffle arguments can have multiple use cases:

Secret leader election protocols
Message shuffling in mixnets
Universally verifiable electronic voting protocols

§Documentation

The user-facing documentation for this library can be found here.

In this library, we provide high-level protocol documentation for the core curdleproofs shuffle argument and its sub-arguments:

There are also notes on the optimizations deployed to speed up the verifier.

For all the details and the security proofs, please see the Curdleproofs paper.

§Performance

The following table gives the proof size as well as timings for proving and verifying Curdleproofs on an Intel i7-8550U CPU @ 1.80GHz over the BLS12-381 curve:

Shuffled Elements	Proving (ms)	Verification (ms)	Shuffling (ms):	Proof Size (bytes)
60	177	22	28	3968
124	304	27	57	4448
252	560	35	121	4928

(The number of shuffled elements above is disturbingly close to a power of two but not quite, because we reserve four elements for zero-knowledge blinders.)

§Example

The following example shows how to create and verify a shuffle proof that shuffles 28 elements:

let mut rng = StdRng::seed_from_u64(0u64);

// Number of elements we are shuffling
let ell = 28;

// Construct the CRS
let crs = generate_crs(ell);

// Generate some witnesses: the permutation and the randomizer
let mut permutation: Vec<u32> = (0..ell as u32).collect();
permutation.shuffle(&mut rng);
let k = Fr::rand(&mut rng);

// Generate some shuffle input vectors
let vec_R: Vec<G1Affine> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
    .take(ell)
    .collect();
let vec_S: Vec<G1Affine> = iter::repeat_with(|| G1Projective::rand(&mut rng).into_affine())
    .take(ell)
    .collect();

// Shuffle and permute inputs to generate output vectors and permutation commitments
let (vec_T, vec_U, M, vec_m_blinders) =
    shuffle_permute_and_commit_input(&crs, &vec_R, &vec_S, &permutation, &k, &mut rng);

// Generate a shuffle proof
let shuffle_proof = CurdleproofsProof::new(
    &crs,
    vec_R.clone(),
    vec_S.clone(),
    vec_T.clone(),
    vec_U.clone(),
    M,
    permutation,
    k,
    vec_m_blinders,
    &mut rng,
);

// Verify the shuffle proof
assert!(shuffle_proof
        .verify(&crs, &vec_R, &vec_S, &vec_T, &vec_U, &M, &mut rng)
        .is_ok());

§Building & Running

This library can be compiled with cargo build and requires rust nightly.

You can run the tests using cargo test --release and the benchmarks using cargo bench.

Modules§

commitments: GroupCommitment commitment scheme
curdleproofs: The Curdleproofs shuffle argument
grand_product_argument: GrandProduct Argument
inner_product_argument: Discrete Logarithm Inner Product Argument
msm_accumulator: Accumulate all MSMs into a giant MSM and verify them all at the end to amortize costs.
notes: This module contains various notes about Curdleproofs.
same_multiscalar_argument: SameMultiscalar Argument
same_permutation_argument: Same Permutation Argument
same_scalar_argument: SameScalar Argument
transcript: A Fiat-Shamir transcript implementation using Merlin
util: Utility functions used around Curdleproofs

Constants§

N_BLINDERS: Number of blinders $n_{bl}$ needed for zero-knowledge