w3f_ring_proof/
ring.rs

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

w3f_ring_proof/
ring.rs
