testudo/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2#![doc = include_str!("../README.md")]
3#![allow(clippy::assertions_on_result_states)]
4
5extern crate ark_std;
6extern crate core;
7extern crate digest;
8extern crate lazy_static;
9extern crate merlin;
10extern crate rand;
11extern crate sha3;
12
13#[macro_use]
14extern crate json;
15
16#[cfg(feature = "multicore")]
17extern crate rayon;
18
19mod commitments;
20mod dense_mlpoly;
21mod errors;
22#[macro_use]
23pub(crate) mod macros;
24mod math;
25pub(crate) mod mipp;
26mod nizk;
27mod product_tree;
28mod r1csinstance;
29mod r1csproof;
30mod sparse_mlpoly;
31pub mod sqrt_pst;
32mod sumcheck;
33pub mod testudo_nizk;
34pub mod testudo_snark;
35mod timer;
36pub(crate) mod transcript;
37mod unipoly;
38
39pub mod parameters;
40
41mod constraints;
42pub mod poseidon_transcript;
43
44use core::cmp::max;
45use errors::R1CSError;
46
47use r1csinstance::{R1CSCommitment, R1CSDecommitment, R1CSInstance};
48
49use ark_ec::CurveGroup;
50
51/// `ComputationCommitment` holds a public preprocessed NP statement (e.g., R1CS)
52pub struct ComputationCommitment<G: CurveGroup> {
53 comm: R1CSCommitment<G>,
54}
55
56use ark_ff::PrimeField;
57/// `ComputationDecommitment` holds information to decommit `ComputationCommitment`
58pub struct ComputationDecommitment<F: PrimeField> {
59 decomm: R1CSDecommitment<F>,
60}
61
62/// `Assignment` holds an assignment of values to either the inputs or variables in an `Instance`
63#[derive(Clone)]
64pub struct Assignment<F: PrimeField> {
65 assignment: Vec<F>,
66}
67
68impl<F: PrimeField> Assignment<F> {
69 /// Constructs a new `Assignment` from a vector
70 pub fn new(assignment: &Vec<Vec<u8>>) -> Result<Self, R1CSError> {
71 let bytes_to_scalar = |vec: &Vec<Vec<u8>>| -> Result<Vec<F>, R1CSError> {
72 let mut vec_scalar: Vec<F> = Vec::new();
73 for v in vec {
74 let val = F::from_random_bytes(v.as_slice());
75 if let Some(v) = val {
76 vec_scalar.push(v);
77 } else {
78 return Err(R1CSError::InvalidScalar);
79 }
80 }
81 Ok(vec_scalar)
82 };
83
84 let assignment_scalar = bytes_to_scalar(assignment);
85
86 // check for any parsing errors
87 if assignment_scalar.is_err() {
88 return Err(R1CSError::InvalidScalar);
89 }
90
91 Ok(Assignment {
92 assignment: assignment_scalar.unwrap(),
93 })
94 }
95
96 /// pads Assignment to the specified length
97 fn pad(&self, len: usize) -> VarsAssignment<F> {
98 // check that the new length is higher than current length
99 assert!(len > self.assignment.len());
100
101 let padded_assignment = {
102 let mut padded_assignment = self.assignment.clone();
103 padded_assignment.extend(vec![F::zero(); len - self.assignment.len()]);
104 padded_assignment
105 };
106
107 VarsAssignment {
108 assignment: padded_assignment,
109 }
110 }
111}
112
113/// `VarsAssignment` holds an assignment of values to variables in an `Instance`
114pub type VarsAssignment<F> = Assignment<F>;
115
116/// `InputsAssignment` holds an assignment of values to variables in an `Instance`
117pub type InputsAssignment<F> = Assignment<F>;
118
119/// `Instance` holds the description of R1CS matrices and a hash of the matrices
120pub struct Instance<F: PrimeField> {
121 inst: R1CSInstance<F>,
122 digest: Vec<u8>,
123}
124
125impl<F: PrimeField> Instance<F> {
126 /// Constructs a new `Instance` and an associated satisfying assignment
127 pub fn new(
128 num_cons: usize,
129 num_vars: usize,
130 num_inputs: usize,
131 A: &[(usize, usize, Vec<u8>)],
132 B: &[(usize, usize, Vec<u8>)],
133 C: &[(usize, usize, Vec<u8>)],
134 ) -> Result<Self, R1CSError> {
135 let (num_vars_padded, num_cons_padded) = {
136 let num_vars_padded = {
137 let mut num_vars_padded = num_vars;
138
139 // ensure that num_inputs + 1 <= num_vars
140 num_vars_padded = max(num_vars_padded, num_inputs + 1);
141
142 // ensure that num_vars_padded a power of two
143 if num_vars_padded.next_power_of_two() != num_vars_padded {
144 num_vars_padded = num_vars_padded.next_power_of_two();
145 }
146 num_vars_padded
147 };
148
149 let num_cons_padded = {
150 let mut num_cons_padded = num_cons;
151
152 // ensure that num_cons_padded is at least 2
153 if num_cons_padded == 0 || num_cons_padded == 1 {
154 num_cons_padded = 2;
155 }
156
157 // ensure that num_cons_padded is power of 2
158 if num_cons.next_power_of_two() != num_cons {
159 num_cons_padded = num_cons.next_power_of_two();
160 }
161 num_cons_padded
162 };
163
164 (num_vars_padded, num_cons_padded)
165 };
166
167 let bytes_to_scalar =
168 |tups: &[(usize, usize, Vec<u8>)]| -> Result<Vec<(usize, usize, F)>, R1CSError> {
169 let mut mat: Vec<(usize, usize, F)> = Vec::new();
170 for (row, col, val_bytes) in tups {
171 // row must be smaller than num_cons
172 if *row >= num_cons {
173 return Err(R1CSError::InvalidIndex);
174 }
175
176 // col must be smaller than num_vars + 1 + num_inputs
177 if *col >= num_vars + 1 + num_inputs {
178 return Err(R1CSError::InvalidIndex);
179 }
180
181 let val = F::from_random_bytes(val_bytes.as_slice());
182 if let Some(v) = val {
183 // if col >= num_vars, it means that it is referencing a 1 or input in the satisfying
184 // assignment
185 if *col >= num_vars {
186 mat.push((*row, *col + num_vars_padded - num_vars, v));
187 } else {
188 mat.push((*row, *col, v));
189 }
190 } else {
191 return Err(R1CSError::InvalidScalar);
192 }
193 }
194
195 // pad with additional constraints up until num_cons_padded if the original constraints were 0 or 1
196 // we do not need to pad otherwise because the dummy constraints are implicit in the sum-check protocol
197 if num_cons == 0 || num_cons == 1 {
198 for i in tups.len()..num_cons_padded {
199 mat.push((i, num_vars, F::zero()));
200 }
201 }
202
203 Ok(mat)
204 };
205
206 let A_scalar = bytes_to_scalar(A);
207 if A_scalar.is_err() {
208 return Err(A_scalar.err().unwrap());
209 }
210
211 let B_scalar = bytes_to_scalar(B);
212 if B_scalar.is_err() {
213 return Err(B_scalar.err().unwrap());
214 }
215
216 let C_scalar = bytes_to_scalar(C);
217 if C_scalar.is_err() {
218 return Err(C_scalar.err().unwrap());
219 }
220
221 let inst = R1CSInstance::new(
222 num_cons_padded,
223 num_vars_padded,
224 num_inputs,
225 &A_scalar.unwrap(),
226 &B_scalar.unwrap(),
227 &C_scalar.unwrap(),
228 );
229
230 let digest = inst.get_digest();
231
232 Ok(Instance { inst, digest })
233 }
234
235 /// Checks if a given R1CSInstance is satisfiable with a given variables and inputs assignments
236 pub fn is_sat(
237 &self,
238 vars: &VarsAssignment<F>,
239 inputs: &InputsAssignment<F>,
240 ) -> Result<bool, R1CSError> {
241 if vars.assignment.len() > self.inst.get_num_vars() {
242 return Err(R1CSError::InvalidNumberOfInputs);
243 }
244
245 if inputs.assignment.len() != self.inst.get_num_inputs() {
246 return Err(R1CSError::InvalidNumberOfInputs);
247 }
248
249 // we might need to pad variables
250 let padded_vars = {
251 let num_padded_vars = self.inst.get_num_vars();
252 let num_vars = vars.assignment.len();
253 if num_padded_vars > num_vars {
254 vars.pad(num_padded_vars)
255 } else {
256 vars.clone()
257 }
258 };
259
260 Ok(
261 self
262 .inst
263 .is_sat(&padded_vars.assignment, &inputs.assignment),
264 )
265 }
266
267 /// Constructs a new synthetic R1CS `Instance` and an associated satisfying assignment
268 pub fn produce_synthetic_r1cs(
269 num_cons: usize,
270 num_vars: usize,
271 num_inputs: usize,
272 ) -> (Instance<F>, VarsAssignment<F>, InputsAssignment<F>) {
273 let (inst, vars, inputs) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
274 let digest = inst.get_digest();
275 (
276 Instance { inst, digest },
277 VarsAssignment { assignment: vars },
278 InputsAssignment { assignment: inputs },
279 )
280 }
281}
282
283#[inline]
284pub(crate) fn dot_product<F: PrimeField>(a: &[F], b: &[F]) -> F {
285 let mut res = F::zero();
286 for i in 0..a.len() {
287 res += a[i] * &b[i];
288 }
289 res
290}
291
292#[cfg(test)]
293mod tests {
294
295 use super::*;
296
297 type F = ark_bls12_377::Fr;
298
299 #[test]
300 pub fn check_r1cs_invalid_index() {
301 let num_cons = 4;
302 let num_vars = 8;
303 let num_inputs = 1;
304
305 let zero: [u8; 32] = [
306 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
307 0,
308 ];
309
310 let A = vec![(0, 0, zero.to_vec())];
311 let B = vec![(100, 1, zero.to_vec())];
312 let C = vec![(1, 1, zero.to_vec())];
313
314 let inst = Instance::<F>::new(num_cons, num_vars, num_inputs, &A, &B, &C);
315 assert!(inst.is_err());
316 assert_eq!(inst.err(), Some(R1CSError::InvalidIndex));
317 }
318
319 #[test]
320 pub fn check_r1cs_invalid_scalar() {
321 let num_cons = 4;
322 let num_vars = 8;
323 let num_inputs = 1;
324
325 let zero: [u8; 32] = [
326 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
327 0,
328 ];
329
330 let larger_than_mod = [
331 3, 0, 0, 0, 255, 255, 255, 255, 254, 91, 254, 255, 2, 164, 189, 83, 5, 216, 161, 9, 8, 216,
332 57, 51, 72, 125, 157, 41, 83, 167, 237, 115,
333 ];
334
335 let A = vec![(0, 0, zero.to_vec())];
336 let B = vec![(1, 1, larger_than_mod.to_vec())];
337 let C = vec![(1, 1, zero.to_vec())];
338
339 let inst = Instance::<F>::new(num_cons, num_vars, num_inputs, &A, &B, &C);
340 assert!(inst.is_err());
341 assert_eq!(inst.err(), Some(R1CSError::InvalidScalar));
342 }
343}