curdleproofs 0.0.1-alpha2

An implementation of the Curdleproofs shuffle zero-knowledge argument
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

# Curdleproofs

<center>
<img
    width="30%"
    src="https://github.com/asn-d6/curdleproofs/raw/backup/doc/images/logo.jpg"
/>
</center>

[Curdleproofs](https://XXX.com) is a *zero-knowledge shuffle argument* inspired by [BG12](http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf).

Zero-knowledge shuffle arguments can have multiple use cases:
- [Secret leader election](https://ethresear.ch/t/whisk-a-practical-shuffle-based-ssle-protocol-for-ethereum/11763#proofs-of-correct-shuffle-13) protocols
- Message shuffling in [mixnets](https://eprint.iacr.org/2020/490.pdf)
- Universally verifiable [electronic voting](https://web.cs.ucdavis.edu/~franklin/ecs228/2013/neff_2001.pdf) protocols

## Documentation

The Curdleproofs protocol is described and proved secure on the [Curdleproofs paper](https://XXX.com).

The user-facing documentation for this library can be [found here](https://XXX.com).

In this library we provide high-level protocol overviews for the core [`curdleproofs`] 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](crate::notes::optimizations) to speed up the verifier.

## Performance

The following table gives the proof size as well as timings for proving and verifying Curdleproofs on an Intel i7-XXX over BLS12-381:

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

## Example

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

```rust
# // 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`.