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

w3f_ring_proof/
lib.rs
