1use ark_ec::CurveGroup;
 2use ark_std::{rand::RngCore, UniformRand};
 3
 4use super::{CommittedInstance, Witness};
 5use crate::arith::ArithSampler;
 6use crate::arith::{r1cs::R1CS, Arith};
 7use crate::commitment::CommitmentScheme;
 8use crate::folding::circuits::CF1;
 9use crate::Error;
10
11/// Implements `Arith` for R1CS, where the witness is of type [`Witness`], and
12/// the committed instance is of type [`CommittedInstance`].
13///
14/// Due to the error terms `Witness.E` and `CommittedInstance.u`, R1CS here is
15/// considered as a relaxed R1CS.
16///
17/// One may wonder why we do not provide distinct structs for R1CS and relaxed
18/// R1CS.
19/// This is because both plain R1CS and relaxed R1CS have the same structure:
20/// they are both represented by three matrices.
21/// What makes them different is the error terms, which are not part of the R1CS
22/// struct, but are part of the witness and committed instance.
23///
24/// As a follow-up, one may further ask why not providing a trait for relaxed
25/// R1CS and implement it for the `R1CS` struct, where the relaxed R1CS trait
26/// has methods for relaxed satisfiability check, while the `Arith` trait that
27/// `R1CS` implements has methods for plain satisfiability check.
28/// However, it would be more ideal if we have a single method that can smartly
29/// choose the type of satisfiability check, which would make the code more
30/// generic and easier to maintain.
31///
32/// This is achieved thanks to the new design of the [`Arith`] trait, where we
33/// can implement the trait for the same constraint system with different types
34/// of witnesses and committed instances.
35/// For R1CS, whether it is relaxed or not is now determined by the types of `W`
36/// and `U`: the satisfiability check is relaxed if `W` and `U` are defined by
37/// folding schemes, and plain if they are vectors of field elements.
38impl<C: CurveGroup> Arith<Witness<C>, CommittedInstance<C>> for R1CS<CF1<C>> {
39    type Evaluation = Vec<CF1<C>>;
40
41    fn eval_relation(
42        &self,
43        w: &Witness<C>,
44        u: &CommittedInstance<C>,
45    ) -> Result<Self::Evaluation, Error> {
46        self.eval_at_z(&[&[u.u][..], &u.x, &w.W].concat())
47    }
48
49    fn check_evaluation(
50        w: &Witness<C>,
51        _u: &CommittedInstance<C>,
52        e: Self::Evaluation,
53    ) -> Result<(), Error> {
54        (w.E == e).then_some(()).ok_or(Error::NotSatisfied)
55    }
56}
57
58impl<C: CurveGroup> ArithSampler<C, Witness<C>, CommittedInstance<C>> for R1CS<CF1<C>> {
59    fn sample_witness_instance<CS: CommitmentScheme<C, true>>(
60        &self,
61        params: &CS::ProverParams,
62        mut rng: impl RngCore,
63    ) -> Result<(Witness<C>, CommittedInstance<C>), Error> {
64        // Implements sampling a (committed) RelaxedR1CS
65        // See construction 5 in https://eprint.iacr.org/2023/573.pdf
66        let u = C::ScalarField::rand(&mut rng);
67        let rE = C::ScalarField::rand(&mut rng);
68        let rW = C::ScalarField::rand(&mut rng);
69
70        let W = (0..self.A.n_cols - self.l - 1)
71            .map(|_| C::ScalarField::rand(&mut rng))
72            .collect();
73        let x = (0..self.l)
74            .map(|_| C::ScalarField::rand(&mut rng))
75            .collect::<Vec<C::ScalarField>>();
76        let mut z = vec![u];
77        z.extend(&x);
78        z.extend(&W);
79
80        let E = self.eval_at_z(&z)?;
81
82        let witness = Witness { E, rE, W, rW };
83        let mut cm_witness = witness.commit::<CS, true>(params, x)?;
84
85        // witness.commit() sets u to 1, we set it to the sampled u value
86        cm_witness.u = u;
87
88        debug_assert!(
89            self.check_relation(&witness, &cm_witness).is_ok(),
90            "Sampled a non satisfiable relaxed R1CS, sampled u: {}, computed E: {:?}",
91            u,
92            witness.E
93        );
94
95        Ok((witness, cm_witness))
96    }
97}