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