w3f_ring_proof/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2
3use ark_ff::PrimeField;
4use ark_serialize::CanonicalSerialize;
5use ark_std::rand::RngCore;
6use w3f_pcs::pcs::PCS;
7
8pub use piop::index;
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
15mod 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::{AffineRepr, 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::piop::FixedColumnsCommitted;
64    use crate::ring::{Ring, RingBuilderKey};
65    use crate::ring_prover::RingProver;
66    use crate::ring_verifier::RingVerifier;
67
68    use super::*;
69
70    impl<F: PrimeField, CS: PCS<F>> Clone for VerifierKey<F, CS> {
71        fn clone(&self) -> Self {
72            Self {
73                pcs_raw_vk: self.pcs_raw_vk.clone(),
74                fixed_columns_committed: self.fixed_columns_committed.clone(),
75            }
76        }
77    }
78
79    impl<F: PrimeField, CS: PCS<F>, G: AffineRepr<BaseField = F>> Clone for ProverKey<F, CS, G> {
80        fn clone(&self) -> Self {
81            Self {
82                pcs_ck: self.pcs_ck.clone(),
83                fixed_columns: self.fixed_columns.clone(),
84                verifier_key: self.verifier_key.clone(),
85            }
86        }
87    }
88
89    fn _test_ring_proof<CS: PCS<Fq> + Clone>(
90        domain_size: usize,
91        batch_size: usize,
92    ) -> (
93        RingVerifier<Fq, CS, BandersnatchConfig>,
94        Vec<(EdwardsAffine, RingProof<Fq, CS>)>,
95    ) {
96        let rng = &mut test_rng();
97
98        let (pcs_params, piop_params) = setup::<_, CS>(rng, domain_size);
99        let keyset_size = piop_params.keyset_part_size;
100        let pks = random_vec::<EdwardsAffine, _>(keyset_size, rng);
101        let (prover_key, verifier_key) = index::<_, CS, _>(&pcs_params, &piop_params, &pks);
102
103        let t_prove = start_timer!(|| "Prove");
104        let claims: Vec<(EdwardsAffine, RingProof<Fq, CS>)> = (0..batch_size)
105            .map(|_| {
106                let prover_idx = rng.gen_range(0..keyset_size);
107                let prover = RingProver::init(
108                    prover_key.clone(),
109                    piop_params.clone(),
110                    prover_idx,
111                    ArkTranscript::new(b"w3f-ring-proof-test"),
112                );
113                let prover_pk = pks[prover_idx].clone();
114                let blinding_factor = Fr::rand(rng);
115                let blinded_pk = prover_pk + piop_params.h.mul(blinding_factor);
116                let blinded_pk = blinded_pk.into_affine();
117                let proof = prover.prove(blinding_factor);
118                (blinded_pk, proof)
119            })
120            .collect();
121        end_timer!(t_prove);
122
123        let ring_verifier = RingVerifier::init(
124            verifier_key,
125            piop_params,
126            ArkTranscript::new(b"w3f-ring-proof-test"),
127        );
128        let t_verify = start_timer!(|| "Verify");
129        let (blinded_pks, proofs) = claims.iter().cloned().unzip();
130        assert!(ring_verifier.verify_batch(proofs, blinded_pks));
131        end_timer!(t_verify);
132        (ring_verifier, claims)
133    }
134
135    #[test]
136    fn test_lagrangian_commitment() {
137        let rng = &mut test_rng();
138
139        let domain_size = 2usize.pow(9);
140
141        let (pcs_params, piop_params) = setup::<_, KZG<Bls12_381>>(rng, domain_size);
142        let ring_builder_key = RingBuilderKey::from_srs(&pcs_params, domain_size);
143
144        let max_keyset_size = piop_params.keyset_part_size;
145        let keyset_size: usize = rng.gen_range(0..max_keyset_size);
146        let pks = random_vec::<EdwardsAffine, _>(keyset_size, rng);
147
148        let (_, verifier_key) = index::<_, KZG<Bls12_381>, _>(&pcs_params, &piop_params, &pks);
149
150        let ring = Ring::<_, Bls12_381, _>::with_keys(&piop_params, &pks, &ring_builder_key);
151
152        let fixed_columns_committed = FixedColumnsCommitted::from_ring(&ring);
153        assert_eq!(
154            fixed_columns_committed,
155            verifier_key.fixed_columns_committed
156        );
157    }
158
159    fn setup<R: Rng, CS: PCS<Fq>>(
160        rng: &mut R,
161        domain_size: usize,
162    ) -> (CS::Params, PiopParams<Fq, BandersnatchConfig>) {
163        let setup_degree = 3 * domain_size;
164        let pcs_params = CS::setup(setup_degree, rng);
165
166        let domain = Domain::new(domain_size, true);
167        let h = EdwardsAffine::rand(rng);
168        let seed = EdwardsAffine::rand(rng);
169        let padding = EdwardsAffine::rand(rng);
170        let piop_params = PiopParams::setup(domain, h, seed, padding);
171
172        (pcs_params, piop_params)
173    }
174
175    // cargo test test_ring_proof_kzg --release --features="print-trace" -- --show-output
176    //
177    // Batch vs sequential verification times (ms):
178    //
179    // | proofs | sequential | batch  | speedup |
180    // |--------|------------|--------|---------|
181    // | 1      | 3.032      | 2.790  | 1.09x   |
182    // | 2      | 6.425      | 3.218  | 2.00x   |
183    // | 4      | 11.968     | 5.122  | 2.34x   |
184    // | 8      | 23.922     | 6.487  | 3.69x   |
185    // | 16     | 47.773     | 10.002 | 4.78x   |
186    // | 32     | 95.570     | 16.601 | 5.76x   |
187    // | 64     | 210.959    | 29.484 | 7.15x   |
188    // | 128    | 422.217    | 52.170 | 8.09x   |
189    // | 256    | 762.874    | 85.164 | 8.96x   |
190    //
191    // Sequential verification scales linearly with proof count.
192    // Batch verification scales sub-linearly.
193    #[test]
194    fn test_ring_proof_kzg() {
195        let batch_size: usize = 16;
196        let (verifier, claims) = _test_ring_proof::<KZG<Bls12_381>>(2usize.pow(10), batch_size);
197        let t_verify_batch = start_timer!(|| format!("Verify Batch KZG (batch={batch_size})"));
198        let (blinded_pks, proofs) = claims.into_iter().unzip();
199        assert!(verifier.verify_batch_kzg(proofs, blinded_pks));
200        end_timer!(t_verify_batch);
201    }
202
203    #[test]
204    fn test_ring_proof_id() {
205        _test_ring_proof::<w3f_pcs::pcs::IdentityCommitment>(2usize.pow(10), 1);
206    }
207}
w3f_ring_proof/lib.rs

w3f_ring_proof/
lib.rs
