w3f_ring_proof/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2use ark_ff::PrimeField;
3use ark_serialize::CanonicalSerialize;
4use ark_std::rand::RngCore;
5use w3f_pcs::pcs::PCS;
6
7pub use piop::index;
8pub use w3f_plonk_common::cond_select::CondSelect;
9pub use w3f_plonk_common::domain::Domain;
10use w3f_plonk_common::Proof;
11
12pub use crate::piop::{params::PiopParams, FixedColumnsCommitted, ProverKey, VerifierKey};
13use crate::piop::{RingCommitments, RingEvaluations};
14
15pub mod multi_ring_batch_verifier;
16pub mod piop;
17pub mod ring;
18pub mod ring_prover;
19pub mod ring_verifier;
20
21pub type RingProof<F, CS> = Proof<F, CS, RingCommitments<F, <CS as PCS<F>>::C>, RingEvaluations<F>>;
22
23/// Polynomial Commitment Schemes.
24pub use w3f_pcs::pcs;
25
26#[derive(Clone)]
27pub struct ArkTranscript(ark_transcript::Transcript);
28
29impl<F: PrimeField, CS: PCS<F>> w3f_plonk_common::transcript::PlonkTranscript<F, CS>
30    for ArkTranscript
31{
32    fn _128_bit_point(&mut self, label: &'static [u8]) -> F {
33        self.0.challenge(label).read_reduce()
34    }
35
36    fn _add_serializable(&mut self, label: &'static [u8], message: &impl CanonicalSerialize) {
37        self.0.label(label);
38        self.0.append(message);
39    }
40
41    fn to_rng(mut self) -> impl RngCore {
42        self.0.challenge(b"transcript_rng")
43    }
44}
45
46impl ArkTranscript {
47    pub fn new(label: &'static [u8]) -> Self {
48        Self(ark_transcript::Transcript::new_labeled(label))
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    use ark_bls12_381::Bls12_381;
55    use ark_ec::CurveGroup;
56    use ark_ed_on_bls12_381_bandersnatch::{BandersnatchConfig, EdwardsAffine, Fq, Fr};
57    use ark_std::ops::Mul;
58    use ark_std::rand::Rng;
59    use ark_std::{end_timer, start_timer, test_rng, UniformRand};
60    use w3f_pcs::pcs::kzg::KZG;
61
62    use w3f_plonk_common::test_helpers::random_vec;
63
64    use crate::ring::{Ring, RingBuilderKey};
65    use crate::ring_prover::RingProver;
66    use crate::ring_verifier::RingVerifier;
67
68    use super::*;
69
70    fn _test_ring_proof<CS: PCS<Fq> + Clone>(
71        domain_size: usize,
72        batch_size: usize,
73    ) -> (
74        RingVerifier<Fq, CS, BandersnatchConfig>,
75        Vec<(EdwardsAffine, RingProof<Fq, CS>)>,
76    ) {
77        let rng = &mut test_rng();
78
79        let (pcs_params, piop_params) = setup::<_, CS>(rng, domain_size);
80        let keyset_size = piop_params.keyset_part_size;
81        let pks = random_vec::<EdwardsAffine, _>(keyset_size, rng);
82        let (prover_key, verifier_key) = index::<_, CS, _>(&pcs_params, &piop_params, &pks);
83
84        let prover = RingProver::init(
85            prover_key.clone(),
86            piop_params.clone(),
87            0,
88            ArkTranscript::new(b"w3f-ring-proof-test"),
89        );
90
91        let ring_verifier = RingVerifier::init(
92            verifier_key,
93            piop_params.clone(),
94            ArkTranscript::new(b"w3f-ring-proof-test"),
95        );
96        let t_prove = start_timer!(|| {
97            format!("Proving {batch_size} KZG ring-proofs with plonk, domain={domain_size}, max_keys={keyset_size}")
98        });
99        let claims: Vec<(EdwardsAffine, RingProof<Fq, CS>)> = (0..batch_size)
100            .map(|_| {
101                let pk_idx = rng.gen_range(0..keyset_size);
102                let r = Fr::rand(rng);
103                let (blinded_pk, mem_proof) = prover.rerandomize_pk(pk_idx, r);
104                assert_eq!(blinded_pk, piop_params.blind_pk(pks[pk_idx], r));
105                (blinded_pk, mem_proof)
106            })
107            .collect();
108        end_timer!(t_prove);
109
110        let t_verify =
111            start_timer!(|| format!("Verifying {batch_size} KZG ring-proofs with plonk"));
112        let (blinded_pks, proofs) = claims.iter().cloned().unzip();
113        assert!(ring_verifier.verify_batch(proofs, blinded_pks));
114        end_timer!(t_verify);
115        (ring_verifier, claims)
116    }
117
118    #[test]
119    // cargo test test_ring_proof_kzg --release --features="print-trace" -- --show-output
120    fn test_ring_proof_kzg() {
121        _test_ring_proof::<KZG<Bls12_381>>(2usize.pow(9), 1);
122    }
123
124    #[test]
125    fn test_ring_proof_id() {
126        _test_ring_proof::<pcs::IdentityCommitment>(2usize.pow(10), 1);
127    }
128
129    // `zip` would silently drop unmatched elements, reporting success for
130    // inputs that received no verification at all (srlabs_findings#713).
131    #[test]
132    fn test_batch_length_mismatch_rejected() {
133        let (verifier, mut claims) = _test_ring_proof::<KZG<Bls12_381>>(2usize.pow(9), 1);
134        let (result, proof) = claims.pop().unwrap();
135        assert!(verifier.verify(proof.clone(), result));
136
137        assert!(!verifier.verify_batch(Vec::new(), vec![result]));
138        assert!(!verifier.verify_batch(vec![proof.clone()], Vec::new()));
139        assert!(!verifier.verify_batch_kzg(Vec::new(), vec![result]));
140        assert!(!verifier.verify_batch_kzg(vec![proof], Vec::new()));
141    }
142
143    #[test]
144    fn test_lagrangian_commitment() {
145        let rng = &mut test_rng();
146
147        let domain_size = 2usize.pow(9);
148
149        let (pcs_params, piop_params) = setup::<_, KZG<Bls12_381>>(rng, domain_size);
150        let ring_builder_key = RingBuilderKey::from_srs(&pcs_params, domain_size);
151
152        let max_keyset_size = piop_params.keyset_part_size;
153        let keyset_size: usize = rng.gen_range(0..max_keyset_size);
154        let pks = random_vec::<EdwardsAffine, _>(keyset_size, rng);
155
156        let (_, verifier_key) = index::<_, KZG<Bls12_381>, _>(&pcs_params, &piop_params, &pks);
157
158        let ring = Ring::<_, Bls12_381, _>::with_keys(&piop_params, &pks, &ring_builder_key);
159
160        let fixed_columns_committed = FixedColumnsCommitted::from_ring(&ring);
161        assert_eq!(
162            fixed_columns_committed,
163            verifier_key.fixed_columns_committed
164        );
165    }
166
167    pub fn setup<R: Rng, CS: PCS<Fq>>(
168        rng: &mut R,
169        domain_size: usize,
170    ) -> (CS::Params, PiopParams<EdwardsAffine>) {
171        let setup_degree = 3 * domain_size;
172        let pcs_params = CS::setup(setup_degree, rng);
173        let piop_params = PiopParams::rand(domain_size, rng);
174        (pcs_params, piop_params)
175    }
176
177    // cargo test test_ring_proof_batch_kzg_verification --release --features="print-trace" -- --show-output
178    //
179    // Batch vs sequential verification times (ms):
180    //
181    // | proofs | sequential | batch  | speedup |
182    // |--------|------------|--------|---------|
183    // | 1      | 3.032      | 2.790  | 1.09x   |
184    // | 2      | 6.425      | 3.218  | 2.00x   |
185    // | 4      | 11.968     | 5.122  | 2.34x   |
186    // | 8      | 23.922     | 6.487  | 3.69x   |
187    // | 16     | 47.773     | 10.002 | 4.78x   |
188    // | 32     | 95.570     | 16.601 | 5.76x   |
189    // | 64     | 210.959    | 29.484 | 7.15x   |
190    // | 128    | 422.217    | 52.170 | 8.09x   |
191    // | 256    | 762.874    | 85.164 | 8.96x   |
192    //
193    // Sequential verification scales linearly with proof count.
194    // Batch verification scales sub-linearly.
195    #[test]
196    fn test_ring_proof_batch_kzg_verification() {
197        let batch_size: usize = 2;
198        let domain_size = 2usize.pow(9);
199        let (verifier, claims) = _test_ring_proof::<KZG<Bls12_381>>(domain_size, batch_size);
200        let (blinded_pks, proofs) = claims.into_iter().unzip();
201        let t_batch_verify =
202            start_timer!(|| format!("Batch-verifying {batch_size} KZG ring-proofs with plonk"));
203        assert!(verifier.verify_batch_kzg(proofs, blinded_pks));
204        end_timer!(t_batch_verify);
205    }
206
207    #[test]
208    fn test_multi_ring_batch_verify_kzg() {
209        let rng = &mut test_rng();
210        let domain_size = 2usize.pow(9);
211        let proofs_per_ring = 4;
212
213        let (pcs_params, piop_params) = setup::<_, KZG<Bls12_381>>(rng, domain_size);
214
215        // Ring A
216        let keyset_size_a = piop_params.keyset_part_size;
217        let pks_a = random_vec::<EdwardsAffine, _>(keyset_size_a, rng);
218        let (prover_key_a, verifier_key_a) =
219            index::<_, KZG<Bls12_381>, _>(&pcs_params, &piop_params, &pks_a);
220
221        // Ring B (smaller keyset)
222        let keyset_size_b = piop_params.keyset_part_size / 2;
223        let pks_b = random_vec::<EdwardsAffine, _>(keyset_size_b, rng);
224        let (prover_key_b, verifier_key_b) =
225            index::<_, KZG<Bls12_381>, _>(&pcs_params, &piop_params, &pks_b);
226
227        let mut generate_claims = |prover_key: &ProverKey<Fq, KZG<Bls12_381>, EdwardsAffine>,
228                                   pks: &[EdwardsAffine],
229                                   keyset_size: usize| {
230            (0..proofs_per_ring)
231                .map(|_| {
232                    let prover_idx = rng.gen_range(0..keyset_size);
233                    let prover = RingProver::init(
234                        prover_key.clone(),
235                        piop_params.clone(),
236                        prover_idx,
237                        ArkTranscript::new(b"w3f-ring-proof-test"),
238                    );
239                    let blinding_factor = Fr::rand(rng);
240                    let blinded_pk =
241                        (pks[prover_idx] + piop_params.h.mul(blinding_factor)).into_affine();
242                    let proof = prover.prove(blinding_factor);
243                    (blinded_pk, proof)
244                })
245                .collect::<Vec<_>>()
246        };
247
248        let claims_a = generate_claims(&prover_key_a, &pks_a, keyset_size_a);
249        let claims_b = generate_claims(&prover_key_b, &pks_b, keyset_size_b);
250
251        let verifier_a = RingVerifier::init(
252            verifier_key_a,
253            piop_params.clone(),
254            ArkTranscript::new(b"w3f-ring-proof-test"),
255        );
256        let verifier_b = RingVerifier::init(
257            verifier_key_b,
258            piop_params,
259            ArkTranscript::new(b"w3f-ring-proof-test"),
260        );
261
262        // Sanity: individual verification
263        for (result, proof) in &claims_a {
264            assert!(verifier_a.verify(proof.clone(), *result));
265        }
266        for (result, proof) in &claims_b {
267            assert!(verifier_b.verify(proof.clone(), *result));
268        }
269
270        // Multi-ring batch verification
271        use crate::multi_ring_batch_verifier::BatchVerifier;
272        let mut batch = BatchVerifier::new(
273            verifier_a.pcs_vk().clone(),
274            verifier_a.plonk_verifier.transcript_prelude.clone(),
275        );
276        for (result, proof) in claims_a {
277            batch.push(&verifier_a, proof, result);
278        }
279        for (result, proof) in claims_b {
280            batch.push(&verifier_b, proof, result);
281        }
282        assert!(batch.verify());
283    }
284}
w3f_ring_proof/lib.rs

w3f_ring_proof/
lib.rs
