1use crate::poseidon_transcript::{PoseidonTranscript, TranscriptWriter};
  2use ark_crypto_primitives::sponge::Absorb;
  3use ark_ff::{Field, PrimeField};
  4use ark_serialize::*;
  5// ax^2 + bx + c stored as vec![c,b,a]
  6// ax^3 + bx^2 + cx + d stored as vec![d,c,b,a]
  7#[derive(Debug, CanonicalDeserialize, CanonicalSerialize, Clone)]
  8pub struct UniPoly<F: Field> {
  9  pub coeffs: Vec<F>,
 10  // pub coeffs_fq: Vec<Fq>,
 11}
 12
 13// ax^2 + bx + c stored as vec![c,a]
 14// ax^3 + bx^2 + cx + d stored as vec![d,b,a]
 15#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
 16pub struct CompressedUniPoly<F: Field> {
 17  pub coeffs_except_linear_term: Vec<F>,
 18}
 19
 20impl<F: Field> UniPoly<F> {
 21  pub fn from_evals(evals: &[F]) -> Self {
 22    // we only support degree-2 or degree-3 univariate polynomials
 23    assert!(evals.len() == 3 || evals.len() == 4);
 24    let coeffs = if evals.len() == 3 {
 25      // ax^2 + bx + c
 26      let two_inv = F::from(2 as u8).inverse().unwrap();
 27
 28      let c = evals[0];
 29      let a = two_inv * (evals[2] - evals[1] - evals[1] + c);
 30      let b = evals[1] - c - a;
 31      vec![c, b, a]
 32    } else {
 33      // ax^3 + bx^2 + cx + d
 34      let two_inv = F::from(2 as u8).inverse().unwrap();
 35      let six_inv = F::from(6 as u8).inverse().unwrap();
 36
 37      let d = evals[0];
 38      let a = six_inv
 39        * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1] - evals[0]);
 40      let b = two_inv
 41        * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
 42          + evals[2]
 43          + evals[2]
 44          + evals[2]
 45          + evals[2]
 46          - evals[3]);
 47      let c = evals[1] - d - a - b;
 48      vec![d, c, b, a]
 49    };
 50
 51    UniPoly { coeffs }
 52  }
 53
 54  pub fn degree(&self) -> usize {
 55    self.coeffs.len() - 1
 56  }
 57
 58  pub fn eval_at_zero(&self) -> F {
 59    self.coeffs[0]
 60  }
 61
 62  pub fn eval_at_one(&self) -> F {
 63    (0..self.coeffs.len()).map(|i| self.coeffs[i]).sum()
 64  }
 65
 66  pub fn evaluate(&self, r: &F) -> F {
 67    let mut eval = self.coeffs[0];
 68    let mut power = *r;
 69    for i in 1..self.coeffs.len() {
 70      eval += power * self.coeffs[i];
 71      power *= r;
 72    }
 73    eval
 74  }
 75  // pub fn compress(&self) -> CompressedUniPoly<F> {
 76  //   let coeffs_except_linear_term = [&self.coeffs[..1], &self.coeffs[2..]].concat();
 77  //   assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
 78  //   CompressedUniPoly {
 79  //     coeffs_except_linear_term,
 80  //   }
 81  // }
 82}
 83
 84// impl<F: PrimeField> CompressedUniPoly<F> {
 85//   // we require eval(0) + eval(1) = hint, so we can solve for the linear term as:
 86//   // linear_term = hint - 2 * constant_term - deg2 term - deg3 term
 87//   pub fn decompress(&self, hint: &F) -> UniPoly<F> {
 88//     let mut linear_term =
 89//       (*hint) - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
 90//     for i in 1..self.coeffs_except_linear_term.len() {
 91//       linear_term -= self.coeffs_except_linear_term[i];
 92//     }
 93
 94//     let mut coeffs = vec![self.coeffs_except_linear_term[0], linear_term];
 95//     coeffs.extend(&self.coeffs_except_linear_term[1..]);
 96//     assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
 97//     UniPoly { coeffs }
 98//   }
 99// }
100
101impl<F: PrimeField + Absorb> TranscriptWriter<F> for UniPoly<F> {
102  fn write_to_transcript(&self, transcript: &mut PoseidonTranscript<F>) {
103    // transcript.append_message(label, b"UniPoly_begin");
104    for i in 0..self.coeffs.len() {
105      transcript.append_scalar(b"", &self.coeffs[i]);
106    }
107    // transcript.append_message(label, b"UniPoly_end");
108  }
109}
110
111#[cfg(test)]
112mod tests {
113
114  use ark_ff::One;
115
116  use super::*;
117
118  type F = ark_bls12_377::Fr;
119
120  #[test]
121  fn test_from_evals_quad() {
122    // polynomial is 2x^2 + 3x + 1
123    let e0 = F::one();
124    let e1 = F::from(6 as u8);
125    let e2 = F::from(15 as u8);
126    let evals = vec![e0, e1, e2];
127    let poly = UniPoly::from_evals(&evals);
128
129    assert_eq!(poly.eval_at_zero(), e0);
130    assert_eq!(poly.eval_at_one(), e1);
131    assert_eq!(poly.coeffs.len(), 3);
132    assert_eq!(poly.coeffs[0], F::one());
133    assert_eq!(poly.coeffs[1], F::from(3 as u8));
134    assert_eq!(poly.coeffs[2], F::from(2 as u8));
135
136    // let hint = e0 + e1;
137    // // let compressed_poly = poly.compress();
138    // // let decompressed_poly = compressed_poly.decompress(&hint);
139    // for i in 0..poly.coeffs.len() {
140    //   assert_eq!(poly.coeffs[i], poly.coeffs[i]);
141    // }
142
143    let e3 = F::from(28 as u8);
144    assert_eq!(poly.evaluate(&F::from(3 as u8)), e3);
145  }
146
147  #[test]
148  fn test_from_evals_cubic() {
149    // polynomial is x^3 + 2x^2 + 3x + 1
150    let e0 = F::one();
151    let e1 = F::from(7);
152    let e2 = F::from(23);
153    let e3 = F::from(55);
154    let evals = vec![e0, e1, e2, e3];
155    let poly = UniPoly::from_evals(&evals);
156
157    assert_eq!(poly.eval_at_zero(), e0);
158    assert_eq!(poly.eval_at_one(), e1);
159    assert_eq!(poly.coeffs.len(), 4);
160    assert_eq!(poly.coeffs[0], F::one());
161    assert_eq!(poly.coeffs[1], F::from(3));
162    assert_eq!(poly.coeffs[2], F::from(2));
163    assert_eq!(poly.coeffs[3], F::from(1));
164
165    // let hint = e0 + e1;
166    // let compressed_poly = poly.compress();
167    // let decompressed_poly = compressed_poly.decompress(&hint);
168    // for i in 0..decompressed_poly.coeffs.len() {
169    //   assert_eq!(decompressed_poly.coeffs[i], poly.coeffs[i]);
170    // }
171
172    let e4 = F::from(109);
173    assert_eq!(poly.evaluate(&F::from(4)), e4);
174  }
175}