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::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    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 t_prove = start_timer!(|| "Prove");
85        let claims: Vec<(EdwardsAffine, RingProof<Fq, CS>)> = (0..batch_size)
86            .map(|_| {
87                let prover_idx = rng.gen_range(0..keyset_size);
88                let prover = RingProver::init(
89                    prover_key.clone(),
90                    piop_params.clone(),
91                    prover_idx,
92                    ArkTranscript::new(b"w3f-ring-proof-test"),
93                );
94                let prover_pk = pks[prover_idx].clone();
95                let blinding_factor = Fr::rand(rng);
96                let blinded_pk = prover_pk + piop_params.h.mul(blinding_factor);
97                let blinded_pk = blinded_pk.into_affine();
98                let proof = prover.prove(blinding_factor);
99                (blinded_pk, proof)
100            })
101            .collect();
102        end_timer!(t_prove);
103
104        let ring_verifier = RingVerifier::init(
105            verifier_key,
106            piop_params,
107            ArkTranscript::new(b"w3f-ring-proof-test"),
108        );
109        let t_verify = start_timer!(|| "Verify");
110        let (blinded_pks, proofs) = claims.iter().cloned().unzip();
111        assert!(ring_verifier.verify_batch(proofs, blinded_pks));
112        end_timer!(t_verify);
113        (ring_verifier, claims)
114    }
115
116    #[test]
117    fn test_lagrangian_commitment() {
118        let rng = &mut test_rng();
119
120        let domain_size = 2usize.pow(9);
121
122        let (pcs_params, piop_params) = setup::<_, KZG<Bls12_381>>(rng, domain_size);
123        let ring_builder_key = RingBuilderKey::from_srs(&pcs_params, domain_size);
124
125        let max_keyset_size = piop_params.keyset_part_size;
126        let keyset_size: usize = rng.gen_range(0..max_keyset_size);
127        let pks = random_vec::<EdwardsAffine, _>(keyset_size, rng);
128
129        let (_, verifier_key) = index::<_, KZG<Bls12_381>, _>(&pcs_params, &piop_params, &pks);
130
131        let ring = Ring::<_, Bls12_381, _>::with_keys(&piop_params, &pks, &ring_builder_key);
132
133        let fixed_columns_committed = FixedColumnsCommitted::from_ring(&ring);
134        assert_eq!(
135            fixed_columns_committed,
136            verifier_key.fixed_columns_committed
137        );
138    }
139
140    fn setup<R: Rng, CS: PCS<Fq>>(
141        rng: &mut R,
142        domain_size: usize,
143    ) -> (CS::Params, PiopParams<Fq, BandersnatchConfig>) {
144        let setup_degree = 3 * domain_size;
145        let pcs_params = CS::setup(setup_degree, rng);
146
147        let domain = Domain::new(domain_size, true);
148        let h = EdwardsAffine::rand(rng);
149        let seed = EdwardsAffine::rand(rng);
150        let padding = EdwardsAffine::rand(rng);
151        let piop_params = PiopParams::setup(domain, h, seed, padding);
152
153        (pcs_params, piop_params)
154    }
155
156    // cargo test test_ring_proof_kzg --release --features="print-trace" -- --show-output
157    //
158    // Batch vs sequential verification times (ms):
159    //
160    // | proofs | sequential | batch  | speedup |
161    // |--------|------------|--------|---------|
162    // | 1      | 3.032      | 2.790  | 1.09x   |
163    // | 2      | 6.425      | 3.218  | 2.00x   |
164    // | 4      | 11.968     | 5.122  | 2.34x   |
165    // | 8      | 23.922     | 6.487  | 3.69x   |
166    // | 16     | 47.773     | 10.002 | 4.78x   |
167    // | 32     | 95.570     | 16.601 | 5.76x   |
168    // | 64     | 210.959    | 29.484 | 7.15x   |
169    // | 128    | 422.217    | 52.170 | 8.09x   |
170    // | 256    | 762.874    | 85.164 | 8.96x   |
171    //
172    // Sequential verification scales linearly with proof count.
173    // Batch verification scales sub-linearly.
174    #[test]
175    fn test_ring_proof_kzg() {
176        let batch_size: usize = 16;
177        let (verifier, claims) = _test_ring_proof::<KZG<Bls12_381>>(2usize.pow(10), batch_size);
178        let t_verify_batch = start_timer!(|| format!("Verify Batch KZG (batch={batch_size})"));
179        let (blinded_pks, proofs) = claims.into_iter().unzip();
180        assert!(verifier.verify_batch_kzg(proofs, blinded_pks));
181        end_timer!(t_verify_batch);
182    }
183
184    #[test]
185    fn test_ring_proof_id() {
186        _test_ring_proof::<w3f_pcs::pcs::IdentityCommitment>(2usize.pow(10), 1);
187    }
188}
w3f_ring_proof/lib.rs

w3f_ring_proof/
lib.rs
