1use crate::boolean::Boolean;
  2use crate::eq::EqGadget;
  3use crate::fields::fp::FpVar;
  4use crate::fields::FieldVar;
  5use ark_ff::PrimeField;
  6use ark_relations::r1cs::SynthesisError;
  7use ark_std::vec::Vec;
  8
  9pub mod vanishing_poly;
 10
 11#[derive(Clone, Debug)]
 12/// Defines an evaluation domain over a prime field. The domain is a coset of size `1<<dim`.
 13///
 14/// Native code corresponds to `ark-poly::univariate::domain::radix2`, but `ark-poly` only supports
 15/// subgroup for now.
 16///
 17// TODO: support cosets in `ark-poly`.
 18pub struct Radix2DomainVar<F: PrimeField> {
 19    /// generator of subgroup g
 20    pub gen: F,
 21    /// index of the quotient group (i.e. the `offset`)
 22    offset: FpVar<F>,
 23    /// dimension of evaluation domain
 24    pub dim: u64,
 25}
 26impl<F: PrimeField> Radix2DomainVar<F> {
 27    /// Construct an evaluation domain with the given offset.
 28    pub fn new(gen: F, dimension: u64, offset: FpVar<F>) -> Result<Self, SynthesisError> {
 29        offset.enforce_not_equal(&FpVar::zero())?;
 30        Ok(Self {
 31            gen,
 32            offset,
 33            dim: dimension,
 34        })
 35    }
 36
 37    /// What is the offset of `self`?
 38    pub fn offset(&self) -> &FpVar<F> {
 39        &self.offset
 40    }
 41}
 42
 43impl<F: PrimeField> EqGadget<F> for Radix2DomainVar<F> {
 44    fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
 45        if self.gen != other.gen || self.dim != other.dim {
 46            Ok(Boolean::constant(false))
 47        } else {
 48            self.offset.is_eq(&other.offset)
 49        }
 50    }
 51}
 52
 53impl<F: PrimeField> Radix2DomainVar<F> {
 54    /// order of the domain
 55    pub fn order(&self) -> usize {
 56        1 << self.dim
 57    }
 58
 59    /// Returns g, g^2, ..., g^{dim}
 60    fn powers_of_gen(&self, dim: usize) -> Vec<F> {
 61        let mut result = Vec::new();
 62        let mut cur = self.gen;
 63        for _ in 0..dim {
 64            result.push(cur);
 65            cur = cur * cur;
 66        }
 67        result
 68    }
 69
 70    /// Size of the domain
 71    pub fn size(&self) -> u64 {
 72        1 << self.dim
 73    }
 74
 75    /// For domain `h<g>` with dimension `n`, `position` represented by `query_pos` in big endian form,
 76    /// returns `h*g^{position}<g^{n-query_pos.len()}>`
 77    pub fn query_position_to_coset(
 78        &self,
 79        query_pos: &[Boolean<F>],
 80        coset_dim: u64,
 81    ) -> Result<Vec<FpVar<F>>, SynthesisError> {
 82        let mut coset_index = query_pos;
 83        assert!(
 84            query_pos.len() == self.dim as usize
 85                || query_pos.len() == (self.dim - coset_dim) as usize
 86        );
 87        if query_pos.len() == self.dim as usize {
 88            coset_index = &coset_index[0..(coset_index.len() - coset_dim as usize)];
 89        }
 90        let mut coset = Vec::new();
 91        let powers_of_g = &self.powers_of_gen(self.dim as usize)[(coset_dim as usize)..];
 92
 93        let mut first_point_in_coset: FpVar<F> = FpVar::zero();
 94        for i in 0..coset_index.len() {
 95            let term = coset_index[i].select(&FpVar::constant(powers_of_g[i]), &FpVar::zero())?;
 96            first_point_in_coset += &term;
 97        }
 98
 99        first_point_in_coset *= &self.offset;
100
101        coset.push(first_point_in_coset);
102        for i in 1..(1 << (coset_dim as usize)) {
103            let new_elem = &coset[i - 1] * &FpVar::Constant(self.gen);
104            coset.push(new_elem);
105        }
106
107        Ok(coset)
108    }
109}