1use ark_crypto_primitives::sponge::Absorb;
  2use ark_ec::{CurveGroup, Group};
  3use ark_ff::{One, PrimeField};
  4use ark_poly::univariate::DensePolynomial;
  5use ark_poly::{DenseMultilinearExtension, DenseUVPolynomial, Polynomial};
  6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
  7use ark_std::{log2, Zero};
  8
  9use super::mova::{CommittedInstance, Witness};
 10use crate::transcript::Transcript;
 11use crate::utils::mle::dense_vec_to_dense_mle;
 12use crate::Error;
 13
 14/// Implements the Points vs Line as described in
 15/// [Mova](https://eprint.iacr.org/2024/1220.pdf) and Section 4.5.2 from Thaler’s book
 16
 17/// Claim from step 3 protocol 6
 18pub struct PointvsLineEvaluationClaim<C: CurveGroup> {
 19    pub mleE1_prime: C::ScalarField,
 20    pub mleE2_prime: C::ScalarField,
 21    pub rE_prime: Vec<C::ScalarField>,
 22}
 23/// Proof from step 1 protocol 6
 24#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 25pub struct PointVsLineProof<C: CurveGroup> {
 26    pub h1: DensePolynomial<C::ScalarField>,
 27    pub h2: DensePolynomial<C::ScalarField>,
 28}
 29
 30#[derive(Clone, Debug, Default)]
 31pub struct PointVsLine<C: CurveGroup, T: Transcript<C::ScalarField>> {
 32    _phantom_C: std::marker::PhantomData<C>,
 33    _phantom_T: std::marker::PhantomData<T>,
 34}
 35
 36/// Protocol 6 from Mova
 37impl<C: CurveGroup, T: Transcript<C::ScalarField>> PointVsLine<C, T>
 38where
 39    <C as Group>::ScalarField: Absorb,
 40{
 41    pub fn prove(
 42        transcript: &mut T,
 43        ci1: &CommittedInstance<C>,
 44        ci2: &CommittedInstance<C>,
 45        w1: &Witness<C>,
 46        w2: &Witness<C>,
 47    ) -> Result<(PointVsLineProof<C>, PointvsLineEvaluationClaim<C>), Error> {
 48        let n_vars: usize = log2(w1.E.len()) as usize;
 49
 50        let mleE1 = dense_vec_to_dense_mle(n_vars, &w1.E);
 51        let mleE2 = dense_vec_to_dense_mle(n_vars, &w2.E);
 52
 53        // We have l(0) = r1, l(1) = r2 so we know that l(x) = r1 + x(r2-r1) thats why we need r2-r1
 54        let r1_sub_r2: Vec<<C>::ScalarField> = ci1
 55            .rE
 56            .iter()
 57            .zip(&ci2.rE)
 58            .map(|(&r1, r2)| r1 - r2)
 59            .collect();
 60
 61        let h1 = compute_h(&mleE1, &ci1.rE, &r1_sub_r2)?;
 62        let h2 = compute_h(&mleE2, &ci1.rE, &r1_sub_r2)?;
 63
 64        transcript.absorb(&h1.coeffs());
 65        transcript.absorb(&h2.coeffs());
 66
 67        let beta_scalar = C::ScalarField::from_le_bytes_mod_order(b"beta");
 68        transcript.absorb(&beta_scalar);
 69        let beta = transcript.get_challenge();
 70
 71        let mleE1_prime = h1.evaluate(&beta);
 72        let mleE2_prime = h2.evaluate(&beta);
 73
 74        let rE_prime = compute_l(&ci1.rE, &r1_sub_r2, beta)?;
 75
 76        Ok((
 77            PointVsLineProof { h1, h2 },
 78            PointvsLineEvaluationClaim {
 79                mleE1_prime,
 80                mleE2_prime,
 81                rE_prime,
 82            },
 83        ))
 84    }
 85
 86    pub fn verify(
 87        transcript: &mut T,
 88        ci1: &CommittedInstance<C>,
 89        ci2: &CommittedInstance<C>,
 90        proof: &PointVsLineProof<C>,
 91        mleE1_prime: &<C>::ScalarField,
 92        mleE2_prime: &<C>::ScalarField,
 93    ) -> Result<
 94        Vec<<C>::ScalarField>, // rE=rE1'=rE2'.
 95        Error,
 96    > {
 97        if proof.h1.evaluate(&C::ScalarField::zero()) != ci1.mleE {
 98            return Err(Error::NotEqual);
 99        }
100
101        if proof.h2.evaluate(&C::ScalarField::one()) != ci2.mleE {
102            return Err(Error::NotEqual);
103        }
104
105        transcript.absorb(&proof.h1.coeffs());
106        transcript.absorb(&proof.h2.coeffs());
107
108        let beta_scalar = C::ScalarField::from_le_bytes_mod_order(b"beta");
109        transcript.absorb(&beta_scalar);
110        let beta = transcript.get_challenge();
111
112        if *mleE1_prime != proof.h1.evaluate(&beta) {
113            return Err(Error::NotEqual);
114        }
115
116        if *mleE2_prime != proof.h2.evaluate(&beta) {
117            return Err(Error::NotEqual);
118        }
119
120        let r1_sub_r2: Vec<<C>::ScalarField> = ci1
121            .rE
122            .iter()
123            .zip(&ci2.rE)
124            .map(|(&r1, r2)| r1 - r2)
125            .collect();
126        let rE_prime = compute_l(&ci1.rE, &r1_sub_r2, beta)?;
127
128        Ok(rE_prime)
129    }
130}
131
132fn compute_h<F: PrimeField>(
133    mle: &DenseMultilinearExtension<F>,
134    r1: &[F],
135    r1_sub_r2: &[F],
136) -> Result<DensePolynomial<F>, Error> {
137    let n_vars: usize = mle.num_vars;
138    if r1.len() != r1_sub_r2.len() || r1.len() != n_vars {
139        return Err(Error::NotEqual);
140    }
141
142    // Initialize the polynomial vector from the evaluations in the multilinear extension.
143    // Each evaluation is turned into a constant polynomial.
144    let mut poly: Vec<DensePolynomial<F>> = mle
145        .evaluations
146        .iter()
147        .map(|&x| DensePolynomial::from_coefficients_slice(&[x]))
148        .collect();
149
150    for (i, (&r1_i, &r1_sub_r2_i)) in r1.iter().zip(r1_sub_r2.iter()).enumerate().take(n_vars) {
151        // Create a linear polynomial r(X) = r1_i + (r1_sub_r2_i) * X (basically l)
152        let r = DensePolynomial::from_coefficients_slice(&[r1_i, r1_sub_r2_i]);
153        let half_len = 1 << (n_vars - i - 1);
154
155        for b in 0..half_len {
156            let left = &poly[b << 1];
157            let right = &poly[(b << 1) + 1];
158            poly[b] = left + &(&r * &(right - left));
159        }
160    }
161
162    // After the loop, we should be left with a single polynomial, so return it.
163    Ok(poly.swap_remove(0))
164}
165
166fn compute_l<F: PrimeField>(r1: &[F], r1_sub_r2: &[F], x: F) -> Result<Vec<F>, Error> {
167    if r1.len() != r1_sub_r2.len() {
168        return Err(Error::NotEqual);
169    }
170
171    // we have l(x) = r1 + x(r2-r1) so return the result
172    Ok(r1
173        .iter()
174        .zip(r1_sub_r2)
175        .map(|(&r1, &r1_sub_r0)| r1 + x * r1_sub_r0)
176        .collect())
177}
178
179#[cfg(test)]
180mod tests {
181    use super::{compute_h, compute_l};
182    use ark_pallas::Fq;
183    use ark_poly::{DenseMultilinearExtension, DenseUVPolynomial};
184
185    #[test]
186    fn test_compute_h() {
187        let mle = DenseMultilinearExtension::from_evaluations_slice(1, &[Fq::from(1), Fq::from(2)]);
188        let r0 = [Fq::from(5)];
189        let r1 = [Fq::from(6)];
190        let r1_sub_r0: Vec<Fq> = r1.iter().zip(&r0).map(|(&x, y)| x - y).collect();
191
192        let result = compute_h(&mle, &r0, &r1_sub_r0).unwrap();
193        assert_eq!(
194            result,
195            DenseUVPolynomial::from_coefficients_slice(&[Fq::from(6), Fq::from(1)])
196        );
197
198        let mle = DenseMultilinearExtension::from_evaluations_slice(1, &[Fq::from(1), Fq::from(2)]);
199        let r0 = [Fq::from(4)];
200        let r1 = [Fq::from(7)];
201        let r1_sub_r0: Vec<Fq> = r1.iter().zip(&r0).map(|(&x, y)| x - y).collect();
202
203        let result = compute_h(&mle, &r0, &r1_sub_r0).unwrap();
204        assert_eq!(
205            result,
206            DenseUVPolynomial::from_coefficients_slice(&[Fq::from(5), Fq::from(3)])
207        );
208
209        let mle = DenseMultilinearExtension::from_evaluations_slice(
210            2,
211            &[Fq::from(1), Fq::from(2), Fq::from(3), Fq::from(4)],
212        );
213        let r0 = [Fq::from(5), Fq::from(4)];
214        let r1 = [Fq::from(2), Fq::from(7)];
215        let r1_sub_r0: Vec<Fq> = r1.iter().zip(&r0).map(|(&x, y)| x - y).collect();
216
217        let result = compute_h(&mle, &r0, &r1_sub_r0).unwrap();
218        assert_eq!(
219            result,
220            DenseUVPolynomial::from_coefficients_slice(&[Fq::from(14), Fq::from(3)])
221        );
222        let mle = DenseMultilinearExtension::from_evaluations_slice(
223            3,
224            &[
225                Fq::from(1),
226                Fq::from(2),
227                Fq::from(3),
228                Fq::from(4),
229                Fq::from(5),
230                Fq::from(6),
231                Fq::from(7),
232                Fq::from(8),
233            ],
234        );
235        let r0 = [Fq::from(1), Fq::from(2), Fq::from(3)];
236        let r1 = [Fq::from(5), Fq::from(6), Fq::from(7)];
237        let r1_sub_r0: Vec<Fq> = r1.iter().zip(&r0).map(|(&x, y)| x - y).collect();
238
239        let result = compute_h(&mle, &r0, &r1_sub_r0).unwrap();
240        assert_eq!(
241            result,
242            DenseUVPolynomial::from_coefficients_slice(&[Fq::from(18), Fq::from(28)])
243        );
244    }
245
246    #[test]
247    fn test_compute_h_errors() {
248        let mle = DenseMultilinearExtension::from_evaluations_slice(1, &[Fq::from(1), Fq::from(2)]);
249        let r0 = [Fq::from(5)];
250        let r1_sub_r0 = [];
251        let result = compute_h(&mle, &r0, &r1_sub_r0);
252        assert!(result.is_err());
253
254        let mle = DenseMultilinearExtension::from_evaluations_slice(
255            2,
256            &[Fq::from(1), Fq::from(2), Fq::from(1), Fq::from(2)],
257        );
258        let r0 = [Fq::from(4)];
259        let r1 = [Fq::from(7)];
260        let r1_sub_r0: Vec<Fq> = r1.iter().zip(&r0).map(|(&x, y)| x - y).collect();
261
262        let result = compute_h(&mle, &r0, &r1_sub_r0);
263        assert!(result.is_err())
264    }
265
266    #[test]
267    fn test_compute_l() {
268        // Test with simple non-zero values
269        let r1 = vec![Fq::from(1), Fq::from(2), Fq::from(3)];
270        let r1_sub_r2 = vec![Fq::from(4), Fq::from(5), Fq::from(6)];
271        let x = Fq::from(2);
272
273        let expected = vec![
274            Fq::from(1) + Fq::from(2) * Fq::from(4),
275            Fq::from(2) + Fq::from(2) * Fq::from(5),
276            Fq::from(3) + Fq::from(2) * Fq::from(6),
277        ];
278
279        let result = compute_l(&r1, &r1_sub_r2, x).unwrap();
280        assert_eq!(result, expected);
281    }
282}