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