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:
- [
same_scalar_argument] - [
same_permutation_argument] - [
grand_product_argument] - [
inner_product_argument] - [
same_multiscalar_argument]
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:
# // 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.
#
# use ark_std::rand::prelude::SliceRandom;
# use ark_std::UniformRand;
# use ark_bls12_381::Fr;
# use ark_bls12_381::G1Affine;
# use ark_bls12_381::G1Projective;
# use ark_ec::ProjectiveCurve;
# use ark_std::rand::{rngs::StdRng, SeedableRng};
# use core::iter;
#
# use curdleproofs::N_BLINDERS;
# use curdleproofs::curdleproofs::{CurdleproofsProof, generate_crs};
# use curdleproofs::util::shuffle_permute_and_commit_input;
#
# fn main() {
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.
17 Aug 29, 2022
270 Jan 5, 2023
75 Jul 4, 2022
50 Oct 31, 2022
1 Dec 30, 2021
404 Jan 1, 2023
529 Jan 5, 2023
65 Dec 16, 2022
44 Dec 27, 2022
7 Dec 20, 2022
21 Dec 28, 2022
68 Dec 5, 2022
40 Mar 6, 2023
43 May 20, 2023
7 Jul 28, 2023
3 Nov 8, 2023
10.4k Jan 10, 2023
743 Jan 1, 2023
3 Sep 30, 2021
2 Nov 8, 2022
2 Jan 14, 2022
2.8k Dec 31, 2022
5 Dec 20, 2022
11 May 9, 2023
97 Jun 26, 2023
2 Jul 13, 2023
4 Jun 12, 2023
4 Nov 21, 2023
653 Jan 3, 2023