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