w3f_ring_proof/
ring.rs

1use ark_ec::pairing::Pairing;
2use ark_ec::twisted_edwards::{Affine, TECurveConfig};
3use ark_ec::{AffineRepr, CurveGroup, VariableBaseMSM};
4use ark_ff::PrimeField;
5use ark_poly::EvaluationDomain;
6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
7use ark_std::fmt;
8use ark_std::iter;
9use ark_std::ops::Range;
10use ark_std::vec::Vec;
11use w3f_pcs::pcs::kzg::urs::URS;
12use w3f_pcs::pcs::PcsParams;
13
14use w3f_plonk_common::domain::ZK_ROWS;
15
16use crate::PiopParams;
17
18const IDLE_ROWS: usize = ZK_ROWS + 1;
19
20/// Commitment to a list of VRF public keys as is used as a public input to the ring proof SNARK verifier.
21///
22/// The VRF keys are (inner) curve points that we represent in the affine Twisted Edwards coordinates.
23/// We commit to the coordinate vectors independently using KZG on the outer curve. To make the commitment
24/// updatable we use SRS in the Lagrangian form: `L1, ..., Ln`, where `Li = L_i(t)G`.
25/// The commitment to a vector `a1, ..., an` is then `a1L1 + ... + anLn`.
26///
27/// We pad the list of keys with a `padding` point with unknown dlog up to a certain size.
28/// Additionally, to make the commitment compatible with the snark,
29/// we append the power-of-2 powers of the VRF blinding Pedersen base
30/// `H, 2H, 4H, ..., 2^(s-1)H`, where `s` is the bitness of the VRF curve scalar field.
31/// The last `IDLE_ROWS = 4` elements are set to `(0, 0)`.
32///
33/// Thus, the vector of points we commit to coordinatewise is
34/// `pk1, ..., pkn, padding, ..., padding, H, 2H, ..., 2^(s-1)H, 0, 0, 0, 0`
35#[derive(Clone, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
36pub struct Ring<
37    F: PrimeField,
38    KzgCurve: Pairing<ScalarField = F>,
39    VrfCurveConfig: TECurveConfig<BaseField = F>,
40> {
41    /// KZG commitment to the x coordinates of the described vector.
42    pub cx: KzgCurve::G1Affine,
43    /// KZG commitment to the y coordinates of the described vector.
44    pub cy: KzgCurve::G1Affine,
45    /// KZG commitment to a bitvector highlighting the part of the vector corresponding to the public keys.
46    pub selector: KzgCurve::G1Affine,
47    /// Maximal number of keys the commitment can "store". For domain of size `N` it is `N - (s + IDLE_ROWS)`.
48    pub max_keys: usize,
49    /// Number of keys "stored" in this commitment.
50    pub curr_keys: usize,
51    // Padding point.
52    pub padding: Affine<VrfCurveConfig>,
53}
54
55impl<
56        F: PrimeField,
57        KzgCurve: Pairing<ScalarField = F>,
58        VrfCurveConfig: TECurveConfig<BaseField = F>,
59    > fmt::Debug for Ring<F, KzgCurve, VrfCurveConfig>
60{
61    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
62        write!(
63            f,
64            "Ring(curr_keys={}, max_keys{})",
65            self.curr_keys, self.max_keys
66        )
67    }
68}
69
70impl<
71        F: PrimeField,
72        KzgCurve: Pairing<ScalarField = F>,
73        VrfCurveConfig: TECurveConfig<BaseField = F>,
74    > Ring<F, KzgCurve, VrfCurveConfig>
75{
76    /// Builds the commitment to the vector
77    /// `padding, ..., padding, H, 2H, ..., 2^(s-1)H, 0, 0, 0, 0`.
78    ///
79    /// We compute it as a sum of commitments of 2 vectors:
80    /// `padding, ..., padding`, and
81    /// `0, ..., 0, (H - padding), (2H - padding), ..., (2^(s-1)H  - padding), -padding, -padding, -padding, -padding`.
82    /// The first one is `padding * G`, the second requires an `(IDLE_ROWS + s)`-msm to compute.
83    ///
84    /// - `piop_params`: SNARK parameters
85    /// - `srs`: Should return `srs[range]` for `range = (piop_params.keyset_part_size..domain_size)`
86    /// - `g`: Generator used in the SRS
87    pub fn empty(
88        piop_params: &PiopParams<F, VrfCurveConfig>,
89        srs: impl Fn(Range<usize>) -> Result<Vec<KzgCurve::G1Affine>, ()>,
90        g: KzgCurve::G1,
91    ) -> Self {
92        let (padding_x, padding_y) = piop_params.padding.xy().unwrap(); // panics on inf, never happens
93        let c1x = g * padding_x;
94        let c1y = g * padding_y;
95
96        let powers_of_h = piop_params.power_of_2_multiples_of_h();
97        let (mut xs, mut ys): (Vec<F>, Vec<F>) = powers_of_h
98            .iter()
99            .map(|p| p.xy().unwrap())
100            .map(|(x, y)| (x - padding_x, y - padding_y))
101            .unzip();
102        xs.resize(xs.len() + IDLE_ROWS, -padding_x);
103        ys.resize(ys.len() + IDLE_ROWS, -padding_y);
104        let domain_size = piop_params.domain.domain().size();
105        let srs_segment = &srs(piop_params.keyset_part_size..domain_size).unwrap();
106        let c2x = KzgCurve::G1::msm(srs_segment, &xs).unwrap();
107        let c2y = KzgCurve::G1::msm(srs_segment, &ys).unwrap();
108
109        let selector_inv = srs_segment.iter().sum::<KzgCurve::G1>();
110        let selector = g - selector_inv;
111
112        let (cx, cy, selector) = {
113            let affine = KzgCurve::G1::normalize_batch(&[c1x + c2x, c1y + c2y, selector]);
114            (affine[0], affine[1], affine[2])
115        };
116
117        Self {
118            cx,
119            cy,
120            selector,
121            max_keys: piop_params.keyset_part_size,
122            curr_keys: 0,
123            padding: piop_params.padding,
124        }
125    }
126
127    /// Appends a set key sequence to the ring.
128    ///
129    /// - `keys`: Keys to append.
130    /// - `srs`: Should return `srs[range]` for `range = (self.curr_keys..self.curr_keys + keys.len())`
131    pub fn append(
132        &mut self,
133        keys: &[Affine<VrfCurveConfig>],
134        srs: impl Fn(Range<usize>) -> Result<Vec<KzgCurve::G1Affine>, ()>,
135    ) {
136        let new_size = self.curr_keys + keys.len();
137        assert!(new_size <= self.max_keys);
138        let (padding_x, padding_y) = self.padding.xy().unwrap();
139        let (xs, ys): (Vec<F>, Vec<F>) = keys
140            .iter()
141            .map(|p| p.xy().unwrap())
142            .map(|(x, y)| (x - padding_x, y - padding_y))
143            .unzip();
144        let srs_segment = &srs(self.curr_keys..self.curr_keys + keys.len()).unwrap();
145        let cx_delta = KzgCurve::G1::msm(srs_segment, &xs).unwrap();
146        let cy_delta = KzgCurve::G1::msm(srs_segment, &ys).unwrap();
147
148        let (new_cx, new_cy) = {
149            let affine = KzgCurve::G1::normalize_batch(&[self.cx + cx_delta, self.cy + cy_delta]);
150            (affine[0], affine[1])
151        };
152
153        self.cx = new_cx;
154        self.cy = new_cy;
155        self.curr_keys = new_size;
156    }
157
158    /// Builds the ring from the keys provided with 2 MSMs of size `keys.len() + scalar_bitlen + 5`.
159    ///
160    /// In some cases it may be beneficial to cash the empty ring, as updating it costs 2 MSMs of size `keys.len()`.
161    ///
162    /// - `piop_params`: SNARK parameters.
163    /// - `srs`: full-size Lagrangian SRS.
164    pub fn with_keys(
165        piop_params: &PiopParams<F, VrfCurveConfig>,
166        keys: &[Affine<VrfCurveConfig>],
167        srs: &RingBuilderKey<F, KzgCurve>,
168    ) -> Self {
169        let (padding_x, padding_y) = piop_params.padding.xy().unwrap(); // panics on inf, never happens
170        let powers_of_h = piop_params.power_of_2_multiples_of_h();
171
172        // Computes
173        // [(pk1 - padding), ..., (pkn - padding),
174        //  (H - padding), ..., (2^(s-1)HH - padding),
175        //  -padding, -padding, -padding, -padding,
176        //  padding].
177        let (xs, ys): (Vec<F>, Vec<F>) = keys
178            .iter()
179            .chain(&powers_of_h)
180            .map(|p| p.xy().unwrap())
181            .map(|(x, y)| (x - padding_x, y - padding_y))
182            .chain(iter::repeat((-padding_x, -padding_y)).take(4))
183            .chain(iter::once((padding_x, padding_y)))
184            .unzip();
185
186        // Composes the corresponding slices of the SRS.
187        let bases = [
188            &srs.lis_in_g1[..keys.len()],
189            &srs.lis_in_g1[piop_params.keyset_part_size..],
190            &[srs.g1.into()],
191        ]
192        .concat();
193
194        let cx = KzgCurve::G1::msm(&bases, &xs).unwrap();
195        let cy = KzgCurve::G1::msm(&bases, &ys).unwrap();
196        let selector_inv = srs.lis_in_g1[piop_params.keyset_part_size..]
197            .iter()
198            .sum::<KzgCurve::G1>();
199        let selector = srs.g1 - selector_inv;
200
201        let (cx, cy, selector) = {
202            let affine = KzgCurve::G1::normalize_batch(&[cx, cy, selector]);
203            (affine[0], affine[1], affine[2])
204        };
205
206        Self {
207            cx,
208            cy,
209            selector,
210            max_keys: piop_params.keyset_part_size,
211            curr_keys: keys.len(),
212            padding: piop_params.padding,
213        }
214    }
215
216    pub fn slots_left(&self) -> usize {
217        self.max_keys - self.curr_keys
218    }
219
220    pub const fn empty_unchecked(
221        domain_size: usize,
222        cx: KzgCurve::G1Affine,
223        cy: KzgCurve::G1Affine,
224        selector: KzgCurve::G1Affine,
225        padding: Affine<VrfCurveConfig>,
226    ) -> Self {
227        let max_keys =
228            domain_size - (VrfCurveConfig::ScalarField::MODULUS_BIT_SIZE as usize + IDLE_ROWS);
229        Self {
230            cx,
231            cy,
232            selector,
233            max_keys,
234            curr_keys: 0,
235            padding,
236        }
237    }
238}
239
240#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
241pub struct RingBuilderKey<F: PrimeField, KzgCurve: Pairing<ScalarField = F>> {
242    // Lagrangian SRS
243    pub lis_in_g1: Vec<KzgCurve::G1Affine>,
244    // generator used in the SRS
245    pub g1: KzgCurve::G1,
246}
247
248impl<F: PrimeField, KzgCurve: Pairing<ScalarField = F>> RingBuilderKey<F, KzgCurve> {
249    pub fn from_srs(srs: &URS<KzgCurve>, domain_size: usize) -> Self {
250        let g1 = srs.powers_in_g1[0].into_group();
251        let ck = srs.ck_with_lagrangian(domain_size);
252        let lis_in_g1 = ck.lagrangian.unwrap().lis_in_g;
253        Self { lis_in_g1, g1 }
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use ark_bls12_381::{Bls12_381, Fr, G1Affine};
260    use ark_ed_on_bls12_381_bandersnatch::{BandersnatchConfig, EdwardsAffine};
261    use ark_std::{test_rng, UniformRand};
262    use w3f_pcs::pcs::kzg::urs::URS;
263    use w3f_pcs::pcs::kzg::KZG;
264    use w3f_pcs::pcs::PCS;
265
266    use w3f_plonk_common::domain::Domain;
267    use w3f_plonk_common::test_helpers::random_vec;
268
269    use crate::ring::Ring;
270    use crate::PiopParams;
271
272    use super::*;
273
274    type TestRing = Ring<Fr, Bls12_381, BandersnatchConfig>;
275
276    #[test]
277    fn test_ring_mgmt() {
278        let rng = &mut test_rng();
279
280        let domain_size = 1 << 9;
281
282        let pcs_params = KZG::<Bls12_381>::setup(domain_size - 1, rng);
283        let ring_builder_key = RingBuilderKey::from_srs(&pcs_params, domain_size);
284        let srs = |range: Range<usize>| Ok(ring_builder_key.lis_in_g1[range].to_vec());
285
286        // piop params
287        let h = EdwardsAffine::rand(rng);
288        let seed = EdwardsAffine::rand(rng);
289        let padding = EdwardsAffine::rand(rng);
290        let domain = Domain::new(domain_size, true);
291        let piop_params = PiopParams::setup(domain, h, seed, padding);
292
293        let mut ring = TestRing::empty(&piop_params, srs, ring_builder_key.g1);
294        let (monimial_cx, monimial_cy) = get_monomial_commitment(&pcs_params, &piop_params, &[]);
295        assert_eq!(ring.cx, monimial_cx);
296        assert_eq!(ring.cy, monimial_cy);
297
298        let keys = random_vec::<EdwardsAffine, _>(ring.max_keys, rng);
299        ring.append(&keys, srs);
300        let (monimial_cx, monimial_cy) = get_monomial_commitment(&pcs_params, &piop_params, &keys);
301        assert_eq!(ring.cx, monimial_cx);
302        assert_eq!(ring.cy, monimial_cy);
303
304        let same_ring = TestRing::with_keys(&piop_params, &keys, &ring_builder_key);
305        assert_eq!(ring, same_ring);
306    }
307
308    #[test]
309    fn test_empty_rings() {
310        let rng = &mut test_rng();
311
312        let domain_size = 1 << 9;
313
314        let pcs_params = KZG::<Bls12_381>::setup(domain_size - 1, rng);
315        let ring_builder_key = RingBuilderKey::from_srs(&pcs_params, domain_size);
316        let srs = |range: Range<usize>| Ok(ring_builder_key.lis_in_g1[range].to_vec());
317
318        // piop params
319        let h = EdwardsAffine::rand(rng);
320        let seed = EdwardsAffine::rand(rng);
321        let padding = EdwardsAffine::rand(rng);
322        let domain = Domain::new(domain_size, true);
323        let piop_params = PiopParams::setup(domain, h, seed, padding);
324
325        let ring = TestRing::empty(&piop_params, srs, ring_builder_key.g1);
326        let same_ring = TestRing::with_keys(&piop_params, &[], &ring_builder_key);
327        assert_eq!(ring, same_ring);
328    }
329
330    fn get_monomial_commitment(
331        pcs_params: &URS<Bls12_381>,
332        piop_params: &PiopParams<Fr, BandersnatchConfig>,
333        keys: &[EdwardsAffine],
334    ) -> (G1Affine, G1Affine) {
335        let (_, verifier_key) =
336            crate::piop::index::<_, KZG<Bls12_381>, _>(pcs_params, piop_params, keys);
337        let [monimial_cx, monimial_cy] = verifier_key.fixed_columns_committed.points;
338        (monimial_cx.0, monimial_cy.0)
339    }
340}
w3f_ring_proof/ring.rs

w3f_ring_proof/
ring.rs
