1use ark_crypto_primitives::sponge::{constraints::AbsorbGadget, Absorb};
  2use ark_ec::CurveGroup;
  3use ark_ff::PrimeField;
  4use ark_r1cs_std::{
  5    eq::EqGadget,
  6    fields::{fp::FpVar, FieldVar},
  7    uint8::UInt8,
  8    ToConstraintFieldGadget,
  9};
 10use ark_relations::r1cs::SynthesisError;
 11use ark_std::{cfg_into_iter, log2, One};
 12use rayon::prelude::*;
 13
 14use super::{
 15    constants::RUNNING,
 16    utils::{pow_i, pow_i_var},
 17    CommittedInstance, CommittedInstanceVar, Witness, WitnessVar,
 18};
 19use crate::{
 20    arith::{
 21        r1cs::{circuits::R1CSMatricesVar, R1CS},
 22        Arith, ArithGadget,
 23    },
 24    folding::circuits::CF1,
 25    transcript::AbsorbNonNative,
 26    utils::vec::is_zero_vec,
 27    Error,
 28};
 29
 30// Implements the trait for absorbing ProtoGalaxy's CommittedInstance.
 31impl<C: CurveGroup, const TYPE: bool> Absorb for CommittedInstance<C, TYPE>
 32where
 33    C::ScalarField: Absorb,
 34{
 35    fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
 36        C::ScalarField::batch_to_sponge_bytes(&self.to_sponge_field_elements_as_vec(), dest);
 37    }
 38
 39    fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
 40        self.phi
 41            .to_native_sponge_field_elements_as_vec()
 42            .to_sponge_field_elements(dest);
 43        self.betas.to_sponge_field_elements(dest);
 44        self.e.to_sponge_field_elements(dest);
 45        self.x.to_sponge_field_elements(dest);
 46    }
 47}
 48
 49// Implements the trait for absorbing ProtoGalaxy's CommittedInstanceVar in-circuit.
 50impl<C: CurveGroup, const TYPE: bool> AbsorbGadget<C::ScalarField>
 51    for CommittedInstanceVar<C, TYPE>
 52{
 53    fn to_sponge_bytes(&self) -> Result<Vec<UInt8<C::ScalarField>>, SynthesisError> {
 54        FpVar::batch_to_sponge_bytes(&self.to_sponge_field_elements()?)
 55    }
 56
 57    fn to_sponge_field_elements(&self) -> Result<Vec<FpVar<C::ScalarField>>, SynthesisError> {
 58        Ok([
 59            self.phi.to_constraint_field()?,
 60            self.betas.to_sponge_field_elements()?,
 61            self.e.to_sponge_field_elements()?,
 62            self.x.to_sponge_field_elements()?,
 63        ]
 64        .concat())
 65    }
 66}
 67
 68/// Implements `Arith` for R1CS, where the witness is of type [`Witness`], and
 69/// the committed instance is of type [`CommittedInstance`].
 70///
 71/// Due to the error term `CommittedInstance.e`, R1CS here is considered as a
 72/// relaxed R1CS.
 73///
 74/// See `nova/traits.rs` for the rationale behind the design.
 75impl<C: CurveGroup, const TYPE: bool> Arith<Witness<CF1<C>>, CommittedInstance<C, TYPE>>
 76    for R1CS<CF1<C>>
 77{
 78    type Evaluation = Vec<CF1<C>>;
 79
 80    fn eval_relation(
 81        &self,
 82        w: &Witness<CF1<C>>,
 83        u: &CommittedInstance<C, TYPE>,
 84    ) -> Result<Self::Evaluation, Error> {
 85        self.eval_at_z(&[&[C::ScalarField::one()][..], &u.x, &w.w].concat())
 86    }
 87
 88    fn check_evaluation(
 89        _w: &Witness<C::ScalarField>,
 90        u: &CommittedInstance<C, TYPE>,
 91        e: Vec<C::ScalarField>,
 92    ) -> Result<(), Error> {
 93        let ok = if TYPE == RUNNING {
 94            if u.betas.len() != log2(e.len()) as usize {
 95                return Err(Error::NotSameLength(
 96                    "instance.betas.len()".to_string(),
 97                    u.betas.len(),
 98                    "log2(e.len())".to_string(),
 99                    log2(e.len()) as usize,
100                ));
101            }
102
103            u.e == cfg_into_iter!(e)
104                .enumerate()
105                .map(|(i, e_i)| pow_i(i, &u.betas) * e_i)
106                .sum::<CF1<C>>()
107        } else {
108            is_zero_vec(&e)
109        };
110        ok.then_some(()).ok_or(Error::NotSatisfied)
111    }
112}
113
114/// Unlike its native counterpart, we only need to support running instances in
115/// circuit, as the decider circuit only checks running instance satisfiability.
116impl<C: CurveGroup> ArithGadget<WitnessVar<CF1<C>>, CommittedInstanceVar<C, RUNNING>>
117    for R1CSMatricesVar<CF1<C>, FpVar<CF1<C>>>
118{
119    type Evaluation = (Vec<FpVar<CF1<C>>>, Vec<FpVar<CF1<C>>>);
120
121    fn eval_relation(
122        &self,
123        w: &WitnessVar<CF1<C>>,
124        u: &CommittedInstanceVar<C, RUNNING>,
125    ) -> Result<Self::Evaluation, SynthesisError> {
126        self.eval_at_z(&[&[FpVar::one()][..], &u.x, &w.W].concat())
127    }
128
129    fn enforce_evaluation(
130        _w: &WitnessVar<C::ScalarField>,
131        u: &CommittedInstanceVar<C, RUNNING>,
132        (AzBz, uCz): Self::Evaluation,
133    ) -> Result<(), SynthesisError> {
134        let mut e = vec![];
135        for (i, (l, r)) in AzBz.iter().zip(uCz).enumerate() {
136            e.push(pow_i_var(i, &u.betas) * (l - r));
137        }
138        // Call `sum` on a vector instead of computing the sum in the above loop
139        // to avoid stack overflow (the cause of this is similar to issue #80
140        // https://github.com/privacy-scaling-explorations/sonobe/issues/80)
141        e.iter().sum::<FpVar<_>>().enforce_equal(&u.e)
142    }
143}
144
145#[cfg(test)]
146pub mod tests {
147    use super::*;
148    use ark_bn254::{Fr, G1Projective as Projective};
149    use ark_r1cs_std::{alloc::AllocVar, R1CSVar};
150    use ark_relations::r1cs::ConstraintSystem;
151    use ark_std::UniformRand;
152    use rand::Rng;
153
154    /// test that checks the native CommittedInstance.to_sponge_{bytes,field_elements}
155    /// vs the R1CS constraints version
156    #[test]
157    pub fn test_committed_instance_to_sponge_preimage() {
158        let mut rng = ark_std::test_rng();
159
160        let t = rng.gen::<u8>() as usize;
161        let io_len = rng.gen::<u8>() as usize;
162
163        let ci = CommittedInstance::<Projective, true> {
164            phi: Projective::rand(&mut rng),
165            betas: (0..t).map(|_| Fr::rand(&mut rng)).collect(),
166            e: Fr::rand(&mut rng),
167            x: (0..io_len).map(|_| Fr::rand(&mut rng)).collect(),
168        };
169
170        let bytes = ci.to_sponge_bytes_as_vec();
171        let field_elements = ci.to_sponge_field_elements_as_vec();
172
173        let cs = ConstraintSystem::<Fr>::new_ref();
174
175        let ciVar =
176            CommittedInstanceVar::<Projective, true>::new_witness(cs.clone(), || Ok(ci.clone()))
177                .unwrap();
178        let bytes_var = ciVar.to_sponge_bytes().unwrap();
179        let field_elements_var = ciVar.to_sponge_field_elements().unwrap();
180
181        assert!(cs.is_satisfied().unwrap());
182
183        // check that the natively computed and in-circuit computed hashes match
184        assert_eq!(bytes_var.value().unwrap(), bytes);
185        assert_eq!(field_elements_var.value().unwrap(), field_elements);
186    }
187}