1use super::commitments::{Commitments, MultiCommitGens};
  2use super::group::GroupElement;
  3use super::scalar::{Scalar, ScalarFromPrimitives};
  4use super::transcript::{AppendToTranscript, ProofTranscript};
  5use merlin::Transcript;
  6use serde::{Deserialize, Serialize};
  7
  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(Serialize, Deserialize, 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 = (2 as usize).to_scalar().invert().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 = (2 as usize).to_scalar().invert().unwrap();
 37      let six_inv = (6 as usize).to_scalar().invert().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<Scalar> = Vec::new();
106    coeffs.push(self.coeffs_except_linear_term[0]);
107    coeffs.push(linear_term);
108    coeffs.extend(&self.coeffs_except_linear_term[1..]);
109    assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
110    UniPoly { coeffs }
111  }
112}
113
114impl AppendToTranscript for UniPoly {
115  fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
116    transcript.append_message(label, b"UniPoly_begin");
117    for i in 0..self.coeffs.len() {
118      transcript.append_scalar(b"coeff", &self.coeffs[i]);
119    }
120    transcript.append_message(label, b"UniPoly_end");
121  }
122}
123
124#[cfg(test)]
125mod tests {
126
127  use super::*;
128
129  #[test]
130  fn test_from_evals_quad() {
131    // polynomial is 2x^2 + 3x + 1
132    let e0 = Scalar::one();
133    let e1 = (6 as usize).to_scalar();
134    let e2 = (15 as usize).to_scalar();
135    let evals = vec![e0, e1, e2];
136    let poly = UniPoly::from_evals(&evals);
137
138    assert_eq!(poly.eval_at_zero(), e0);
139    assert_eq!(poly.eval_at_one(), e1);
140    assert_eq!(poly.coeffs.len(), 3);
141    assert_eq!(poly.coeffs[0], Scalar::one());
142    assert_eq!(poly.coeffs[1], (3 as usize).to_scalar());
143    assert_eq!(poly.coeffs[2], (2 as usize).to_scalar());
144
145    let hint = e0 + e1;
146    let compressed_poly = poly.compress();
147    let decompressed_poly = compressed_poly.decompress(&hint);
148    for i in 0..decompressed_poly.coeffs.len() {
149      assert_eq!(decompressed_poly.coeffs[i], poly.coeffs[i]);
150    }
151
152    let e3 = (28 as usize).to_scalar();
153    assert_eq!(poly.evaluate(&(3 as usize).to_scalar()), e3);
154  }
155
156  #[test]
157  fn test_from_evals_cubic() {
158    // polynomial is x^3 + 2x^2 + 3x + 1
159    let e0 = Scalar::one();
160    let e1 = (7 as usize).to_scalar();
161    let e2 = (23 as usize).to_scalar();
162    let e3 = (55 as usize).to_scalar();
163    let evals = vec![e0, e1, e2, e3];
164    let poly = UniPoly::from_evals(&evals);
165
166    assert_eq!(poly.eval_at_zero(), e0);
167    assert_eq!(poly.eval_at_one(), e1);
168    assert_eq!(poly.coeffs.len(), 4);
169    assert_eq!(poly.coeffs[0], Scalar::one());
170    assert_eq!(poly.coeffs[1], (3 as usize).to_scalar());
171    assert_eq!(poly.coeffs[2], (2 as usize).to_scalar());
172    assert_eq!(poly.coeffs[3], (1 as usize).to_scalar());
173
174    let hint = e0 + e1;
175    let compressed_poly = poly.compress();
176    let decompressed_poly = compressed_poly.decompress(&hint);
177    for i in 0..decompressed_poly.coeffs.len() {
178      assert_eq!(decompressed_poly.coeffs[i], poly.coeffs[i]);
179    }
180
181    let e4 = (109 as usize).to_scalar();
182    assert_eq!(poly.evaluate(&(4 as usize).to_scalar()), e4);
183  }
184}