w3f_ring_proof/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2
3use ark_ec::{
4    short_weierstrass::{Affine, SWCurveConfig},
5    AffineRepr,
6};
7use ark_ff::{One, PrimeField, Zero};
8use ark_serialize::CanonicalSerialize;
9use ark_std::rand::RngCore;
10use w3f_pcs::pcs::PCS;
11
12pub use w3f_plonk_common::domain::Domain;
13use w3f_plonk_common::Proof;
14pub use piop::index;
15
16pub use crate::piop::{params::PiopParams, FixedColumnsCommitted, ProverKey, VerifierKey};
17use crate::piop::{RingCommitments, RingEvaluations};
18
19mod piop;
20pub mod ring;
21pub mod ring_prover;
22pub mod ring_verifier;
23
24pub type RingProof<F, CS> = Proof<F, CS, RingCommitments<F, <CS as PCS<F>>::C>, RingEvaluations<F>>;
25
26/// Polynomial Commitment Schemes.
27pub use w3f_pcs::pcs;
28
29// Calling the method for a prime-order curve results in an infinite loop.
30pub fn find_complement_point<Curve: SWCurveConfig>() -> Affine<Curve> {
31    let mut x = Curve::BaseField::zero();
32    loop {
33        let p = Affine::<Curve>::get_point_from_x_unchecked(x, false);
34        if p.is_some() && !p.unwrap().is_in_correct_subgroup_assuming_on_curve() {
35            return p.unwrap();
36        }
37        x = x + Curve::BaseField::one()
38    }
39}
40
41// Try and increment hash to curve.
42pub(crate) fn hash_to_curve<F: PrimeField, Curve: SWCurveConfig<BaseField = F>>(
43    message: &[u8],
44) -> Affine<Curve> {
45    use blake2::Digest;
46    let mut seed = message.to_vec();
47    let cnt_offset = seed.len();
48    seed.push(0);
49    loop {
50        let hash: [u8; 64] = blake2::Blake2b::digest(&seed[..]).into();
51        let x = F::from_le_bytes_mod_order(&hash);
52        if let Some(point) = Affine::<Curve>::get_point_from_x_unchecked(x, false) {
53            let point = point.clear_cofactor();
54            assert!(point.is_in_correct_subgroup_assuming_on_curve());
55            return point;
56        }
57        seed[cnt_offset] += 1;
58    }
59}
60
61#[derive(Clone)]
62pub struct ArkTranscript(ark_transcript::Transcript);
63
64impl<F: PrimeField, CS: PCS<F>> w3f_plonk_common::transcript::PlonkTranscript<F, CS> for ArkTranscript {
65    fn _128_bit_point(&mut self, label: &'static [u8]) -> F {
66        self.0.challenge(label).read_reduce()
67    }
68
69    fn _add_serializable(&mut self, label: &'static [u8], message: &impl CanonicalSerialize) {
70        self.0.label(label);
71        self.0.append(message);
72    }
73
74    fn to_rng(mut self) -> impl RngCore {
75        self.0.challenge(b"transcript_rng")
76    }
77}
78
79impl ArkTranscript {
80    pub fn new(label: &'static [u8]) -> Self {
81        Self(ark_transcript::Transcript::new_labeled(label))
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use ark_bls12_381::Bls12_381;
88    use ark_ec::CurveGroup;
89    use ark_ed_on_bls12_381_bandersnatch::{BandersnatchConfig, Fq, Fr, SWAffine};
90    use ark_ff::MontFp;
91    use ark_std::ops::Mul;
92    use ark_std::rand::Rng;
93    use ark_std::{end_timer, start_timer, test_rng, UniformRand};
94    use w3f_pcs::pcs::kzg::KZG;
95
96    use w3f_plonk_common::test_helpers::random_vec;
97
98    use crate::piop::FixedColumnsCommitted;
99    use crate::ring::{Ring, RingBuilderKey};
100    use crate::ring_prover::RingProver;
101    use crate::ring_verifier::RingVerifier;
102
103    use super::*;
104
105    fn _test_ring_proof<CS: PCS<Fq>>(domain_size: usize) {
106        let rng = &mut test_rng();
107
108        let (pcs_params, piop_params) = setup::<_, CS>(rng, domain_size);
109
110        let max_keyset_size = piop_params.keyset_part_size;
111        let keyset_size: usize = rng.gen_range(0..max_keyset_size);
112        let pks = random_vec::<SWAffine, _>(keyset_size, rng);
113        let k = rng.gen_range(0..keyset_size); // prover's secret index
114        let pk = pks[k].clone();
115
116        let (prover_key, verifier_key) = index::<_, CS, _>(&pcs_params, &piop_params, &pks);
117
118        // PROOF generation
119        let secret = Fr::rand(rng); // prover's secret scalar
120        let result = piop_params.h.mul(secret) + pk;
121        let ring_prover = RingProver::init(
122            prover_key,
123            piop_params.clone(),
124            k,
125            ArkTranscript::new(b"w3f-ring-proof-test"),
126        );
127        let t_prove = start_timer!(|| "Prove");
128        let proof = ring_prover.prove(secret);
129        end_timer!(t_prove);
130
131        let ring_verifier = RingVerifier::init(
132            verifier_key,
133            piop_params,
134            ArkTranscript::new(b"w3f-ring-proof-test"),
135        );
136        let t_verify = start_timer!(|| "Verify");
137        let res = ring_verifier.verify_ring_proof(proof, result.into_affine());
138        end_timer!(t_verify);
139        assert!(res);
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::<SWAffine, _>(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    fn setup<R: Rng, CS: PCS<Fq>>(
167        rng: &mut R,
168        domain_size: usize,
169    ) -> (CS::Params, PiopParams<Fq, BandersnatchConfig>) {
170        let setup_degree = 3 * domain_size;
171        let pcs_params = CS::setup(setup_degree, rng);
172
173        let domain = Domain::new(domain_size, true);
174        let h = SWAffine::rand(rng);
175        let seed = find_complement_point::<BandersnatchConfig>();
176        let piop_params = PiopParams::setup(domain, h, seed);
177
178        (pcs_params, piop_params)
179    }
180
181    #[test]
182    fn test_complement_point() {
183        let p = find_complement_point::<BandersnatchConfig>();
184        assert!(p.is_on_curve());
185        assert!(!p.is_in_correct_subgroup_assuming_on_curve());
186        assert_eq!(
187            p,
188            SWAffine::new_unchecked(
189                MontFp!("0"),
190                MontFp!(
191                    "11982629110561008531870698410380659621661946968466267969586599013782997959645"
192                )
193            )
194        )
195    }
196
197    #[test]
198    fn test_ring_proof_kzg() {
199        _test_ring_proof::<KZG<Bls12_381>>(2usize.pow(10));
200    }
201
202    #[test]
203    fn test_ring_proof_id() {
204        _test_ring_proof::<w3f_pcs::pcs::IdentityCommitment>(2usize.pow(10));
205    }
206}
w3f_ring_proof/lib.rs

w3f_ring_proof/
lib.rs
